tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

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财富值 NOIP复赛谈天津名师 9页 2财富值 NOIP初赛谈 29页 免费 NOIP初赛谈1 29页 免费 noip复赛 2页 免费 NOIP复赛题集 11页 5财富值 ...


NOIP复赛经验漫谈

NOIP200-2009提高组复赛_回... 3页 1财富值 tyvj部分题解 191页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反...


NOIP复赛

NOIP复赛谈 7页 免费 (信息学奥赛辅导)程序设计... 51页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


第十届NOIP复赛试题及答案

NOIP复赛谈 7页 免费 (信息学奥赛辅导)程序设计... 51页 免费 历届NOIp动态规划梳理 54页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建...


noip

NOIP初赛谈 29页 免费 noip复赛 2页 免费 NOIP初赛复习 53页 1下载券 NOIP复赛...第 10 页共 110 页 全国信息学奥林匹克联赛 复赛 提高组 哈师大附中信息学...


NOIP学习内容

noip 8页 2下载券 NOIP 12页 免费 noip 58页 1下载券 NOIP初赛谈 29页 免费 NOIP初赛辅导 69页 1下载券 NOIP初赛 9页 2下载券 noip复赛 2页 免费 NOIP...


NOIP复赛模拟试卷(三)

noip普及组初赛模拟试卷 3页 1财富值 2107_【NOIP复赛模拟题(三... 暂无评价 5页 5财富值 noip复赛 2页 免费 NOIP复赛 6页 免费 NOIP复赛谈 2页 2财富值...


Noip备考全攻略

NOIP初赛谈 29页 免费 NOIP初赛 9页 5财富值 NOIP初赛辅导 69页 1财富值 noip复赛 2页 免费 NOIP复赛谈 16页 1财富值喜欢此文档的还喜欢 ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com