NOIP2008提高组前三题解题报告

1、NOIP2008提高组前三题解题报告日期：2008-11-18来源：  作者：张恩权字体：大 中 小 NOIP2008提高组前三题解题报告1.笨小猴基本的字符串处理，细心一点应该没问题的，不过判断素数时似乎需要考虑下0和1的情况。参考程序：program word;const inp='word.in' oup='word.out'var i,j,k,min,max:longint; s:string; ch:char; f:array'a'.'z' of integer;/记录每个字符出现的次数procedure fl

2、ink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(input); close(output); end;function judge(k:longint):boolean;/判断素数，需考虑0和1的情况 var i:longint; begin if (k=0) or (k=1) then exit(false); for i:=2 to trunc(sqrt(k) do if k mod i = 0 then ex

3、it(false); exit(true); end;begin flink; readln(s); fillchar(f,sizeof(f),0); for i:= 1 to length(s) do /统计每个字符出现的次数 inc(fsi); min:=1000; max:=0; for ch:= 'a' to 'z' do/统计最大和最小 begin if ( fch<>0 ) and (fch>max) then max:=fch; if ( fch<>0 ) and (fch<min) then min:=fch;

4、 end; k:=max-min; if judge(k) then/输出 begin writeln('Lucky Word'); write(k); end else begin writeln('No Answer'); write(0); end; fclose;end.2.火柴棒等式预处理下，然后枚举、剪枝，范围稍微开大点，弄到2000似乎足够了，剪枝后不会超时的。首先预处理下每个数（02000）需要多少个火柴棒，然后枚举A和B，再判断。参考程序：program matches;const inp='matches.in' oup=&#

5、39;matches.out' num:array'0'.'9' of integer=(6,2,5,5,4,5,6,3,7,6);/09需要的火柴棒数 maxn=1000;var f:array0.maxn*2 of longint; i,j,k,n,ans:longint; s:string;procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(inpu

6、t); close(output); end;procedure init;/预处理02000每个数需要的火柴棒数 var i,j,k:longint; s:string; begin for i:= 0 to maxn*2 do begin str(i,s); fi:=0; for j:= 1 to length(s) do inc(fi,numsj); end; end; begin flink; readln(n); init; ans:=0; n:=n-4;/总火柴棒数减去'+'和'='所需的火柴棒数 for i:= 0 to maxn do/枚举A b

7、egin if fi>=n then continue;/剪枝 for j:= 0 to maxn do/枚举B begin if fi+fj>=n then continue;/剪枝 k:=i+j; if fi+fj+fk=n then inc(ans);/符合条件,总数加一 end; end; write(ans); fclose;end.3.传纸条从A传给B，再从B传给A，中间路径不相交与某个人。换种思路，它完全等价于，从A点传出2张纸条到B，中间不能经过同一人。这么看来似乎就是vijos三取方格数的简化版了。解题思想就是双进程的动态规划。阶段是按传递次数划分的。F(d,x1

8、,y1,x2,y2）表示第d次传递到坐标为（x1，y1），（x2，y2）两个人手中是得到的最大好心度。那么可以列出方程：F(d,x1,y1,x2,y2)=max f (d-1,x1',y1',x2',y2' )+ax1,y1+ax2,y2 | (x1',y1')为把纸条(x1,y1)的人，（x2' , y2'）为把纸条转给(x2,y2)的人（数学不太好，方程列的不专业，见谅_）这么看来时间复杂度是O（maxd*n*m*n*m）,其中maxd=n+m-2。相当于505=312500000，超时是没得说的了。其实我们可以把状态再压缩下

9、，先来看下其中的规律：起点 （1，1）第1次传递可到达 （1，2）（2，1）第2次传递可到达 （1，3）（2，2）（3，1）很快就可以发展其中的规律第d次传递可到达的坐标(xi,yi)和d之间存在d+2=xi+yi那么我们就可以把上面的状态转移方程转化成f(d,x1,x2)=max f(d-1,x1' ,x2' ) +ax1, (d+2-x1) + ax2, (d+2-x2) | x1' , x2' 合法 参考程序：program message;const inp='message.in' oup='message.out'va

10、r a:array1.50,1.50 of longint; f:array0.200,1.100,1.100 of longint; tmp,i,j,k,n,m,d,x1,x2,y1,y2:longint;procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(input); close(output); end;function max(a,b:longint):longint; begin i

11、f a>b then exit(a); exit(b); end;begin flink; readln(n,m); for i:= 1 to n do begin for j:= 1 to m do read(ai,j); readln; end; fillchar(f,sizeof(f),0); f0,1,1:=a1,1; f1,1,2:=a2,1+a1,2; f1,2,1:=a1,2+a2,1; /边界，因为中间需要判断点不重合，所以把必须重合的状态单独考虑 for d:= 2 to (n+m-3) do for x1:= 1 to n do begin y1:=(d+2)-x1;

12、 if (y1<=0) or (y1>m) then continue; / 排除不合法的x1 for x2:= 1 to n do begin if x1=x2 then continue;/排除不合法的x1,x2 y2:=(d+2) - x2; if (y2<=0) or (y2>m) then continue; / 排除不合法的x2 tmp:=fd-1,x1,x2; /各自从上方取,即从(x1,y1-1)传到（x1,y1),（x2,y2-1)传到(x2,y2) if (x1-1>0) and (x2-1>0) then tmp:=max(tmp,fd

13、-1,x1-1,x2-1); /从(x1-1,y1) 传到（x1,y1),（x2-1,y2)传到(x2,y2) if (x1-1>0) and (x1-1<>x2) then tmp:=max(tmp,fd-1,x1-1,x2); /从(x1-1,y1) 传到（x1,y1),（x2,y2-1)传到(x2,y2) if (x2-1>0) and (x1<>x2-1) then tmp:=max(tmp,fd-1,x1,x2-1); /从(x1,y1-1) 传到（x1,y1),（x2-1,y2)传到(x2,y2) fd,x1,x2:=tmp+ax1,y1+ax2

14、,y2; end; end; write(fn+m-3,n,n-1); / 终点的只可能从两个点来，所以终点状态前移一个阶段。 fclose;end.4.双栈排序难，写不出满分程序，所以还是不写了NOIP2008提高组复赛 解题思路1、字符串中统计字母出现次数 最大减最小的 然后判断质数 字符串长度<=1002、给出n<=24个火柴棍，求最多能摆出多少a+b=c形式的等式。数字的摆法和计算器相同，a,b,c>=03、双进程方格取数：m*n的棋盘，m,n<=50，不需使用高精度4、给出1.n的排列，两个栈S1、S2，入栈出栈共4个操作：（n<=1000） 

15、   A：输入队列头入S1    B：弹出S1栈顶元素，进入输出队列    C：输入队列头入S2    D：弹出S2栈顶元素，进入输出队列    要求将1.n的排列排序，采用字典序最小的操作方法个人感觉是，单就难度来看，奥赛历史最简单，由于类似2，3题的模型大多数能拿一等的同学们都见过。我的想法：1、水题，最多40分钟搞定2、如果是考试的话，10000*10000的枚举，差不多写程序+跑+打表=10+3+2min就够了吧（不过我用的是骗分手段，一个一个手算

16、。然后IF-THEN,IF-THEN，最后15分钟搞定）。3、经典题目，斜向划分阶段。35分钟搞定（前三个题目1小时思路+编程+检查够了）4、本届唯一挑战性题目。考虑到要求字典序最小，那么按照ABCD的顺序贪心即可。对于当前的状态，设该进入到输出序列中的是p，输入队列头是q，S1栈顶是t1，S2栈顶是t2，那么依次判断，容易知道q>=pi)如果q<t1或者t1不存在，执行A，continue;ii)如果t1=p，执行B，continue;iii)如果q<t2或者t2不存在，执行C，continue;iv)如果q=t2，执行D，continue;v)输出无解信息，halt;这个

17、算法应该是错误的。 一个反例是：7 2 5 1 4 6 3。在上述四个判断条件中，能够产生冲突的只有i和iii，在i和iii冲突的时候需要判断。所以我对上述算法进行修改：i)如果(q<t1或者t1不存在)and(输入队列中不存在x，使得q<t2<x<t1) ，执行A，continue;ii)如果t1=p，执行B，continue;iii)如果q<t2或者t2不存在，执行C，continue;iv)如果q=t2，执行D，continue;v)输出无解信息，halt;归纳法证明算法正确性：当n很小的时候（至少我没举出反例）算法是正确的。设n<k成立，考虑n=k的

18、情况。当q=k时，显然(不存在x，使得q<t2<x<t1)，也没有q<t1或者q<t2的情况，所以k能够入栈的充要条件是t1不存在或者t2不存在。只要最大的数k放在了栈底，对其他的数都是没有影响的。所以算法依然正确。证毕。（表述的很不规范。）NOIP2008提高组解题报告angwuy1 word这道题完全是送分题，只需要直接统计，再判断素数。参考程序：var st:string; max,min,i:longint; a:array'a'.'z'of longint; ch:char;function fun(n:longint):

19、boolean;var i:longint;begin if n<2 then begin fun:=false;exit;end; for i:=2 to n-1 do if n mod i=0 then begin fun:=false;exit;end; fun:=true;end;begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(st); fillchar(a,sizeof(a),0); for i:=1 t

20、o length(st) do inc(asti); max:=0; min:=101; for ch:='a' to 'z' do if ach>0 then begin if ach>max then max:=ach; if ach<min then min:=ach; end; if fun(max-min) then begin writeln('Lucky Word'); writeln(max-min); end else begin writeln('No Answer'); writeln(0)

21、; end; close(input); close(Output);end.2 matches搜索题，由于输入的情况只有25种，所以打表也是一种可行的方法。在数据最大时，经过人工和电脑证明是不会到达四位数的，所以可以直接用O(1000*1000)的搜索算法参考程序:const mat:array0.9of longint=(6,2,5,5,4,5,6,3,7,6);function fun(m:longint):longint;var t:longint;begin t:=0; while m>0 do begin inc(t,matm mod 10); m:=m div 10; en

22、d; fun:=t;end;var a:array0.1000 of longint; n,i,j,ans:longint;begin assign(input,'matches.in'); reset(input); assign(output,'matches.out'); rewrite(output); readln(n); if n<10 then begin writeln(0);close(output);exit;end; a0:=6; for i:=1 to 1000 do ai:=fun(i); dec(n,4); for i:=0 t

23、o 1000 do if ai<n then begin for j:=0 to 1000-i do if ai+aj+ai+j=n then inc(ans); end; writeln(ans); close(input); close(output);end.3 messageDP题，两条路线必定一上一下，而且，当到达某一列后，前面对后面的不会有影响，符合动态规划的无后效性，方程如下：用dpI,j,k表示当到达I列时，上路线在j行到，下路线在k行到的最大值。另外加一个预处理，sumI,j1,j2表示在第I列j1到j2行的数加起来的和。边界条件：dp2,1,k:=sum1,1,k;递推方程:dpI,j,k:=max(dpI-1,j2,k2+sumI-1,j,j2+sumI-1,k,k2) j<=j2<k<=k2答案：max(dpm,j,n+summ,j,n)参考程序：const maxn=10;var a:array1.maxn,1.maxnof longint; dp,sum:array1.maxn,1.maxn,1.maxnof longint; n,m,i,j,k,i1,i2,j1,j2,k1,k2:longint;fun