第十二届全国信息学奥林匹克分区联赛（NOIP2006）复赛试题
（提高组竞赛用时：3小时）
关于竞赛中不同语言使用限制的说明
一．关于使用Pascal语言与编译结果的说明
1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。
2．允许使用数学库(uses math子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal 的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。
二．关于C++语言中模板使用的限制说明
1．允许使用的部分：标准容器中的布尔集合，迭代器，串，流。
相关的头文件：
2．禁止使用的部分：序列：vector，list，deque
序列适配器：stack, queue, priority_queue 关联容器：map, multimap, set, multiset 拟容器：valarray 散列容器：hash_map, hash_set, hash_multimap, hash_multiset 所有的标准库算法
相关头文件：
1．能量项链(energy.pas/c/cpp)
【问题描述】
在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。
需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4⊕1)=10*2*3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【输入文件】
输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。 【输出文件】 输出文件energy.out只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。 【输入样例】 4 2 3 5 10 【输出样例】 710 2．金明的预算方案(budget.pas/c/cpp) 【问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子： 主件。每个主件可以有0个、1个或2个附件。附件不再有 从属于自己的附件。金明想买的东西很多，肯定会超过妈 妈限定的N元。于是，他把每件物品规定了一个重要度， 分为5等：用整数1~5表示，第5等最重要。他还从因特 网上查到了每件物品的价格（都是10元的整数倍）。他希 望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为： v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号） 请你帮助金明设计一个满足要求的购物单。 【输入文件】 输入文件budget.in 的第1行，为两个正整数，用一个空格隔开： n m （其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。） 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数 v p q （其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号） 【输出文件】 输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。 【输入样例】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200 3．作业调度方案(jsp.pas/c/cpp) 【问题描述】 我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。 每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。 例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。 一方面，每个操作的安排都要满足以下的两个约束条件。 (1) 对同一个工件，每道工序必须在它前面的工序完成后才能开始； (2) 同一时刻每一台机器至多只能加工一个工件。 另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。 由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。 还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。 例如，取n=3,m=2 则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。 当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。 显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。 【输入文件】 输入文件jsp.in 的第1行为两个正整数，用一个空格隔开： m n （其中m（<20）表示机器数，n（<20）表示工件数） 第2行：个用空格隔开的数，为给定的安排顺序。 接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。后n行依次表示每个工件的每个工序的加工时间。 可以保证，以上各数据都是正确的，不必检验。 【输出文件】 输出文件jsp.out只有一个正整数，为最少的加工时间。 【输入样例】 2 3 1 1 2 3 3 2 1 2 1 2 2 1 3 2 2 5 2 4 【输出样例】 10 4．2k进制数（digital.pas/c/cpp） 【问题描述】 设r是个2k进制数，并满足以下条件： （1）r至少是个2位的2k进制数。 （2）作为2k进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。 （3）将r转换为2进制数q后，则q的总位数不超过w。 在这里，正整数k（1≤k≤9）和w（k 问：满足上述条件的不同的r共有多少个？ 我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k的段，每段对应一位2k 进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2k进制数r。 例：设k=3，w=7。则r是个八进制数（23=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。 3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。 所以，满足要求的r共有36个。 【输入文件】 输入文件digital.in只有1行，为两个正整数，用一个空格隔开： k w 【输出文件】 输出文件digital.out为1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。 （提示：作为结果的正整数可能很大，但不会超过200位） 【输入样例】 3 7 【输出样例】 36 第十三届全国信息学奥林匹克分区联赛（NOIP2007）复赛试题 （提高组竞赛用时：3小时） 说明： 1. 文件名（程序名和输入输出文件名）必须使用小写 2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3. 全国统一评测时采用的机器参考配置为：CPU 2.0GHz，内存256M。 1、统计数字（count.pas/c/cpp） 【问题描述】 某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。 【输入】 输入文件count.in包含n+1行； 第一行是整数n，表示自然数的个数； 第2~n+1每行一个自然数。 【输出】 输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 【输入输出样例】 【限制】 40%的数据满足：1<=n<=1000 80%的数据满足：1<=n<=50000 100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109） 2、字符串的展开（expand.pas/c/cpp） 【问题描述】 在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下： (1)遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。 (2)参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号“*”来填充。 (3)参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。 (4)参数p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。 (5)如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。 【输入】 输入文件expand.in包括两行： 第1行为用空格隔开的3个正整数，一次表示参数p1，p2，p3。 第2行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。 【输出】 输出文件expand.out只有一行，为展开后的字符串。 【输入输出样例1】 【输入输出样例2】 【输入输出样例3】 【限制】 40%的数据满足：字符串长度不超过5 100%的数据满足：1<=p1<=3，1<=p2<=8，1<=p3<=2。字符串长度不超过100 3、矩阵取数游戏（game.pas/c/cpp） 【问题描述】 帅帅经常更同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下： 1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素； 2.每次取走的各个元素只能是该元素所在行的行首或行尾； 3.每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）； 4. 游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 【输入】 输入文件game.in包括n+1行； 第一行为两个用空格隔开的整数n和m。1+2+（2+3）*4+8*6 第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开 【输出】 输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大的分。 【输入输出样例1】 【输入输出样例1解释】 第1次：第一行取行首元素，第二行取行尾元素，本次的氛围1*21+2*21=6 第2次：两行均取行首元素，本次得分为2*22+3*22=20 第3次：得分为3*23+4*23=56。总得分为6+20+56=82 【输入输出样例2】 【输入输出样例3】 【限制】 60%的数据满足：1<=n, m<=30，答案不超过1016 100%的数据满足：1<=n, m<=80，0<=aij<=1000 4、树网的核（core.pas/c/cpp ） 【问题描述】 设T=(V, E, W) 是一个无圈且连通的无向图（也称为无根树），每条边到有正整数的权，我们称T 为树网（treebetwork ），其中V ，E 分别表示结点与边的集合，W 表示各边长度的集合，并设T 有n 个结点。 路径：树网中任何两结点a ，b 都存在唯一的一条简单路径，用d(a, b)表示以a, b 为端点的路径的长度，它是该路径上各边长度之和。我们称d(a, b)为a, b 两结点间的距离。 D(v, P)=min{d(v, u), u 为路径P 上的结点}。 树网的直径：树网中最长的路径成为树网的直径。对于给定的树网T ，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。 偏心距ECC(F)：树网T 中距路径F 最远的结点到路径F 的距离，即 ECC(F)=max{d(v, F)，v ∈V} 任务：对于给定的树网T=(V, E, W)和非负整数s ，求一个路径F ，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过s （可以等于s ），使偏心距ECC(F)最小。我们称这个路径为树网T=(V, E, W)的核（Core ）。必要时，F 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。 下面的图给出了树网的一个实例。图中，A-B 与A-C 是两条直径，长度均为20。点W 是树网的中心，EF 边的长度为5。如果指定s=11，则树网的核为路径DEFG （也可以取为路径DEF ），偏心距为8。如果指定s=0（或s=1、s=2），则树网的核为结点F ，偏心距为12。 【输入】 输入文件core.in包含n行： 第1行，两个正整数n和s，中间用一个空格隔开。其中n为树网结点的个数，s为树网的核的长度的上界。设结点编号以此为1，2，……，n。 从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。 所给的数据都是争取的，不必检验。 【输出】 输出文件core.out只有一个非负整数，为指定意义下的最小偏心距。 【输入输出样例1】 【输入输出样例2】 【限制】 40%的数据满足：5<=n<=15 70%的数据满足：5<=n<=80 100%的数据满足：5<=n<=300，0<=s<=1000。边长度为不超过1000的正整数 第十四届全国信息学奥林匹克分区联赛（NOIP2008）复赛试题 （提高组竞赛用时：3小时） 一、题目概览 二、提交源程序文件名 三、编译命令（不包含任何优化开关） 四、运行内存限制 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用大写。 2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3. 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。 1. 笨小猴(word.pas/c/cpp) 【问题描述】 笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试 验证明，用这种方法去选择选项的时候选对的几率非常大！ 这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。 【输入】 输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。 【输出】 输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”； 第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。 【输入输出样例1】 【输入输出样例1解释】 单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。【输入输出样例2】 【输入输出样例2解释】 单词olympic中出现最多的字母i出现了2次，出现次数最少的字母出现了1次，2-1=1，1不是质数。 2. 火柴棒等式(matches.pas/c/cpp) 【问题描述】 给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示： 注意： 1）加号与等号各自需要两根火柴棍 2）如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0） 3）n根火柴棍必须全部用上 【输入】 输入文件matches.in共一行，又一个整数n（n<=24）。 【输出】 输出文件matches.out共一行，表示能拼成的不同等式的数目。 【输入输出样例1】 【输入输出样例1解释】 2个等式为0+1=1和1+0=1。 【输入输出样例2】 【输入输出样例2解释】9个等式为： 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11 3. 传纸条(message.pas/c/cpp) 【问题描述】 小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。 【输入】 输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。 接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。 【输出】 输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。 【输入输出样例】 【限制】 30%的数据满足：1<=m,n<=10 100%的数据满足：1<=m,n<=50 4. 双栈排序(twostack.pas/c/cpp) 【问题描述】 Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。 操作a：如果输入序列不为空，将第一个元素压入栈S1 操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2 操作d：如果栈S2 不为空，将S2栈顶元素弹出至输出序列 如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P 是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列： 当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)， 【输入】 输入文件twostack.in的第一行是一个整数n。第二行有n个用空格隔开的正整数，构成一个1~n 的排列。 【输出】 输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。 【输入输出样例1】 【输入输出样例2】 【输入输出样例3】 【限制】 30%的数据满足：n<=10 50%的数据满足：n<=50 100%的数据满足：n<=1000 第十五届全国信息学奥林匹克分区联赛（NOIP2009）复赛试题 （提高组竞赛用时：3小时） 一．题目概况 二．提交程序文件名 三．编译命令（不包含任何优化开关） 四．运行内存限制 注意事项： 1、文件名（程序名和输入输出文件名）必须使用小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU 1.9GHz，内存1G，上述时限以此配置为准。各 省在自测时可根据具体配置调整时限。 1、潜伏者（spy.pas/c/cpp） 【问题描述】 R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历经艰险后，潜伏于S国的R国间谍小C终于摸清了S国军用密码的编码规则： 1）S国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所的内容均由大写字母‘A’—‘Z’构成（无空格等其他字母）。 2）S国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换为其对应的“密字”。 3）每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以和原字母相同。 例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信息“ABA”被加密为“ACA”。 现在，小C通过内线掌握了S国网络上发送的一条加密信息及其对应的原信息。小C希望能通过这条信息，破译S国的军用密码。小C的破译过程是这样的：扫描原信息，对于原信息中的字母x（代表任一大写字母），找督其在加密信息中的对应大写字母y，并认为在密码里y是x的密字。如此进行下去直到停止于如下的某个状态： 1）所有信息扫描完毕，‘A’—‘Z’所有26个字母在原信息中均出现过并获得了相应的“密字”。 2）所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。 3）扫描中发现掌握的信息里有明显的自相矛盾或错误（违反S过密码的编码规则）。例如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。 在小C忙得头昏脑胀之际，R国司令部又发来电报，要求他翻译另外一条从S国刚刚截取到的加密信息。现在请你帮助小C：通过内线掌握的信息，尝试破译密码。然后利用破译的密码，翻译电报中的加密信息。 【输入】 输入文件名为spy.in，共3行，每行为一个长度在1到100之间的字符串。第1行为小C掌握的一条加密信息。第2行为第1行的加密信息所对应的原信息。第3行为R国司令部要求小C翻译的加密信息。 输入数据保证所有字符串仅由大写字母‘A’—‘Z’构成，且第1行长度与第2行相等。 【输出】 输出文件spy.out共1行。若破译密码停止时出现2，3两种情况，请你输出“Failed”（不含引号，注意首字母大写，其它小写）。否则请输出利用密码翻译电报中加密信息后得到的原信息。 【输入输出样例1】 【输入输出样例说明】 原信息中的字母“A”禾 B”对应相同的密字，输出“Failed”。 【输入输出样例2】 【输入输出样例2说明】 字母“Z”在原信息中没有出现，输出“Failed”。 【输入输出样例3】 2、Hankson的趣味题（son.pas/c/cpp） 【问题描述】 Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。 今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”禾 求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0，a1，b0，b1，设某未知正整数x满足：1）x和a0的最大公约数是a1； 2）x和b0的最小公倍数是b1。Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x 的个数。请你帮助他编程求解这个问题。 【输入】 输入文件名为son.in。第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。 【输出】 输出文件son.out共n行。每组输入数据的输出结果占一行，为一个整数。对于每组数据：若不存在这样的x，请输出0； 若存在这样的x，请输出满足条件的x的个数； 【输入输出样例】 【说明】 第一组输入数据，X可以是9、18、36、72、144、288，共有6个。 第二组输入数据，X可以是48、1776，共有2个。 【数据范围】 对于50%的数据，保证有1≤a0，b1，b0，b1≤且n≤100。 对于100%的数据，保证有1≤a0，b1，b0，b1≤2000000000且n≤2000。 3、最优贸易（trade.pas/c/cpp） 【问题描述】 C国有n个大城市和m条道路，每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。 C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。 商人阿龙来到C国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设C国n个城市的标号从1-n，阿龙决定从1号城市出发，并最终在n号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有n个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市迈入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球。用赚取的差价当作旅费。由于阿龙主要是来C国旅游，他决定这个贸易只进行最多一次。当然，在赚不到差价的情况下它就无需进行贸易。 假设C国有5个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行。双向箭头表示这条道路为双向通行。 假设1~n号城市的水晶球价格分别为4，3，5，6，1。 阿龙可以选择如下一条线路：1->2->3->5，并在2号城市以3的价格买入水晶球，在3号城市 CCF全国信息学奥林匹克联赛（NOIP2014）复赛 提高组 day1 1．生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势： 斯波克：《星际迷航》主角之一。 蜥蜴人：《星际迷航》中的反面角色。 这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。 表一石头剪刀布升级版胜负关系 现在，小A和小B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”，而如果小B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……” 已知小A和小B一共进行N次猜拳。每一次赢的人得1分，输的得0分；平局两人都得0分。现请你统计N次猜拳结束之后两人的得分。 【输入】 输入文件名为rps.in。 第一行包含三个整数：N，NA，NB，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。数与数之间以一个空格分隔。 第二行包含NA个整数，表示小A出拳的规律，第三行包含NB个整数，表示小B出拳的规律。其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”， 4表示“斯波克”。数与数之间以一个空格分隔。 1. 话说去年苹果们被陶陶摘下来后都很生气，于是就用最先进的克隆技术把陶陶克隆了好多份>.<然后把他们挂在树上，准备摘取。摘取的规则是，一个苹果只能摘一个陶陶，且只能在它所能摘到的高度以下（即是小于关系）的最高的陶陶，如果摘不到的话只能灰溜溜的走开了>.<给出苹果数目及每个苹果可以够到的高度和各个陶陶的高度，求苹果们都摘完后剩下多少个陶陶…… 【输入格式】第一行为两个数，分别为苹果的数量n和陶陶的数量m（n,m<=2000）以下的n行，分别为各个苹果能够到的最大高度。再接下来的m行，分别为各个陶陶的高度。高度均不高于300。 当然了，摘取的顺序按照输入的“苹果够到的最大高度”的顺序来摘。 【输出格式】输出仅有一个数，是剩下的陶陶的数量 【样例输入】5 5↙9↙10↙2↙3↙1↙6↙7↙8↙9↙10 【样例输出】3 2. 某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。 任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：7 279 5 279 这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是：5 279 7 279则按输出错误处理，不能得分。【输入】输入文件scholar.in包含n+1行： 第1行为一个正整数n，表示该校参加评选的学生人数。 第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n（恰好是输入数据的行号减1）。 所给的数据都是正确的，不必检验。 【输出】输出文件scholar.out共有5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。 【输入输出样例1】 scholar.in scholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 【输入输出样例2】 scholar.in scholar.out 8 80 89 89 8 265 2 264 全国信息学奥林匹克联赛（NOIP2008）复赛 提高组 一、题目概览 二、提交源程序文件名 三、编译命令（不包含任何优化开关） 四、运行内存限制 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用大写。 2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3. 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。 1. 笨小猴 (word.pas/c/cpp) 【问题描述】 笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！ 这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。 【输入】 输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。【输出】 输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”； 第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。 【输入输出样例1】 【输入输出样例1解释】 单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。 【输入输出样例2】 【输入输出样例2解释】 单词olympic中出现最多的字母i出现了2次，出现次数最少的字母出现了1次，2-1=1，1不是质数。 基本的字符串处理，细心一点应该没问题的，不过判断素数时似乎需要考虑下0和1的情况。var a:array['a'..'z']of integer; s:string; l,i,max,min,n:integer; ch:char;flag:boolean; begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(s); 2002年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （普及组竞赛用时：3 小时） 题一级数求和（存盘名：NOIPC1） [问题描述]: 已知：Sn= 1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。 现给出一个整数K（1<=k<=15），要求计算出一个最小的n；使得Sn＞K。 [输入] 键盘输入 k [输出] 屏幕输出 n [输入输出样例] 输人：1 输出：2 题二选数（存盘名：NOIPC2） [问题描述]: 已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。 现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数：3＋7＋19＝29）。 [输入]： 键盘输入，格式为： n , k （1<=n<=20，k＜n） x1,x2，…,xn （1<=xi<=5000000） [输出]： 屏幕输出，格式为： 一个整数（满足条件的种数）。 [输入输出样例]: 输入： 4 3 3 7 12 19 输出： 1 [问题描述]: 给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。 规则： 一位数可变换成另一个一位数： 规则的右部不能为零。 例如：n=234。有规则（k＝2）： 2－> 5 3－> 6 上面的整数 234 经过变换后可能产生出的整数为（包括原数）: 234 534 264 564 共 4 种不同的产生数 问题： 给出一个整数 n 和 k 个规则。 求出： 经过任意次的变换（0次或多次），能产生出多少个不同整数。 仅要求输出个数。 [输入]: 键盘输人，格式为： n k x1 y1 x2 y2 ... ... xn yn [输出]: 屏幕输出，格式为： 一个整数（满足条件的个数）： [输入输出样例]: 输入: 234 2 2 5 3 6 输出： 4 第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （普及组 竞赛用时：3小时） 第一题 Cantor 表（30分） 现代数学的著名证明之一是Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的： 我们以Z 字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，… 输入：整数N （1≤N ≤10000000） 输出：表中的第N 项 样例： INPUT OUTPUT N=7 1/4 第二题 回文数（30分） 若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在这里的一步是指进行了一次N 进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N （2<=N<=10，N=16）进制数M ，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible ！” 样例： INPUT OUTPUT N = 9 M= 87 STEP=6 第三题 旅行家的预算（40分） 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C （以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P 和沿途油站数N （N 可以为零），油站i 离出发点的距离Di 、每升汽油价格Pi （i=1，2，…，N ）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution ”。 样例： INPUT … 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … 3/1 3/2 3/3 … 4/1 4/2 … 5/1 … … 第十九届全国青少年信息学奥林匹克联赛初赛 提高组Pascal 语言试题 竞赛时间：2013 年10 月13 日14:30~16:30 选手注意： ●试题纸共有12 页，答题纸共有2 页，满分100 分。请在答题纸上作答，写在试题纸上 的一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。 一、单项选择题（共15 题，每题1.5 分，共计22.5 分；每题有且仅有一个正确选项） 1. 一个32 位整型变量占用（）个字节。 A. 4 B. 8 C. 32 D. 128 2. 二进制数11.01 在十进制下是（）。 A. 3.25 B. 4.125 C. 6.25 D. 11.125 3. 下面的故事与（）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：?从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’? A. 枚举 B. 递归 C. 贪心 D. 分治 4. 1948 年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。 A. 冯·诺伊曼（John von Neumann） B. 图灵（Alan Turing） C. 欧拉（Leonhard Euler） D. 克劳德·香农（Claude Shannon） 5. 已知一棵二叉树有2013 个节点，则其中至多有（）个节点有2 个子节点。 A. 1006 B. 1007 C. 1023 D. 1024 6. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通 图，至少要删去其中的（）条边。 NOIP2017普及组初赛试题及答案 一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项） 1.在8位二进制补码中，10101011表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D. -84 2.计算机存储数据的基本单位是( )。 A. bit B. Byte C. GB D. KB 3.下列协议中与电子邮件无关的是( )。 A. POP3 B. SMTP C. WTO D. IMAP 4.分辨率为800x600、16位色的位图，存储图像信息所需的空间为( )。 A.937.5KB B. 4218.75KB C.4320KB D. 2880KB 5.计算机应用的最早领域是( )。 A.数值计算 B.人工智能 C.机器人 D.过程控制 6.下列不属于面向对象程序设计语言的是( )。 A. C B. C++ C. Java D. C# 7.NOI的中文意思是( )。 A.中国信息学联赛 B.全国青少年信息学奥林匹克竞赛 C.中国青少年信息学奥林匹克竞赛 D.中国计算机协会 8. 2017年10月1日是星期日，1999年10月1日是( )。 A.星期三 B.星期日 C.星期五 D.星期二 9.甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有( )种。 A. 36 B. 48 C. 96 D. 192 10.设G是有n个结点、m条边(n ≤m)的连通图，必须删去G的( )条边，才能使得G变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 11.对于给定的序列{ak}，我们把(i, j)称为逆序对当且仅当i < j且ai> aj。那么 序列1, 7, 2, 3, 5, 4的逆序对数为()个。 A. 4 B. 5 C. 6 D. 7 12.表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行( )。 CCF全国信息学奥林匹克联赛（NOIP2015）复赛 普及组 （请选手务必仔细阅读本页内容） 一、题目概况 中文题目名称金币扫雷游戏求和推销员 coin mine sum salesman 英文题目与子目 录名 可执行文件名coin mine sum salesman 输入文件名coin.in mine.in sum.in salesman.in 输出文件名coin.out mine.out sum.out salesman.out 每个测试点时限1秒 测试点数目10 每个测试点分值10 附加样例文件有 结果比较方式全文比较（过滤行末空格及文末回车） 题目类型传统 运行内存上限128M 二、提交源程序文件名 对于C++语言coin.cpp mine.cpp sum.cpp salesman.cpp 对于C语言coin.c mine.c sum.c salesman.c 对于Pascal语言coin.pas mine.pas sum.pas salesman.pas 四、注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm)II x2240processor，2.8GHz，内存4G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。 1.金币 (coin.cpp/c/pas) 【问题描述】 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。 请计算在前K天里，骑士一共获得了多少金币。 【输入格式】 输入文件名为coin.in。 输入文件只有1行，包含一个正整数K，表示发放金币的天数。 【输出格式】 输出文件名为coin.out。 输出文件只有1行，包含一个正整数，即骑士收到的金币数。 【输入输出样例1】 coin.in coin.out 614 见选手目录下的coin/coin1.in和coin/coin1.ans。 【输入输出样例1说明】 骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到1+2+2+3+3+3=14枚金币。 【输入输出样例2】 coin.in coin.out 100029820 见选手目录下的coin/coin2.in和coin/coin2.ans。 【数据说明】 对于100%的数据，1≤K≤10,000。 CCF 全国信息学奥林匹克联赛（NOIP2017）复赛 提高组 day1 （请选手务必仔细阅读本页内容） 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz， 内存4G，上述时限以此配置为准。 4、只提供Linux 格式附加样例文件。 5、提交的程序代码文件的放置位置请参照各省的具体要求。 6、特别提醒：评测在当前最新公布的NOI Linux 下进行，各语言的编译器版本以其为准。 【问题描述】1．小凯的疑惑 (math.cpp/c/pas) 小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。 【输入格式】 输入文件名为math.in。 输入数据仅一行，包含两个正整数a 和b，它们之间用一个空格隔开，表示小凯手中金币的面值。 【输出格式】 输出文件名为math.out。 输出文件仅一行，一个正整数N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。 见选手目录下的math/math1.in 和math/math1.ans。 【输入输出样例1 说明】 小凯手中有面值为3 和7 的金币无数个，在不找零的前提下无法准确支付价值为1、2、4、5、8、11 的物品，其中最贵的物品价值为11，比11 贵的物品都能买到，比如： 12 = 3 * 4 + 7 * 0 13 = 3 * 2 + 7 * 1 14 = 3 * 0 + 7 * 2 15 = 3 * 5 + 7 * 0 …… 【输入输出样例2】 见选手目录下的math/math2.in 和math/math2.ans。 【数据规模与约定】 对于30%的数据： 1 ≤ a，b ≤ 50。 对于60%的数据： 1 ≤ a，b ≤ 10,000。 对于100%的数据：1 ≤ a，b ≤ 1,000,000,000。 【最新整理，下载后即可编辑】 历年noip普及组初赛试题汇编 芜湖县实验学校NOIP初赛复习资料 第十五届全国青少年信息学奥林匹克联赛初赛试题(2009) （普及组C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸 上一律无效●● 一．单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。） 1、关于图灵机下面的说法哪个是正确的： A)图灵机是世界上最早的电子计算机。 B)由于大量使用磁带操作，图灵机运行速度很慢。 C)图灵机是英国人图灵发明的，在二战中为破译德军的密码 发挥了重要作用。 D)图灵机只是一个理论上的计算模型。 2、关于计算机内存下面的说法哪个是正确的： A)随机存储器（RAM）的意思是当程序运行时，每次具体分 配给程序的内存位置是随机而不确定的。 B)1MB内存通常是指1024*1024字节大小的内存。 C)计算机内存严格说来包括主存（memory）、高速缓存（cache） 和寄存器（register）三个部分。 D)一般内存中的数据即使在断电的情况下也能保留2个小时 以上。 3、关于BIOS下面说法哪个是正确的： A)BIOS是计算机基本输入输出系统软件的简称。 B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输 入输出设备的驱动程序。 C)BIOS一般由操作系统厂商来开发完成。 D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文 件管理功能。 4、关于CPU下面哪个说法是正确的： A)CPU全称为中央处理器（或中央处理单元）。 B)CPU可以直接运行汇编语言。 C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。 D)CPU最早是由Intel公司发明的。 5、关于ASCII，下面哪个说法是正确的： A)ASCII码就是键盘上所有键的唯一编码。 B)一个ASCII码使用一个字节的内存空间就能够存放。 C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的 编码。 D)ASCII码是英国人主持制定并推广使用的。 6、下列软件中不是计算机操作系统的是： A) Windows B) Linux C) OS/2 D) WPS 7、关于互联网，下面的说法哪一个是正确的： A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。 B)互联网的入网主机如果有了域名就不再需要IP地址。 C)互联网的基础协议为TCP/IP协议。 D)互联网上所有可下载的软件及数据资源都是可以合法免 费使用的。 8、关于HTML下面哪种说法是正确的： A）HTML实现了文本、图形、声音乃至视频信息的统一编码。 B）HTML全称为超文本标记语言。 C）网上广泛使用的Flash动画都是由HTML编写的。 D）HTML也是一种高级程序设计语言。 全国信息学奥林匹克联赛（NOIP2007）复赛提高组 1．统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了n 个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数 不超过10000 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【输入】 输入文件count.in包含n+1 行：第1 行是整数 n，表示自然数的个数。 第2~n+1 行每行一个自然数。 【输出】输出文件count.out包含m 行（m 为n 个自然数中不相同数的个数），按照自然数从小到大 的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 【输入输出样例】 【限制】 40%的数据满足：1<=n<=1000 80%的数据满足：1<=n<=50000 100%的数据满足：1<=n<=200000，每个数均不超过1 500 000 000（1.5*109） 2．字符串的展开 (expand.pas/c/cpp) 【问题描述】 在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或“4-8”的子串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：（1）遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧 同为小写字母或同为数字，且按照ASCII 码的顺序，减号右边的字符严格大于左边的字符。 （2）参数p1：展开方式。p1=1 时，对于字母子串，填充小写字母；p1=2 时，对于字母子串， 填充大写字母。这两种情况下数字子串的填充方式相同。p1=3 时，不论是字母子串还是数字子串， 都用与要填充的字母个数相同的星号“*”来填充。 （3）参数p2：填充字符的重复个数。p2=k 表示同一个字符要连续填充k 个。例如，当p2=3 时，子串“d-h”应扩展为“deeefffgggh”。减号两侧的字符不变。 （4）参数p3：是否改为逆序：p3=1 表示维持原有顺序，p3=2 表示采用逆序输出，注意这时仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2 时，子串“d-h”应扩展为“dggffeeh”。 （5）如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCII 码的顺序小于或等于左边字符， 输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。 【输入】 输入文件expand.in包括两行： 第1 行为用空格隔开的3 个正整数，依次表示参数p1，p2，p3。 第2 行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。 【输出】 输出文件expand.out只有一行，为展开后的字符串。 第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题 (普及组PASCAL语言二小时完成) 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一.选择一个正确答案代码(A/B/C/D,填入每题的括号内(每题1.5分,多选无分,共30分) 1)微型计算机的问世是由于( ) 的出现。 A) 中小规模集成电路 B) 晶体管电路 C) (超)大规模集成电路 D) 电子管电路 2)下列说法中正确的是( ) 。 A) 计算机体积越大,其功能就越强 B) CPU的主频越高,其运行速度越快 C) 两个显示器屏幕大小相同,则它们的分辨率必定相同 D)点阵打印机的针数越多,则能打印的汉字字体越多 3)Windows98中,通过查找命令查找文件时,若输入F*.? , 则下列文件( ) 可以被查到。 A) F.BAS B) FABC.BAS C) F.C D) EF. 4)CPU处理数据的基本单位是字,一个字的字长( ) 。 A) 为8个二进制位 B) 为16个二进制位 C) 为32个二进制位 D) 与芯片的型号有关 5)资源管理器的目录前图标中增加"+"号,这个符号的意思是( ) 。 A) 该目录下的子目录已经展开 B) 该目录下还有子目录未展开 C) 该目录下没有子目录 D) 该目录为空目录, 6)下列哪一种程序设计语言是解释执行的( ) 。 A) Pascal B) GWBASIC C) C++ D) FORTRAN 7)启动WORD的不正确方法是( ) 。 A) 单击Office工具栏上的Word图标 B) 单击"开始"→"程序"→Word C) 单击"开始"→"运行",并输入Word按回车 D) 双击桌面上的"Word快捷图标" 8)多媒体计算机是指( ) 计算机。 A) 专供家庭使用的 B) 装有CDROM的 C) 连接在网络上的高级 D) 具有处理文字、图形、声音、影像等信息的 9)在树型目录结构中,不允许两个文件名相同主要是指( ) 。 A) 同一个磁盘的不同目录下 B) 不同磁盘的同一个目录下 C) 不同磁盘的不同目录下、 D) 同一个磁盘的同一个目录下 10)用画笔(Paintbrush)绘制图形并存储在文件中,该图形文件的文件名缺省的后缀为( ) 。 A) .jpg B) .bmp C) .gif D).tiff t11)E-ml地址中用户名和邮件所在服务器名之间的分隔符号是( ) 。 E A) # B) @ C) & D) $ 12)(0.5)10=( ) 16. A) 0.1 B) 0.75 C) 0.8 D) 0.25 N O I P2011普及组复赛 1．数字反转（c/pas） 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。（参见样例2） 【输入】 输入文件名为。 输入共一行，一个整数N。 【输出】 输出文件名为。 输出共1行，一个整数，表示反转后的新数。 -1,000,000,000≤N≤1,000,000,000。 【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题（以及-0，但测试数据没出）。 【法一】字符串处理 Var i,l,k:integer; s:string; p:boolean; begin assign(input, ''); reset(input); assign(output, ''); rewrite(output); readln(s); l:=length(s); k:=1; if s[1]='-' then begin write('-'); k:=2; end; p:=true;; for i:=l downto k do begin if(p)and((s[i]='0')) then continue else begin write(s[i]); p:=false;; end; end; close(input); close(output); end. 【法二】数字处理 Var f:integer; n,ans:longint; begin assign(input, ''); reset(input); 第十届信息学奥林匹克联赛复赛试题（NOIP2004） 一、津津的储蓄计划(save.pas/c/cpp) 【问题描述】 津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。 例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。 津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。 现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。 【输入文件】 输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。 【输出文件】 输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。 【样例输入1】 290 230 280 200 300 170 340 50 90 80 200 60 【样例输出1】 -7 【样例输入2】 290 230 NOIP复赛普及组试题 ————————————————————————————————作者：————————————————————————————————日期： CCF全国信息学奥林匹克联赛（NOIP2013）复赛 普及组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称计数问题表达 式求 值 小朋友的 数字 车站分 级 英文 题目 与子 目录 名 count expr number level 可执行 文件名 count expr number level 输入文 件名 count.in expr.in number.in level.in 输出文count.out expr.out n umber.out level.out 件名 每个 测试 点时 限 1 秒 1 秒 1 秒 1 秒 测试点 数目 10 10 10 10 每个 测试 点分 值 10 10 10 10 附加样 例文件 有有有有 结果比较方式全文比较（过滤行末空格及文末回车） 题目类 型 传统传统传统传统 运行内 存上限 128M 128M 128M 128M 二．提交源程序文件名 对于 C++语 言 count.cpp expr.cpp number.cpp level.cpp 对于 C 语 言 count.c expr.c number.c level.c 对于 pascal 语言 count.pas expr.pas number.pas level.pas 三．编译命令（不包含任何优化开关） 对于C++语言 g++ -o count count.cpp -lm g++ -o expr expr.cpp –lm g++ -o number number.cpp -lm g++ -o level level.cpp -lm 对于C 语言gcc -o count gcc -o expr gcc-o number gcc -o level 全国信息学奥林匹克联赛（2012）复赛提高组2 2． 1 ·同余方程 〖问题描述〗 求关于的同余方程三1 (句的最小正整数解。 输入〗 输入文件为 输入只有一行，包含两个正整数用一个空格隔开 输出〗 输出文件为 输出只有一行，包含一个正整数№即最小正整数解。输入数据保证一定有解。 〖输入输出样例〗 对于40％的数据，2 L000：对于60％的数据， 2 50，000，000： 对于100％的数据，2，2，000，000，000。 2 ·借教室 (. ) 问题描述〗 在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 面对海量租借教室的信息，我们自然希望编程解决这个问 题。 我们需要处理接下来n天的借教室信息，其中第i天学校有个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为d]，斗t}，表示某租借者需要从第丬天到第t]天租借教室（包括第丬天和第t)天），每天需要租借个教室。 我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供d]个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。 借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第丬天到第t)天中有至少一天剩余的教室数量不足d)个。现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改 输入〗 输入文件为 第一行包含两个正整数n，m,表示天数和订单的数量。 第二行包含n个正整数，其中第i个数为，表示第i天可用于租借的教室数量。 接下来有m行，每行包含三个正整数]，t]，表示租借的数量，租借开始、结束分别在第几天。 每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。 〖输出〗 输出文件为 如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足）输出两行，第一行输出一个负整数一1 ,第二行输出需要修改订单的申请人编号。 〖输入输出样例〗 CCF全国信息学奥林匹克联赛（NOIP2017）复赛 普及组 （请选手务必仔细阅读本页内容） 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz， 内存4G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、提交的程序代码文件的放置位置请参照各省的具体要求。 6、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。 1. 成绩 (score.cpp/c/pas) 【问题描述】 牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是： 总成绩=作业成绩×20%+小测成绩×30%+期末考试成绩×50% 牛牛想知道，这门课程自己最终能得到多少分。 【输入格式】 输入文件名为score.in。 输入文件只有1行，包含三个非负整数A、B、C，分别表示牛牛的作业成绩、小测成绩和期末考试成绩。相邻两个数之间用一个空格隔开，三项成绩满分都是100分。 【输出格式】 输出文件名为score.out。 输出文件只有1行，包含一个整数，即牛牛这门课程的总成绩，满分也是100分。 见选手目录下的score/score1.in和score/score1.ans。 【输入输出样例1说明】 牛牛的作业成绩是100分，小测成绩是100分，期末考试成绩是80分，总成绩是100×20%+100×30%+80×50%=20+30+40=90。 【输入输出样例2说明】 牛牛的作业成绩是60分，小测成绩是90分，期末考试成绩是80分，总成绩是60×20%+90×30%+80×50%=12+27+40=79。 【数据说明】 对于30%的数据，A=B=0。 对于另外30%的数据，A=B=100。 对于100%的数据，0≤A、B、C≤100且A、B、C都是10的整数倍。 NOIP 2008普及组解题报告 一、ISBN号码（isbn.pas/c/cpp） 【问题描述】 每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。 识别码的计算方法如下： 首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。 你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。 【输入】 输入文件isbn.in只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。 【输出】 输出文件isbn.out共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。 【输入输出样例1】 isbn.in 0-670-82162-4 isbn.out Right 【输入输出样例2】 isbn.in 第十三届全国青少年信息学奥林匹克联赛初赛试题 （提高组Pascal语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共10题，每题 1.5分，共计15分。每题有且仅有一个正确答案.）。 1.在以下各项中。（）不是CPU的组成部分。 A.控制器 B.运算器 C.寄存器 D.主板 E.算术逻辑单元(ALU) 2.在关系数据库中,存放在数据库中的数据的逻辑结构以()为主。 A.二叉树 B.多叉树 C.哈希表 D.B+树 E.二维表 3.在下列各项中，只有（）不是计算机存储容量的常用单位。 A.Byte B.KB C.MB D.UB E.TB 4．ASCII码的含义是（）。 A.二—十进制转换码 B.美国信息交换标准代码 C.数字的二进制数码 D.计算机可处理字符的唯一编码 E.常用字符的二进制编码 5．在Pascal语言中，表达式(23or2xor5)的值是（） A.18 B.1 C.23 D.32 E.24 6．在Pascal语言中，判断整数a等于0或b等于0或c等于0的正确的条件表达式是（） A.not((a<>0)or(b<>0)or(c<>0)) B.not((a<>0)and(b<>0)and(c<>0)) C.not((a=0)and(b=0))or(c=0) D.(a=0)and(b=0)and(c=0) E.not((a=0)or(b=0)or(c=0)) 7.地面上有标号为A、B、C的3根细柱,在A柱上放有10个直径相同中间有孔的圆盘,从上到下次依次编号为1,2,3,……，将A柱上的部分盘子经过B柱移入C柱,也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么,在C柱上,从下到上的盘子的编号为（）。 A.243657 B.241257 C.243176 D.243675 E.214375 8.与十进制数17.5625相对应的8进制数是（）。 A.21.5625 B.21.44 C.21.73 D.21.731 E.前4个答案都不对 9.欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中,不一定是欧拉图的是：（）。 A.图G中没有度为奇数的顶点 B.包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径)NOIP2014提高组复赛精彩试题(卷)
noip普及组复赛模拟试题18
NOIP2008提高组复赛试题及题解
NOIP2002普及组(复赛)
NOIP1999普及组(复赛)
NOIP2013初赛提高组Pascal试题及答案
NOIP2017普及组初赛试题及答案
NOIP2015普及组复赛试题
noip2017提高组试题
历年noip初赛普及组试题(完整资料).doc
NOIP2007_提高组_复赛试题
NOIP2002普及组初赛试题及答案
NOIP普及组复赛试题源程序
noip2004 提高组复赛试题及参考程序(pascal)
NOIP复赛普及组测试试题
NOIP2012提高组复赛试题
NOIP普及组复赛试题
NOIP2008普及组复赛试题与解题报告
NOIP2007初赛提高组试题和答案
相关主题
文本预览