当前位置:首页 >> 学科竞赛 >>

NOIP复赛谈


NOIP 复赛谈
? 复赛的命题
1. 准循大纲:考察常用的数据结构和基本算法; 2. 考察能力:包括阅读理解能力、构建数学模型的能力、程序编码与调试能力、程序 的时空性能分析和测试数据的生成能力、各种知识的综合应用能力等; 3. 有区分度:4 题,复赛题目的特点是:2 题算法和数据结构比较明显、或者和数学 关系比较大的题目,得率比较高;1 题好上手,但程序量

要大一点或数据规模大的 题目,考虑全面、得满分也不容易;还有 1 题一般是搜索、或者算法不明显、或者 用到复杂高深一点的数据结构的题目,难度较大。但顺序不一定! ! ! 新大纲: 复赛的题型和考试形式与 NOI 类似,全部为上机编程题,但难度比 NOI 低。 题目包括 4 道题,每题 100 分,共计 400 分。 每一试题包括:题目、问题描述、输入输出要求、样例描述及相关说明。 测试时,为每道题提供了 5-10 组测试数据,选手程序每答对一组得 10-20 分, 累计分即为该道题的得分。

? 如何备战复赛
1. 做做以往历年的竞赛题和网上的模拟题,熟悉比赛的题型和要求,找出自己的不 足,加强训练; 2. 增强自己编写代码和调试的熟练程度,提高做题的时间和节奏感; 3. 熟练掌握文件的输入/输出操作,新大纲中对复赛的要求; 4. 提高自己设计测试数据的能力; 5. 提高自己做题的正确率(分数/时间) ; 6. 算法方面:递推、递归、动态规划、贪心、搜索(初中到回溯就差不多了)基本 上是必考! ! !对一些经典问题和算法,一定要熟练的不能再熟练; 7. 数据结构方面:字符串经常考,树(尤其二叉树) 、图的基本算法(最短路径、最 小生成树等) ;

? 复赛注意事项
1. 认真审题,尤其要注意问题的规模(数据范围) ,从某种意义上说,问题规模也 暗示了你可能的算法。数据小,也许是搜索派上用场的时候;数据大了,可能 只能考虑动态规划,数学方法等高算法了。 正确的估计题目的难度和自己的水平。拿到试题后先从总体上分析一下题目, 做到心中有数!注意:题目的难易对所有人是公平的,只要最大限度地发挥自 己的水平,不要有包袱,考出自己的最佳成绩。

2.

3. 4. 5.

正确地选择题目去做 (最擅长、 最简单的先完成) , 合理地安排时间和解题顺序。 复赛中:一定提高正确率! ! !解题速度是其次。 复赛考查的算法并不困难,选手在实现上的问题往往要多一些。建议大家: 1) 充分利用草稿纸, 不要对自己的 “心算能力” 太自信! 编程熟练的同学喜欢 “一 气呵成” ,拿到题目就开始编码。我认为这样不好,做信息学竞赛题的思维过 程是丰富而曲折多变的,考虑问题必须全面,仅凭一时的“感觉”来编程往往 是漏洞百出。比如初学者常常忘记做一些初始化工作(远不止变量赋初值这种 最简单的) ,即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要 命的是“第一感觉”的算法是错误的或者效率太低(命题者的陷阱) ,而程序 编了大半才发现,时间浪费了不说,还影响了信心和发挥。 2) 做一些复杂的题目,编码采取自顶向下,逐步求精的方法,调试时采用输出中 间结果的办法及时找出错误的地方。可以这么说,思路越清晰,对自己程序的 算法和编码越了解,调试也会越顺利(一定不要忽视这一点) 。 3) 多测试:样例数据、极限(小大)数据、特殊数据,分析能否在规定的时空范 围内出解,精度是否够,格式是否对,输入输出文件名、格式是否正确等。 4) 不一定要拿满分,有些题目如果你很拿手,也肯定能做对,那么一定要保证拿 满分;但有些题目,在有限的竞赛时间里,你很难拿满分,或者自己觉得没有 足够的时间和信心, 没有好的方法, 那么在很少的时间内用投机取巧的方法 (如 贪心等)能得到不错的分数,也是一种很大的成功。

? 历年复赛题目分布如下(1997 年以来)
题目 1997-c1 1997-c2 1997-c3 1997-g1 1997-g2 1997-g3 1998-c1 1998-c2 1998-c3 1998-g1 1998-g2 1998-g3 数矩形 数字三角形 数路径 素数方阵 表达式判错 骑士游历 1:2:3 S! 2 的幂次方 上下车问题 连接多位数 加法表 名称 算法 数学(乘法原理) 穷举 递推(迭代)+加法原理+高精度 递归回溯+构造 字符串+栈 宽搜+递推 穷举 高精度 递归+二进制 递推或者枚举 贪心+字符串 递归+直接判断 参考难度 * * *** ** ** ** * * *** * ** ***

1999-c1

Cantor 表

数学 字符串 贪心 动态规划、贪心 搜索+优化 字符串 数学或穷举 动态规划+高精度 回溯 类比+穷举 动态规划 递归或递推或动态规划 穷举+优化+乘法原理 递归或穷举,构造 宽搜+hash 表,或动态规划 穷举或随机化+迭代 递推或动态规划 贪心或随机化或动态规划 图论(Dijkstra 算法) 高精度 搜索(递归) 乘法原理+图论 递推+加法原理+高精度 数学 广搜(双向)+剪枝 物理题 搜索

* ** *** ** *** * ** *** ** ** *** * ** ** *** ** ** *** *** * *** *** ** ** *** ** ****

1999-c2/g2 回文数 1999-c3/g3 旅行家的预算 1999-g1 1999-g4 2000-c1 2000-c2 导弹拦截 邮票面值设计 计算器的改良 税收与补贴问题

2000-c3/g2 乘积最大 2000-c4/g3 单词接龙 2000-g1 2000-g4 2001-c1 2001-c2 2001-c3 2001-c4 2001-g1 2001-g2 2001-g3 2001-g4 2002-c1 2002-c2 2002-c3 2002-c4 2002-g1 2002-g2 2002-g3 2002-g4 进制转换 方格取数 数的计数 最大公约数与最小公倍数 二叉树的先序序列 装箱问题 一元三次方程求解 数的划分 统计单词个数 Car 的旅行路线 级数求和 选数 产生数 过河卒 均分纸牌 字串变换 自由落体 矩形覆盖

归纳:递推、动态规划、贪心、搜索、数学(物理) 、图论、高精度、回溯、穷举、字符串

? 复赛试题分析
1.递推(2002 年初中组 4:过河卒)
[问题描述] 棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。 同时在棋盘上的任一点有一个对方的马(如 C 点) ,该马所在的点和所有跳跃一步可达的点 称为对方马的控制点,如图中的 C 点和 P1,??,P8,卒不能通过对方马的控制点。棋盘 用坐标表示,A 点(0,0)、B 点(n, m) (n,m 为不超过 20 的整数),同样马的位置坐标是需要 给出的,C≠A 且 C≠B。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

[问题分析] 跳马是一道老得不能再老的题目,我想每位编程初学者都学过,可能是在学回溯或搜 索等算法的时候,很多书上也有类似的题目,一些比赛中也出现过这一问题的变形(如 NOIP1997 初中组的第三题) 。 有些同学一看到这条题目就去搜索, 即使你编程调试全通过了, 运行时你也会发现:当 n,m=15 就会超时。 其实,本题稍加分析就能发现,要到达棋盘上的一个点,只能从左边过来(我们称之 为左点)或是从上面过来(我们称之为上点) ,所以根据加法原理,到达某一点的路径数目, 就等于到达其相邻的上点和左点的路径数目之和,因此我们可以使用逐列(或逐行)递推 的方法来求出从起点到终点的路径数目。障碍点(马的控制点)也完全适用,只要将到达 该点的路径数目设置为 0 即可。 用 F[i,j]表示到达点(i,j)的路径数目,g[i,j]表示点(i, j)有无障碍,g[i,j]=0 表 示无障碍,g[i,j]=1 表示有障碍。

则,递推关系式如下: F[i,j] = F[i-1,j] + F[i,j-1] {i>0 且 j>0 且 g[x, y] = 0} 递推边界有 4 个: F[i,j] = 0 { g[x,y] = 1 } F[i,0] = F[i-1,0] {i > 0 且 g[x,y] = 0} F[0,j] = F[0,j-1] {j > 0 且 g[x,y] = 0} F[0,0] = 1 考虑到最大情况下: n=20,m=20, 路径条数可能会超过 MaxLongInt,所以要用高精度 (使 用 Comp 类型计数即可) 。 程序:见文件夹。

例 1、递推举例:储油点
[问题描述] 一辆重型卡车欲穿过 1000 公里的沙漠,卡车耗油为 1 升/公里,卡车总载油能力为 500 公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个贮油点,使 卡车能顺利穿越沙漠,试问司机如何建立这些贮油点?每一贮油点应存多少汽油,才能使 卡车以消耗最少汽油的代价通过沙漠? 编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。 No. distance(k.m.) oil(litre) 1 ×× ×× 2 ×× ×× 3 ×× ×× [问题分析] 设 dis[i]─第 i 个贮油点至终点(i=0)的距离;oil[i]─第 i 个贮油点的存贮油量。 我们可以用倒推法来解决这个问题。从终点向始点倒推,逐一求出每个贮油点的位置 及存油量。下图表示倒推时的返回点。 终点 始点 └───────────┬──┬──────────────┬┘ i=0 i=1 i=2 ? ?i=n 从贮油点 i 向贮油点 i+1 倒推的策略是,卡车在点 i 和点 i+1 间往返若干次。卡车每 次返回 i+1 处时正好耗尽 500 公升汽油,而每次从 i+1 处出发时又必须装足 500 公升汽油。 两点之间的距离必须满足在耗油最少的条件下使 i 点贮足 i*500 公升汽油的要求(0≤i≤ n-1)。具体地讲,第一个贮油点 i=1 应距终点 i=0 处 500km 且在该处贮藏 500 公升汽油, 这样才能保证卡车能由 i=1 处到达终点 i=0 处,这就是说:dis[1]=500;oil[1]=500。为 了在 i=1 处贮藏 500 公升汽油,卡车至少从 i=2 处开两趟满载油的车至 i=1 处。所以 i=2 处至少存贮 2*500 公升汽油,即 oil[2]=500*2=1000。另外,再加上从 i=1 返回至 i=2 处的 一趟空载,合计往返 3 次。三次往返路程的耗油量按最省要求只能为 500 公升,即 d1,2 =

500 km。 3
dis[2]=dis[1]+d1,2 =dis[1]+

500 3

为了在 i=2 处贮存 1000 公升汽油, 卡车至少从 i=3 处开三趟满载油的车至 i=2 处。 所 以 i=3 处至少存贮 3*500 公升汽油,即 oil[3]=500*3=1500。加上 i=2 至 i=3 处的二趟返程 空车,合计 5 次。路途耗油量亦应 500 公升,即 d2,3 = dis[3]=dis[2]+d2,3 =dis[2]+

500 km。 5

500 5

依次类推,为了在 i=k 处贮藏 k*500 公升汽油,卡车至少从 i=k+1 处开 k 趟满载车至 i=k 处, 即 oil[k+1]=(k+1)*500=oil[k]+500,加上从 i=k 返回 i=k+1 的 k-1 趟返程空车, 合计 2*k-1 次。这 2*k-1 次总耗油量按最省要求为 500 公升,即 dk, k+1= dis[k+1]=dis[k]+dk,k+1 =dis[k]+

500 km。 2 * k ?1

500 2 * k ?1

最后, i=n 至始点的距离为 1000-dis[n],oil[n]=500*n。为了在 i=n 处取得 n*500 公升汽油, 卡车至少从始点开 n+1 次满载车至 i=n,加上从 i=n 返回始点的 n 趟返程空车, 合计 2*n+1 次, 2*n+1 趟的总耗油量应正好为 (1000-dis[n])*(2*n+1) ,即始点藏油为 oil[n]+(1000-dis[n])*(2*n+1)。 由此得出如下的程序框架(程序略) : begin k:=1;d:=500; { 从 i=1 处开始向始点倒推} dis[1]:=500;oil[1]:=500; repeat k:=k+1;d:=d+500/(2*k-1); dis[k]:=d;

oil[k]:=oil[k-1]+500; until d>=1000; dis[k]:=1000; {置始点至终点的距离值} d1:=1000-dis[k-1]; {求贮油点 k 处至始点的距离} oil[k]:=d1*(2*k+1)+oil[k-1]; {求始点藏油量} for i:=0 to k do 输出第 i 个贮油点的距离为 1000-dis[k-i],藏油量为 oil[k-i]; end. 程序:见文件夹。

2. 动态规划(2000 年初中组 3/高中组 2: 乘积最大)
[问题描述] 今年是国际数学联盟确定的“2000——世界数学年” ,又恰逢我国著名数学家华罗庚先 生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活 动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样 一道题目: 设有一个长度为 N 的数字串,要求选手使用 K 个乘号将它分成 K+1 个部分,找出一种 分法,使得这 K+1 个部分的乘积能够为最大。 同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子: 有一个数字串:312, 当 N=3,K=1 时会有以下两种分法: 3*12=36 31*2=62 这时,符合题目要求的结果是:31*2=62 现在,请你帮助你的好朋友 XZ 设计一个程序,求得正确的答案。 [输入] 程序的输入共有两行: 第一行共有 2 个自然数 N,K(6≤N≤40,1≤K≤6) 第二行是一个长度为 N 的数字串。 [输出] 结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数) 。 [样例输入] 4 2 1231 [样例输出] 62 [问题分析] 首先,由于问题的规模为 6<=N<=40,1<=K<=6,要在长为 N 的数字串中插入 K 个乘号使 得乘积最大,显然将会超出长整数的范围,所以运算要用高精度乘法。 其次,让我们考虑穷举的方法行不行,由组合数学知识知道:在长为 N 的数字串中插 入 K 个乘号的方案有 C(N-1,K)种,极限数据等于 6500000 种插入方案,而高精度本身也 很费时间,所以穷举算法肯定会超时。看来只有找动态规划这样的高效算法了! ! ! 那么如何使用动态规划呢?分析发现:问题中只有乘号插入的位置是变化的,取数字

串中的任意一段(P1 到 P2)来考虑,若能求出在其中插入 K-1 个乘号的最大乘积,则只需 穷举第 K 个乘号的插入位置 P(P 从初始的 P1+K-1 开始插入,最多插入到 P2-1 后) 。该乘 号把数字串分成了两段,前半段包含 K-1 个乘号(其最大值已经算出) ,将它的值与后半段 的值相乘得到第 K 个乘号在位置 P 时的最大乘积。打擂台选出 P 在各个位置时得到的最大 乘积即为问题的解。 依此类推,把 K-1 的问题归结为 K-2 的情况,??,直到求在任意一段中插入 1 个乘 号的最大乘积时,需预先算出在任意一段中插入 0 个乘号时的最大乘积。而此时的值是已 知的(即为该段的数值) 。假设 C[p1,p2,K]表示在长为 N 的数字串中,从第 p1 个数字到第 p2 个数字之间插入 K 个乘号的最大乘积,动态转移方程如下: p2-1

C[p1,p2,k] =

MAX (C[p1,p,k-1] * C[p+1,p2,0])

P=p1+k-1 假设输入的数字已保存在 d[1..n]中(n<=maxn=40) ,定义三维数组 max 存放结果,即: var max:array[1..maxn,1..maxn,0..maxn-1] of byte;其中 max[i,j,0]到 max[i,j,maxn-1] 存放任意一段的最大乘积。则,动态规划的初始化工作如下: for i:=1 to n-1 do for j:=i to n do begin for m:=0 to maxn-1 do max[I,j,m]:=0; {清 0} w:=0; {记录高精度数的有效位数} for m:=j downto I do begin {高精度数的初始化} max[I,j,w]:=d[m]; w:=w+1; end; end; 程序:见文件夹。

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

接下来的 p 行,每行均有 20 个字符。 再接下来有一个正整数 s,表示字典中单词个数。 (1≤s≤6) 接下来的 s 行,每行均有一个单词。 [输出格式] 结果输出至屏幕,每行一个整数,分别对应每组测试数据的相应结果。 [输入输出样例] 输入:1 3 t h i s i s a b o o k y o u a r e a o h 4 is a ok sab

输出:7
[问题分析] 首先,通过分析可以得出下面的结论:当给定的字符串中以同一个字母开头的单词有多 个时,只须选用最短的一个,因为该单词受分段的影响最小,所以可以设数组 shortest 存储 给定的字符串中所有位置上的最短单词的长度,shortest[i]=0 表示给定的字符串中从第 i 个字符开始的一段不包含任何单词,否则表示从该位置起包含的最短的单词的长度。 另外, 为了方便处理,可以将所有单词按从短到长的次序重新排序,并引入二维数组 pos 记录单词在给定的字符串中的分布情况,pos[i,j]=true 表示在给定的字符串中从第 i 个字 符开始包含第 j 个单词。 算法上可以从以下几个方面考虑: 1、贪心法 毎次根据数组 shortest 选定一个分段位置使得被截断的最短单词最少,将这些被截断 的最短单词从数组 shortest 中去除,重复上述过程,直到将给定的字符串分成 k 段为止; 2、随机化算法 用随机的方法将给定的字符串分成 k 段,统计毎一段中包含的单词数,全部段包含的单 词总数即为问题的一个解,多次随机直到限定时间用完为止,此时输出最优解; 3、结合以上两种方法; 4、动态规划 substr(b,e)表示给定字符串中从第 b 个字符到第 e 个字符为止的子串,用数组 most 记 录给定字符串中从第一个字符到任意一个字符为止的子串被分成 i 段后包含的最多单词数, 如 most[i,t] 表 示 子 串 substr(1,t) 分 成 i 段 后 包 含 的 最 多 单 词 数 , 则 most[i+1,j]=max(most[i,t]+maxword(substr(t+1,j))),t=i..j-1,其中 maxword 为求某字 符串中最多单词的函数,程序中没有用二维数组,去掉了第一维,递推时下标要从大往小推, 类似于杨辉三角用一维数组递推。 程序:见文件夹。

3. 字符串(1998 年高中组 2: 连接多位数)
[问题描述]

设有 n 个正整数(n≤20) ,将它们联接成一排,组成一个最大的多位整数。 例如:n=3 时,3 个整数 13,312,343 联接成的最大整数为:34331213 又如:n=4 时,4 个整数 7,13,4,246 联接成的最大整数为:7424613 程序输入:n n 个数 程序输出:联接成的多位数 [问题分析] 举例说明正常的字符串比较缺陷!如:A=’321’,B=’32’,按照标准的字符串比较 规则因为 A>B,所以 A+B > B+A ,而实际上’32132’< ’32321’。 所以,自定义一种字符串的比较规则:即如果 A+B>B+A,则我们认为 A>B。且可以证明: 如果 A+B>=B+A,B+C>=C+B,则一定有:A+C>=C+A。 这样一来,程序就很简单了。分 3 步,先把 n 个数字转换成字符串存储;再按照自定 义的规则把 n 个字符串排序;最后按照从大到小的顺序输出这些字符串。 小结:有些问题看起来是数学问题,认真分析会发现用字符串处理很简单。另外,一 定要掌握有关字符串的各种函数,以免用到时自己编子程序。 程序:略。

4.贪心(删数问题)
[问题描述] 键盘输入一个高精度的正整数 n(小于等于 240 位) ,去掉其中任意 s 个数字后,剩下 的数字按原次序将组成一个新的正整数。编程对给定的 n 和 s,寻找一种方案,使得剩下的 数字组成的新数最小。 [输入格式] n s [输出格式] 顺序列出 s 个被删去的数字。 [算法分析] 首先,这是一个高精度数。但是否一定用数组存放这个数呢?这要看具体的算法实现。 由于正整数 n 的有效数位为 240 位,因此我们采用字符串类型存贮 n。 为了尽可能逼近目标,我们的“贪心策略”是:每一步总是选择一个使剩下的数最小 的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删最大(最后)的数字; 否则删第一个递减区间的首字符,这样便形成了一个新数串。然后回到串首,按上述规则 删下一个数字,??,依次类推,直到删除了 s 个数字为止,输出剩余部分即可。 例如:n=‘1 7 8 5 4 3’ s=4 删数过程如下: n=‘1 7 8 5 4 3’ 删‘8’ ‘1 7 5 4 3’ 删‘7’ ‘1 5 4 3’ 删‘5’ ‘1 4 3’ 删‘4’ ‘1 3’

这样删数问题与“如何寻找递减区间首字符”这样一个简单的问题对应起来。按贪心 策略编制的程序框架为: begin 输入 n,s; while s>0 do begin i:=1; {从串首开始找} while (i<length(n)) and (n[i]<=n[i+1]) do i:=i+1; delete (n,i,1); {删除字符串 n 的第 i 个字符} s:=s-1; end; while (length(n)>1)and (n[1]=‘0’) do delete(n,1,1); {删去串首的无用零} 输出 n; end. 程序:略。

例 3、贪心举例:取数游戏
[问题描述] 给出 2*n 个自然数。游戏双方分别为 A 方(计算机方)和 B 方(对奕的人) 。只允许从 数列两头取数。 A 先取, 然后双方依次轮流取数。 取完时, 谁取得的数字总和最大为取胜方; 双方和相等,属于 A 胜。试问 A 方可否有必胜的策略 [输入] 2*n 个自然数 [输出] 前 2*n 行为游戏经过。每两行分别为 A 方所取的数和 B 方所取的数,其中 B 方取数时 应给予提示,让游戏者选择取哪一头的数(L/R—左端或右端) 。最后一行分别为 A 方取得 的数和和 B 方取得的数和。 [问题分析] 设自然数列:7 9 3 6 4 2 5 3 我们设计一种方案,从数大的一头让 A、B 轮流取两个连续数: A 方:7 3 4 5 B 方:9 6 2 3 由此得出: A 方取得的数和为 7+3+4+5=19 B 方取得的数和为 9+6+2+3=20 按照规则,判定 A 方输。虽然 A 方败给 B 方,但是我们却发现了一个有趣的事实:A 方 取走偶位置的数后,剩下两端数都处于奇位置;反之,若 A 方取走奇位置的数后,剩下两 端数都处于偶位置。即无论 B 方如何取法,A 方即可以取走奇位置的所有数,亦可以取走偶 位置的所有数。由此萌发一种“贪心策略” :让 A 方取走“数和较大的奇(或偶)位置上的 所有数” ,则 A 方必胜。这样,取数问题便对应于一个简单问题:让 A 方取奇偶位置中数和 较大的一半数。设 j 为 A 取数的奇偶位置标志,则:

?0 j?? ?1

偶位置数和较大, A取偶位置的所有数 奇位置数和较大, A取奇位置的所有数

设 SA,SB 分别表示 A 方取数和,B 方取数和(SA≥SB) ;a 存储 2*n 个自然数序列;lp, rp 为序列的左端位置和右端位置;ch 为 B 方取数的位置信息(’L’或’R’ ) ;则,程序框 架如下: begin SA:=0;SB:=0; {计算 A 方取数和、B 方取数和,A 方取数的位置标志} for i:=1 to n do begin SA:=SA+a[2*i-1];SB:=SB+a[2*i]; end; if SA>=SB then j:=1 else begin j:=0;交换 SA 和 SB;end; lp:=1;rp:=2*n; for i:=1 to n do {A 方和 B 方依次进行 n 次对奕} begin if ((j=1) and (lp mod 2=1)) or ((j=0)and (lp mod 2=0)) {若 A 方应取奇位置数且左端位置为奇, 或者 A 方应取偶位置数且左端位置为偶, 则 A 方取走左端位置的数} then begin 输出 A 方取 a[lp];lp:=lp+1;end else begin 输出 A 方取 a[rp];rp:=rp-1;end;{否则 A 方取走右端位置的数} 输出提示信息:B 方的取数位置(L/R) ; repeat 读 ch; if ch=‘L’ then begin 输出 B 方取 a[lp];lp:=lp+1;end; if ch=‘R’ then begin 输出 B 方取 a[rp];rp:=rp-1;end; until ch ? {‘L’ , ’R’}; end; 输出 A 方取数的和 SA 和 B 方取数的和 SB; end. 程序:略。

5.穷举(2000 年高中组 1:进制转换)
[问题描述] 我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该数字所 处位置的(值减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 1 0 110001=1*(-2) + 1*(-2) + 0*(-2) + 0*(-2) + 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) [问题分析] 其实,本题拿到手的第一个想法是进制转换的常规方法“除 R 取余,除尽为止,倒取 输出” ,但当你用一个样例去试的时候,发现毫无规律(如果有的人习惯不好,拿到手自以 为是,不喜欢用草稿纸,则会沿着死路往前走) 。 其实,分析一下问题的规模 N(注意这是第 1 题) ,-32767-32768! ! !穷举。对任一个 -R 进制数 k(从 0 开始),计算它对应的十进制数是多少,如果等于 N,则输出这个-R 进制 数,否则继续找下一个-R 进制数。 思考:-R 进制数好象没有符号位哎: ) 程序:见文件夹。

6.简单搜索、回溯(1999 年高中组 4:邮票面值设计)
[问题描述] 给定一个信封,最多只允许粘贴 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 OUTPUT N=3 K=2 1 3 MAX=7 [问题分析] 首先,看数据规模 n+k<=40,显然很大,所以有的选手想用动态规划,但注意本题具有 明显的后效性(前面方案的不同使得构成某面值的邮票数不同) ,所以不满足动态规划的条 件。 那么,解决这类问题只能用递归搜索了。但很快有人发现:搜索所能解决的问题规模 远远达不到题目的要求,一般搜索到 n,k 同时超过 6,就不行了。而实际的测试数据也就到 n=10,k=5,且 n+k<13。 所以,我们总结出分区联赛的题目难易程度,其实和数据规模(尤其是实际测试数据) 息息相关。有的题目很难,但实际的测试数据很简单(小) ;而有的题目算法和思想很简单, 但数据规模巨大。如果题目难度大且测试数据很刁钻、很大,那么得分率就会极低,这时 就相当于去掉这一题比赛(比如 2002 高中组的矩形覆盖问题) 。这种题目这几年基本上是 用搜索!所以,选手做题时应充分估计 4 个题目的难度和命题人的命题动机。对难度小的、 有把握的要拿满分;对于难度大,但小数据能很容易算出的要把该拿的分拿住;对于自己 能力以外的,不要浪费宝贵的时间(记住:评奖的原则是名次,而不是分数和哪一条题目) 。 回到原题中来,首先面值为 1 的邮票是必须的;此后每加进一种面值都要把当前所能 取得的金额记下来。通过 k-1 次添加得到一种方案。穷举所有的方案得到最优解。 在搜索的过程中,对数据的记录方式很关键。如果仅仅记录一个金额能否被达到,则 这样的记录基本上没有用,因为下一次添加邮票时,不知能否从这个金额出发再加上新邮 票,推导出达到哪些新面值,必须全部重算,浪费了大量时间;所以,我们记录最少要用 几张邮票达到一个面值,这样有利于添加新邮票时迅速判断可行性。 搜索一种新邮票面值的起点(即新邮票的选择策略)应该是:从上一个面值加 1 开始, 直到当前连续取得的最大金额加 1。因为过大会造成不连续,过小得不到最优解。 程序:见文件夹。

7.搜索+剪枝优化+构造(1997 年高中组 1:素数方阵)
[问题描述] 在 N*N 的棋盘上(1≤N≤10) ,填入 1,2,?,N*N 共 N*N 个数,使得任意两个相邻的 数之和为素数。 例如:当 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! ” 。 [问题分析] 由于素数的变换是没有规律的,本题只能搜。因为 N 的值是从 1 到 10 的之间的任意一 个自然数,每个方格中的数字不相同,所以采用递归回溯的方法实现。具体讲,就是将所 有方格编一个次序,根据“如有多种解,则输出第一行、第一列之和为最小的排列方案“这 句话,填数的顺序应是先填第一行第一列(1) ,以后选择填入的数应该从小到大依次选择, 首先选一个 2 到 N*N 之间的自然数填入第一行第二列,要求填入的数与已填的相邻方格中 的数之和为素数;然后再用相同的方法填第一行的第三列到第 N 列,填完第一行后,再依 次填第一列中的第二行到第 N 行。依此类推,再填第二行的第二列到第 N 列,再填第二列 的第三行到第 N 行,??,直到右下角最后一个数填好为止(再按要求输出) 。 在填数的过程中有几个要求: 一要保证填入的数没用过 (很简单, 设一个 used[1..n*n], 值为布尔型) ;二是当前格子选不到数填时要回溯,??,直到所有情况都搜索到了(回溯 的控制) ;三是判断填入的数是否合法(类似于 N 皇后问题的判断合法性) 。 对于第三个问题,如果每填入一个数,都要判断它与上方和左方的格子中的数之和是 否为素数,效率会很低。所以想到了用构造(查表)法判断素数。因为任意一个格子的最 大数为 N*N,所以相邻两个格子的数之和最大为 2N*N。即把 1 到 2N*N 中的素数求出来保存 好(200 以内的素数太简单了) ,然后每次判断只要查表了。 小结:1.素数总是一奇一偶的和,所以,行列上肯定是奇数偶数相隔的,优化? 2.如果去掉 a[1,1]=1 这个约定,则发现:只有当 a[1,1]中填奇数时问题才有可 能有解,为什么?因为 1..n*n 个数中奇数的个数一定大于等于偶数的个数,再结合 1。 3.求所有解及总数。 程序:见文件夹。

(完)


相关文章:
NOIP复赛谈
NOIP复赛谈_计算机软件及应用_IT/计算机_专业资料。NOIP 复赛谈 ? 复赛的命题 1. 准循大纲:考察常用的数据结构和基本算法; 2. 考察能力:包括阅读理解能力、构建...
NOIP复赛谈
NOIP复赛谈_学科竞赛_高中教育_教育专区。NOIP 复赛谈 ? 复赛的命题 1. 准循大纲:考察常用的数据结构和基本算法; 2. 考察能力:包括阅读理解能力、构建数学模型...
NOIP复赛谈
NOIP复赛谈 15页 2财富值 NOIP2011普及组复赛试题 5页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
NOIP复赛谈
16页 免费 NOIP复赛谈 2页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 NOIP复赛谈 NOIP复赛谈NOIP复赛谈隐藏>...
NOIP复赛经验漫谈
NOIP200-2009提高组复赛_回... 3页 1财富值 tyvj部分题解 191页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反...
NOIP复赛谈天津名师
33页 免费 NOIP辅导骗分 6页 免费 NOIP复赛谈 16页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
NOIP2015提高组复赛试题Day1
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目...
第十届NOIP复赛试题及答案
NOIP复赛谈 7页 免费 (信息学奥赛辅导)程序设计... 51页 免费 历届NOIp动态规划梳理 54页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建...
NOIP2014普及组复赛试题解答
NOIP2014普及组复赛试题解答_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 NOIP2014普及组复赛试题解答_学科竞赛_初中教育_教育专区。NOIP2014...
NOIP复赛注意事项
NOIP复赛注意事项_IT/计算机_专业资料。NOIP复赛注意事项NOIP 复赛注意事项 1、做...NOIP复赛谈 15页 1下载券 NOIP复赛模拟卷(六) 5页 1下载券喜欢...
更多相关标签:
noip2016提高组复赛 | noip2016普及组复赛 | noip2015提高组复赛 | noip2016复赛成绩 | 2016noip复赛成绩查询 | noip2016复赛 | noip2015普及组复赛 | noip2016复赛名单 |