当前位置:首页 >> 学科竞赛 >> 历届noip提高组复赛试题

历届noip提高组复赛试题


NOI’95 “同创杯”全国青少年信息学(计算机)奥林匹克竞赛 分区联赛复赛试题(高中组) (上机编程,完成时间:210 分钟)
<1> 编码问题: 设有一个数组 A:ARRAY[0..N-1] OF INTEGER; 数组中存放的元素为 0~N-1 之间的整数,且 A[i]≠A[j](当 i≠j 时) 。 例如:N=6 时,有: A=(4,3,0,5,1,

2) 此时,数组 A 的编码定义如下: A[0]的编码为 0; A[i]的编码为:在 A[0],A[1],?,A[i-1]中比 A[i]的值小的个数(i=1,2,?,N-1) ∴ 上面数组 A 的编码为: B=(0,0,0,3,1,2) 程序要求解决以下问题: ① 给出数组 A 后,求出其编码。 ② 给出数组 A 的编码后,求出 A 中的原数据。 <2> 灯的排列问题: 设在一排上有 N 个格子(N≤20) ,若在格子中放置有不同颜色的灯,每种灯的个数记 为 N1,N2,??Nk(k 表示不同颜色灯的个数) 。 放灯时要遵守下列规则: ①同一种颜色的灯不能分开; ②不同颜色的灯之间至少要有一个空位置。 例如:N=8(格子数) R=2(红灯数) B=3(蓝灯数) 放置的方法有: R-B 顺序 R R R R R R R R R R R R B B B B B B B B B B B B B B B B B B

B-R 顺序 B B B B B B B B B B B B B B 放置的总数为 12 种。 数据输入的方式为: N P1(颜色,为一个字母) N1(灯的数量) P2 N2 ?? Q(结束标记,Q 本身不是灯的颜色) 程序要求:求出一种顺序的排列方案及排列总数。 <3> 设有一个四层的积木块,1~4 层积木块的数量依次为:5,6,7,8 如下图所示放置: B B B B R R R R R R R R R R R R

8 2 3

15 4

8 1

5 4

16 3

9 2

14 6

其中, 给出第三层与第四层所标示的数字, 并已知第三层的数据是由第四层的数据计算 出来的。 计算的方法是:第三层的某个数据 A 是由第四层相邻的两个数据 B,C 经过某种计算 后产生的: A B C

计算所用到的计算符为:+,-,? ,且无优先级之分(自左向右计算) ,运算符最多为 2 个。 如:3+4 ? 5=35 5 ? 4+3=23 可以看出,上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的: A=B ? C+B 也就是:8=2 ? 3+2,15=3 ? 4+3,??14=2 ? 6+2 程序要求: 给出第四层与第三层的数据后,将第一、二层的每块积木标上相应的数据,并输出整个 完整的积木图及计算公式。 ① 输入数据不存在出错的情况,同时也不会超过整数的范围。

② 计算时可允许出现以下情况: A=B (即可理解为运算符的个数为零) A=B ? B+B (即全部由 B 产生)

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

1.比赛安排(20 分) 设有有 2 n(n<=6)个球队进行单循环比赛,计划在 2 n – 1 天内完成,每个队每天进行 一场比赛。设计一个比赛的安排,使在 2 n – 1 天内每个队都与不同的对手比赛。 例如 n=2 时的比赛安排: 队 1 2 3 4 比赛 1==2 3==4 一天 1==3 2==4 二天 1==4 2==3 三天 2.数制转换(20 分) 设有一个字符串 A$的结构为: A$=‘m<n>p‘ 其中 m 为数字串 (长度<=20) 而 n,p 均为 1 或 2 位的数字串 , (其中所表达的内容在 2-10 之间) 。 程序要求:从键盘上读入 A$后(不用正确性检查) ,将 A$中的数字串 m(n 进制),以 p 进制的形式输出。 例如:A$=‘48<10>8‘ 其意义为:将 10 进制数 48,转换成 8 进制数输出。 输出结果为:48<10>=60<8> 4.挖地雷(30 分) 在一个地图上有 N 个地窖(N<=20) ,每个地窖中埋有一定数量的地雷。同时,给出地 窖之间的连接路径。 例如:

V1 V5

V

2

V3

V4

[题目要求] 当地窖及其连接的数据给出之后, 某人可以从任一处开始挖地雷, 然后可以沿着指出的 连接往下挖(仅能选择一条路径) ,当无连接时挖地雷工作结束。设计一个挖地雷的方案, 使某人能挖到最多的地雷。 输入格式: N: (表示地窖的个数) W1,W2,W3,……WN (表示每个地窖中埋藏的地雷数量)

A12…………… . A1N A23…………..A2N …….. AN-1 N 输出格式: K1--K2--……….KV MAX 例如: ⑩--------⑧

地窖之间连接路径(其中Aij=1 表示地窖 i,j 之间是否有通路:通 Aij=1,不通 Aij==0)

(挖地雷的顺序) (挖地雷的数量)

④-----⑦-------⑥ 输出: 1 –3 -4 max=27

其输入格式为: 5 10,8,4,7,6 1 1 1 0 0 0 0 1 1 1

-5

4.砝码称重(30 分) 设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚(其总重<=1000) , 要求: 输入方式:a1 a2 a3 a4 a5 a6 (表示 1g 砝码有 a1 个,2g 砝码有 a2 个,?,20g 砝码有 a6 个) 输出方式:Total=N (N 表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不 用的情况) 如输入:1_1_0_0_0_0 (注:下划线表示空格) 输出:TOTAL=3 表示可以称出 1g,2g,3g 三种不同的重量。

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

1.在 N*N 的棋盘上(1≤N≤10) ,填入 1,2,?,N*N 共 N*N 个数,使得任意两个相邻 的数之和为素数。 (30%) 例如:当 N=2 时,有: 其相邻数的和为素数的有: 1 2 1+2,1+4,4+3,2+3 4 3 当 N=4 时,一种可以填写的方案如下:

1 16 13 6

2 15 4 7

11 8 9 10

12 5 14 3

在这里我们约定:左上角的格子里必须填数字 1。 程序要求: 输入:N; 输出:如有多种解,则输出第一行、第一列之和为最小的排列方案;若无解,则输 出“NO!。 ” 2.代数表达式的定义如下:

字母

a b c

例如,下面的式子是合法的代数表达式: a; a+b*(a+c); a*a/(b+c) 下面的式子是不合法的代数表达式: ab; a+a*/(b+c); 程序要求: 输入:输入一个字符串,以“; ”结束, ”本身不是代数表达式中字符,仅作为 “; 结束) ; 输出:若表达式正确,则输出“OK” ;若表达式不正确,则输出“ERROR” ,及错 误类型。 错误类型约定: 1.式了中出现不允许的字符; 2.括号不配对; 3.其它错误。 例如:输入:a+(b); 输出:OK

例如:输入:a+(b+c*a;

输出:ERROR 2

3.骑士游历: 设有一个 n*m 的棋盘(2≤n≤50,2≤m≤50) ,如下图,在棋盘上左下角有一个中国 象棋马。 (n,m)



(1,1) 马走的规则为: (1) 马走日字; (2) 马只能向右走 即如下图如示:

任务 1:当 n,m 输入之后,找出一条从左下角到右上角的路径。 例如,输入:n=4,m=4 (4,4)

(1,1) 输出:路径的格式:(1,1)→(2,3)→(4,4)。若不存在路径,则输出‘NO’ 任务 2:当 n,m 给出之后,同时给出马起点的位置和终点的位置,试找出从起点到终 点的所有路径的数目。 例如: (n=10,m=10)(1,5) , (起点)(3,5) , (终点) 10 9 8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8 9 10 输 出:2(即由(1,5)到(3,5)共有 2 条路径) 输入格式:n,m,x1,y1,x2,y2 (分别表示 n,m,起点坐标,终点坐标) 输出格式:路径数目(若不存在从起点到终点的路径,输出 0)

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

1.火车从始发站(称为第 1 站)开出,在始发站上车的人数为 a,然后到达第 2 站,在第 2 站有人上、下车,但上、下车的人数相同,因此在第 2 站开出时(即在到达第 3 站之前) 车上的人数保持为 a 人。从第 3 站起(包括第 3 站)上、下车的人数有一定规律:上车 的人数都是前两站上车人数之和,而下车人数等于上一站上车人数,一直到终点站的前 一站(第 n-1 站) ,都满足此规律。现给出的条件是:共有 N 个车站,始发站上车的人 数为 a,最后一站下车的人数是 m(全部下车) 。试问 x 站开出时车上的人数是多少? 输入:a,n,m 和 x 输出:从 x 站开出时车上的人数。 2.设有 n 个正整数(n≤20) ,将它们联接成一排,组成一个最大的多位整数。 例如:n=3 时,3 个整数 13,312,343 联接成的最大整数为:34331213 又如:n=4 时,4 个整数 7,13,4,246 联接成的最大整数为:7424613 程序输入:n n 个数 程序输出:联接成的多位数 {40%} {20%}

3.著名科学家卢斯为了检查学生对进位制的理解,他给出了如下的一张加法表,表中的字 母代表数字。 例如: 其含义为: + L K V E L L K V E K K V E KL V V E KL KK E E KL KK KV L+L=L,L+K=K,L+V=V,L+E=E K+L=K,K+K=V,K+V=E,K+E=KL ?? E+E=KV {40%}

根据这些规则可推导出:L=0,K=1,V=2,E=3 同时可以确定该表表示的是 4 进制加法 程序输入: n(n≤9)表示行数。 以下 n 行,每行包括 n 个字符串,每个字串间用空格隔开。 (字串仅有一个为‘+’号, 其它都由大写字母组成) 程序输出:

① 各个字母表示什么数,格式如:L=0,K=1,?? ② 加法运算是几进制的。 ③ 若不可能组成加法表,则应输出“ERROR! ”

第五届全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (提
第一题 拦截导弹(28 分) 某国为了防御敌国的导弹袭击, 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一 个缺陷: 虽然它的第一发炮弹能够到达任意的高度, 但是以后每一发炮弹都不能高于前一发 的高度。 某天, 雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段, 所以只有一套系统, 因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数) ,计算这套 系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例: INPUT 389 207 155 300 299 170 158 65





竞赛用时:3 小时)

OUTPUT 6(最多能拦截的导弹数) 2(要拦截所有导弹最少要配备的系统数)

第二题 回文数(25 分) 若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。 例如:给定一个 10 进制数 56,将 56 加 65(即把 56 从右向左读) ,得到 121 是一个回 文数。 又如:对于 10 进制数 87: STEP1:87+78 = 165 STEP3:726+627 = 1353

STEP2:165+561 = 726 STEP4:1353+3531 = 4884

在这里的一步是指进行了一次 N 进制的加法,上例最少用了 4 步得到回文数 4884。 写一个程序,给定一个 N(2<=N<=10 或 N=16)进制数 M,求最少经过几步可以得到回文 数。 如果在 30 步以内(包含 30 步)不可能得到回文数,则输出“Impossible! ” 样例: INPUT

OUTPUT

N = 9 M= 87 第三题 旅行家的预算(27 分)

STEP=6

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空 的) 。给定两个城市之间的距离 D1、汽车油箱的容量 C(以升为单位) 、每升汽油能行驶的距 离 D2、出发点每升汽油价格 P 和沿途油站数 N(N 可以为零) ,油站 i 离出发点的距离 Di、 每升汽油价格 Pi(i=1,2,??N) 。计算结果四舍五入至小数点后两位。如果无法到达目 的地,则输出“No Solution” 。 样例: INPUT D1=275.6 C=11.9 D2=27.4 P=2.8 N=2 油站号 I 1 2 离出发点的距离 Di 102.0 220.0 每升汽油价格 Pi 2.9 2.2

OUTPUT 26.95(该数据表示最小费用) 第四题 邮票面值设计(40 分) 给定一个信封,最多只允许粘贴 N 张邮票,计算在给定 K(N+K≤40)种邮票的情况下 (假定所有的邮票数量都足够) ,如何设计邮票的面值,能得到最大值 MAX,使在 1~MAX 之 间的每一个邮资值都能得到。 例如,N=3,K=2,如果面值分别为 1 分、4 分,则在 1 分~6 分之间的每一个邮资值都 能得到(当然还有 8 分、9 分和 12 分) ;如果面值分别为 1 分、3 分,则在 1 分~7 分之间 的每一个邮资值都能得到。可以验证当 N=3,K=2 时,7 分就是可以得到的连续的邮资最大 值,所以 MAX=7,面值分别为 1 分、3 分。 样例: INPUT N=3 K=2

OUTPUT 1 3 MAX=7

2000 年 题一
问题描述 我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该数字所 处位置的(值减1)为指数,以10为底数的幂之和的形式。例如:123可表示为 1* 2 1 0 10 +2*10 +3*10 这样的形式。 与之相似的,对二进制数来说,也可表示成每个二进制数码乘以一个以该数字所处位 置的(值-1)为指数,以2为底数的幂之和的形式。一般说来,任何一个正整数R或一个 负整数-R都可以被选来作为一个数制系统的基数。 如果是以R或-R为基数, 则需要用到 的数码为 0,1,..R-1。例如,当R=7时,所需用到的数码是0,1,2,3, .. 4,5和6,这与其是R或-R无关。如果作为基数的数绝对值超过10,则为了表示这些 数码, 通常使用英文字母来表示那些大于9的数码。 例如对16进制数来说, 用A表示10, 用B表示11,用C表示12,用D表示13,用E表示14,用F表示15。 在负进制数中是用-R 作为基数, 例如-15 (十进制) 相当于110001 (-2进制) , 并且它可以被表示为2的幂级数的和数: 5 4 3 2 110001=1*(-2) +1*(-2) +0*(-2) +0*(-2) + 1 0 0*(-2) +1*(-2) 问题求解 设计一个程序,读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负 进制下的数: -R∈{-2,-3,-4,.,-20} .. 输 入 输入的每行有两个输入数据。 第一个是十进制数N(-32768<=N<=32767) 第二个是负进制数的基数-R。 ; 输 出 结果显示在屏幕上,相对于输入,应输出此负进制数及其基数,若此基数超过10,则 参照16进制的方式处理。 样 例 输入 30000 -2 -20000 -2 28800 -16 -25000 -16 输出 30000=11011010101110000(base -2) -20000=1111011000100000 (base -2) 28000=19180 (base -16) -25000=7FB8 (base -16)

进制转换

(18 分)

提高组

题二

乘积最大

(22 分)

问题描述 今年是国际数学联盟确定的“2000——世界数学年” ,又恰逢我国著名数学家华罗庚先 生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活 动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样 一道题目: 设有一个长度为 N 的数字串,要求选手使用 K 个乘号将它分成 K+1 个部分,找出一种 分法,使得这 K+1 个部分的乘积能够为最大。 同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子: 有一个数字串:312, 当 N=3,K=1 时会有以下两种分法: 1) 3*12=36 2) 31*2=62 这时,符合题目要求的结果是:31*2=62 现在,请你帮助你的好朋友 XZ 设计一个程序,求得正确的答案。 输 入

程序的输入共有两行: 第一行共有 2 个自然数 N,K(6≤N≤40,1≤K≤6) 第二行是一个长度为 N 的数字串。





结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数) 。 样 输入 4 2 1231 例

输出 62 提高组

题三.

单词接龙

(27 分)

问题描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏, 现在我们已知一组单词, 且给 定一个开头的字母,要求出以这个字母开头的最长的“龙” (每个单词都最多在“龙”中出 现两次) ,在两个单词相连时,其重合部分合为一部分,例如 beast 和 astonish,如果接成一 条龙则变为 beastonish, 另外相邻的两部分不能存在包含关系, 例如 at 和 atide 间不能相连。 输 入

输入的第一行为一个单独的整数 n (n<=20)表示单词数, 以下 n 行每行有一个单词, 输入 的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一 定存在. 输 出

只需输出以此字母开头的最长的“龙”的长度 样 输入 5 at touch cheat choose tact a 输出 23 (连成的“龙”为 atoucheatactactouchoose) 例 :

提高组

题四. 方格取数

(33 分)

问题描述 设有 N*N 的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放 入数字 0。如下图所示(见样例) : A 1 2 3 4 向 下 5 6 7 8 0 0 0 0 0 0 0 1 0 0 0 0 21 0 14 0 2 0 0 13 0 0 0 15 0 0 3 4 0 0 0 14 0 0 0 0 5 0 0 7 0 0 0 0 0 6 0 6 0 0 4 0 0 0 向右 7 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B

某人从图的左上角的 A 点出发,可以向下行走,也可以向右走,直到到达右下角的 B 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 0) 。 此人从 A 点到 B 点共走两次,试找出 2 条这样的路径,使得取得的数之和为最大。 输 入 输入的第一行为一个整数 N(表示 N*N 的方格图) ,接下来的每行有三个整数,前两个 表示位置,第三个数为该位置上所放的数。一行单独的 0 表示输入结束。 输 出 只需输出一个整数,表示 2 条路径上取得的最大的和。 样 例 输 入 8 2 3 2 6 3 5 4 4 5 2 5 6 6 3 7 2 0 0 输 出 :

13 6 7 14 21 4 15 14 0

67

2001 年 题一 一元三次方程求解(20 分) 问题描述 有形如: 3+bx2+cx+d=0 这样的一个一元三次方程。 ax 给出该方程中各项的系数(a, c, 均 b, d 为实数),并约定该方程存在三个不同实根(根的范围在-100 至 100 之间),且根与根之差的 绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到 小数点后 2 位。 提示:记方程 f(x)=0,若存在 2 个数 x1 和 x2,且 x1<x2,f(x1)*f(x2)<0,则在(x1,x2)之间 一定有一个 根。 样例 输入:1 -5 -4 20 输出:-2.00 2.00 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 13 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)表示城市的个数, 表示飞机单位里程的价格, B 分别为城市 A, 的序号, t 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

2002 年 题一 均分纸牌(存盘名 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 张牌放到 ② 11 10 10) 从 (9 -> ② 取 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 : 42 11 22 36 07 屏幕显示: 4

2003 年

第九届全国青少年信息学奥林匹克联赛(N0IP2003)
2003 年 11 月 29 日 提高组试题 试题输入:苏州高斌 大榕树 http://drs.126.com 三小时完成

题一

神经网络

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

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

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

?W

ji

Cj ? 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。 【输入样例】 56 10 10 01 01 01 131 141 151 231 241 251 【输出样例】 31 41 51

题二

侦探推理

【问题描述】 明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学 玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明

明不知情的情况下) ,明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被 询问者可能会说:

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

题四

传染病控制

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

的潜在传播途径图(一棵树) 。但是,麻烦还没有结束。由于蓬莱国疾控中心人手不够,同 时也缺乏强大的技术,以致他们在一个疾病传播周期内,只能设法切断一条传播途径,而 没有被控制的传播途径就会引起更多的易感人群被感染(也就是与当前已经被感染的人有 传播途径相连,且连接途径没有被切断的人群) 。当不可能有健康人被感染时,疾病就中止 传播。所以,蓬莱国疾控中心要制定出一个切断传播途径的顺序,以使尽量少的人被感染。 你的程序要针对给定的树,找出合适的切断顺序。 【输入格式】 输入格式的第一行是两个整数 n(1≤n≤300)和 p。接下来 p 行,每一行有两个整数 i 和 j,表示节点 i 和 j 间有边相连(意即,第 i 人和第 j 人之间有传播途径相连) 。其中节点 1 是已经被感染的患者。 【输出格式】 只有一行,输出总共被感染的人数。 【输入样例】 76 12 13 24 25 36 37 【输出样例】 3

2004 年

第十届全国青少年信息学奥林匹克联赛复赛试题 (提高组 3 小时完成) http://www.oifans.cn 一、津津的储蓄计划 (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 1 2 9 【样例输出】 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<...<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#9865#045 8468#6633 44445506978

+

其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两 个数字分别是 5 和 3,第二行的数字是 5。 现在,我们对问题做两个限制:

首先,我们只考虑加法的虫食算。这里的加法是 N 进制加法,算式中三个数 都有 N 位,允许有前导的 0。 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相 同的数字用相同的字母表示,不同的数字用不同的字母表示。如果这个算式是 N 进制的,我们就取英文字母表午的前 N 个大写字母来表示这个算式中的 0 到 N-1 这 N 个不同的数字:但是这 N 个字母并不一定顺序地代表 0 到 N-1)。输入数据 保证 N 个字母分别至少出现一次。

+

BADC CRDA 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 【样例输出】 1 0 3 4 2

【数据规模】 对于 30%的数据,保证有 N<=10; 对于 50%的数据,保证有 N<=15; 对于全部的数据,保证有 N<=26。

2005 年

第十二届全国青少年信息学奥林匹克 联赛复赛试题
(NOIP2006 普及组) 竞赛时间:2006 年 11 月 18 日 下午 1:30-4:30
试题名称 目录 输入文件名 输出文件名 试题类型 附加文件 时限 random random random.in random.out 非交互式程序 题 无 1秒 Happy Happy happy.in happy.out 非交互式程序题 无 1秒 count count count.in count.out 非交互式程序 题 无 1秒 sequence sequence sequence.in sequence.out 非交互式程序 题 无 1秒

关于竞赛中不同语言使用限制的说明
一.关于使用 Pascal 语言与编译结果的说明 1.对于 Pascal 语言的程序,当使用 IDE 和 fpc 编译结果不一致时,以 fpc 的 编译结果为准。 2.允许使用数学库(uses math 子句),以及 ansistring。但不允许使用编译开 关(最后测试时 pascal 的范围检查开关默认关闭:{$R-,Q-,S-}),也不支 持与优化相关的选项。

二.关于 C++语言中模板使用的限制说明 1.允许使用的部分: 标准容器中的布尔集合,迭代器,串,流。 相关的头文件: 2.禁止使用的部分: 序列:vector,list,deque 序列适配器:stack, queue, priority_queue 关联容器:map, multimap, set, multiset 拟容器:valarray 散列容器:hash_map, hash_set, hash_multimap, hash_multiset 所有的标准库算法 相关头文件:

1.明明的随机数
(random.pas/c/cpp) 【问题描述】 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先 用计算机生成了 N 个 1 到 1000 之间的随机整数(N≤100),对于其中重复的 数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。 然后再把这些数从小到大排序, 按照排好的顺序去找同学做调查。请你协助明明 完成“去重”与“排序”的工作。 【输入文件】 输入文件 random.in 有 2 行,第 1 行为 1 个正整数,表示所生成的随机数 的个数: N 第 2 行有 N 个用空格隔开的正整数,为所产生的随机数。 【输出文件】 输出文件 random.out 也是 2 行,第 1 行为 1 个正整数 M,表示不相同的随 机数的个数。第 2 行为 M 个用空格隔开的正整数,为从小到大排好序的不相同 的随机数。 【输入样例】 10 20 40 32 67 40 20 89 300 400 15 【输出样例】

8 15 20 32 40 67 89 300 400

2.开心的金明
(happy.pas/c/cpp) 【问题描述】 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用 的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些 物品,怎么布置,你说了算,只要不超过 N 元钱就行”。今天一早金明就开始做 预算,但是他想买的东西太多了,肯定会超过妈妈限定的 N 元。于是,他把每件 物品规定了一个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从 因特网上查到了每件物品的价格(都是整数元)。他希望在不超过 N 元(可以等 于 N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号 依次为 j1,j2,??,jk,则所求的总和为:

v[j1]*w[j1]+v[j2]*w[j2]+ ?+v[jk]*w[jk]。(其中*为乘号) 请你帮助金明设计一个满足要求的购物单。 【输入文件】 输入文件 happy.in 的第 1 行,为两个正整数,用一个空格隔开: N m (其中 N(<30000)表示总钱数,m(<25)为希望购买物品的个数。)

从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 2 个非负整数 v p (其中 v 表示该物品的价格(v<=10000),p 表示该物品的重要度(1~5)) 【输出文件】 输出文件 happy.out 只有一个正整数,为不超过总钱数的物品的价格与重要 度乘积的总和的最大值(<100000000)。 【输入样例】
1000 5 800 2 400 5 300 5 400 3 200 2

【输出样例】 3900

3.Jam 的计数法
(count.pas/c/cpp) 【问题描述】

Jam 是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数,而是使用小 写英文字母计数,他觉得这样做,会使世界更加丰富多彩。在他的计数法中,每 个数字的位数都是相同的(使用相同个数的字母),英文字母按原先的顺序,排 在前面的字母小于排在它后面的字母。我们把这样的“数字”称为 Jam 数字。 在 Jam 数字中,每个字母互不相同,而且从左到右是严格递增的。每次,Jam 还指定使用字母的范围,例如,从 2 到 10,表示只能使用{b,c,d,e,f,g,h, i,j}这些字母。如果再规定位数为 5,那么,紧接在 Jam 数字“bdfij”之后 的数字应该是“bdghi”。(如果我们用 U、V 依次表示 Jam 数字“bdfij”与 “bdghi”,则 U<V< span>,且不存在 Jam 数字 P,使 U<P<V< span>)。 你的任务是:对于从文件读入的一个 Jam 数字,按顺序输出紧接在后面的 5 个 Jam 数字,如果后面没有那么多 Jam 数字,那么有几个就输出几个。 【输入文件】 输入文件 counting.in 有 2 行,第 1 行为 3 个正整数,用一个空格隔开: s t w (其中 s 为所使用的最小的字母的序号,t 为所使用的最大的字母的序号。w 为数字的位数,这 3 个数满足:1≤s<T< span>≤26, 2≤w≤t-s )

第 2 行为具有 w 个小写字母的字符串,为一个符合要求的 Jam 数字。 所给的数据都是正确的,不必验证。 【输出文件】

输出文件 counting.out 最多为 5 行, 为紧接在输入的 Jam 数字后面的 5 个 Jam 数字,如果后面没有那么多 Jam 数字,那么有几个就输出几个。每行只 输出一个 Jam 数字,是由 w 个小写字母组成的字符串,不要有多余的空格。 【输入样例】 2 10 5 bdfij 【输出样例】 bdghi bdghj bdgij bdhij befgh

4.数列
(sequence.pas/c/cpp) 【问题描述】 给定一个正整数 k(3≤k≤15),把所有 k 的方幂及所有有限个互不相等的 k 的方幂之和构成一个递增的序列,例如,当 k=3 时,这个序列是:

1,3,4,9,10,12,13,?

(该序列实际上就是:30,31,30+31,32,30+32,31+32,30+31+32,?)

请你求出这个序列的第 N 项的值(用 10 进制数表示)。

例如,对于 k=3,N=100,正确答案应该是 981。 【输入文件】 输入文件 sequence.in 只有 1 行,为 2 个正整数,用一个空格隔开: k N (k、N 的含义与上述的问题描述一致,且 3≤k≤15,10≤N≤1000)。 【输出文件】 输出文件 sequence.out 为计算结果,是一个正整数(在所有的测试数据 中,结果均不超过 2.1*109)。(整数前不要有空格和其他符号)。 【输入样例】 3 100 【输出样例】 981

2007 年

全国信息学奥林匹克联赛(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. 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 行: 第 1 行是整数 n,表示自然数的个数。 第 2~n+1 行每行一个自然数。 【输出】 输出文件 count.out 包含 m 行(m 为 n 个自然数中不相同数的个数) ,按照自然数从 小到大的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格 隔开。 【输入输出样例】 count.in 8 2 4 2 4 5 100 2 100

count.out 2 3 4 2 5 1 100 2

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

2.字符串的展开
(expand.pas/c/cpp) 【问题描述】 在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如 果在输入的字符串中,含有类似于“d-h”或“4-8”的子串,我们就把它当作一种简写,输 出时, 用连续递增的字母或数字串替代其中的减号, 将上面两个子串分别输出为 即, “defgh” 和“45678” 。在本题中,我们通过增加一些参数的设置,使字符串的展开更为灵活。具体约 定如下: (1)遇到下面的情况需要做字符串的展开:在输入的字符串中,出现了减号“-” ,减

号两侧同为小写字母或同为数字,且按照 ASCII 码的顺序,减号右边的字符严格大于左边 的字符。 (2)参数 p1:展开方式。p1=1 时,对于字母子串,填充小写字母;p1=2 时,对于字 母子串,填充大写字母。这两种情况下数字子串的填充方式相同。p1=3 时,不论是字母子 串还是数字子串,都用与要填充的字母个数相同的星号“*”来填充。 (3)参数 p2:填充字符的重复个数。p2=k 表示同一个字符要连续填充 k 个。例如, 当 p2=3 时,子串“d-h”应扩展为“deeefffgggh” 。减号两侧的字符不变。 (4)参数 p3:是否改为逆序:p3=1 表示维持原有顺序,p3=2 表示采用逆序输出,注 意这时仍然不包括减号两端的字符。例如当 p1=1、p2=2、p3=2 时,子串“d-h”应扩展为 “dggffeeh” 。 (5)如果减号右边的字符恰好是左边字符的后继,只删除中间的减号,例如: “d-e” 应输出为“de”“3-4”应输出为“34” , 。如果减号右边的字符按照 ASCII 码的顺序小于或等 于左边字符,输出时,要保留中间的减号,例如: “d-d”应输出为“d-d”“3-1”应输出为 , “3-1” 。 【输入】 输入文件 expand.in 包括两行: 第 1 行为用空格隔开的 3 个正整数,依次表示参数 p1,p2,p3。 第 2 行为一行字符串,仅由数字、小写字母和减号“-”组成。行首和行末均无空格。 【输出】 输出文件 expand.out 只有一行,为展开后的字符串。 【输入输出样例 1】 expand.in 1 2 1 abcs-w1234-9s-4zz 【输入输出样例 2】 expand.in 2 3 2 a-d-d 【输入输出样例 3】 expand.in 3 4 2 di-jkstra2-6 expand.out dijkstra2************6 expand.out aCCCBBBd-d expand.out abcsttuuvvw1234556677889s-4zz

【限制】 40%的数据满足:字符串长度不超过 5 100%的数据满足:1<=p1<=3, 1<=p2<=8, 1<=p3<=2。字符串长度不超过 100

3. 矩阵取数游戏
(game.pas/c/cpp) 【问题描述】 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元 素 aij 均为非负整数。游戏规则如下: 1. 每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素; 2. 每次取走的各个元素只能是该元素所在行的行首或行尾; 3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素 值*2i,其中 i 表示第 i 次取数(从 1 开始编号) ; 4. 游戏结束总得分为 m 次取数得分之和。 帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。 【输入】 输入文件 game.in 包括 n+1 行: 第 1 行为两个用空格隔开的整数 n 和 m。 第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。 【输出】 输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。 【输入输出样例 1】 game.in 2 3 1 2 3 3 4 2

game.out 82

【输入输出样例 1 解释】 第 1 次:第 1 行取行首元素,第 2 行取行尾元素,本次得分为 1*21+2*21=6 第 2 次:两行均取行首元素,本次得分为 2*22+3*22=20 第 3 次:得分为 3*23+4*23=56。总得分为 6+20+56=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

game.out 122

game.out 316994

【限制】 60%的数据满足:1<=n, m<=30, 答案不超过 1016 100%的数据满足:1<=n, m<=80, 0<=aij<=1000

4. 树网的核
(core.pas/c/cpp) 【问题描述】 设 T=(V, E, W) 是一个无圈且连通的无向图(也称为无根树) ,每条边带有正整数的 权,我们称 T 为树网(treenetwork) ,其中 V, E 分别表示结点与边的集合,W 表示各边 长度的集合,并设 T 有 n 个结点。 路径:树网中任何两结点 a,b 都存在唯一的一条简单路径,用 d(a,b)表示以 a,b 为 端点的路径的长度,它是该路径上各边长度之和。我们称 d(a,b)为 a,b 两结点间的距离。 一点 v 到一条路径 P 的距离为该点与 P 上的最近的结点的距离: d(v,P)=min{d(v,u),u 为路径 P 上的结点}。 树网的直径:树网中最长的路径称为树网的直径。对于给定的树网 T,直径不一定是唯 一的,但可以证明:各直径的中点(不一定恰好是某个结点,可能在某条边的内部)是唯一 的,我们称该点为树网的中心。 偏心距 ECC(F):树网 T 中距路径 F 最远的结点到路径 F 的距离,即
ECC ( F ) ? max{ d ( v , F ), v ? V } 。

任务:对于给定的树网 T=(V, E,W)和非负整数 s,求一个路径 F,它是某直径上的一 段路径 (该路径两端均为树网中的结点) 其长度不超过 s , (可以等于 s) 使偏心距 ECC(F) , 最小。我们称这个路径为树网 T=(V,E,W)的核(Core) 。必要时,F 可以退化为某个结点。 一般来说,在上述定义下,核不一定只有一个,但最小偏心距是唯一的。 下面的图给出了树网的一个实例。图中,A-B 与 A-C 是两条直径,长度均为 20。点 W 是树网的中心,EF 边的长度为 5。如果指定 s=11,则树网的核为路径 DEFG(也可以取为 路径 DEF) ,偏心距为 8。如果指定 s=0(或 s=1、s=2) ,则树网的核为结点 F,偏心距为 12。

【输入】 输入文件 core.in 包含 n 行: 第 1 行,两个正整数 n 和 s,中间用一个空格隔开。其中 n 为树网结点的个数,s 为树 网的核的长度的上界。设结点编号依次为 1, 2, ..., n。 从第 2 行到第 n 行, 每行给出 3 个用空格隔开的正整数, 依次表示每一条边的两个端点

编号和长度。例如,―2 4 7‖表示连接结点 2 与 4 的边的长度为 7。 所给的数据都是正确的,不必检验。 【输出】 输出文件 core.out 只有一个非负整数,为指定意义下的最小偏心距。 【输入输出样例 1】 core.in 5 2 1 2 5 2 3 2 2 4 4 2 5 3 core.out 5

【输入输出样例 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 core.out 5

【限制】 40%的数据满足:5<=n<=15 70%的数据满足:5<=n<=80 100%的数据满足:5<=n<=300, 0<=s<=1000。边长度为不超过 1000

2008 年

全国信息学奥林匹克联赛(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,上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。

1. 笨小猴
(wird.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 的拼法如图所 示:

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

多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标 (m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向 上或者向左传递。 在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学 都可以帮他们传递, 但只会帮他们一次, 也就是说如果此人在小渊递给小轩纸条的时候帮忙, 那么在小轩递给小渊的时候就不会再帮忙。反之亦然。 还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩 的好心程度没有定义,输入时用 0 表示) ,可以用一个 0-100 的自然数来表示,数越大表示 越好心。 小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条, 即找到来回两条传递路 径,使得这两条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两 条路径。 【输入】 输入文件 message.in 的第一行有 2 个用空格隔开的整数 m 和 n,表示班里有 m 行 n 列 (1<=m,n<=50) 。 接下来的 m 行是一个 m*n 的矩阵,矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生 的好心程度。每行的 n 个整数之间用空格隔开。 【输出】 输出文件 message.out 共一行,包含一个整数,表示来回两条路上参与传递纸条的学生 的好心程度之和的最大值。

【输入输出样例】
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

操作 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; 否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

【输入输出样例 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

2009 年

潜伏者
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:通过内线掌握的信息, 尝试破译密码。然后利用破译的密码,翻译电报中的加密信息。 Input 共 3 行,每行为一个长度在 1 到 100 之间的字符串。 第 1 行为小 C 掌握的一条加密信息。 第 2 行为第 1 行的加密信息所对应的原信息。 第 3 行为 R 国司令部要求小 C 翻译的加密信息。 输入数据保证所有字符串仅由大写字母‘A’-‘Z’构成, 且第 1 行长度与第 2 行相等。 Output 若破译密码停止时出现 2,3 两种情况,请你输出“Failed” (不含引 号,注意首字母大写,其它小写) 。 否则请输出利用密码翻译电报中加密信息后得到的原信息。 Sample Input MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPPYIZ SDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLLFLSO

Sample Output NOIP

Hankson 的趣味题
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 的个数。请你帮助他编程求解这个问题。 Input 第一行为一个正整数 n,表示有 n 组输入数据。接下来的 n 行每行 一组输入数据,为四个正整数 a0,a1,b0,b1,每两个整数之间用一个空格隔 开。输入数据保证 a0 能被 a1 整除,b1 能被 b0 整除。 Output 共 n 行。每组 输入数据的输出结果占一行,为一个整数。

对于每组数据:若不存在这样的 x,请输出 0; 若存在这样的 x,请输出满足 条件的 x 的个数; Sample Input 241 1 96 28895 1 37 1776 Sample Output 62 Hint 第一组输入数据,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。

最优贸易
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。

现在给出 n 个城市的水晶球价格,m 条道路的信息(每条道路所连接的两 个城市的编号以及该条道路的通行情况) 。请你告诉阿龙,他最多能赚取多少 旅费。 Input 第一行包含 2 个正整数 n 和 m,中间用一个空格隔开,分别表 示城市的数目和道路的数目。 第二行 n 个正整数, 每两个整数之间用一个空格隔开, 按标号顺序分别表示这 n 个城市的商品价格。 接下来 m 行, 每行有 3 个正整数, x, y, z, 每两个整数之间用一个空格 隔开。 如果 z=1, 表示这条道路是城市 x 到城市 y 之间的单向道路; 如果 z=2, 表示这条道路为城市 x 和城市 y 之间的双向道路。 Output 共 1 行, 包含 1 个 整数, 表示最多能赚取的旅费。 如果没有进行贸易,则输出 0。 Sample Input 5 54 3 5 6 11 2 11 4 12 3 23 5 14 5 2 Sample Output 5 Hint 输入数据保证 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。

靶形数独
小城和小华都是热爱数学的好学生,最近,他们不约而同地迷上了数独游戏,好 胜的他们想用数独来一比高低。 但普通的数独对他们来说都过于简单了,于是他 们向 Z 博士请教,Z 博士拿出了他最近发明的“靶形数独” ,作为这两个孩子 比试的题目。 靶形数独的方格同普通数独一样,在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格(用粗黑色线隔开的) 。在这个大九宫格中,有 一些数字是已知的, 根据这些数字, 利用逻辑推理, 在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能重复出现,每个数字在每行、每列也不 能重复出现。但靶形数独有一点和普通数独不同,即每一个方格都有一个分值, 而且如同一个靶子一样,离中心越近则分值越高。 (如图)

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

由于求胜心切,小城找到了善于编程的你,让你帮他求出,对于给定的靶 形数独,能够得到的最高分数。 Input 一共 9 行。每行 9 个整数(每个数都在 0—9 的范围内) ,表示一个 尚未填满的数独方格,未填的空格用“0”表示。每两个数字之间用一个空格隔 开。 Output 输出可以得到的靶形数独的最高分数。如果这个数独无解,则输出 整数-1。 Sample Input 7 0 0 9 0 0 0 0 11 0 0 0 0 5 9 0 00 0 0 2 0 0 0 8 00 0 5 0 2 0 0 0 30 0 0 0 0 0 6 4 84 1 3 0 0 0 0 0 00 0 7 0 0 2 0 9 02 0 1 0 6 0 8 0 40 8 0 5 0 4 0 1 2 Sample Output 2829 Hint40%的数据,数独中非 0 数的个数不少于 30。

80%的数据,数独中非 0 数的个数不少于 26。 100%的数据,数独中非 0 数的个数不少于 24。


更多相关文档:

历届noip提高组复赛试题

历届noip提高组复赛试题_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档历届noip提高组复赛试题_学科竞赛_高中教育_教育专区。NOI’95 “同创杯”...

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

2004~2013 年 NOIP 复赛试题集(提高组) 第十届全国信息学奥林匹克分区联赛(NOIP2004)复赛试题(提高组 竞赛用时:3 小时) 1、津津的储蓄计划(Save.pas/dpr/c...

NOIP2013提高组复赛试题

全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 1.转圈游戏 (circle.cpp/c/pas) 【问题描述】 ...

NOIP2014提高组复赛试题

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...

NOIP2015提高组复赛试题Day1

全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目...

NOIP2014提高组复赛试题

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

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

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

NOIP2015提高组复赛试题Day2

全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day2 (请选手务必仔细阅读本页内容)一.题目概况中文题目...

NOIP2014提高组复赛试题day1+day2

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

NOIP2016提高组复赛试题(Day1+Day2)

NOIP2016提高组复赛试题(Day1+Day2)_IT/计算机_专业资料。NOIP2016提高组复赛试题 第22 届全国青少年信息学奥林匹克联赛 CCF-NOIP-2016 提高组(复赛) 第一试...
更多相关标签:
noip提高组复赛试题 | noip2016提高组复赛 | noip2015提高组复赛 | noip2014提高组复赛 | noip2010提高组复赛 | noip2016复赛试题 | noip2012提高组复赛 | noip2013提高组复赛 |
网站地图

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