省淳中信息学奥赛辅导 奥赛试题解析
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次，平均跳的次数f3=2.5次；f3=(3+f2)/2=2.5
6
省淳中信息学奥赛辅导 奥赛试题解析
（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); end;
7
省淳中信息学奥赛辅导 奥赛试题解析
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]
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]上升序列长度 【2.状态转移】
8
省淳中信息学奥赛辅导 奥赛试题解析
1. 初始状态：num[i]:=1; num[1]:=1;
2. 状态转移：从下标1逐步递推到n，求解num[i]
num[i]=Max{ num[j], (1<= j<= i-1, height[j]
【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]
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; ans:=0; 9 read(x,y); a[x][y]:=1; 省淳中信息学奥赛辅导 奥赛试题解析 for i:=1 to n do for j:=1 to m do if a[i][j]=0 then begin count:=0; colour(i,j); if (ans end; writeln(ans); end. 输入： 6 5 9 1 4 2 3 2 4 3 2 4 1 4 3 4 5 5 4 6 4 输出： 7 【分析】 【1.状态描述】 （1）棋盘状态：a[x][y]:=1或0 （2）count,ans：数字为0的连续单元格数量，count当前解,ans当前最优解 【2.状态转移】 1. 初始状态：查找棋盘每个值为0的单元格 a[i][j]=0 2. 状态转移：如果a[i][j]=0则 （1）：状态修改 inc(count); a[i][j]:=1; （2）：按上下左右4个方向深度搜索下一单元格 【3.算法分析】分上下左右找数字为0的连续单元格数量 10
2013NOIP初赛提高组试题解析
