历届奥赛试题解析-初赛讲解(2)

省淳中信息学奥赛辅导 奥赛试题解析

内给出答案，则称它为多项式时间算法。

2. P类、NP类问题

（1）P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，

那么这个问题就属于P问题。

（2）NP类问题：NP（Non-deterministic Polynomial）问题是指可以在多项式的时间里

验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

（3）所有的P类问题都是NP问题。 NP问题不是非P类问题

3. NPC问题（NP完全问题）：Cook 在1971年给出并证明了有一类问题具有下述性质： （1）这类问题中任何一个问题至今未找到多项式时间算法；

（2）如果这类问题中存在一个问题有多项式时间算法，则这类问题都有多项式时间算法

这类问题就是所谓的NP完全问题。

（3）NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它

得是一个NP问题；然后，所有的NP问题都可以约化到它。

6

省淳中信息学奥赛辅导 奥赛试题解析

5．CCF NOIP复赛考试结束后，因（ ABCD ）提出的申诉将不会被受理。

A．源程序文件名大小写错误

B．源程序保存在指定文件夹以外的位置 C．输出文件的文件名错误

D．只提交了可执行文件，未提交源程序

三、问题求解（共2题，每题5分，共计10分；每题全部答对得5分，没有部分分） 1． 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1，s2，…，sn，均为

0或1。该系统每次随机生成n个数a1，a2，…，an，均为0或1，请用户回答（s1a1+s2a2+…+snan）除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答：

就破解出了密码s1= 0 ，s2= 1 ，s3= 1 ，s4= 1 。

【分析】

（1）由第5组得到s1=0；

（2）由第1组、第5组得到s2=1； （3）由第1组、第3组得到s3=1； （3）由第2组、第3组得到s4=1；

2． 现有一只青蛙，初始时在n号荷叶上。当它某一时刻在k号荷叶上时，下一时刻将等概率

地随机跳到1，2，…，k号荷尔蒙叶之一上，直至跳到1号荷叶为止。当n=2时，平均一共跳2次；当n=3时，平均一共跳2.5次。则当n=5时，平均一共跳 37/12 次。

【分析——递推】

（1）由n=2时，跳法2→2，2→1共2次，平均跳的次数f2=2次，说明在求平均时编号1不统计在内。

（2）由n=3时，跳法3→3，3→2，3→1，再从2号跳跳法2→2，2→1共5次，平均跳的

7

省淳中信息学奥赛辅导 奥赛试题解析

次数f3=2.5次；f3=(3+f2)/2=2.5

（3）由n=4时，跳法分别是落在1号、2号、3号、4号；平均跳的次数 f4=（4+f2+f3）/3=（4+2+2.5）/3 = 8.5/3

（4）由n=5时，跳法分别是落在1号、2号、3号、4号、5号；平均跳的次数 f5=（5+f2+f3+f4）/4=（5+2+2.5+8.5/3）/4= 37/12

四、阅读程序写结果（共4题，每题8分，共计32分） 1．【字符串——判定输入的字符串是否是回文串】 var

n,i:integer; str:string;

isPlalindrome:Boolean; begin

readln(str); n:=Length(str); isPlalindrome:=true; for i:=1 to (n idv 2) do begin

if (str[i]<>str[n-i+1]) then end;

if (isPlalindrome) then writeln(‘Yes’) else

writeln(‘No’);

isPlalindrome:=false;

end.

输入：abceecba 输出： Yes

【分析】 str[1]——str[8]、str[2]——str[7] 、 str[3]——str[6] 、str[4]——str[5]

这4对字符相同则返回true

2．【数学——１到1000中是１０或１５的倍数的数的个数】 Var a,b,u,v,I,num:integer; begin

readln(a,b,u,v); num:=0;

for i:=a to b do begin

if (I mod u=0)or(I mod v=0) then inc(num);

8

省淳中信息学奥赛辅导 奥赛试题解析

end;

writeln(num); end.

输入：1 1000 10 15 输出： 133

【分析】此题计数1-1000范围内能够整除10或15的数有多少个，使用容斥原理或者集合求

并很容易可以得到1000/10+1000/15-1000/30=133.

3．【动态规划——最长上升子序列的长度】 const SIZE=100;

var n,ans,I,j:integer;

height,num:array[1..SIZE] of integer; begin

read(n);

for i:=1 to n do begin

read(height[i]); num[i]:=1;

for j:=1 to i-1 do begin

if ((height[j]=num[i])) then

end; ans:=0;

for i:=1 to n do begin end;

writeln(ans);

if (num[i]>ans) then ans:=ans+num[i]; num[i]:=num[j]+1; end;

end. 输入： 8

3 2 5 11 12 7 4 10 输出： 4 【分析】

【1.状态描述】

（1）height[i]存放的数组

（2）num[i]：数组height[1]——height[i]中中包含height[i]上升序列长度

9

省淳中信息学奥赛辅导 奥赛试题解析

【2.状态转移】

1. 初始状态：num[i]:=1; num[1]:=1;

2. 状态转移：从下标1逐步递推到n，求解num[i]

num[i]=Max{ num[j], (1<= j<= i-1, height[j] height[3]=5，num[4]= num[3]+1=3

【4.算法设计】

1. 初始状态：num[i]:=1; num[1]:=1; 求解num[i]的最优解 2. 状态前驱： num[i]的前驱状态num[j]：num[1]—— num[i-1] 3. 状态转移：

（1）条件：if ((height[j]=num[i])) （2）转移方程：num[i]:=num[j]+1;

4．【深度优先搜索——上下左右找棋盘数字为0的连续单元格数量】 const SIZE=100; var

procedure colour(x,y:integer); begin begin

n,m,p,count,ans,x,y,I,j:integer; a:array[1..SIZE,1..SIZE] of integer;

inc(count); a[x][y]:=1;

if (x>1)and(a[x-1][y]=0) then colour(x-1,y); //上 if (y>1)and(a[x][y-1]=0) then if (x

colour(x,y-1); //左 colour(x+1,y); //下 colour(x,y+1); //右

end;

fillchar(a,sizeof(a),0); readln(n,m,p); for i:=1 to p do begin end;

10

read(x,y); a[x][y]:=1;