当前位置:首页 >> 学科竞赛 >> NOIP2001-2011提高组复赛试题合集

NOIP2001-2011提高组复赛试题合集


2001 年全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (高中组 竞赛用时:3 小时) 题一 一元三次方程求解(20 分)

问题描述 有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实 数),并约定该方程存在三个不同实根(根的范围在-100 至 100 之间),且根与根之差的绝对值>=1

。要求 由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后 2 位。 提示:记方程 f(x)=0,若存在 2 个数 x1 和 x2,且 x1<x2,f(x1)*(x2)<0,则在(x1,x2)之间一定有一个 根。 样例 输入:1 -5 -4 输出:-2.00 2.00

20 5.00

题二 数的划分(20 分) 问题描述 将整数 n 分成 k 份,且每份不能为空,任意两份不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入:n,k (6<n<=200,2<=k<=6) 输出:一个整数,即不同的分法。 样例 输入: 7 3 输出:4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

题三 统计单词个数(30 分) 问题描述 给出一个长度不超过 200 的由小写英文字母组成的字母串(约定;该字串以每行 20 个字母的方式输入,且 保证每行一定为 20 个)。要求将此字母串分成 k 份(1<k<=40),且每份中包含的单词个数加起来总数最大 (每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串 this 中 可包含 this 和 is,选用 this 之后就不能包含 th)。 单词在给出的一个不超过 6 个单词的字典中。 要求输出最大的个数。 输入格式 去部输入数据放在文本文件 input3.dat 中,其格式如下: 第一行为一个正整数(0<n<=5)表示有 n 组测试数据 每组的第一行有二个正整数(p,k) p 表示字串的行数; k 表示分为 k 个部分。 接下来的 p 行,每行均有 20 个字符。

再接下来有一个正整数 s,表示字典中单词个数。(1<=s<=6) 接下来的 s 行,每行均有一个单词。 输出格式 结果输出至屏幕,每行一个整数,分别对应每组测试数据的相应结果。 样例 输入: 1 1 3 thisisabookyouareaoh 4 is a ok sab 输出: //说明:(不必输出) 7 // this/isabookyoua/reaoh

题四 Car 的旅行路线(30 分) 问题描述 又到暑假了,住在城市 A 的 Car 想和朋友一起去城市 B 旅游。她知道每个城市都有四个飞机场,分别位 于一个矩形的四个顶点上,同一个城市中两个机场之间有一条笔直的高速铁路,第 I 个城市中高速铁路 了的单位里程价格为 Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为 t。

那么 Car 应如何安排到城市 B 的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她 来向你请教。 任务 找出一条从城市 A 到 B 的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。 输入文件:键盘输入文件名 输 出:到屏幕(输出最小费用,小数点后保留 1 位。) 输入格式 第一行为一个正整数 n(0<=n<=10),表示有 n 组测试数据。 每组的第一行有四个正整数 s,t,A,B。 S(0<S<=100)表示城市的个数,t 表示飞机单位里程的价格,A,B 分别为城市 A,B 的序号,(1<=A,

B<=S)。 接下来有 S 行,其中第 I 行均有 7 个正整数 xi1,yi1,xi2,yi2,xi3,yi3,Ti,这当中的(xi1, yi1),(xi2,yi2),(xi3,yi3)分别是第 I 个城市中任意三个机场的坐标,T I 为第 I 个城市高速铁路单 位里程的价格。 输出格式 共有 n 行,每行一个数据对应测试数据。 样例 输入 1 1 10 1 3 1 1 1 3 3 1 30 2 5 7 4 5 2 1 8 6 8 8 11 6 3 输出: 47.55

信息学初学者之家 http://www.ioiforum.org/oibh/

2002 年全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (提高组 竞赛用时:3 小时)

题一 均分纸牌(存盘名 NOIPG1) [问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可 以在任一堆上取若于张纸牌,然后移动。 移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上 取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4,4 堆纸牌数分别为: ① 9 ② 8 ③ 17 ④ 6 移动 3 次可达到目的: 从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10)。 [输 入]: 键盘输入文件名。文件格式: N(N 堆纸牌,1 <= N <= 100) A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输 出]: 输出至屏幕。格式为: 所有堆均达到相等时的最少移动次数。‘ [输入输出样例] a.in: 4 9 8 17 6 屏慕显示: 3
题二 字串变换 (存盘名: NOIPG2) [问题描述]: 已知有两个字串 A$, B$ 及一组字串变换的规则(至多 6 个规则): A1$ -> B1$ A2$ -> B2$ 规则的含义为:在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。 例如:A$='abcd' B$='xyz' 变换规则为: ‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 则此时,A$ 可以经过一系列的变换变为 B$,其变换的过程为:

‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换,使得 A$ 变换为 B$。 [输入]: 键盘输人文件名。文件格式如下: A$ B$ A1$ B1$ \ A2$ B2$ |-> 变换规则 ... ... / 所有字符串长度的上限为 20。 [输出]: 输出至屏幕。格式如下: 若在 10 步(包含 10 步)以内能将 A$ 变换为 B$ ,则输出最少的变换步数;否则输出"NO ANSWER!" [输入输出样例] b.in: abcd wyz abc xu ud y y yz 屏幕显示: 3

题三 自由落体(存盘名:NOIPG3) [问题描述]: 在高为 H 的天花板上有 n 个小球,体积不计,位置分别为 0,1,2,….n-1。在地面上有一个小车(长为 L, 高为 K,距原点距离为 S1)。已知小球下落距离计算公式为 d=1/2*g*(t^2),其中 g=10,t 为下落时间。地面上 的小车以速度 V 前进。 如下图:

小车与所有小球同时开始运动,当小球距小车的距离 <= 0.00001 时,即认为小球被小车接受(小球落到地面 后不能被接受)。 请你计算出小车能接受到多少个小球。 [输入]: 键盘输人: H,S1,V,L,K,n (l<=H,S1,V,L,K,n <=100000) [输出]: 屏幕输出: 小车能接受到的小球个数。 [输入输出样例] [输入]: 5.0 9.0 5.0 2.5 1.8 5 [输出]: 1 题四 矩形覆盖(存盘名 NOIPG4) [问题描述]: 在平面上有 n 个点(n <= 50),每个点用一对整数坐标表示。例如:当 n=4 时,4 个点的坐标分另为:p1 (1,1),p2(2,2),p3(3,6),P4(0,7),见图一。

这些点可以用 k 个矩形 (1<=k<=4) 全部覆盖, 矩形的边平行于坐标轴。 当 k=2 时, 可用如图二的两个矩形 sl, s2 覆盖,s1,s2 面积和为 4。问题是当 n 个点坐标和 k 给出后,怎样才能使得覆盖所有点的 k 个矩形的面积之 和为最小呢。约定:覆盖一个点的矩形面积为 0;覆盖平行于坐标轴直线上点的矩形面积也为 0。各个矩形必须完全 分开(边线与顶点也都不能重合)。 [输入]: 键盘输人文件名。文件格式为 n k xl y1 x2 y2 ... ... xn yn (0<=xi,yi<=500) [输出]: 输出至屏幕。格式为: 一个整数,即满足条件的最小的矩形面积之和。 [输入输出样例] d.in : 4 2 1 1 2 2 3 6 0 7 屏幕显示: 4 信息学初学者之家

?

第九届全国青少年信息学奥林匹克联赛(N0IP2003)
2003 年 11 月 29 日 提高组试题 三小时完成

题一

神经网络

【问题背景】 人工神经网络(Artificial Neural Network)是一种新兴的具有自我学习能力的计算 系统,在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究 一直是当今的热门方向, 兰兰同学在自学了一本神经网络的入门书籍后, 提出了一个简化模 型,他希望你能帮助他用程序检验这个神经网络模型的实用性。 【问题描述】 在兰兰的模型中,神经网络就是一张有向图,图中的节点称为神经元,而且两个神经 元之间至多有一条边相连,下图是一个神经元的例子:

神经元〔编号为 1) 图中,X1—X3 是信息输入渠道,Y1-Y2 是信息输出渠道,C1 表示神经元目前的状态, Ui 是阈值,可视为神经元的一个内在参数。 神经元按一定的顺序排列,构成整个神经网络。在兰兰的模型之中,神经网络中的神 经无分为几层;称为输入层、输出层,和若干个中间层。每层神经元只向下一层的神经元 输出信息,只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定,Ci 服从公式: (其中 n 是网络中所有神经元的数目)

Ci ?

( j,i )?E

?W C
ji

j

? Ui

公式中的 Wji(可能为负值)表示连接 j 号神经元和 i 号神经元的边的权值。当 Ci 大 于 0 时,该神经元处于兴奋状态,否则就处于平静状态。当神经元处于兴奋状态时,下一秒

它会向其他神经元传送信号,信号的强度为 Ci。 如此.在输入层神经元被激发之后,整个网络系统就在信息传输的推动下进行运作。 现在,给定一个神经网络,及当前输入层神经元的状态(Ci) ,要求你的程序运算出最后网 络输出层的状态。 【输入格式】 输入文件第一行是两个整数 n(1≤n≤20)和 p。接下来 n 行,每行两个整数,第 i+1 行是神经元 i 最初状态和其阈值(Ui) ,非输入层的神经元开始时状态必然为 0。再下面 P 行,每行由两个整数 i,j 及一个整数 Wij,表示连接神经元 i、j 的边权值为 Wij。 【输出格式】 输出文件包含若干行,每行有两个整数,分别对应一个神经元的编号,及其最后的状 态,两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态,并且按照编号由 小到大顺序输出! 若输出层的神经元最后状态均为 0,则输出 NULL。 【输入样例】 5 6 1 0 1 0 0 1 0 1 0 1 1 3 1 1 4 1 1 5 1 2 3 1 2 4 1 2 5 1 【输出样例】 3 1 4 1 5 1

题二

侦探推理

【问题描述】 明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学 玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明 明不知情的情况下) ,明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被 询问者可能会说:

证词中出现的其他话,都不列入逻辑推理的内容。 明明所知道的是,他的同学中有 N 个人始终说假话,其余的人始终说真。 现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一 个! 【输入格式】 输入由若干行组成, 第一行有二个整数, M (1≤M≤20) 、 N (1≤N≤M) 和P (1≤P≤100) ; M 是参加游戏的明明的同学数,N 是其中始终说谎的人数,P 是证言的总数。接下来 M 行, 每行是明明的一个同学的名字(英文字母组成,没有主格,全部大写) 。 往后有 P 行,每行开始是某个同学的名宇,紧跟着一个冒号和一个空格,后面是一句证 词,符合前表中所列格式。证词每行不会超过 250 个字符。 输入中不会出现连续的两个空格,而且每行开头和结尾也没有空格。 【输出格式】 如果你的程序能确定谁是罪犯,则输出他的名字;如果程序判断出不止一个人可能是 罪 犯 , 则 输 出 Cannot Determine ; 如 果 程 序 判 断 出 没 有 人 可 能 成 为 罪 犯 , 则 输 出 Impossible。 【输入样例】 3 1 5 MIKE CHARLES KATE MIKE:I am guilty. MIKE:Today is Sunday. CHARLES:MIKE is guilty. KATE:I am guilty. KATE:How are you?? 【输出样例】 MIKE

题三

加分二叉树

【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n) ,其中数字 1,2,3,…,n 为 节点编号。每个节点都有一个分数(均为正整数) ,记第 j 个节点的分数为 dj,tree 及它的

每个子树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下: subtree 的左子树的加分× subtree 的右子树的加分+subtree 的根的分数 若某个子树为空,规定其加分为 1,叶子的加分就是叶节点本身的分数。不考虑它的空 子树。 试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树 tree。要求输出; (1)tree 的最高加分 (2)tree 的前序遍历 【输入格式】 第 1 行:一个整数 n(n<30) ,为节点个数。 第 2 行:n 个用空格隔开的整数,为每个节点的分数(分数<100) 。 【输出格式】 第 1 行:一个整数,为最高加分(结果不会超过 4,000,000,000) 。 第 2 行:n 个用空格隔开的整数,为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 3 1 2 4 5

题四

传染病控制

【问题背景】 近来,一种新的传染病肆虐全球。蓬莱国也发现了零星感染者,为防止该病在蓬莱国 大范围流行,该国政府决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完 全认识这种传染病,难以准确判别病毒携带者,更没有研制出疫苗以保护易感人群。于是, 蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO(世界卫 生组织)以及全球各国科研部门的努力,这种新兴传染病的传播途径和控制方法已经研究 消楚,剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。 【问题描述】 研究表明,这种传染病的传播具有两种很特殊的性质; 第一是它的传播途径是树型的,一个人 X 只可能被某个特定的人 Y 感染,只要 Y 不 得病,或者是 XY 之间的传播途径被切断,则 X 就不会得病。 第二是,这种疾病的传播有周期性,在一个疾病传播周期之内,传染病将只会感染一 代患者,而不会再传播给下一代。 这些性质大大减轻了蓬莱国疾病防控的压力,并且他们已经得到了国内部分易感人群 的潜在传播途径图(一棵树) 。但是,麻烦还没有结束。由于蓬莱国疾控中心人手不够,同 时也缺乏强大的技术,以致他们在一个疾病传播周期内,只能设法切断一条传播途径,而

没有被控制的传播途径就会引起更多的易感人群被感染(也就是与当前已经被感染的人有 传播途径相连,且连接途径没有被切断的人群) 。当不可能有健康人被感染时,疾病就中止 传播。所以,蓬莱国疾控中心要制定出一个切断传播途径的顺序,以使尽量少的人被感染。 你的程序要针对给定的树,找出合适的切断顺序。 【输入格式】 输入格式的第一行是两个整数 n(1≤n≤300)和 p。接下来 p 行,每一行有两个整数 i 和 j,表示节点 i 和 j 间有边相连(意即,第 i 人和第 j 人之间有传播途径相连) 。其中节 点 1 是已经被感染的患者。 【输出格式】 只有一行,输出总共被感染的人数。 【输入样例】 7 6 1 2 1 3 2 4 2 5 3 6 3 7 【输出样例】 3

第十届全国青少年信息学奥林匹克联赛复赛试题
( 提高组 三小时完成 )
(3 小时完成,对于每个测试点时限均为 1 秒,机器配置:PⅣ2.8/512MB)

津津的储蓄计划
(save.pas/dpr/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 280 200 300 170 330 50 90 80 200 60 【样例输出 2】 1580

合并果子
(fruit.pas/dpr/c/cpp)
【问题描述】 在一个果园里, 多多已经将所有的果子打了下来, 而且按果子的不同种类分成了不同的 堆。多多决定把所有的果子合成一堆。 每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。 可以看出,所有的果子经过 n-1 次合并之后,就只剩下一堆了。多多在合并果子时总共消耗 的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家, 所以多多在合并果子时要尽可能地节省体力。 假 定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并 的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。 例如有 3 种果子,数目依次为 1,2,9。可以先将 1、2 堆合并,新堆数目为 3,耗费 体力为 3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。 所以多多总共耗费体力=3+12=15。可以证明 15 为最小的体力耗费值。 【输入文件】 输入文件 fruit.in 包括两行,第一行是一个整数 n(1 <= n <= 10000) ,表示果子的种类 数。第二行包含 n 个整数,用空格分隔,第 i 个整数 ai(1 <= ai <= 20000)是第 i 种果子的 数目。 【输出文件】 输出文件 fruit.out 包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输 入数据保证这个值小于 231。 【样例输入】 3 129 【样例输出】 15 【数据规模】 对于 30%的数据,保证有 n <= 1000; 对于 50%的数据,保证有 n <= 5000; 对于全部的数据,保证有 n <= 10000。

合唱队形
(chorus.pas/dpr/c/cpp)
【问题描述】 N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的 K 位同学排成 合唱队形。 合唱队形是指这样的一种队形:设 K 位同学从左到右依次编号为 1, 2, …, K,他们的身 高分别为 T1, T2, …, TK, 则他们的身高满足 T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是,已知所有 N 位同学的身高,计算最少需要几位同学出列,可以使得剩下 的同学排成合唱队形。 【输入文件】 输入文件 chorus.in 的第一行是一个整数 N(2 <= N <= 100) ,表示同学的总数。第一行 有 n 个整数,用空格分隔,第 i 个整数 Ti(130 <= Ti <= 230)是第 i 位同学的身高(厘米) 。 【输出文件】 输出文件 chorus.out 包括一行,这一行只包含一个整数,就是最少需要几位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 4 【数据规模】 对于 50%的数据,保证有 n <= 20; 对于全部的数据,保证有 n <= 100。

虫食算
(alpha.pas/dpr/c/cpp)
【问题描述】 所谓虫食算, 就是原先的算式中有一部分被虫子啃掉了, 需要我们根据剩下的数字来判 定被啃掉的字母。来看一个简单的例子: 43#98650#45 + 8468#6633 44445506978 其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两个数字分别 是 5 和 3,第二行的数字是 5。 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算。这里的加法是 N 进制加法,算式中三个数都有 N 位, 允许有前导的 0。 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的。我们将相同的数字用 相同的字母表示,不同的数字用不同的字母表示。如果这个算式是 N 进制的,我们就取英 文字母表中的前 N 个大写字母来表示这个算式中的 0 到 N-1 这 N 个不同的数字(但是这 N 个字母并不一定顺序地代表 0 到 N-1) 。输入数据保证 N 个字母分别至少出现一次。 BADC + CBDA DCCC 上面的算式是一个 4 进制的算式。很显然,我们只要让 ABCD 分别代表 0123,便可以 让这个式子成立了。你的任务是,对于给定的 N 进制加法算式,求出 N 个不同的字母分别 代表的数字,使得该加法算式成立。输入数据保证有且仅有一组解。 【输入文件】 输入文件 alpha.in 包含 4 行。第一行有一个正整数 N(N <= 26) ,后面的 3 行每行有一 个由大写字母组成的字符串, 分别代表两个加数以及和。 这 3 个字符串左右两端都没有空格, 从高位到低位,并且恰好有 N 位。 【输出文件】 输出文件 alpha.out 包含一行。在这一行中,应当包含唯一的那组解。解是这样表示的: 输出 N 个数字,分别表示 A,B,C……所代表的数字,相邻两数之间只能用一个空格隔开, 不能用两个、三个或更多的空格隔开。输出的应为十进制的数。 【样例输入】 5 ABCED

BDACE EBBAA 【样例输出】 10342 【数据规模】 对于 30%的数据,保证有 N <= 10; 对于 50%的数据,保证有 N <= 15; 对于全部的数据,保证有 N <= 26。

NOIP2005 复赛试题(提高组)

第十一届全国青少年信息学奥林匹克联赛复赛试题
( 提高组 三小时完成 )

谁拿了最多奖学金
(scholar.pas/c/cpp)
【问题描述】 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种,获取的条 件各自不同: 1) 2) 3) 4) 5) 院士奖学金,每人 8000 元,期末平均成绩高于 80 分(>80) ,并且在本学期内发表 1 篇或 1 篇以上论文的学生均可获得; 五四奖学金,每人 4000 元,期末平均成绩高于 85 分(>85) ,并且班级评议成绩高 于 80 分(>80)的学生均可获得; 成绩优秀奖,每人 2000 元,期末平均成绩高于 90 分(>90)的学生均可获得; 西部奖学金,每人 1000 元,期末平均成绩高于 85 分(>85)的西部省份学生均可 获得; 班级贡献奖,每人 850 元,班级评议成绩高于 80 分(>80)的学生干部均可获得;

只要符合条件就可以得奖,每项奖学金的获奖人数没有限制,每名学生也可以同时获得 多项奖学金。例如姚林的期末平均成绩是 87 分,班级评议成绩 82 分,同时他还是一位学生 干部,那么他可以同时获得五四奖学金和班级贡献奖,奖金总数是 4850 元。 现在给出若干学生的相关数据, 请计算哪些同学获得的奖金总数最高 (假设总有同学能 满足获得奖学金的条件) 。 【输入文件】 输入文件 scholar.in 的第一行是一个整数 N(1 <= N <= 100) ,表示学生的总数。接下 来的 N 行每行是一位学生的数据,从左向右依次是姓名,期末平均成绩,班级评议成绩, 是否是学生干部,是否是西部省份学生,以及发表的论文数。姓名是由大小写英文字母组成 的长度不超过 20 的字符串 (不含空格) ; 期末平均成绩和班级评议成绩都是 0 到 100 之间的 整数(包括 0 和 100) ;是否是学生干部和是否是西部省份学生分别用一个字符表示,Y 表 示是,N 表示不是;发表的论文数是 0 到 10 的整数(包括 0 和 10) 。每两个相邻数据项之 间用一个空格分隔。 【输出文件】 输出文件 scholar.out 包括三行,第一行是获得最多奖金的学生的姓名,第二行是这名 学生获得的奖金总数。 如果有两位或两位以上的学生获得的奖金最多, 输出他们之中在输入

NOIP2005 复赛试题(提高组)
文件中出现最早的学生的姓名。第三行是这 N 个学生获得的奖学金的总数。 【样例输入】 4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 【样例输出】 ChenRuiyi 9000 28700

过河
(river.pas/c/cpp)
【问题描述】 在河上有一座独木桥, 一只青蛙想沿着独木桥从河的一侧跳到另一侧。 在桥上有一些石 子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可 以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中 L 是桥的长 度) 。坐标为 0 的点表示桥的起点,坐标为 L 的点表示桥的终点。青蛙从桥的起点开始,不 停的向终点方向跳跃。一次跳跃的距离是 S 到 T 之间的任意正整数(包括 S,T) 。当青蛙跳 到或跳过坐标为 L 的点时,就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L,青蛙跳跃的距离范围 S,T,桥上石子的位置。你的任务是确 定青蛙要想过河,最少需要踩到的石子数。 【输入文件】 输入文件 river.in 的第一行有一个正整数 L(1 <= L <= 109) ,表示独木桥的长度。第二 行有三个正整数 S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的 个数,其中 1 <= S <= T <= 10,1 <= M <= 100。第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置(数据保证桥的起点和终点处没有石子) 。所有相邻的整数之间用一 个空格隔开。 【输出文件】 输出文件 river.out 只包括一个整数,表示青蛙过河最少需要踩到的石子数。

NOIP2005 复赛试题(提高组)

【样例输入】
10 2 3 5

23567
【样例输出】

2
【数据规模】 对于 30%的数据,L <= 10000; 对于全部的数据,L <= 109。

篝火晚会
(fire.pas/c/cpp)
【问题描述】 佳佳刚进高中, 在军训的时候, 由于佳佳吃苦耐劳, 很快得到了教官的赏识, 成为了“小 教官”。在军训结束的那天晚上,佳佳被命令组织同学们进行篝火晚会。一共有 n 个同学, 编号从 1 到 n。一开始,同学们按照 1,2,……,n 的顺序坐成一圈,而实际上每个人都有 两个最希望相邻的同学。如何下命令调整同学的次序,形成新的一个圈,使之符合同学们的 意愿,成为摆在佳佳面前的一大难题。 佳佳可向同学们下达命令,每一个命令的形式如下: (b1, b2,... bm -1, bm) 这里 m 的值是由佳佳决定的,每次命令 m 的值都可以不同。这个命令的作用是移动编 号是 b1,b2,…… bm –1,bm 的这 m 个同学的位置。要求 b1 换到 b2 的位置上,b2 换到 b3 的 位置上,……,要求 bm 换到 b1 的位置上。 执行每个命令都需要一些代价。我们假定如果一个命令要移动 m 个人的位置,那么这 个命令的代价就是 m。 我们需要佳佳用最少的总代价实现同学们的意愿, 你能帮助佳佳吗? 【输入文件】 输入文件 fire.in 的第一行是一个整数 n(3 <= n <= 50000) ,表示一共有 n 个同学。其 后 n 行每行包括两个不同的正整数, 以一个空格隔开, 分别表示编号是 1 的同学最希望相邻 的两个同学的编号,编号是 2 的同学最希望相邻的两个同学的编号,……,编号是 n 的同学 最希望相邻的两个同学的编号。 【输出文件】

NOIP2005 复赛试题(提高组)

输出文件 fire.out 包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么 调整都不能符合每个同学的愿望,则输出-1。 【样例输入】 4 34 43 12 12 【样例输出】 2 【数据规模】 对于 30%的数据,n <= 1000; 对于全部的数据,n <= 50000。

等价表达式
(equal.pas/c/cpp)
【问题描述】 明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻烦的选择题。这个题 目的题干中首先给出了一个代数表达式, 然后列出了若干选项, 每个选项也是一个代数表达 式,题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。 这个题目手算很麻烦, 因为明明对计算机编程很感兴趣, 所以他想是不是可以用计算机 来解决这个问题。假设你是明明,能完成这个任务吗? 这个选择题中的每个表达式都满足下面的性质: 1. 表达式只可能包含一个变量‘a’。 2. 表达式中出现的数都是正整数,而且都小于 10000。 3. 表达式中可以包括四种运算‘+’(加) ,‘-’(减) ,‘*’(乘) ,‘^’(乘幂) ,以及小括 号‘(’,‘)’。小括号的优先级最高,其次是‘^’,然后是‘*’,最后是‘+’和‘-’。‘+’和‘-’ 的优先级是相同的。相同优先级的运算从左到右进行。 (注意:运算符‘+’,‘-’,‘*’, ‘^’以及小括号‘(’,‘)’都是英文字符) 4. 幂指数只可能是 1 到 10 之间的正整数(包括 1 和 10) 。 5. 表达式内部,头部或者尾部都可能有一些多余的空格。

NOIP2005 复赛试题(提高组)
下面是一些合理的表达式的例子: ((a^1) ^ 2)^3,a*a+a-a,((a+a)),9999+(a-a)*a,1 + (a -1)^3,1^10^9…… 【输入文件】 输入文件 equal.in 的第一行给出的是题干中的表达式。第二行是一个整数 n(2 <= n <= 26) ,表示选项的个数。后面 n 行,每行包括一个选项中的表达式。这 n 个选项的标号分别 是 A,B,C,D…… 输入中的表达式的长度都不超过 50 个字符,而且保证选项中总有表达式和题干中的表 达式是等价的。 【输出文件】 输出文件 equal.out 包括一行,这一行包括一系列选项的标号,表示哪些选项是和题干 中的表达式等价的。选项的标号按照字母顺序排列,而且之间没有空格。 【样例输入】 ( a + 1) ^2 3 (a-1)^2+4*a a + 1+ a a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a 【样例输出】 AC 【数据规模】 对于 30%的数据,表达式中只可能出现两种运算符‘+’和‘-’; 对于其它的数据,四种运算符‘+’,‘-’,‘*’,‘^’在表达式中都可能出现。 对于全部的数据,表达式中都可能出现小括号‘(’和‘)’。

NOIP 2006 复赛试题 (提高组)

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

试题名称 目录 输入文件名 输出文件名 试题类型 附加文件 时限

energy energy energy.in energy.out 非交互式程序题 无 1秒

budget budget budget.in budget.out 非交互式程序题 无 1秒

jsp jsp jsp.in jsp.out 非交互式程序题 无 1秒

digital digital digital.in digital.out 非交互式程序题 无 1秒

关于竞赛中不同语言使用限制的说明
一.关于使用 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 >

?

中国计算机学会,2006

1

NOIP 2006 复赛试题 (提高组)

1.能量项链
(energy.pas/c/cpp) 【问题描述】 在 Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠 是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一 颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是 Mars 人吸收能 量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如 果前一颗能量珠的头标记为 m,尾标记为 r,后一颗能量珠的头标记为 r,尾标记为 n,则聚合后 ,新产生的珠子的头标记为 m,尾标记为 n。 释放的能量为 m ? r ? n (Mars 单位) 需要时,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<N 时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N 颗珠子的尾标 记应该等于第 1 颗珠子的头标记。 至于珠子的顺序, 你可以这样确定: 将项链放到桌面上, 不要出现交叉, 随意指定第一颗珠子, 然后按顺时针方向确定其他珠子的顺序。 【输出文件】 ,为一个最优聚合顺序所 输出文件 energy.out 只有一行,是一个正整数 E(E≤2.1*109) 释放的总能量。 【输入样例】 4 2 3 5 10 【输出样例】 710

?

中国计算机学会,2006

2

NOIP 2006 复赛试题 (提高组)

2.金明的预算方案
(budget.pas/c/cpp) 【问题描述】 金明今天很开心, 家里购置的新房就要领钥匙了, 新房里有一间金明自己专用的很宽敞的房间。 更让他高兴的是,妈妈昨天对他说: “你的房间需要购买哪些物品,怎么布置,你说了算,只要不 超过 N 元钱就行” 。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附 件是从属于某个主件的,下表就是一些主件与附件的例子: 主件 电脑 书柜 书桌 工作椅 附件 打印机,扫描仪 图书 台灯,文具 无

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。 附件不再有从属于自己的附件。 金明想买的东西很多, 肯定会超过妈妈限定的 N 元。 于是, 他把每件物品规定了一个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从因特网上 查到了每件物品的价格(都是 10 元的整数倍) 。他希望在不超过 N 元(可以等于 N 元)的前提下, 使每件物品的价格与重要度的乘积的总和最大。 j2, ……, 设第 j 件物品的价格为 v[j], 重要度为 w[j], 共选中了 k 件物品, 编号依次为 j1, 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

?

中国计算机学会,2006

3

NOIP 2006 复赛试题 (提高组) 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 工序 2 1 1/3 2/2 2 3 1/2 2/2 2/5 1/4

则对于安排顺序“1 1 2 3 3 2” ,下图中的两个实施方案都是正确的。但所需要的总时间分别是 10 与 12。

?

中国计算机学会,2006

4

NOIP 2006 复赛试题 (提高组)

当一个操作插入到某台机器的某个空档时 (机器上最后的尚未安排操作的部分也可以看作一个 空档) ,可以靠前插入,也可以靠后或居中插入。为了使问题简单一些,我们约定:在保证约束条 件(1) (2)的条件下,尽量靠前插入。并且,我们还约定,如果有多个空档可以插入,就在保证 约束条件(1) (2)的条件下,插入到最前面的一个空档。于是,在这些约定下,上例中的方案一 是正确的,而方案二是不正确的。 显然,在这些约定下,对于给定的安排顺序,符合该安排顺序的实施方案是唯一的,请你计算 出该方案完成全部任务所需的总时间。 【输入文件】 输入文件 jsp.in 的第 1 行为两个正整数,用一个空格隔开: m n (其中 m(<20)表示机器数,n(<20)表示工件数) 第 2 行: m ? n 个用空格隔开的数,为给定的安排顺序。 接下来的 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

?

中国计算机学会,2006

5

NOIP 2006 复赛试题 (提高组)

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)是事先给定的。 问:满足上述条件的不同的 r 共有多少个? 我们再从另一角度作些解释:设 S 是长度为 w 的 01 字符串(即字符串 S 由 w 个“0”或“1” 组成) ,S 对应于上述条件(3)中的 q。将 S 从右起划分为若干个长度为 k 的段,每段对应一位 k 2 进制的数,如果 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

?

中国计算机学会,2006

6

NOIP2007 复赛试题(提高组)

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

提高组
题目一览 题目名称 代号 输入文件 输出文件 时限 统计数字 count count.in count.out 1秒 字符串的展开 expand expand.in expand.out 1秒 矩阵取数游戏 game game.in game.out 1秒 树网的核 core core.in core.out 1秒

(2007 年 11 月 17 日 3 小时完成)

说明: 1. 2. 3. 文件名(程序名和输入输出文件名)必须使用小写 C/C++中函数 main()的返回值必须是 int, 程序正常结束时返回值必须是 0。 全国统一评测时采用的机器参考配置为:CPU 2.0GHz,内存 256M。

NOIP2007 复赛试题(提高组)

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 【限制】
40%的数据满足:1<=n<=1000 80%的数据满足:1<=n<=50000 100%的数据满足:1<=n<=200000,每个数均不超过 1500 000 000(1.5*109)

count.out 2 3 4 2 5 1 100 2

NOIP2007 复赛试题(提高组)

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 expand.out expand.out abcsttuuvvw1234556677889s-4zz

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

aCCCBBBd-d

expand.out dijkstra2************6

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。 第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开

【输出】
输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大的分。

NOIP2007 复赛试题(提高组) 【输入输出样例 1】 game.in 2 3 1 2 3 3 4 2 【输入输出样例 1 解释】
第 1 次:第一行取行首元素,第二行取行尾元素,本次的氛围 1*21+2*21=6 第 2 次:两行均取行首元素,本次得分为 2*22+3*22=20 第 3 次:得分为 3*23+4*23=56。总得分为 6+20+56=82

game.out 82

【输入输出样例 2】 game.in 1 4 4 5 0 5 【输入输出样例 3】 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,答案不超过 1016 100%的数据满足:1<=n, m<=80,0<=aij<=1000

game.out 122

game.out 316994

4. 树网的核
(core.pas/c/cpp) 【问题描述】

NOIP2007 复赛试题(提高组)
设 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 只有一个非负整数,为指定意义下的最小偏心距。

NOIP2007 复赛试题(提高组) 【输入输出样例】 【输入输出样例 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

NOIP2008 复赛试题(提高组)

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

提高组
一、题目概览
中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 比较方式 题目类型 笨小猴 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,上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。

NOIP2008 复赛试题(提高组)

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】
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 的拼法如图所 示:

NOIP2008 复赛试题(提高组)

注意: 1. 加号与等号各自需要两根火柴棍 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 【输入输出样例 1 解释】 2 个等式为 0+1=1 和 1+0=1。 matches.out 2

【输入输出样例 2】
matches.in 18 【输入输出样例 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 matches.out 9

3. 传纸条
(message.pas/c/cpp)
【问题描述】 小渊和小轩是好朋友也是同班同学, 他们在一起总有谈不完的话题。 一次素质拓展活动 中,班上同学安排做成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端, 因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许

NOIP2008 复赛试题(提高组)
多同学传到对方手里,小渊坐在矩阵的左上角,坐标(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 共一行,包含一个整数,表示来回两条路上参与传递纸条的学生 的好心程度之和的最大值。

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

4. 双栈排序
(twostack.pas/c/cpp)
【问题描述】 Tom 最近在研究一个有趣的排序问题。如图所示,通过 2 个栈 S1 和 S2,Tom 希望借助 以下 4 种操作实现将输入序列升序排序。 操作 a 如果输入序列不为空,将第一个元素压入栈 S1 操作 b 如果栈 S1 不为空,将 S1 栈顶元素弹出至输出 序列 操作 c 如果输入序列不为空,将第一个元素压入栈 S2

NOIP2008 复赛试题(提高组)
操作 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>

当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个 可行的操作序列。Tom 希望知道其中字典序最小的操作序列是什么。 【输入】 输入文件 twostack.in 的第一行是一个整数 n。 第二行有 n 个用空格隔开的正整数,构成一个 1~n 的排列。 【输出】 输出文件 twostack.out 共一行,如果输入的排列不是“可双栈排序排列” ,输出数字 0; 否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

NOIP2008 复赛试题(提高组) 【输入输出样例 1】
twostack.in 4 1324 twostack.out abaabbab

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

【输入输出样例 3】
twostack.in 3 231 【限制】 30%的数据满足: n<=10 50%的数据满足: n<=50 100%的数据满足: n<=1000 twostack.out acabbd

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

提高组

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

提高组
(请选手务必仔细阅读本页内容)
一.题目概况
中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 潜伏者 spy spy spy.in spy.out 1秒 10 10 有 全文比较 过滤行末空格 及文末回车 传统 Hankson 的趣味题 son son son.in son.out 1秒 10 10 有 全文比较 过滤行末空格及 文末回车 传统 最优贸易 trade trade trade.in trade.out 1秒 10 10 有 全文比较 过滤行末空格 及文末回车 传统 靶形数独 sudoku sudoku sudoku.in sudoku.out 2秒 20 5 有 全文比较 过滤行末空格 及文末回车 传统

题目类型

二.提交源程序文件名
对于 pascal 语言 对于 C 语言 对于 C++语言 spy.pas spy.c spy.cpp son.pas son.c son.cpp trade.pas trade.c trade.cpp sudoku.pas sudoku.c sudoku.cpp

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

四.运行内存限制
内存上限 128M 128M 128M 128M

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

第 1 页 共 7 页

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

提高组

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

第 2 页 共 7 页

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

提高组

【输入输出样例 1 说明】 原信息中的字母‘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 的个数;

第 3 页 共 7 页

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

提高组

【输入输出样例】 son.in 2 41 1 96 288 95 1 37 1776

son.out 6 2

【说明】 第一组输入数据,x 可以是 9、18、36、72、144、288,共有 6 个。 第二组输入数据,x 可以是 48、1776,共有 2 个。 【数据范围】 对于 50%的数据,保证有 1≤a0,a1,b0,b1≤10000 且 n≤100。 对于 100%的数据,保证有 1≤a0,a1,b0,b1≤2,000,000,000 且 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 号城市以 5 的价格卖出水晶球,赚取的旅费数为 2。 阿龙也可以选择如下一条线路 1->4->5->4->5,并在第 1 次到达 5 号城市时以 1 的价格 买入水晶球,在第 2 次到达 4 号城市时以 6 的价格卖出水晶球,赚取的旅费数为 5。
第 4 页 共 7 页

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

提高组

现在给出 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 5 4 1 1 2 3 4 5 3 2 4 3 5 5 5 6 1 1 1 2 1 2

trade.out 5

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

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

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

提高组

数字,利用逻辑推理,在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能 重复出现,每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同,即 每一个方格都有一个分值,而且如同一个靶子一样,离中心越近则分值越高。 (如图)

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

由于求胜心切,小城找到了善于编程的你,让你帮他求出,对于给定的靶形数独,能 够得到的最高分数。
第 6 页 共 7 页

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

提高组

【输入】 输入文件名为 sudoku.in。 一共 9 行。每行 9 个整数(每个数都在 0—9 的范围内) ,表示一个尚未填满的数独方 格,未填的空格用“0”表示。每两个数字之间用一个空格隔开。 【输出】 输出文件 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。

第 7 页 共 7 页

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

提高组

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

提高组
(请选手务必仔细阅读本页内容)
一.题目概况
中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 传统 机器翻译 translate translate translate.in translate.out 1秒 10 10 有 乌龟棋 tortoise tortoise tortoise.in tortoise.out 1秒 10 10 有 传统 关押罪犯 prison prison prison.in prison.out 1秒 10 10 有 传统 引水入城 flow flow flow.in flow.out 1秒 10 10 有 传统

全文比较(过滤行末空格及文末回车)

二.提交源程序文件名
对于 pascal 语言 对于 C 语言 对于 C++语言 translate.pas translate.c translate.cpp tortoise.pas tortoise.c tortoise.cpp prison.pas prison.c prison.cpp flow.pas flow.c flow.cpp

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

四.运行内存限制
内存上限 128M 128M 128M 128M

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

第 1 页 共 7 页

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

提高组

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

translate.out 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 次词典。

第 2 页 共 7 页

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

提高组

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

translate.out 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= 【输出】 输出文件名 tortoise.out。
第 3 页 共 7 页

∑b 。
i 1

M

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

提高组

输出只有 1 行,1 个整数,表示小明最多能得到的分数。 【输入输出样例 1】 tortoise.in 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1

tortoise.out 73

【输入输出样例 1 说明】 小明使用爬行卡片顺序为 1,1,3,1,2,得到的分数为 6+10+14+8+18+17=73。注意, 由于起点是 1,所以自动获得第 1 格的分数 6。 【输入输出样例 2】 tortoise.in 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 1 1 1 1 1 2 4 1

tortoise.out 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=

∑b 。
i 1

M

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

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

提高组

少? 【输入】 输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。 第一行为两个正整数 N 和 M,分别表示罪犯的数目以及存在仇恨的罪犯对数。 接下来的 M 行每行为三个正整数 aj,bj,cj,表示 aj 号和 bj 号罪犯之间存在仇恨,其怨 气值为 cj。数据保证 1 ≤ a j < b j ≤ N ,0 < c j ≤ 1,000,000,000 ,且每对罪犯组合只出现一 次。 【输出】 输出文件 prison.out 共 1 行,为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱 中未发生任何冲突事件,请输出 0。

【输入输出样例】 prison.in 4 1 2 1 1 2 3 6 4 3 2 3 4 4 2534 3512 28351 6618 1805 12884

prison.out 3512

【输入输出样例说明】 罪犯之间的怨气值如下面左图所示, 右图所示为罪犯的分配方法, 市长看到的冲突事件 影响力是 3512(由 2 号和 3 号罪犯引发) 。其他任何分法都不会比这个分法更优。 1
6618 2534 28351 1805 3512 2534 3512

2

1

2

4

12884

3

4

3

【数据范围】 对于 30%的数据有 N ≤ 15。 对于 70%的数据有 N ≤ 2000,M ≤ 50000。 对于 100%的数据有 N ≤ 20000,M ≤ 100000。

第 5 页 共 7 页

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

提高组

4.引水入城
(flow.pas/c/cpp) 【问题描述】 湖泊

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

flow.out 1 1

第 6 页 共 7 页

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

提高组

【样例 1 说明】 只需要在海拔为 9 的那座城市中建造蓄水厂,即可满足要求。 【输入输出样例 2】 flow.in 3 8 7 3 6 4 5 6 4 4 3 4 3 3 3 2 2 1 1 2

flow.out 1 3

【样例 2 说明】 湖泊 8 7 3 4 3 2 5 4 2 6 3 1 4 3 1 4 3 2

沙漠 上图中,在 3 个粗线框出的城市中建造蓄水厂,可以满足要求。以这 3 个蓄水厂为源头 在干旱区中建造的输水站分别用 3 种颜色标出。当然,建造方法可能不唯一。 【数据范围】 本题共有 10 个测试数据,每个数据的范围如下表所示: 测试数据编号 1 2 3 4 5 6 7 8 9 10 能否满足要求 不能 不能 不能 能 能 能 能 能 能 能 N ≤ 10 ≤ 100 ≤ 500 =1 ≤ 10 ≤ 100 ≤ 100 ≤ 100 ≤ 200 ≤ 500
6

M ≤ 10 ≤ 100 ≤ 500 ≤ 10 ≤ 10 ≤ 20 ≤ 50 ≤ 100 ≤ 200 ≤ 500

对于所有的 10 个数据,每座城市的海拔高度都不超过 10 。

第 7 页 共 7 页

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

提高组 day1

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

提高组 day1
(请选手务必仔细阅读本页内容)
一.题目概况
中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 铺地毯 carpet carpet carpet.in carpet.out 1秒 10 10 有 传统 选择客栈 hotel hotel hotel.in hotel.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 传统 mayan 游戏 mayan mayan mayan.in mayan.out 3秒 10 10 有

二.提交源程序文件名
对于 C++语言 对于 C 语言 对于 pascal 语言 carpet.cpp carpet.c carpet.pas hotel.cpp hotel.c hotel. pas mayan.cpp mayan.c mayan. pas

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

四.运行内存限制
内存上限 128M 128M 128M

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

第 1 页 共 6 页

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

提高组 day1

1.铺地毯
(carpet.cpp/c/pas) 【问题描述】 为了准备一个独特的颁奖典礼, 组织者在会场的一片矩形区域 (可看做是平面直角坐标 系的第一象限)铺上一些矩形地毯。一共有 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 号地毯。

y

? ? ? ? ?

? ? ? ? ?

? ? ? ? ?

? ? ? ? ?

? ? ? ? ?

x
第 2 页 共 6 页

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

提高组 day1

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

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

提高组 day1

输出只有一行,一个整数,表示可选的住宿方案的总数。 【输入输出样例 1】 hotel.in 5 0 1 0 1 1 2 3 5 3 2 4 5

hotel.out 3

【输入输出样例说明】 客栈编号 色调 最低消费 ① 0 5 ② 1 3 ③ 0 2 ④ 1 4 ⑤ 1 5

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

第 4 页 共 6 页

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

提高组 day1

图 1

图 2

图 3

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

图 4 图 5 3、 方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注 意:掉落的过程中将不会有方块的消除。 上面图 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。
第 5 页 共 6 页

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

提高组 day1

如果有解决方案,输出 n 行,每行包含 3 个整数 x,y,g,表示一次移动,每两个整数 之间用一个空格隔开,其中(x,y)表示要移动的方块的坐标,g 表示移动的方向,1 表示 向右移动,-1 表示向左移动。注意:多组解时,按照 x 为第一关健字,y 为第二关健字,1 优先于-1,给出一组字典序最小的解。游戏界面左下角的坐标为(0,0) 。 如果没有解决方案,输出一行,包含一个整数-1。 【输入输出样例 1】 mayan.in mayan.out 3 1 2 2 3 2 0 1 3 1 4 2 1 1 3 1 1 3 0 1

0 4 0 0 3 4 0

【输入输出样例说明】 按箭头方向的顺序分别为图 6 到图 11

图6

图7

图8

图 11

图 10

图9

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

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

提高组 day2

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

提高组 day2
(请选手务必仔细阅读本页内容)
一.题目概况
中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 计算系数 factor factor factor.in factor.out 1秒 10 10 有 传统 聪明的质监员 qc qc qc.in qc.out 1秒 20 5 有 全文比较(过滤行末空格及文末回车) 传统 传统 观光公交 bus bus bus.in bus.out 1秒 20 5 有

二.提交源程序文件名
对于 C++语言 对于 C 语言 对于 pascal 语言 factor.cpp factor.c factor.pas qc.cpp qc.c qc. Pas bus.cpp bus.c bus. pas

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

四.运行内存限制
内存上限 128M 128M 128M

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

第 1 页 共 4 页

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

提高组 day2

1.计算系数
(factor.cpp/c/pas) 【问题描述】 给定一个多项式 (ax + by ) ,请求出多项式展开后 x y 项的系数。
k n m

【输入】 输入文件名为 factor.in。 共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。 【输出】 输出文件名为 factor.out。 输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10007 取 模后的结果。 【输入输出样例】 factor.in 1 1 3 1 2

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。

2.聪明的质监员
(qc.cpp/c/pas) 【问题描述】 小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1 到 n 逐一编号,每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是: 1、给定 m 个区间[Li,Ri]; 2、选出一个参数 W; 3、对于一个区间[Li,Ri],计算矿石在这个区间上的检验值 Yi :

Yi = ∑1* ∑ v j , j ∈ [ Li , Ri ] 且 w j ≥ W ,j 是矿石编号
j j

这批矿产的检验结果 Y 为各个区间的检验值之和。即: Y =

∑Y
i =1

m

i

若这批矿产的检验结果与所给标准值 S 相差太多,就需要再去检验另一批矿产。小 T 不想费时间去检验另一批矿产,所以他想通过调整参数 W 的值,让检验结果尽可能的靠近 标准值 S,即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。 【输入】 输入文件 qc.in。
第 2 页 共 4 页

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

提高组 day2

第一行包含三个整数 n,m,S,分别表示矿石的个数、区间的个数和标准值。 接下来的 n 行,每行 2 个整数,中间用空格隔开,第 i+1 行表示 i 号矿石的重量 wi 和价 值 vi 。 接下来的 m 行,表示区间,每行 2 个整数,中间用空格隔开,第 i+n+1 行表示区间[Li, Ri]的两个端点 Li 和 Ri。注意:不同区间可能重合或相互重叠。 【输出】 输出文件名为 qc.out。 输出只有一行,包含一个整数,表示所求的最小值。 【输入输出样例】 qc.in 5 1 2 3 4 5 1 2 3 3 15 5 5 5 5 5 5 4 3

qc.out 10

【输入输出样例说明】 当 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≤1012,1≤Li≤Ri≤n。

3.观光公交
(bus.cpp/c/pas) 【问题描述】 风景迷人的小城 Y 市,拥有 n 个美丽的景点。由于慕名而来的游客越来越多,Y 市特 意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1 号景点,随后依次前往 2、3、4……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。 任意时刻,公交车只能往前开,或在景点处等待。 设共有 m 个游客,每位游客需要乘车 1 次从一个景点到达另一个景点,第 i 位游客在 Ti 分钟来到景点 Ai,希望乘车前往景点 Bi(Ai<Bi) 。为了使所有乘客都能顺利到达目的地,
第 3 页 共 4 页

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

提高组 day2

公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。 假设乘客上下车不需要时间。 一个乘客的旅行时间, 等于他到达目的地的时刻减去他来到出发地的时刻。 因为只有一 辆观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司 机 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 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。 【输出】 输出文件名为 bus.out。共一行,包含一个整数,表示最小的总旅行时间。 【输入输出样例】 bus.in 3 1 0 1 5 3 4 1 1 2 2 3 2 3

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。

第 4 页 共 4 页


更多相关文档:

noip2001提高组复赛试题

noip2001提高组复赛试题_IT/计算机_专业资料。2001 年全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (高中组 竞赛用时:3 小时) 题一 一元三次方程求解(20 ...

历届noip提高组复赛试题

历届noip提高组复赛试题_学科竞赛_高中教育_教育专区。NOI’95 “同创杯”全国...13 6 7 14 21 4 15 14 0 67 2001 年 题一 一元三次方程求解(20 分)...

2011noip提高组复赛题解

Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则更新结果 或者倒着扫一遍,找到第一个覆盖询问点的矩形...

NOIP2011提高组复赛试题与简解(转载)

NOIP2011提高组复赛试题与简解(转载)_中考_初中教育_教育专区。NOIP2011提高组复赛试题与简解 Day1 铺地毯 【问题描述】 为了准备一个独特的颁奖典礼,组织者在...

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

2006~2014 年 NOIP 复赛试题集(提高组) 第十二届全国信息学奥林匹克分区联赛(...29 2006~2014 年 NOIP 复赛试题集(提高组) 全国信息学奥林匹克联赛(NOIP2011...

NOIP历年复赛提高组试题

第七届全国信息学奥林匹克分区联赛(NOIP2001)复赛试题(提高组 竞赛用时:3 小时) 1、一元三次方程求解 【问题描述】 有形如:ax3+bx2+cx+d=0 这样的一个...

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

NOIP历年复赛提高组试题(2004-2013)_学科竞赛_高中教育...(NOIP2011)复赛 提高组 Day1 一. 题目概况 二. ...笑话大全集 笑话大全爆笑版 幽默笑话大全 全球冷笑话...

2011十七届noip提高组题目及答案

2011十七届noip提高组题目及答案_学科竞赛_高中教育_教育专区。为了打印各种调的~~~第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高组 Pascal 语言 两小时完成...

NOIP2011提高组解题报告day1

下面附加几个剪枝 左右交换是等价的,根据题中的顺序,只需向右交换即可 某个...Noip2011解题报告 11页 免费 NOIP2001提高组解题报告... 10页 免费 Noip 2013...
更多相关标签:
noip2001普及组复赛 | noip2016提高组复赛 | noip2015提高组复赛 | noip2014提高组复赛 | noip2010提高组复赛 | noip2012提高组复赛 | noip2013提高组复赛 | noip提高组复赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com