nbhkdz.com冰点文库

温州中学noip一试模拟

时间:2012-11-29


温州中学 NOIP2011 模拟赛 DAY1
题目 题目名称 输入文件 输出文件 时间限制 空间限制 每个测试点分值 数的计数 count count.in count.out 1s 64MB 10 跑路 road road.in road.out 1s 64MB 10 RP字符串 string string.in string.out 1s 64MB 10


代码长度限制:50KB 评测机配置为Celeron(R) CPU2.66GHz,1G的内存(古董机,速度你懂的)。 为了评测及整理方便起见, 文件夹名请使用"学校名-选手名"的格式, 里面需要使用子文件。

数的计数
【题目描述】
小 A 终于找到了一份工作!工作的内容是统计[L,R]区间的 K 超级数的数目。X 是 K 超 级数, 当且仅当 X 各位数字之和的 K 倍能被 X 整除 (整除的定义大家都懂吧) 小 A 的 Boss 。 说小 A 每统计一次,就给他 1RMB。然则,这工作实在索然无味,所以小 A 找到了你,以 每题 1 津巴布韦币的价钱雇佣了你帮他解决这个问题。

【输入说明】
第一行一个数字 T,表示数据组数。接下来 T 行每行两个数字 L,R,K 表示询问。

【输出说明】
共 T 行,每行一个数字,表示询问区间超级数的数目。

【样例输入】
3 1 100 1 1 100 2 1 100 3

【样例输出】
9 10 10

【样例说明】
三组数据的超级数分别为<1,2,3,4,5,6,7,8,9>,<1,2,3,4,5,6,7,8,9,18>,<1,2,3,4,5,6,7,8,9,27>。

【数据范围】
60%的数据满足 r-l<=50000; 100%的数据满足 1<=l,r<=10^18,k<=1000,T<=10。

跑路
【题目描述】
小 A 的工作不仅繁琐,更有苛刻的规定,要求小 A 每天早上在 6:00 之前到达公司, 否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资,小 A 买了一个十分牛 B 的空间跑路器,每秒钟可以跑 2^k 千米(k 是任意数) 。当然,这个机器 是用 longint 存的,所以总跑路长度不能超过 maxlongint 千米。小 A 的家到公司的路可以看 做一个有向图,小 A 家为点 1,公司为点 n,每条边长度均为一千米。小 A 想每天能醒地尽 量晚,所以让你帮他算算,他最少需要几秒才能到公司。数据保证 1 到 n 至少有一条路径。

【输入说明】
第一行两个整数 n,m,表示点的个数和边的个数。 接下来 m 行每行两个数字 u,v,表示一条 u 到 v 的边。

【输出说明】
一行一个数字,表示到公司的最少秒数。

【样例输入】
44 11 12 23 34

【样例输出】
1

【样例解释】
1->1->2->3->4,总路径长度为 4 千米,直接使用一次跑路器即可。

【数据范围】
50%的数据满足最优解路径长度<=1000; 100%的数据满足 n<=50,m<=10000,最优解路径长度<=maxlongint。

RP 字符串
【题目描述】
小 A 在经过长期的实践和研究之后发现有一类特殊的 01 字符串能够增加 RP,小 A 称 之为 RP 字符串。首先”0”是一个 RP 字符串,如果 A、B 都是 RP 字符串,那么”1AB1”也是 RP 字符串。现在小 A 有一些字符串,他想知道那些能增加 RP,你能帮帮他吗?

【输入说明】
第一行一个数字 T 表示数据组数。下面每组数据第一行一个正整数 n 表示字符串长度, 第二行为一个长度为 n 的字符串。

【输出说明】
输出 T 行,每行一个字符串”YES”,或”NO”表示是不是 RP 字符串。

【样例输入】
3 4 1001 7 1100101 7 0110011

【样例输出】
YES YES NO

【数据范围】
30%的数据满足 n<=100; 50%的数据满足 n<=300; 100%的数据满足 n<=800,T<=10。