nbhkdz.com冰点文库

NOIP历年复赛提高组试题(2006-2014)


2006~2014 年 NOIP 复赛试题集(提高组)

第十二届全国信息学奥林匹克分区联赛(NOIP2006)复赛试题
(提高组 竞赛用时:3 小时)

关于竞赛中不同语言使用限制的说明
一.关于使用 Pascal 语言与编译结果的说明 1.对于 Pascal 语言的程序,当使用 IDE 和 fpc 编译结果不一致时,

以 fpc 的编译结果为准。 2.允许使用数学库(uses math 子句),以及 ansistring。但不允许使用编译开关(最后测试时 pascal 的范围检查开关默认关闭:{$R-,Q-,S-}) ,也不支持与优化相关的选项。 二.关于 C++语言中模板使用的限制说明 1.允许使用的部分: 标准容器中的布尔集合,迭代器,串,流。 相关的头文件:<bitset > <iterator > <string > <iostream > 2.禁止使用的部分: 序列:vector,list,deque 序列适配器: stack, queue, priority_queue 关联容器: map, multimap, set, multiset 拟容器: valarray 散列容器:hash_map, hash_set, hash_multimap, hash_multiset 所有的标准库算法 相关头文件:<vector > <list > <deque > <stack > <map > <set > <algorithm > 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。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
1

2006~2014 年 NOIP 复赛试题集(提高组) ((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<N 时, 第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。 第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。 至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子, 然后按顺时针方向确定其他珠子的顺序。 【输出文件】 输出文件 energy.out 只有一行,是一个正整数 E(E≤2.1*109) ,为一个最优聚合顺序所释放的 总能量。 【输入样例】 4 2 3 5 【输出样例】 710

10

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

2006~2014 年 NOIP 复赛试题集(提高组) 从第 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 400 5 300 5 400 3 500 2 【输出样例】 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 2 3 机器号/加工时间 工序 1 1/3 1/2 2/2
3

0 1 1 0 0

工序 2 2/2 2/5 1/4

2006~2014 年 NOIP 复赛试题集(提高组) 则对于安排顺序“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 1 2 1 2 2 1 3 2 2 5 2 4 【输出样例】 10

3 32

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<w≤30000)是事先给定的。
4

2006~2014 年 NOIP 复赛试题集(提高组) 问:满足上述条件的不同的 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

5

2006~2014 年 NOIP 复赛试题集(提高组)

第十三届全国信息学奥林匹克分区联赛(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 个自然数中不相同数的个数),按照自然数从小到大的 顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。 【输入输出样例】 count.in 8 2 4 2 4 5 100 2 100
6

count.out 2 3 4 2 5 1 100 2

2006~2014 年 NOIP 复赛试题集(提高组)

【限制】 40%的数据满足:1<=n<=1000 80%的数据满足:1<=n<=50000 100%的数据满足:1<=n<=200000,每个数均不超过 1500 000 000(1.5*10 )
9

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】 expand.in 1 2 1 abcs-w1234-9s-4zz 【输入输出样例 2】 expand.in 2 3 2 a-d-d expand.out aCCCBBBd-d expand.out abcsttuuvvw1234556677889s-4zz

7

2006~2014 年 NOIP 复赛试题集(提高组) 【输入输出样例 3】 expand.in 3 4 2 di-jkstra2-6 【限制】 40%的数据满足:字符串长度不超过 5 100%的数据满足:1<=p1<=3,1<=p2<=8,1<=p3<=2。字符串长度不超过 100 expand.out dijkstra2************6

3、矩阵取数游戏(game.pas/c/cpp) 【问题描述】 帅帅经常更同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元素 aij 均 为非负整数。游戏规则如下: 1.每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有的元素; 2.每次取走的各个元素只能是该元素所在行的行首或行尾; 3.每次取数都有一个得分值,为每行取数的得分之和;每行取数的得分 = 被取走的元素值*2 , 其中 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】 game.in 2 3 1 2 3 3 4 2 【输入输出样例 1 解释】 第 1 次:第一行取行首元素,第二行取行尾元素,本次的氛围 1*2 +2*2 =6 第 2 次:两行均取行首元素,本次得分为 2*2 +3*2 =20 第 3 次:得分为 3*2 +4*2 =56。总得分为 6+20+56=82 【输入输出样例 2】 game.in 1 4 4 5 0 5 【输入输出样例 3】
8
3 3 2 2 1 1 i

game.out 82

game.out 122

2006~2014 年 NOIP 复赛试题集(提高组) game.in 2 10 96 56 54 46 86 12 23 88 80 43 16 95 18 29 30 53 88 83 64 67 【限制】 60%的数据满足:1<=n, m<=30,答案不超过 10
16

game.out 316994

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。

9

2006~2014 年 NOIP 复赛试题集(提高组)

【输入】 输入文件 core.in 包含 n 行: 第 1 行,两个正整数 n 和 s,中间用一个空格隔开。其中 n 为树网结点的个数,s 为树网的核的 长度的上界。设结点编号以此为 1,2,??,n。 从第 2 行到第 n 行,每行给出 3 个用空格隔开的正整数,依次表示每一条边的两个端点编号和 长度。例如,“2 4 7”表示连接结点 2 与 4 的边的长度为 7。 所给的数据都是争取的,不必检验。 【输出】 输出文件 core.out 只有一个非负整数,为指定意义下的最小偏心距。 【输入输出样例 1】 core.in 5 2 1 2 5 2 3 2 2 4 4 2 5 3 【输入输出样例 2】 core.in 8 6 1 3 2 2 3 2 3 4 6 4 5 3 4 6 4 4 7 2 7 8 3 【限制】 40%的数据满足:5<=n<=15 70%的数据满足:5<=n<=80 100%的数据满足:5<=n<=300,0<=s<=1000。边长度为不超过 1000 的正整数 core.out 5 Core.out 5

10

2006~2014 年 NOIP 复赛试题集(提高组)

第十四届全国信息学奥林匹克分区联赛(NOIP2008)复赛试题
(提高组 竞赛用时:3 小时)

一、题目概览
中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 比较方式 题目类型 笨小猴 word word word,in word.out 1秒 10 10 全文比较 传统 火柴棒等式 matches matches matches.in matches.out 1秒 10 10 全文比较 传统 传纸条 message message message.in message.out 1秒 10 10 全文比较 传统 双栈排序 twostack twostack twostack.in twostack.out 1秒 10 10 全文比较 传统

二、提交源程序文件名
对于 Pascal 语言 对于 C 语言 对于 C++语言 word.pas word.c word.cpp matches.pas matches.c matches.cpp message.pas message.c message.cpp twostack.pas twostack.c twostack.cpp

三、编译命令(不包含任何优化开关)
对于 Pascal 语言 对于 C 语言 对于 C++语言 fpc word.pas gcc –o word word.c g++ -o word word.cpp fpc matches.pas gcc –o matches matches.c g++-o matches matches.cpp fpc message.pas gcc –o message message.c g++ -o message message.cpp fpc twostack.pas gcc –o twostack twostack.c g++ -o twostack twostack.cpp

四、运行内存限制
运行内存上限 50M 50M 50M 50M

注意事项:
1. 文件名(程序名和输入输出文件名)必须使用大写。 2. C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3. 全国统一评测时采用的机器配置为:CPU 1.9GHz,内存 512M,上述时限以此配置为准。各省在 自测时可根据具体配置调整时限。 1. 笨小猴(word.pas/c/cpp) 【问题描述】 笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试
11

2006~2014 年 NOIP 复赛试题集(提高组) 验证明,用这种方法去选择选项的时候选对的几率非常大! 这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数,minn 是单词 中出现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。

【输入】 输入文件 word.in 只有一行,是一个单词,其中只可能出现小写字母,并且长度小于 100。 【输出】 输出文件 word.out 共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出 “Lucky Word” ,否则输出“No Answer” ; 第二行是一个整数,如果输入单词是 Lucky Word,输出 maxn-minn 的值,否则输出 0。

【输入输出样例 1】 word.in error word.out Lucky Word 2

【输入输出样例 1 解释】 单词 error 中出现最多的字母 r 出现了 3 次, 出现次数最少的字母出现了 1 次, 3-1=2, 2 是质数。 【输入输出样例 2】 word.in olympic word.out No Answer 0

【输入输出样例 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)加号与等号各自需要两根火柴棍
12

2006~2014 年 NOIP 复赛试题集(提高组) 2)如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C>=0) 3)n 根火柴棍必须全部用上

【输入】 输入文件 matches.in 共一行,又一个整数 n(n<=24) 。

【输出】 输出文件 matches.out 共一行,表示能拼成的不同等式的数目。

【输入输出样例 1】 matches.in 14 2 matches.out

【输入输出样例 1 解释】 2 个等式为 0+1=1 和 1+0=1。 【输入输出样例 2】 matches.in 18 9 matches.out

【输入输出样例 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 的自然数来表示,数越大表示越好心。小渊和 小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上 同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两条路径。

13

2006~2014 年 NOIP 复赛试题集(提高组) 【输入】 输入文件 message.in 的第一行有 2 个用空格隔开的整数 m 和 n ,表示班里有 m 行 n 列 (1<=m,n<=50) 。 接下来的 m 行是一个 m*n 的矩阵, 矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程 度。每行的 n 个整数之间用空格隔开。

【输出】 输出文件 message.out 共一行,包含一个整数,表示来回两条路上参与传递纸条的学生的好心程 度之和的最大值。

【输入输出样例】 message.in 33 039 285 570 【限制】 30%的数据满足:1<=m,n<=10 100%的数据满足:1<=m,n<=50 34 message.out

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)排序的操作序列:<a,c,c,b,a,d,d,b>

14

2006~2014 年 NOIP 复赛试题集(提高组)

当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个可行的操 作序列。Tom 希望知道其中字典序最小的操作序列是什么。

【输入】 输入文件 twostack.in 的第一行是一个整数 n。 第二行有 n 个用空格隔开的正整数, 构成一个 1~n 的排列。

【输出】 输出文件 twostack.out 共一行,如果输入的排列不是“可双栈排序排列” ,输出数字 0;否则输 出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。 【输入输出样例 1】 twostack.in 4 1324 twostack.out abaabbab

【输入输出样例 2】 twostack.in 4 2341 0 twostack.out

15

2006~2014 年 NOIP 复赛试题集(提高组)

【输入输出样例 3】 twostack.in 3 231 twostack.out acabbd

【限制】 30%的数据满足: n<=10 50%的数据满足: n<=50 100%的数据满足: n<=1000

16

2006~2014 年 NOIP 复赛试题集(提高组)

第十五届全国信息学奥林匹克分区联赛(NOIP2009)复赛试题
(提高组
一. 题目概况

竞赛用时:3 小时)

二. 提交程序文件名

三. 编译命令(不包含任何优化开关)

四. 运行内存限制

注意事项: 1、文件名(程序名和输入输出文件名)必须使用小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为:CPU 1.9GHz,内存 1G,上述时限以此配置为准。各 省在自测时可根据具体配置调整时限。

17

2006~2014 年 NOIP 复赛试题集(提高组)

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】 Spy.in AA AB EOWIE Spy.out Failed

【输入输出样例说明】

18

2006~2014 年 NOIP 复赛试题集(提高组) 原信息中的字母“A”禾? B”对应相同的密字,输出“Failed” 。

【输入输出样例 2】 Spy.in QWERTYUIOPLKJHGFDSAZXCVBN ABCDEFGHIJKLMNOPQRSTUVWXY DSLIEWO Spy.out Failed

【输入输出样例 2 说明】 字母“Z”在原信息中没有出现,输出“Failed” 。 【输入输出样例 3】 Spy.in MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL FLSO Spy.out NOIP

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 的个数; 【输入输出样例】
19

2006~2014 年 NOIP 复赛试题集(提高组) Son.in 2 41 95 1 96 288 1 37 1776 Son.out 6 2

【说明】 第一组输入数据,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 号城市
20

2006~2014 年 NOIP 复赛试题集(提高组) 以 5 的价格卖出水晶球,赚取的旅费数为 2。 阿龙也可以选择如下一条线路:1->4->5->4->5,并在第 1 次到达 5 号城市时以 1 的价格买入水 晶球,在第 2 次到达 4 号城市时以 6 的价格卖出水晶球,赚取的旅费数为 5。 现在给出 n 个城市的水晶球价格,m 条道路的信息(每条道路所连接的两个城市的编号以及该 条道路的通行情况) 。请你告诉阿龙,他最多能赚钱多少旅费。 【输入】 输入文件名为 trade.in。第一行包含 2 个正整数 n 和 m,中间用一个空格隔开,分别表示城市的 数目和道路的数目。第二行 n 个正整数,每两个正整数之间用一个空格隔开,按标号顺序分别表示 这 n 个城市的商品价格。接下来 m 行,每行有 3 个正整数,x,y,z,每两个整数之间用一个空格 隔开。如果 z=1,表示这条道路是城市 x 到城市 y 之间的单向道路;如果 z=2,表示这条道路为城市 x 和城市 y 之间的双向道路。 【输出】 输出文件 trade.out 共 1 行,包含 1 个整数,表示最多能赚取的旅费。如果没有进行贸易,则输 出 0。 【输入输出样例】 Trade.in 55 43561 121 141 232 351 452 5 Trade.out

【数据范围】 输入数据保证 1 号城市可以到达 n 号城市。 对于 10%的数据,1≤n≤6。 对于 30%的数据,1≤n≤100。 对于 50%的数据,不存在一条旅游路线,可以从一个城市出发,再回到这个城市。 对于 100%的数据,1≤n≤,1≤m≤,1≤x,y≤n,1≤z≤2,1≤各城市水晶球价格≤100。

4、靶形数独(sudoku.pas/c/cpp)
【问题描述】 小城和小华都是热爱数学的好学生,最近,他们不约而同地迷上了数独游戏,好胜的他们想用 数独来一比高堤?但普通的数独对他们来说都过于简单了,于是他们向 Z 博士请教,Z 博士拿出了 他最近发明的“靶形数独” ,作为这两个孩子比试的题目。 靶形数独的方格同普通数独一样, 在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九
21

2006~2014 年 NOIP 复赛试题集(提高组) 宫格(用粗黑色线隔开的) 。在这个大九宫格中,有一些数字是已知的,根据这些数字,利用逻辑推 理,在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能重复出现,每个数字在每 行、每列也不能重复出现。但靶形数独有一点和普通数独不同,即每一个方格都有一个分值,而且 如同一个靶子一样,离中心越近则分值越高。 (如下图)

上图具体的分值分布是:最里面一格(黄色区域)为 10 分,黄色区域外面的一圈(红色区域) 每个格子为 9 分,再外面一圈(蓝色区域)每个格子为 8 分,蓝色区域外面一圈(棕色区域)每个 格子为 7 分,最外面一圈(白色区域)每个格子为 6 分,如上图所示。比赛的要求是:每个人必须 完成一个给定的数独(每个给定数独有可能有不同的填法) ,而且要争取更高的总分数。而这个总分 数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总禾?如图,在以下这个已 经填完数字的靶形数独游戏中,总分为 2829。游戏规定,将以总分数的高低决出胜负。

由于求胜心切,小城找督了善于编程的你,让你帮他求出,对于给定的靶形数独,能够得到的 最高分数。 【输入】 输入文件名为 sudoku.in。一共 9 行,每行 9 个整数(每个数都在 0—9 的范围内) ,表示一个尚 未填满的数独方格,未填满的空格用“0”表示。每两个数字之间用一个空格隔开。
22

2006~2014 年 NOIP 复赛试题集(提高组)

【输出】 输出文件 sudoku.out 共 1 行。输出可以得到的靶形数独的最高分数。如果这个数独无解,则输 出整数-1。 【输入输出样例 1】 sudoku.in 7 1 0 0 0 4 0 2 0 0 0 0 0 0 1 0 0 8 0 0 0 5 0 3 7 1 0 9 0 2 0 0 0 0 0 5 0 0 0 2 0 0 0 6 0 0 5 0 0 0 0 2 0 4 0 9 0 0 6 0 0 8 0 0 0 8 0 4 0 9 0 1 1 0 0 3 8 0 0 4 2 Sudoku.out 2829

【输入输出样例 2】 sudoku.in 0 9 7 1 0 0 0 0 0 0 0 4 9 7 3 0 6 0 0 0 0 5 0 0 0 0 0 7 0 0 0 0 5 6 9 0 0 0 0 8 0 7 0 0 0 2 8 5 0 0 9 1 0 0 4 0 0 0 0 1 0 0 0 5 0 1 0 2 0 0 0 0 3 0 0 0 5 8 0 1 6 Sudoku.out 2852

【数据范围】 40%的数据,数独中非 0 数的个数不少于 30。 80%的数据,数独中非 0 数的个数不少于 26。 100%的数据,数独中非 0 数的个数不少于 24。

23

2006~2014 年 NOIP 复赛试题集(提高组)

第十六届全国信息学奥林匹克分区联赛(NOIP2010)复赛试题
(提高组
1、机器翻译(translate.pas/c/cpp)
【问题描述】 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 这个翻译软件的 原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词, 软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中 没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入 内存,以备后续的查找和翻译。 假设内存中有 M 个单元,每单元能存放一个单词和译义。每当软 件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过 M?1,软件会将新单词存入一 个未使用的内存单元;若内存中已存入 M 个单词,软件会清空最早进入内存的那个单词,腾出单 元来,存放新单词。 假设一篇英语文章的长度为 N 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词 典?假设在翻译开始前,内存中没有任何单词。 【输入】 输入文件名为 translate.in,输入文件共 2 行。每行中两个数之间用一个空格隔开。 第一行为两个正整数 M 和 N,代表内存容量和文章的长度。 第二行为 N 个非负整数,按照文章的顺序,每个数(大小不超过 1000)代表一个英文单词。 文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。 【输出】 输出文件 translate.out 共 1 行,包含一个整数,为软件需要查词典的次数。 【输入输出样例 1】 37 1215441 输出 5 【输入输出样例 1 说明】 整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况: 空:内存初始状态为空。 1. 1:查找单词 1 并调入内存。 2. 1 2:查找单词 2 并调入内存。 3. 1 2:在内存中找到单词 1。 4. 1 2 5:查找单词 5 并调入内存。 5. 2 5 4:查找单词 4 并调入内存替代单词 1。 6. 2 5 4:在内存中找到单词 4。 7. 5 4 1:查找单词 1 并调入内存替代单词 2。 共计查了 5 次词典。
24

竞赛用时:3 小时)

2006~2014 年 NOIP 复赛试题集(提高组)

【输入输出样例 2】 translate.in translate.out 2 10 8 824 11 78 11 78 11 78 8 264 6

【数据范围】 对于 10%的数据有 M=1,N≤ 5。 对于 100%的数据有 0<M≤ 100,0<N≤ 1000。

2、乌龟棋 (tortoise.pas/c/cpp)
【问题描述】 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行 N 个格子,每个格子上一个分数(非负整数) 。棋盘第 1 格是唯一的起 点,第 N 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 …… 1 2 3 4 5 …… N 乌龟棋中 M 张爬行卡片,分成 4 种不同的类型(M 张卡片中不一定包含所有 4 种类 型的卡片,见样例) ,每种类型的卡片上分别标有 1、2、3、4 四个数字之一,表示使用这种卡片 后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前 没有使用过的爬行卡片, 控制乌龟棋子前进相应的格子数, 每张卡片只能使用一次。 游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该 格子相应的分数。 玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总 和。 很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用 顺序使得最终游戏得分最多。 现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分 吗? 【输入】 输入文件名 tortoise.in。输入文件的每行中两个数之间用一个空格隔开。 第 1 行 2 个正整数 N 和 M,分别表示棋盘格子数和爬行卡片数。 第 2 行 N 个非负整数,a1, a2, ??, aN,其中 ai 表示棋盘第 i 个格子上的分数。 第 3 行 M 个整数,b1,b2, ??, bM,表示 M 张爬行卡片上的数字。 输入数据保证到达终点时刚好用光 M 张爬行卡片,即 N?1= ∑Mib1。 【输出】 输出文件名 tortoise.out。 输出只有 1 行,1 个整数,表示小明最多能得到的分数。 【输入输出样例 1】 tortoise.in tortoise.out 95
25

2006~2014 年 NOIP 复赛试题集(提高组) 6 10 14 2 8 8 18 5 17 13121 73 【输入输出样例 1 说明】 小明使用爬行卡片顺序为 1,1,3,1,2,得到的分数为 6+10+14+8+18+17=73。注意,由于 起点是 1,所以自动获得第 1 格的分数 6。 【输入输出样例 2】 tortoise.in tortoise.out 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 11111241 455 【数据范围】 对于 30%的数据有 1 ≤ N≤ 30,1 ≤M≤ 12。 对于 50%的数据有 1 ≤ N≤ 120,1 ≤M≤ 50,且 4 种爬行卡片,每种卡片的张数不会超 过 20。 对于 100%的数据有 1 ≤ N≤ 350,1 ≤M≤ 120,且 4 种爬行卡片,每种卡片的张数不会 超过 40;0 ≤ ai ≤ 100,1 ≤ i ≤ N;1 ≤ bi ≤ 4,1 ≤ i ≤M。输入数据保证 N?1=∑Mib1。

3、关押罪犯 (prison.pas/c/cpp)
【问题描述】 S 城现有两座监狱, 一共关押着 N 名罪犯, 编号分别为 1~N。 他们之间的关系自然也极不和谐。 很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值” (一个正 整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两 名怨气值为 c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为 c 的冲突事件。 每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上 报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力,如果影响很 坏,他就会考虑撤换警察局长。 在详细考察了 N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在两座监 狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监 狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯, 才能使 Z 市长看到的那个冲突事件的影响力最小?这个最小值是多少? 【输入】 输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。 第一行为两个正整数 N 和 M,分别表示罪犯的数目以及存在仇恨的罪犯对数。 接下来的 M 行每行为三个正整数 aj,bj,cj,表示 aj 号和 bj 号罪犯之间存在仇恨,其怨气值 为 cj。数据保证 N b a j j≤ < ≤ 1 , 000 , 000 , 000 , 1 0 ≤ < jc ,且每对罪犯组合只出现一次。 【输出】
26

2006~2014 年 NOIP 复赛试题集(提高组)

输出文件 prison.out 共 1 行,为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未 发生任何冲突事件,请输出 0。 【输入输出样例】 prison.in prison.out 46 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 3512 【输入输出样例说明】 罪犯之间的怨气值如下面左图所示,右图所示为罪犯的分配方法,市长看到的冲突事件影响力 是 3512(由 2 号和 3 号罪犯引发) 。其他任何分法都不会比这个分法更优。 【数据范围】 对于 30%的数据有 N≤ 15。 对于 70%的数据有 N≤ 2000,M≤ 50000。 对于 100%的数据有 N≤ 20000,M≤ 100000。

4、沙漠
在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十 分特殊,刚好构成一个 N 行 M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市 都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种, 别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此, 只有与湖泊毗邻的第 1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落 差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共 边的相邻城市,已经建有水利设施。 由于第 N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。 那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能 建有水利设施的城市数目。 【输入】 输入文件名为 flow.in。输入文件的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数 N 和 M,表示矩形的规模。 接下来 N 行,每行 M 个正整数,依次代表每座城市的海拔高度。 【输出】 输出文件名为 flow.out。
27

2006~2014 年 NOIP 复赛试题集(提高组) 输出有两行。如果能满足要求,输出的第一行是整数 1,第二行是一个整数,代表最少建造几 个蓄水厂;如果不能满足要求,输出的第一行是整数 0,第二行是一个整数,代表有几座干旱区中 的城市不可能建有水利设施。 【输入输出样例 1】 flow.in flow.out 25 91543 87612 1 1 【样例 1 说明】 只需要在海拔为 9 的那座城市中建造蓄水厂,即可满足要求。 【输入输出样例 2】 flow.in flow.out 36 845644 734333 322112 1 3 【样例 2 说明】 湖泊 8 4 5 6 4 4 7 3 4 3 3 3 3 2 2 1 1 2 沙漠 上图中,在 3 个粗线框出的城市中建造蓄水厂,可以满足要求。以这 3 个蓄水厂为源头在干 旱区中建造的输水站分别用 3 种颜色标出。当然,建造方法可能不唯一。 【数据范围】 本题共有 10 个测试数据,每个数据的范围如下表所示: 测试数据编号 能否满足要求 N M 1 不能 ≤ 10 ≤ 10 2 不能 ≤ 100 ≤ 100 3 不能 ≤ 500 ≤ 500 4 能 = 1 ≤ 10 5 能 ≤ 10 ≤ 10 6 能 ≤ 100 ≤ 20
28

2006~2014 年 NOIP 复赛试题集(提高组) 7 能 ≤ 100 ≤ 50 8 能 ≤ 100 ≤ 100 9 能 ≤ 200 ≤ 200 10 能 ≤ 500 ≤ 500 对于所有的 10 个数据,每座城市的海拔高度都不超过 106。

29

2006~2014 年 NOIP 复赛试题集(提高组)

全国信息学奥林匹克联赛(NOIP2011)复赛 提高组 Day1
一. 题目概况

二.

提交源程序文件名

三.

编译命令(不包含任何编译开关

四.

运行内存限制

注意事项: 1、 文件名(程序名和输入输出文件名)必须用英文小写。 2、 C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、 全国统一评测时采用的机器配置为:CPU P4 3.0GHz,内存 1G,上述时限以此配置为准。 4、 特别提醒:评测在 NOI Linux 下进行。

30

2006~2014 年 NOIP 复赛试题集(提高组)

1、铺地毯
【问题描述】 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第 一象限)铺上一些矩形地毯。一共有 n 张地毯,编号从 1 到 n。 现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经 铺好的地毯之上。地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。 注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。 【输入】 输入文件名为 carpet.in。 输入共 n+2 行。 第一行,一个整数 n,表示总共有 n 张地毯。 接下来的 n 行中,第 i+1 行表示编号 i 的地毯的信息,包含四个正整数 a,b,g,k,每两个 整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标(a,b)以及地毯在 x 轴和 y 轴方向 的长度。 第 n+2 行包含两个正整数 x 和 y,表示所求的地面的点的坐标(x,y) 。 【输出】 输出文件名为 carpet.out。 输出共 1 行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出-1。 【输入输出样例 1】 carpet.in 3 1023 0233 2133 22 carpet.out

3

【输入输出样例说明】 如下图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,覆盖点(2,2)的 最上面一张地毯是 3 号地毯。

31

2006~2014 年 NOIP 复赛试题集(提高组) 【输入输出样例 2】 carpet.in 3 1023 0233 2133 45 carpet.out

-1

【输入输出样例说明】 如上图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,点(4,5)没有被 地毯覆盖,所以输出-1。 【数据范围】 对于 30%的数据,有 n≤2; 对于 50%的数据,0≤a, b, g, k≤100; 对于 100%的数据,有 0≤n≤10,000,0≤a, b, g, k≤100,000。

2、选择客栈
【问题描述】 丽江河边有 n 家很有特色的客栈,客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一 种色调进行装饰(总共 k 种,用整数 0 ~ k-1 表示) ,且每家客栈都设有一家咖啡店,每家咖啡店均 有各自的最低消费。 两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住 在色调相同的两家客栈中。晚上,他们打算选择一家咖啡店喝咖啡,要求咖啡店位于两人住的两家 客栈之间(包括他们住的客栈) ,且咖啡店的最低消费不超过 p。 他们想知道总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过 p 元的咖啡 店小聚。 【输入】 输入文件 hotel.in,共 n+1 行。 第一行三个整数 n,k,p,每两个整数之间用一个空格隔开,分别表示客栈的个数,色调的数 目和能接受的最低消费的最高值;接下来的 n 行,第 i+1 行两个整数,之间用一个空格隔开,分别 表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。 【输出】 输出文件名为 hotel.out。 输出只有一行,一个整数,表示可选的住宿方案的总数。 【输入输出样例 1】

32

2006~2014 年 NOIP 复赛试题集(提高组) hotel.in 523 05 13 02 14 15 【输入输出样例说明】 客栈编号 色调 最低消费 ① 0 5 ② 1 3 ③ 0 2 ④ 1 4 ⑤ 1 5 hotel.out

3

2 人要住同样色调的客栈,所有可选的住宿方案包括:住客栈①③,②④,②⑤,④⑤,但是 若选择住 4、5 号客栈的话,4、5 号客栈之间的咖啡店的最低消费是 4,而两人能承受的最低消费 是 3 元,所以不满足要求。因此只有前 3 种方案可选。 【数据范围】 对于 30%的数据,有 n≤100; 对于 50%的数据,有 n≤1,000; 对于 100%的数据,有 2≤n≤200,000,0<k≤50,0≤p≤100, 0≤最低消费≤100。

3、mayan 游戏
【问题描述】 Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 7 行 5 列的棋盘,上面堆放着一些 方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在 规定的步数内消除所有的方块,消除方块的规则如下: 1、 每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果 拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出 样例说明中的图 6 到图 7) ;如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽 出,并从目标位置上掉落(直到不悬空,参见下面图 1 和图 2) ;

33

2006~2014 年 NOIP 复赛试题集(提高组) 2、 任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即 被消除(参见图 1 到图 3) 。 注意: a) 如果同时有多组方块满足消除条件, 几组方块会同时被消除 (例如下面图 4, 三个颜色为 1 的 方块和三个颜色为 2 的方块会同时被消除,最后剩下一个颜色为 2 的方块) 。 b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会 被同时消除(例如下面图 5 所示的情形,5 个方块会同时被消除) 。

方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的 过程中将不会有方块的消除。上面图 1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋 盘的左下角方块的坐标为(0, 0) ,将位于(3, 3)的方块向左移动之后,游戏界面从图 1 变成图 2 所 示的状态,此时在一竖列上有连续三块颜色为 4 的方块,满足消除条件,消除连续 3 块颜色为 4 的 方块后,上方的颜色为 3 的方块掉落,形成图 3 所示的局面。 【输入】 输入文件 mayan.in,共 6 行。 第一行为一个正整数 n,表示要求游戏通关的步数。 接下来的 5 行,描述 7*5 的游戏界面。每行若干个整数,每两个整数之间用一个空格隔开, 每行以一个 0 结束,自下向上表示每竖列方块的颜色编号(颜色不多于 10 种,从 1 开始顺序 编号,相同数字表示相同颜色) 。输入数据保证初始棋盘中没有可以消除的方块。 【输出】 输出文件名为 mayan.out。 如果有解决方案,输出 n 行,每行包含 3 个整数 x,y,g,表示一次移动,每两个整数之间用 一个空格隔开,其中(x,y)表示要移动的方块的坐标,g 表示移动的方向,1 表示向右移动,-1 表 示向左移动。注意:多组解时,按照 x 为第一关健字,y 为第二关健字,1 优先于-1,给出一组字 典序最小的解。游戏界面左下角的坐标为(0,0) 。如果没有解决方案,输出一行,包含一个整数-1。 【输入输出样例 1】 mayan.in 3 10 210 2340 310 24340 【输入输出样例说明】 按箭头方向的顺序分别为图 6 到图 11 mayan.out

211 311 301

34

2006~2014 年 NOIP 复赛试题集(提高组)

样例输入的游戏局面如上面第一个图片所示,依次移动的三步是: (2,1)处的方格向右移动, (3,1)处的方格向右移动, (3,0)处的方格向右移动,最后可以将棋盘上所有方块消除。 【数据范围】 对于 30%的数据,初始棋盘上的方块都在棋盘的最下面一行; 对于 100%的数据,0 < n≤5。

提高组 Day2
一. 题目概括

二.

提交源程序文件名

35

2006~2014 年 NOIP 复赛试题集(提高组)

三.

编译命令(不包含任何优化开关)

四.

运行内存限制

注意事项: 1、 文件名(程序名和输入输出文件名)必须使用英文小写。 2、 C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、 全国统一评测时采用的机器配置为:CPU P4 3.0GHz,内存 1G,上述时限以此配置为准。 4、 特别提醒:评测在 NOI Linux 下进行。

1、计算系数
【问题描述】 给定一个多项式(ax + by)^k,请求出多项式展开后(x^n)*(y^m)项的系数。 【输入】 输入文件名为 factor.in。 共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。 【输出】 输出文件名为 factor.out。 输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10007 取模后的 结果。 【输入输出样例】 factor.in 11312 factor.out 3

【数据范围】 对于 30%的数据,有 0≤k≤10; 对于 50%的数据,有 a = 1,b = 1; 对于 100%的数据,有 0≤k≤1,000,0≤n, m≤k,且 n + m = k,0≤a,b≤1,000,000。

36

2006~2014 年 NOIP 复赛试题集(提高组)

2、聪明的质监员
【问题描述】 小 T 是一名质量监督员, 最近负责检验一批矿产的质量。 这批矿产共有 n 个矿石, 从1到n 逐 一编号,每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是: 1、给定 m 个区间[Li,Ri]; 2、选出一个参数 W; 3、对于一个区间[Li,Ri],计算矿石在这个区间上的检验值 Yi :Yi=sum*sumv。sum 为[Li, Ri]之间 Wi>=W 的矿石数量,sumv 为其价值和。 这批矿产的检验结果 Y 为各个区间的检验值之和。 若这批矿产的检验结果与所给标准值 S 相差太多,就需要再去检验另一批矿产。小 T 不想费时 间去检验另一批矿产,所以他想通过调整参数 W 的值,让检验结果尽可能的靠近标准值 S,即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。 【输入】 输入文件 qc.in。 第一行包含三个整数 n,m,S,分别表示矿石的个数、区间的个数和标准值。 接下来的 n 行,每行 2 个整数,中间用空格隔开,第 i+1 行表示 i 号矿石的重量 wi 和价值 vi 。 接下来的 m 行,表示区间,每行 2 个整数,中间用空格隔开,第 i+n+1 行表示区间[Li,Ri]的 两个端点 Li 和 Ri。注意:不同区间可能重合或相互重叠。 【输出】 输出文件名为 qc.out。 输出只有一行,包含一个整数,表示所求的最小值。 【输入输出样例】 qc.in 5 3 15 15 qc.out 10

37

2006~2014 年 NOIP 复赛试题集(提高组) 25 35 45 55 15 24 33 【输入输出样例说明】 当 W 选 4 的时候,三个区间上检验值分别为 20、5、0,这批矿产的检验结果为 25,此时与标 准值 S 相差最小为 10。 【数据范围】 对于 10%的数据,有 1≤n,m≤10; 对于 30%的数据,有 1≤n,m≤500; 对于 50%的数据,有 1≤n,m≤5,000; 对于 70%的数据,有 1≤n,m≤10,000; 对于 100%的数据,有 1≤n,m≤200,000,0 < wi, vi≤106,0 < S≤10^12,1≤Li≤Ri≤n。

3、观光公交
【问题描述】 风景迷人的小城 Y 市,拥有 n 个美丽的景点。由于慕名而来的游客越来越多,Y 市特意安排 了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1 号景点,随后 依次前往 2、3、4??n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。任意时刻,公交车 只能往前开,或在景点处等待。 设共有 m 个游客, 每位游客需要乘车 1 次从一个景点到达另一个景点, 第 i 位游客在 Ti 分钟 来到景点 Ai,希望乘车前往景点 Bi(Ai<Bi) 。为了使所有乘客都能顺利到达目的地,公交车在每站 都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要 时间。 一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光 车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交 车安装了 k 个氮气加速器,每使用一个加速器,可以使其中一个 Di 减 1。对于同一个 Di 可以重复 使用加速器,但是必须保证使用后 Di 大于等于 0。 那么 ZZ 该如何安排使用加速器,才能使所有乘客的旅行时间总和最小? 【输入】 输入文件名为 bus.in。 第 1 行是 3 个整数 n, m, k,每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮 气加速器个数。 第 2 行是 n-1 个整数, 每两个整数之间用一个空格隔开, 第 i 个数表示从第 i 个景点开往第 i+1 个景点所需要的时间,即 Di。 第 3 行至 m+2 行每行 3 个整数 Ti, Ai, Bi,每两个整数之间用一个空格隔开。第 i+2 行表示第 i 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。 【输出】
38

2006~2014 年 NOIP 复赛试题集(提高组) 输出文件名为 bus.out。共一行,包含一个整数,表示最小的总旅行时间。 【输入输出样例】 bus.in 332 14 013 112 523 bus.out

10

【输入输出样例说明】 对 D2 使用 2 个加速器,从 2 号景点到 3 号景点时间变为 2 分钟。 公交车在第 1 分钟从 1 号景点出发,第 2 分钟到达 2 号景点,第 5 分钟从 2 号景点出发, 第 7 分钟到达 3 号景点。 第 1 个旅客旅行时间 7-0 = 7 分钟。 第 2 个旅客旅行时间 2-1 = 1 分钟。 第 3 个旅客旅行时间 7-5 = 2 分钟。 总时间 7+1+2 = 10 分钟。 【数据范围】 对于 10%的数据,k=0; 对于 20%的数据,k=1; 对于 40%的数据,2 ≤ n ≤ 50,1 ≤ m≤ 1,000,0 ≤ k ≤ 20,0 ≤ Di ≤ 10,0 ≤ Ti ≤ 500; 对于 60%的数据,1 ≤ n ≤ 100,1 ≤ m≤ 1,000,0 ≤ k ≤ 100,0 ≤ Di ≤ 100,0 ≤ Ti ≤ 10,000; 对于 100%的数据, 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 10,000, 0 ≤ k ≤ 100,000, 0 ≤ Di ≤ 100, 0 ≤ Ti ≤ 100,000。

39

2006~2014 年 NOIP 复赛试题集(提高组)

全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 Day1
一. 题目概况

二.

提交源程序文件名

三.

编译命令(不包含任何优化开关)

四.

运行内存限制

注意事项: 1、 文件名(程序名和输入输出文件名)必须使用英文小写。 2、 C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、 全国统一评测时采用的机器配置为:CPU Intel Core2 Quad Q8200 2.33GHz,内存 2G,上述时 限以此配置为准。 4、 特别提醒:评测在 NOI Linux 下进行。

1.Vigenère 密码

(vigenere .cpp/c/pas)

【问题描述】 16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。 Vigenère 密码的加密解密算法简单易用, 且破译难度比较高, 曾在美国南北战争中为南军所广泛使
40

2006~2014 年 NOIP 复赛试题集(提高组) 用。 在密码学中,我们称需要加密的信息为明文,用 M 表示;称加密后的信息为密文,用 C 表示; 而密钥是一种参数, 是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为 k。 在 Vigenère 密码中, 密钥 k 是一个字母串, k=k1k2…kn。当明文 M=m1m2?mn 时,得到的密文 C=c1c2…cn,其中 ci=mi?ki,运算?的规则如下表所示:

Vigenère 加密在操作时需要注意: 1. ?运算忽略参与运算的字母的大小写,并保持字母在明文 M 中的大小写形式; 2. 当明文 M 的长度大于密钥 k 的长度时,将密钥 k 重复使用。 例如,明文 M=Helloworld,密钥 k=abc 时,密文 C=Hfnlpyosnd。

【输入】 输入文件名为 vigenere.in。 输入共 2 行。 第一行为一个字符串,表示密钥 k,长度不超过 100,其中仅包含大小写字母。 第二行为一个字符串,表示经加密后的密文,长度不超过 1000,其中仅包含大小写字母。 【输出】 输出文件名为 vigenere.out。 输出共 1 行,一个字符串,表示输入密钥和密文所对应的明文。 【输入输出样例】

41

2006~2014 年 NOIP 复赛试题集(提高组)

【数据说明】 对于 100%的数据,输入的密钥的长度不超过 100,输入的密文的长度不超过 1000,且都仅包 含英文字母。

2.国王游戏(game.cpp/c/pas)
【问题描述】 恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面 分别写下一个整数,国王自己也在左、 右手上各写一个整数。然后, 让这 n 位大臣排成一排,国 王站在队伍的最前面。 排好队后,所有的大臣都会获得国王奖赏的若干金币, 每位大臣获得的金 币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整 得到的结果。 国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得
42

2006~2014 年 NOIP 复赛试题集(提高组) 获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。 【输入】 输入文件为 game.in。 第一行包含一个整数 n,表示大臣的人数。 第二行包含两个整数 a 和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。 接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右 手上的整数。 【输出】 输出文件名为 game.out。 输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。 【输入输出样例】

【输入输出样例说明】 按 1、2、3 号大臣这样排列队伍,获得奖赏最多的大臣所获得金币数为 2; 按 1、3、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2; 按 2、1、3 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2; 按 2、3、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9; 按 3、1、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2; 按 3、2、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9。 因此,奖赏最多的大臣最少获得 2 个金币,答案输出 2。 【数据范围】 对于 20%的数据,有 1≤ n≤ 10,0 < a、b < 8; 对于 40%的数据,有 1≤ n≤20,0 < a、b < 8; 对于 60%的数据,有 1≤ n≤100; 对于 60%的数据,保证答案不超过 10^9; 对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。

3.开车旅行(drive.cpp/c/pas) 【问题描述】 小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 到 N 编号,且编号较小的城市 在编号较大的城市的西边, 已知各个城市的海拔高度互不相同, 记城市 i 的海拔高度为 Hi , 城市 i 和城市 j 之间的距离 d[i,j] 恰好是这两个城市海拔高度之差的绝对值,即 d[i, j] = |? |。 旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划选择 一个城市 S 作为起点,一直向东行驶,并且最多行驶 X 公里就结束旅行。小 A 和小 B 的驾驶风 格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择
43

2006~2014 年 NOIP 复赛试题集(提高组) 第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的 那个城市更近) 。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的 总距离超出 X 公里,他们就会结束旅行。 在启程之前,小 A 想知道两个问题: 1.对于一个给定的 X=X 0,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果 小 B 的行驶路程为 0, 此时的比值可视为无穷大, 且两个无穷大视为相等) 。 如果从多个城市 出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小,则输出海拔最高的那个城 市。 2. 对任意给定的 X=Xi 和出发城市 Si,小 A 开车行驶的路程总数以及小 B 行驶的路程 总数。 【输入】 输入文件为 drive.in。 第一行包含一个整数 N,表示城市的数目。 第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高 度,即 H1,H2,??,Hn,且每个 Hi 都是不同的。 第三行包含一个整数 X0。 第四行为一个整数 M,表示给定 M 组 Si 和 Xi。 接下来的 M 行,每行包含 2 个整数 Si 和 Xi,表示从城市 Si 出发,最多行驶 Xi 公里。 【输出】 输出文件为 drive.out。 输出共 M+1 行。 第一行包含一个整数 S0,表示对于给定的 X0,从编号为 S0 的城市出发, 小 A 开车行驶 的路程总数与小 B 行驶的路程总数的比值最小。 接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 Si 和 Xi 下 小 A 行驶的里程总数和小 B 行驶的里程总数。 【输入输出样例 1】

【输入输出样例 1 说明】

44

2006~2014 年 NOIP 复赛试题集(提高组)

各个城市的海拔高度以及两个城市间的距离如上图所示。 如果从城市 1 出发, 可以到达的城市为 2,3,4,这几个城市与城市 1 的距离分别为 1,1,2,但 是由于城市 3 的海拔高度低于城市 2,所以我们认为城市 3 离城市 1 最近,城市 2 离城市 1 第 二近,所以小 A 会走到城市 2。到达城市 2 后,前面可以到达的城市为 3,4,这两个城市与城市 2 的距离分别为 2,1,所以城市 4 离城市 2 最近,因此小 B 会走到城市 4。到达城市 4 后,前面 已没有可到达的城市,所以旅行结束。 如果从城市 2 出发, 可以到达的城市为 3,4,这两个城市与城市 2 的距离分别为 2,1,由于 城市 3 离城市 2 第二近,所以小 A 会走到城市 3。到达城市 3 后, 前面尚未旅行的城市为 4, 所以城市 4 离城市 3 最近,但是如果要到达城市 4,则总路程为 2+3=5>3,所以小 B 会直接在 城市 3 结束旅行。 如果从城市 3 出发,可以到达的城市为 4,由于没有离城市 3 第二近的城市,因此旅行还未 开始就结束了。 如果从城市 4 出发,没有可以到达的城市,因此旅行还未开始就结束了。 【输入输出样例 2】

【输入输出样例 2 说明】 当 X=7 时, 如果从城市 1 出发,则路线为 1 -> 2 -> 3 -> 8 -> 9,小 A 走的距离为 1+2=3,小 B 走的距离 为 1+1=2。 (在城市 1 时,距离小 A 最近的城市是 2 和 6,但是城市 2 的海拔更高,视为与城 市 1 第二近的城市,所以小 A 最终选择城市 2;走到 9 后,小 A 只有城市 10 可以走,没有第 2 选择可以选,所以没法做出选择,结束旅行)
45

2006~2014 年 NOIP 复赛试题集(提高组) 如果从城市 2 出发,则路线为 2 -> 6 -> 7 ,小 A 和小 B 走的距离分别为 2,4。 如果从城市 3 出发,则路线为 3 -> 8 -> 9,小 A 和小 B 走的距离分别为 2,1。 如果从城市 4 出发,则路线为 4 -> 6 -> 7,小 A 和小 B 走的距离分别为 2,4。 如果从城市 5 出发,则路线为 5 -> 7 -> 8 ,小 A 和小 B 走的距离分别为 5,1。 如果从城市 6 出发,则路线为 6 -> 8 -> 9,小 A 和小 B 走的距离分别为 5,1。 如果从城市 7 出发,则路线为 7 -> 9 -> 10,小 A 和小 B 走的距离分别为 2,1。 如果从城市 8 出发,则路线为 8 -> 10,小 A 和小 B 走的距离分别为 2,0。 如果从城市 9 出发, 则路线为 9, 小 A 和小 B 走的距离分别为 0, 0 (旅行一开始就结束了) 。 如果从城市 10 出发,则路线为 10,小 A 和小 B 走的距离分别为 0,0。 从城市 2 或者城市 4 出发小 A 行驶的路程总数与小 B 行驶的路程总数的比值都最小,但是 城市 2 的海拔更高,所以输出第一行为 2。 【数据范围】 对于 30%的数据,有 1≤N≤20,1≤M≤20; 对于 40%的数据,有 1≤N≤100,1≤M≤100; 对于 50%的数据,有 1≤N≤100,1≤M≤1,000; 对于 70%的数据,有 1≤N≤1,000,1≤M≤10,000; 对于 100%的数据,有 1≤N≤100,000, 1≤M≤10,000, -1,000,000,000≤Hi≤1,000,000,000, 0≤X0≤1,000,000,000,1≤Si≤N,0≤Xi≤1,000,000,000,数据保证 Hi 互不相同。

提高组 Day2
一. 题目概况

二.

提交源程序文件名

三.

编译命令(不包含任何优化开关)
46

2006~2014 年 NOIP 复赛试题集(提高组)

四.

运行内存限

注意事项: 1、 文件名(程序名和输入输出文件名)必须使用英文小写。 2、 C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值为 0。 3、 全国统一评测时采用的机器配置为:CPU Intel Core2 Quad Q8200 2.33GHz,内存 2G,上述时 限以此配置为准。 4、 特别提醒:评测在 NOI Linux 下进行。

1.同余方程(mod.cpp/c/pas)
【问题描述】 求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。 【输入】 输入文件为 mod.in。 输入只有一行,包含两个正整数 a, b,用一个空格隔开。 【输出】 输出文件为 mod.out。 输出只有一行,包含一个正整数 x0,即最小正整数解。输入数据保证一定有解。 【输入输出样例】

【数据范围】 对于 40%的数据,2 ≤b≤ 1,000; 对于 60%的数据,2 ≤b≤ 50,000,000; 对于 100%的数据,2 ≤a, b≤ 2,000,000,000。

2.借教室(classroom.cpp/c/pas)
【问题描述】 在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校 申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。 面对海量租借教室的信息,我们自然希望编程解决这个问题。
47

2006~2014 年 NOIP 复赛试题集(提高组) 我们需要处理接下来 n 天的借教室信息, 其中第 i 天学校有 ri 个教室可供租借。 共有 m 份订单, 每份订单用三个正整数描述,分别为 dj, sj, tj ,表示某租借者需要从第 sj 天到第 tj 天租借教室(包 括第 sj 天和第 tj 天) ,每天需要租借 dj 个教室。 我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供 dj 个 教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。 借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如 果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。 这里的无法满足指从第 sj 天到第 tj 天中有至少一天剩余的教室数量不足 dj 个。 现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改 订单。 【输入】 输入文件为 classroom.in。 第一行包含两个正整数 n, m,表示天数和订单的数量。 第二行包含 n 个正整数,其中第 i 个数为 ri,表示第 i 天可用于租借的教室数量。 接下来有 m 行,每行包含三个正整数 dj, sj, tj ,表示租借的数量,租借开始、结束分别在 第几天。 每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 1 开始的整数编号。 【输出】 输出文件为 classroom.out。 如果所有订单均可满足,则输出只有一行,包含一个整数 0。否则(订单无法完全满足)输出 两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。 【输入输出样例】

【输入输出样例说明】 第 1 份订单满足后, 4 天剩余的教室数分别为 0, 3, 2, 3。 第 2 份订单要求第 2 天到第 4 天 每天提供 3 个教室,而第 3 天剩余的教室数为 2,因此无法满足。分配停止,通知第 2 个申请人 修改订单。 【数据范围】 对于 10%的数据,有 1 ≤ n, m ≤ 10; 对于 30%的数据,有 1 ≤ n, m ≤ 1000; 对于 70%的数据,有 1 ≤ n, m ≤ 10^5; 对于 100%的数据,有 1 ≤ n, m ≤ 10^6, 0 ≤ ri, dj≤ 10^9, 1 ≤ sj≤ tj≤ n。

3.疫情控制(blockade.cpp/c/pas)
【问题描述】 H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树, 1 号城市是首都, 也是树中的根节点。 H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情, 不让疫情扩散到边境城市
48

2006~2014 年 NOIP 复赛试题集(提高组) (叶子节点所表示的城市) ,决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一 条路径上都至少有一个检查点, 边境城市也可以建立检查点。 但特别要注意的是,首都是不能建 立检查点的。 现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以 在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立 检查点。 一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度 (单位: 小时) 。 请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。 【输入】 输入文件名为 blockade.in。 第一行一个整数 n,表示城市个数。 接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。 接下来一行一个整数 m,表示军队个数。 接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎的城市 的编号。 【输出】 输出文件为 blockade.out。 共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。 【输入输出样例】

【输入输出样例说明】 第一支军队在 2 号点设立检查点,第二支军队从 2 号点移动到 3 号点设立检查点,所需时间 为 3 个小时。 【数据范围】 保证军队不会驻扎在首都。 对于 20%的数据,2≤ n≤ 10; 对于 40%的数据,2 ≤n≤50,0<w <105; 对于 60%的数据,2 ≤ n≤1000,0<w <106; 对于 80%的数据,2 ≤ n≤10,000; 对于 100%的数据,2≤m≤n≤50,000,0<w <10^9。

49

2006~2014 年 NOIP 复赛试题集(提高组)

全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 Day1
一. 题目概

二.

提交源程序文件名

三.

编译命令(不包括任何优化开关)

注意事项: 1、 文件名(程序名和输入输出文件名)必须使用英文小写。 2、 C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、 全国统一评测时采用的机器配置:CPU AMD Athlon(tm)64x2 Dual Core CPU 5200+,2.7GHz, 内存 2G,上述时限以此配置为准。 4、 只提供 Linux 格式附加样例文件。 5、 特别提醒:评测在 NOI Linux 下进行。

1.转圈游戏(circle.cpp/c/pas)
【问题描述】 n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从 0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,??,依此类推。 游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴
50

2006~2014 年 NOIP 复赛试题集(提高组) 走到第 m+1 号位置,??,依此类推,第 n ? m 号位置上的小伙伴走到第 0 号位置,第 n-m+1 号 位置上的小伙伴走到第 1 号位置,??,第 n-1 号位置上的小伙伴顺时针走到第 m-1 号位置。 现在,一共进行了 10k 轮,请问 x 号小伙伴最后走到了第几号位置。 【输入】 输入文件名为 circle.in。 输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。 【输出】 输出文件名为 circle.out。 输出共 1 行,包含 1 个整数,表示 10k 轮后 x 号小伙伴所在的位置编号。 【输入输出样例】

【数据说明】 对于 30%的数据,0 < < 7; 对于 80%的数据,0 < < 10^7; 对于 100%的数据,1 < < 1,000,000,0 < < ,1 ≤ x ≤ n,0 < < 10/69。

2.火柴排队(match.cpp/c/pas)
【问题描述】 涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。 现在将每盒中的火柴各自排 成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为: ∑ (? )2 ni=1 ,其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。 每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请 问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。 【输入】 输入文件为 match.in。
51

2006~2014 年 NOIP 复赛试题集(提高组) 共三行,第一行包含一个整数 n,表示每盒中火柴的数目。 第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。 第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。 【输出】 输出文件为 match.out。 输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。 【输入输出样例 1】

【输入输出样例说明】 最小距离是 0, 最少需要交换 1 次, 比如: 交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。 【输入输出样例 2】

【输入输出样例说明】 最小距离是 10, 最少需要交换 2 次, 比如: 交换第 1 列的中间 2 根火柴的位置, 再交换第 2 列中后 2 根火柴的位置。 【数据范围】 对于 10%的数据, 1 ≤ n ≤ 10; 对于 30%的数据,1 ≤ n ≤ 100; 对于 60%的数据,1 ≤ n ≤ 1,000; 对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤火柴高度≤ 231? 1。

3.货车运输(truck.cpp/c/pas)
【问题描述】 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量 限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下, 最多能运多重的货物。 【输入】 输入文件名为 truck.in。 输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。 接下来 m 行每行 3 个整数 x、 y、 z,每两个整数之间用一个空格隔开,表示从 x 号城市
52

2006~2014 年 NOIP 复赛试题集(提高组) 到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。 接下来一行有一个整数 q,表示有 q 辆货车需要运货。 接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货 物到 y 城市,注意:x 不等于 y。 【输出】 输出文件名为 truck.out。 输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到 达目的地,输出-1。 【输入输出样例】

【数据说明】 对于 30%的数据,0 < < 1,000,0 < < 10,000,0 < < 1,000; 对于 60%的数据,0 < < 1,000,0 < < 50,000,0 < < 1,000; 对于 100%的数据, 0 < < 10,000,0 < < 50,000,0 < < 30,000, 0 ≤ z ≤ 100,000。

提高组 Day2
一. 题目概况

53

2006~2014 年 NOIP 复赛试题集(提高组) 二.提交源程序文件名

三.编译命令(不包括任何优化开关)

注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置:CPU AMD Athlon(tm)64x2 Dual Core CPU 5200+,2.7GHz, 内存 2G,上述时限以此配置为准。 4、只提供 Linux 格式附加样例文件。 5、特别提醒:评测在 NOI Linux 下进行。

1.积木大赛(block.cpp/c/pas)
【题目描述】春春幼儿园举办了一年一度的“积木大赛” 。今年比赛的内容是搭建一座宽度为的大 厦,大厦可以看成由块宽度为 1 的积木组成,第块积木的最终高度需要是 ? 。 在搭建开始之前,没有任何积木(可以看成块高度为 0 的积木) 。接下来每次操作,小朋友们 可以选择一段连续区间[, ],然后将第块到第块之间(含第 L 块和第 R 块)所有积木的高度 分别增加 1。 小是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。 但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。 【输入】 输入文件为 block.in 输入包含两行,第一行包含一个整数,表示大厦的宽度。 第二行包含个整数,第个整数为 ? 。 【输出】 输出文件为 block.out 仅一行,即建造所需的最少操作数。 【输入输出样例】

54

2006~2014 年 NOIP 复赛试题集(提高组)

【样例解释】 其中一种可行的最佳方案,依次选择 [1,5] [1,3] [2,3] [3,3] [5,5] 【数据范围】 对于 30%的数据,有 1 ≤ ≤ 10; 对于 70%的数据,有 1 ≤ ≤ 1000; 对于 100%的数据,有 1 ≤ ≤ 100000,0 ≤ ?≤ 10000。

2.花匠(flower.cpp/c/pas)
【问题描述】 花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排 中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排 列得比较别致。 具体而言,栋栋的花的高度可以看成一列整数 ?1, ?2, … , ?。设当一部分花被移走后,剩下的 花的高度依次为1, 2, … , ,则栋栋希望下面两个条件中至少有一个满足: 条件 A:对于所有的,2> 2?1,且2> 2+1; 条件 B:对于所有的,2< 2?1,且2< 2+1。 注意上面两个条件在 = 1 时同时满足,当 > 1 时最多有一个能满足。 请问,栋栋最多能将多少株花留在原地。 【输入】 输入文件为 flower .in。 输入的第一行包含一个整数,表示开始时花的株数。 第二行包含个整数,依次为 ?1, ?2, … , ?,表示每株花的高度。 【输出】 输出文件为 flower .out。 输出一行,包含一个整数,表示最多能留在原地的花的株数。 【输入输出样例】

【输入输出样例说明】 有多种方法可以正好保留 3 株花,例如,留下第 1、4、5 株,高度分别为 5、1、2,满足条 件 B。 【数据范围】 对于 20%的数据, ≤ 10;
55

2006~2014 年 NOIP 复赛试题集(提高组) 对于 30%的数据, ≤ 25; 对于 70%的数据, ≤ 1000,0 ≤ ?≤ 1000; 对于 100%的数据,1 ≤ ≤ 100,000,0 ≤ ?≤ 1,000,000,所有的 ? 随机生成,所有随机 数服从某区间内的均匀分布。

3.华容道(puzzle.cpp/c/pas)
【问题描述】 小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完 成华容道:给定一种局面, 华容道是否根本就无法完成,如果能完成, 最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的: 1. 在一个 n*m 棋盘上有 n*m 个格子, 其中有且只有一个格子是空白的, 其余 n*m-1 个格子 上每个格子上有一个棋子,每个棋子的大小都是 1*1 的; 2. 有些棋子是固定的,有些棋子则是可以移动的; 3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏的 目的是把某个指定位置可以活动的棋子移动到目标位置。 给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的, 但是棋盘上空 白的格子的初始位置、 指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候, 空白的格子在第 EXi 行第 EYi 列,指定的可移动棋子的初始位置为第 SXi 行第 SYi 列,目标位 置为第 TXi 行第 TYi 列。 假设小 B 每秒钟能进行一次移动棋子的操作, 而其他操作的时间都可以忽略不计。 请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。 【输入】 输入文件为 puzzle.in。 第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n、m 和 q; 接下来的 n 行描述一个 n*m 的棋盘,每行有 m 个整数,每两个整数之间用一个空格隔开, 每个整数描述棋盘上一个格子的状态,0 表示该格子上的棋子是固定的,1 表示该格子上的棋子可 以移动或者该格子是空白的。 接下来的 q 行,每行包含 6 个整数依次是 EXi、EYi、SXi、SYi、TXi、TYi,每两个整数之 间用一个空格隔开,表示每次游戏空白格子的位置,指定棋子的初始位置和目标位置。 【输出】 输出文件名为 puzzle.out。 输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间,如果某次游戏无法完成 目标则输出?1。 【输入输出样例】

56

2006~2014 年 NOIP 复赛试题集(提高组)

【输入输出样例说明】 棋盘上划叉的格子是固定的,红色格子是目标位置,圆圈表示棋子,其中绿色圆圈表示目标棋 子。 1. 第一次游戏,空白格子的初始位置是 (3, 2)(图中空白所示) ,游戏的目标是将初始位置 在(1, 2)上的棋子(图中绿色圆圈所代表的棋子)移动到目标位置(2, 2)(图中红色的格子)上。 移动过程如下:

2. 第二次游戏,空白格子的初始位置是(1, 2) (图中空白所示) ,游戏的目标是将初始位置在 (2, 2)上的棋子(图中绿色圆圈所示)移动到目标位置 (3, 2)上。

要将指定块移入目标位置,必须先将空白块移入目标位置,空白块要移动到目标位置,必然是 从位置(2, 2)上与当前图中目标位置上的棋子交换位置,之后能与空白块交换位置的只有当前图 中目标位置上的那个棋子,因此目标棋子永远无法走到它的目标位置, 游戏无法完成。 【数据范围】 对于 30%的数据,1 ≤ n, m ≤ 10,q = 1; 对于 60%的数据,1 ≤ n, m ≤ 30,q ≤ 10; 对于 100%的数据,1 ≤ n, m ≤ 30,q ≤ 500。

57

2006~2014 年 NOIP 复赛试题集(提高组)

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛

提高组 day1
(请选手务必仔细阅读本页内容)
一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限 二.?交源程序文件名 对于 C++语言 对于 C 语言 对于 pascal 语言 rps.cpp rps.c rps.pas link.cpp link.c link.pas bird.cpp bird.c bird.pas 生活大爆炸版石头剪刀布 rps rps rps.in rps.out 1秒 10 10 有 联合权值 link link link.in link.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 128M 传统 128M 传统 128M 飞扬的小鸟 bird bird bird.in bird.out 1秒 20 5 有

三.编译命令(不包含任何优化开关) 对于 C++语言 对于 C 语言 对于 pascal 语言 g++ -o rps rps.cpp –lm gcc -o rps rps.c –lm fpc rps.pas g++ -o link link.cpp –lm gcc -o link link.c –lm fpc link.pas g++ -o bird bird.cpp –lm gcc -o bird bird.c –lm fpc bird.pas

注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+,2.71GHz, 内存 2G,上述时限以此配置为准。 4、只?供 Linux 格式附加样例文件。 5、特别提醒 :评测在当前最新公布的 NOI Linux 下进行,各语言的编译器版本以其为准。

58

2006~2014 年 NOIP 复赛试题集(提高组)

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 表示“斯波克” 。数与 数之间以一个空格分隔。 【输出】
59

2006~2014 年 NOIP 复赛试题集(提高组) 输出文件名为 rps.out。 输出一行, 包含两个整数,以一个空格分隔,分别表示小 A、小 B 的得分。 【输入输出样例 1】 rps.in 10 5 6 0 1 2 3 4 0 3 4 2 1 0 【输入输出样例 2】 rps.in 9 5 5 0 1 2 3 4 1 0 3 2 4 4 4 rps.out 6 2 rps.out

【数据说明】 对于 100%的数据,0 < N ≤ 200,0 < NA ≤

200,

0 < NB ≤

200。

2.联合权值 (link.cpp/c/pas)
【问题描述】 无向连通图 G 有 n 个点,n-1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi ,每条 边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v), 若它们的距离为 2,则它们之间会产生 Wu×Wv 的联合权值。 请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是 多少? 【输入】 输入文件名为 link.in。 第一行包含 1 个整数 n。 接下来 n-1 行,每行包含 2 个用空格隔开的正整数 u、v,表示编号为 u 和编号为 v 的点之间有 边相连。 最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图 G 上 编号为 i 的点的权值为 Wi。 【输出】 输出文件名为 link.out。 输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和所有联 合权值之和。由于所有联合权值之和可能很大,输出它时要对 10007 取余。
60

2006~2014 年 NOIP 复赛试题集(提高组)

【输入输出样例】 link.in 5 1 2 3 4 1 20 74 2 3 4 5 5 2 3 10 link.out

【样例说明】

本例输入的图如上所示,距离为 2 的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。 其联合权值分别为 2、15、2、20、15、20。其中最大的是 20,总和为 74。 【数据说明】 对于 30%的数据,1<≤100; 对于 60%的数据,1<≤2000; 对于 100%的数据,1<≤200,000,0<Wi ≤10,000。

3. 飞扬的小鸟
61

2006~2014 年 NOIP 复赛试题集(提高组)

(bird.cpp/c/pas)
【问题描述】 Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需 要 不 断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟 顺 利 通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或 者 掉 在地上的话,便宣告失败。 为了简化问题,我们对游戏规则进行了简化和改编: 1. 游戏界面是一个长为 n,高 为 m 的二维平面,其中 有 k 个管道(忽略管道的宽度) 。 2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左 边任意整数高度位置出发, 到达游戏界面最右边时, 游戏完成。 3. 小鸟每个单位时间沿横坐标方向右移的距离为 1,竖直移动的距离由玩家控制。如果点击 屏幕,小鸟就会上升一定高度 X,每个单位时间可以点击多次,效果叠加;如果不点击屏 幕,小鸟就会下降一定高度 Y。小鸟位于横坐标方向不同位置时,上升的高度 X 和下降的 高度 Y 可能互不相同。 4. 小鸟高度等于 0 或者小鸟碰到管道时,游 戏 失 败 。小 鸟 高 度 为 m 时,无法再上升。 现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟 最多可以通过多少个管道缝隙。 【输入】 输入文件名为 bird.in。 第 1 行有 3 个整数 n,m,k,分别表示游戏界面的长度,高度和水管的数量,每两个整数之间 用一个空格隔开; 接下来的 n 行,每行 2 个用一个空格隔开的整数 X 和 Y,依次表示在横坐标位置 0~n-1 上玩家 点击屏幕后,小鸟在下一位置上升的高度 X,以及在这个位置上玩家不点击屏幕时,小鸟在下一位 置下降的高度 Y。 接下来 k 行,每行 3 个整数 P,L,H,每两个整数之间用一个空格隔开。每行表示一个管道, 其中 P 表示管道的横坐标,L 表示此管道缝隙的下边沿高度为 L,H 表示管道缝隙上边沿的高度(输 入数据保证 P 各不相同,但不保证按照大小顺序给出) 。 【输出】 输出文件名为 bird.out。 共两行。 第一行,包含一个整数,如果可以成功完成游戏,则输出 1,否则输出 0。 第二行,包含一个整数,如果第一行为 1,则输出成功完成游戏需要最少点击屏幕数,否则, 输出小鸟最多可以通过多少个管道缝隙。 【输入输出样例 1】 bird.in bird.out

62

2006~2014 年 NOIP 复赛试题集(提高组) 10 10 6 3 9 9 9 1 2 1 3 1 2 1 1 2 1 2 1 1 6 2 2 1 2 7 5 1 5 6 3 5 7 5 8 8 7 9 9 1 3 1 6

【输入输出样例 2】 bird.in 10 10 4 1 2 3 1 2 2 1 8 1 8 3 2 2 1 2 1 2 2 1 2 1 0 2 6 7 9 9 1 4 3 8 10 0 3 bird.out

【输入输出样例说明】 如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。

63

2006~2014 年 NOIP 复赛试题集(提高组)

【数据范围】 对于 30%的数据:5≤n≤10,5≤m≤10,k=0,保证存在一组最优解使得同一单位时间最多点击 屏幕 3 次; 对于 50%的数据:5≤n≤20,5≤m≤10,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次; 对于 70%的数据:5≤n≤1000,5≤m≤100; 对于 100%的数据:5≤n≤10000,5≤m≤1000,0≤k<n,0<X<m,0<Y<m,0<P<n,0≤L<H ≤m, L+1<H。

64


NOIP历年复赛提高组试题(2006-2014)

NOIP历年复赛提高组试题(2006-2014)_学科竞赛_高中教育_教育专区。NOIP历年复赛提高组试题(2006-2014) 2006~2014 年 NOIP 复赛试题集(提高组) 第十二届全国信息...

NOIP历年复赛提高组试题(2004-2013)

?。 9 2004~2013 年 NOIP 复赛试题集(提高组) 第十二届全国信息学奥林匹克分区联赛(NOIP2006)复赛试题(提高组 竞赛用时:3 小时) 关于竞赛中不同语言使用限制...

NOIP2014提高组复赛试题

NOIP2014提高组复赛试题_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文...

NOIP2014提高组复赛试题

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...

历届noip提高组复赛试题

历届noip提高组复赛试题_学科竞赛_高中教育_教育专区。NOI’95 “同创杯”全国...2005 年 第十二届全国青少年信息学奥林匹克 联赛复赛试题(NOIP2006 普及组) ...

NOIP历年复赛提高组试题

‘。 ?程老师电脑培训 35 青少年信息学(计算机)奥林匹克竞赛 第十二届全国信息学奥林匹克分区联赛(NOIP2006)复赛试题(提高组 竞赛用时:3 小时) 1.能量项链(...

NOIP2014提高组复赛试题(C语言版)

NOIP2014提高组复赛试题(C语言版)_其它课程_高中教育_教育专区。NOIP2014提高组复赛试题 C语言CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务...

NOIP2006提高组试卷

第十二届全国青少年信息学奥林匹克 联赛复赛试题(NOIP2006 提高组) 竞赛时间:2006 年 11 月 18 日上午 8:30—11:30 试题名称 目录 输入文件 名 输出文件 名...

所有noip提高组复赛试题

所有noip提高组复赛试题_IT认证_资格考试/认证_教育...联赛复赛试题(NOIP2006 普及组) 竞赛时间:2006 年 ...历届noip提高组复赛试题 56页 免费 NOIP+提高组复赛...

NOIP2014复赛提高组模拟试题

NOIP2014复赛提高组模拟试题_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克...2015国考行测模拟试题历年真题 2015国考申论押密试卷及答案 2015国考面试通关...