奥赛经典题目讲解

巧用数组下标轻松回避重复判断

[作者：佚名转贴自：网络点击数：68文章录入：kknd]

在程序设计的某个环节中，需要统计不同数据的个数，按照常规思路的算法简单描述如下：

①读入下一个数；

②将该数与之前已读入的数一一比较，如果都不同，则该数是新数，累加器加1;否则，表示该数是

旧数，有重复，直接退出比较的循环②。

③是否读完所有数据，如果是，输出累加器值，结束；否则，转到①；

下面用一个实例说明。

例产生10个范围为1—20的随机整数，统计不同数的个数。

按照常规思路，得如下参考程序。

programtongji(input,output);

var

a:array[1..10]ofinteger;

i,j,t:integer;

begin

writeln。产生随机数:)；

randomize;

fori:=1to10do

begina[i]:=l+random(19);write(Jend;

t:=0;

fori:=1to10do

begin

j：=l；

while(j<i)and(a[i]Oa[j])doj:=j+1;

ifj=ithent:=t+l;

end;

writeln;writeln(，统计不同数据有个二)；

end.

由以上程序可知，完成数据统计需要两重循环，时间复杂度为O(n2)。如果数据是正整数，那么试着

换另外一种思路：将数据作为数组的下标，进行一个赋值为1的标记操作。比如，现有数：2,6,2,

用数组b口辅助存储，依次操作：b[2]:=1,b[6]:=1,接下来是2,已重复，在程序中无需特殊判断，

执行相同操作：b[2]:=1,这样就可以有效回避重复判断，最后只要累计b[]数组中值为1的个数，事

实上，数组中其他元素由于没有进行赋值操作，保留了默认值0,因此累加操作也可以扩展到所有数

组元素的直接相加，为了更有效的累加，可以在执行赋值操作时，加入数据范围的上限、下限标识：

max和min,每读入一个数后，更新数据范围，最后只要将下标为上下限范围的数组数据进行累加。

参考程序如下：

programtongji(input,output);

var

a:array[1..10]ofinteger;

b:array[1..20]ofinteger;

i,t,max,min:integer;

begin

wiitelnC产生随机数

randomize;

fori:=1to10do｛产生10个(1-20)随机数｝

begina[i]:=l+random(19);write,end;

t:=0;max:=0;min:=10000;｛设置统计时，数组范围的上下标识｝

fori:=1to10do

begin

"a叩:=1；｛将数据以数组下标的形式写入，避免判断｝

ifa[i]>maxthenmax:=a[i];｛更新数组范围的上下标识｝

ifa[i]<minthenmin:=a[i];

end;

fori:=mintomaxdot:=t+b[i];｛统计不同数据个数｝

writein;writeln。统计不同数据有X'个

end.

如果程序要求将个数统计结果分别显示，如

输入：262；

输出：2:26:1

2

其中输出第1行分别显示每个数的统计情况，第2行统计数据有几个。

要统计每个数的数量情况，在将数据以数组下标的形式写入时，不能直接赋1操作，需执行累加，

以为该数进行统计；这个操作对统计不同数据的总个数发生了变化，因此统计时将原来的直接累加,

变为判断非0后，再累加1完成。改变部分的代码如下：

t:=0;max:=O;min:=10000;｛设置统计时，数组范围的上下标识｝

fori:=1to10do

begin

b[a[i]]:=b[a[i]]+l;

ifa[i]>maxthenmax:=a[i];

ifa[i]<minthenmin:=a[i];

end

fori:=mintomaxdo

ifb[i]<>0then

beginwrite(i,':',b[i]');t:=t+1;end;｛统计不同数据个数｝

writein;writeln(t);

时间复杂度由原来的0(n2)降低为0(n)»

编程时，不妨抛开传统解题思路，尝试着用其他方法解决，一个小小的数据统计程序，或许可以给

你些许启迪，愿本文起到抛砖引玉的作用。

历届NOIP搜索算法全集

用动态规划来解背包问题

在历届NOIP竞赛中，有4道初赛题和5道复赛题均涉及到背包问题，所谓的背包问

题，可以描述如下：一个小偷打劫一个保险箱，发现柜子里有N类不同大小与价值

的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷

选择所偷物品的组合，以使偷走的物品总价值最大。

如有4件物品，容积分别为：3458

对应的价值分别为：45710

小偷背包的载重量为：12

则取编号为123的物品，得到最大价值为16。

算法分析：如果采用贪心法，则先取价值最大的10,消耗了容积8,下面只能取容

积为4的物品，得到价值5,这样总价值是15,这不是最优解，因此贪心法是不正

确的。

采用穷举法，用一个B数组来表示取数的标记，当时表示第i件物品不取，

当B=1时表示第i件物品已取，初始化全部取0,以下算法是从后面的物品开始取

起，通过B数组的取值把15种取法全部穷举出来，价值MAX初始化为0o

B[0]B[l]B[2]B[3]B[4]

00000｛初始化｝

00001｛取第4件物品，容积为8,不超，价值为10,将MAX替换为10｝

00010｛取物品3,容积为5,不超，价值为7,不换｝

00011｛取物品3、4,容积为13,超｝

00100｛取物品2,容积为4,不超，价值为5,不换｝

00101

00110

00111

01110｛这是最佳方案｝

01111

10000｛当B(0)=1时停止，B10〕称为哨兵｝

生成B数组中数据的方法如下：

fillchar(b,sizeof(b),0);

whileb[0]=0do

beginj:=n;

whileb[j]=ldodec(j);

b[j]:=1;

fori:=j+ltondo

b:=0;

end；

小结：以上每件物品只能取1件，所以取法只有0和1两种情况，我们称之为0、1

背包，算法的时间复杂度为0(2N),在1秒内N只能做到20。

例1：选数(N0IP2002初中组复赛第2题)

[问题描述]:已知n个整数xl,x2,…,xn,以及一个整数k(k<n)。从n个整数

中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3,4个整数分别

为3,7,12,19时，可得全部的组合与它们的和为：

3+7+12=223+7+19=297+12+19=383+12+19=34。

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

［输入］:

键盘输入，格式为：

n,k(K=n<=20,k<n)

xl,x2,xn(K=xi<=5000000)

n［输出］：

屏幕输出，格式为：

一个整数(满足条件的种数)。

［输入输出样例］:

输入：

43

371219

输出：

1

［算法分析］:本题应用背包问题中取数的方法进行穷举，在取数的过程中，当B数组

中有K个1的时候将对应的K个数相加，再判断是不是素数。

主要程序段如下：

readln(n,k);sum:=0;

fori:=ltondoread(a);

fillchar(b,sizeof(b),0);

whileb［0］=0do

beginj:=n;

whileb［j］=ldodec(j);

b［j］:=1；

fori:=j+ltondob:=0;

m:=0;

fori:=ltondo

ifb=lthenm:=m+l;｛统计1的个数｝

ifm=kthen

begin计算此种取数方法得到的和S；

ifS是素数thensum:=sum+l;

end;

end;

例2：采药（N0IP2005初中组复赛第3题）

【问题描述】

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附

近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带

到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采

每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时

间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药

的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

【输入文件】

输入文件medic.in的第一行有两个整数T（1<=T<=1000）和M（1〈=M〈=100）,

用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接

下来的M行每行包括两个在1至U100之间（包括1和100）的整数，分别表示采摘

某株草药的时间和这株草药的价值。

【输出文件】

输出文件medic,out包括一行，这一行只包含一个整数，表示在规定的时间内，可

以采到的草药的最大总价值。

【样例输入】

703

71100

691

12

【样例输出】

3

【数据规模】

对于30%的数据，M<=10；

对于全部的数据，M<=100o

【算法分析】本题如果采用上述方法来解，只能将M算到20,而这里M<=100,所

以只能拿30%的分数，比较好的算法是采用动态规划，为了能说清算法，现重新举

一个例子，若输入：

103

34

45

56

表示背包的容量是10,有3种物品。用一个数组用来表示背包容量与其最大价值的

关系，上例中设置一个数组count,用下标表示容量，初始化为0。然后按物品的顺

序一一来统计此时的最大价值，每种药品对应各种背包容量时得到的最大价值为：

对于是第i件物品，背包容量为j时的最大价值Cmax(j)=MAX(Cmaxj,Pi+余下空间

的最大价值Cmax(j-i物品所占的空间))，如上例中，根据物品的不断增加，各容量

背包得到的最大价值不断替换：

容量12345678910

价值

序号0000000000

10044444444

20045559999

30045669101111

［数据结构］time,price数组分别用来存入时间和价值，count来存入背包的价值。

var

time,price:array[1..100]oflongint;

t:longint;i,m,j:integer;

count:array[0..1000]oflongint;

begin

assign(input,?medic.in，);

assign(output,?medic.out，);

reset(input);

rewrite(output);

readln(t,m);

fori:=1tomdo

readln(time,price);

fillchar(count,sizeof(count),0);

fori:=1tomdo

forj:=tdownto1do

begin

if(j>=time)and(price+count[j-time]>count[j])then

count[j]:=price+count[j-time];

end;{j>=time表示当前的容量能放入背包，price+count[j-time]>count[j]表示

第i件物品的价值加上第i件物品对于背包容量为j时余下空间的最大价值大于当

前背包容量为j时的最大价值}

writein(count[t]);

close(input);

close(output);

end.

例3：开心的金明(N0IP2006初中组复赛第2题)

题目较长，省略，本题与例2相比，在比较时要先将价值乘以一个数，其余一样，

但要注意的是：本题N的范围是〈二26,如果用0、1背包穷举法在1秒内只能过10

个点中的8个点。

总结：采用动态规划的时间复杂度为O(n*m),范围比穷举法大多了，但也有弱点,

当数据不是整数时，就不可使用；如果还要求出具体的取法，那也相当麻烦。

竞赛的高分的关键一测试

[作者：王亚峰转贴自：河南大学附属中学点击数：54文章录入：kknd]

竞赛的高分的关键一测试

noip刚结束，很多同学认为题目很容易，但是自测时却没有得到理想的分数，

这主要是因为竞赛时“测试”这个环节没有做好，作为一个。i辅导老师，我

介绍一下一些经验，供大家分享。

信息学奥林匹克竞赛中得高分的关键环节一一测试

河南大学附属中学王亚峰

I、引言

中学生信息学奥林匹克竞赛是中学生奥林匹克竞赛的一个重要组成部分，和其他科目的奥林匹克竞赛相比它在

竞赛方式上和评分标准上有着很大不同。竞赛实施的方式完全是上机编程序，实践性很强，评分的唯一标准是

看通过测试数据的多少。通常竞赛中编写一个程序可以分为这样几个环节：分析题目一设计算法和数据结构一

编码一调试一测试，设计测试数据的能力是竞赛考察的重点之一。但是很多学习信息学奥林匹克竞赛的学生和

一些教师常常只重视算法的学习，忽视了“测试”这个环节。有的同学在竞赛中为了赶时间多做完一道题目，

没有对已经做过的题目进行充分的测试，认为设计测试数据是浪费时间，所以经常会出现会做的题目不得分或

者得不了满分的情况。那么怎么才能提高程序的正确率，在竞赛中取得高分呢？

II、一些良好的习惯可以帮助提高编程正确率

众所周知，要想提高学生编程的正确率必须要培养学生有一个良好的编程习惯。这些良好的习惯包括:

A、规范地书写程序。我们书写程序时要使用缩进格式，不同层次的语句向后缩进若干格，这样可以保证程序

尽量少出语法错误。另外，命名变量名时应尽量有一定意义，增加程序的可读性，调试程序时也方便。但是不

要把变量名起得太长，这样会影响编程速度，可以使用一些简短的汉语拼音或英文缩写，只要自己好记就可以

了。

B、编程时要使用自顶向下分析的方法和模块化的方法。可以将一些独立的功能例如输入、输出功能模块化，

这样在调试的时候可以逐模块地检查排错，将一个大规模问题分解成几个小规模问题。但是也不能盲目地将程

序分割成太多模块，信息学奥林匹克竞赛中出的题目往往都不大，所以不必分成太多的模块，分得太多反而会

成为累赘。模块化的依据主要在于程序的内在逻辑。

C、使用全局变量时要特别小心。信息学奥林匹克竞赛中的程序规模一般比较小，全局变量的使用会很频繁，

有时全局变量可以简化编程复杂度，但是全局变量的使用也会带来危险，特别是在过程或函数中改变全局变量

的值可能会带来不可预期的后果。例如，在深度优先搜索中可以设一个全局的“栈”来存储搜索中的状态，但

是在递归过程中，进入递归时数据“进栈”，回溯时数据“出栈”。在这个过程中要对全局变量“栈”和“栈

的指针”进行操作，在这个过程中非常容易出错，出错后很难检查和调试。所以在教学中一定要给学生讲清楚

全局变量和局部变量的区别，全局变量在过程或函数中被修改时对程序的影响，养成学生正确使用全局变量的

习惯。

III、测试是信息学奥林匹克竞赛中得高分的关键

养成良好的习惯能避免编程中的很多错误，但是这还不足以能保证竞赛中编写的程序能通过所有的测试数据，

这是因为竞赛评测时给的标准测试数据都是相当苛刻的，如果程序提交前没有经过充分的测试，很有可能不能

通过标准测试数据。学生在参加竞赛时经常会遇到这样的情况：竞赛完了以后感觉非常好，觉得题目不难，而

且几道题自己都做完了，都通过了样例数据，但是等成绩出来以后却和期望中的相差甚远。使用标准测试数据

测试自己的程序后才发现，不是某些特殊情况没有考虑到，就是犯了小错误，例如变量误用，或者数组声明地

太小。很多学生不止一次犯过类似这样的错误，常常因为这样的错误而懊悔不已，原本应该能够拿到的分数却

没有拿到。大多数人把这种错误归咎于粗心，其实出现错误是很正常的，无论多么擅长编程的人都不可能完全

避免出错。那么能不能及时纠正这些由“粗心”引起的错误呢？在竞赛中我们编写完一个题目后自己应该设计

多组测试数据来测试自己的程序从而找到程序中隐藏的错误，测试是编程时的“把门将军”，他可以将错误拒

之门外，测试进行得越充分，程序的正确率就越高，所以“测试”这一环节是竞赛中得高分的关键。

程序结构组织的技巧

[作者：风清云淡转贴自：网络博客点击数：28文章录入：kknd]

1概述

1）自顶向下，逐步求精

意思就是，先写主程序，需要用子程序的地方尽管调用（虽然子程序还没有写），

直至完成主程序的框架（顶）。下面再分别完成各各子程序。

这样做的好处很明显：思路连贯，清晰，从全局入手，不会被众多小问题弄的

晕头转向。静态查错和调试也非常方便，程序可读性也极强。

2）子程序的大小

学过一点软件工程基本知识的同学应该知道，子程序因为起到了分割问题的作用

会降低编程复杂度，但过多的子程序会因为接口工作带来额外的程序量。我不

想借用那种N行一个子程序的建议，只是希望大家注意，子程序不能太多。常用

的代码写成子程序就可以了。

3）子程序的相互依赖关系。

我不想深入展开，只是提醒大家，少用全局变量，减少依赖性，增加独立性。这

会给调试带来极大的方便。

4）竞赛需要简洁和清晰的统一

一般来说，竞赛时更看中简洁，因为涉及到编程复杂度和调试复杂度，所以过程不易太多。

[b]2美化你的程序

这是一个值得深入研究的问题。我在这里只是讲一点皮毛，给初学者引引路，

帮你们找到“感觉”。

源程序是给人看的。

不只有你是人，因此程序要让第二个人也能看懂

我知道你不想让别人看到你的程序，但N年以后可能你自己都看不懂了...

所以，我给你一些建议：

a.缩进式。就是每个层次空两格（也不一定是2格，看你的习惯了）。如：

fori:=1tondo

forj:=1tondo

ifi+j>5then

begin

i:=i+l;

j：=j-2;

end；

就写成：

fori:=1tondo

forj:=1tondo

ifi+j>5then

begin

i:=i+1;

j：=j-2;

end；

这样层次很清楚,也比较好看一点。

b.给变量取好记的名字。

如：i,j：循环变量

total:累加器

best:当前最优值

等等。主要也是看你的习惯了。注意一定不要引起混淆。

例如一个变量叫num,一个叫number,就难免会用错。

c.善用子程序。

例如：

begin

Init;

fori:=1tondo

begin

Analyse(i);

Process(i);

AddToResult(i);

end;

end.

程序的作用和结构很明显，如果把init(),analyse0,process().addtoresult()代码放在这里,

就会显得非常臃肿，分不清哪些代码是干什么的，而且很不利于单独调试。

程序调试技巧

[作者：风清云淡转贴自：网络博客点击数：28文章录入：kknd]

1调试技巧

调试之前，先要静态查错。

1.看算法是否正确（其实应该是在编码之前做的工作）

2.看有没有笔误（如i写成j）

调试一般是分几个步骤的。先把开关R,S,Q,I打开！

1.建立测试数据（技巧见后面的文章），可以