《第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解.doc》由会员分享，可在线阅读，更多相关《第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解.doc（14页珍藏版）》请在三一文库上搜索。
1、第十九届全国信息学奥林匹克联赛（NOIP2013）解题报告（普及组）宁波市镇海蛟川书院 郁庭第一题：记数(count)【分析】直接用最朴素的模拟来做，时间复杂度小于(数的个数*每个数位数)， 1千万以内的运算次数是肯定不会超时的。代码：var n,x,i,temp,j,count:longint;begin assign(input,count.in);reset(input); assign(output,count.out);rewrite(output); readln(n,x); for i:=1 to n do begin temp:=i; while temp0 do begin
2、j:=temp mod 10; temp:=temp div 10; if j=x then inc(count);end;end;writeln(count);close(input);close(output);end.【再分析】这样虐题目是会跌人品的，这段时间是非常考验人品的时候（当时数据、成绩未公布，提心吊胆啊），于是就产生了下面的程序（时间复杂度就是数的位数），用几个手算来说明问题：输入：10134 1 （n=10134 x=1便于后面的描述）输出：4204规律总结（从个位到高位用a1.ai来表示）：在第i位上固定x，把原数分成两段，然后考虑ai和x大小的关系，对应了上面013的分析
3、，不难发现：aix时，种数=（左段值+1）*（右段位数）ai=x时，种数=（左段值）*（右段位数）+（右段值+1）ai0 do begininc(count); bcount:=bcount-1*10;acount:=m mod 10;m:=m div 10;end; bcount+1:=bcount*10; if x=0 then dec(count);for i:=1 to count do beginif aix then beginleft:=n div bi;right:=bi-1;inc(ans,left*right);endelse if ai=x then begin left
4、:=n div bi; if x=0 then dec(left); right:=bi-1;inc(ans,left*right+(n mod bi-1)+1);endelse beginleft:=n div bi+1; if x=0 then dec(left); right:=bi-1;inc(ans,left*right);end;end; if (x=0) and (n0 do begin inc(tot,ai); tot:=tot mod 10000; dec(i);end;writeln(tot); close(input);close(output);end.第三题：小朋友的
5、数字(number)【本段吐槽可以无视】联赛赶上自己评职称，没随队过去，回来听说第三题难懂，赶紧瞄了下题目，孩子们啊，我不是和你们说过的吗，联赛普及组就是考读题目的啊，读懂后简单有木有啊，本题就是最好的证明，再普通不过的递推了，状态转移都没有。【题目简述】给你n个数，让你求对应的n个特征值（前面的最大连续和，O(n)的扫描，滚瓜烂熟了），根据特征值求分数值（前面的单个(分数值+特征值)的最大值），题目需要输出n个分数值的最大值。【我的思路】O(n)扫描最大连续和，求出特征值，然后O(n)计算分数值，同时用（分数值+特征值）更新max。这个思路有一个需要注意的地方，分数值+特征值会超过longi
6、nt、int64（高精度可以解决），这里采用计算max时执行mod p操作，于是就产生了如下问题： 输入：5 981-409 -401 97 -96 -301特征值：-409 -409 -312 97 97分数值：-409 -818 -818 -721 -624max ：-818 不变 -721 -624最终max停留在了-624，但明显-409才是最大的分数值，这个问题其实就是max初值两个-409惹的祸，必须要在后面所有特征值中判断有没有绝对值大于409的，否则max需要考虑第一个分数值，以免出现这样的错误。附上代码：vari,n,p:longint;a:array0.1000000 of
7、 longint;f,b:array0.1000000 of int64;max,temp:int64; flag:boolean;begin assign(input,number.in);reset(input); assign(output,number.out);rewrite(output); readln(n,p); for i:=1 to n do beginread(ai);end;max:=-maxlongint; for i:=1 to n do begininc(temp,ai);if tempmax then max:=temp;if temp0 then temp:=
8、0; bi:=max;end; f1:=b1;max:=f1+b1;if b10 then begin if not flag and (bi-b1) then flag:=true; max:=(fi+bi) mod p; end; end; if not flag and (maxf1) then max:=f1; writeln(max); close(input);close(output);end.第四题：车站分级(level)【本段吐槽可以无视】很基础的拓扑排序啊，我看完题目首先想了个贪心，发现有反例，于是画了下图就知道是用拓扑做了，但脑中的思维定式（普及组貌似从来没有过绝对的图论
9、题）让我纠结了一下，想想有没有其他巧方法，这个问题也留给大家。【分析略带吐槽】这个程序没什么难点，第一遍就过了样例，但为什么只有我校念祖一人做对？难道是拓扑写残了，没有用队列存储？这要问几个90分的同学了，应该是超时丢的分吧。【解题思路】画个图，我手稿找不到了（估计是评完职称后随那一大堆纸进了垃圾桶了），不然可以扫描下省得画var n,m,i,j,count,k,w,h,t:longint; get:array0.1000 of boolean; hav:array0.1000,0.1000 of boolean; jin,b,chu,a:array0.1000 of longint; nex
10、t:array0.1000,0.1000 of longint; eq:array0.2000 of longint;procedure deal(j:longint);var i,k,te:longint;beginfor i:=1 to j do begin te:=jineqh; for k:=1 to te do begin dec(chunexteqh,k);/断边 if chunexteqh,k=0 then begineqt:=nexteqh,k;inc(t);end end;inc(h);end;end;begin assign(input,level.in);reset(in
11、put); assign(output,level.out);rewrite(output); readln(n,m);for i:=1 to m do beginread(j);count:=0;fillchar(get,sizeof(get),false);for k:=1 to j do beginread(ak);getak:=true;inc(count);bcount:=ak;end;readln;for k:=b1 to bcount doif not getk thenfor w:=1 to count doif not havk,bw then beginhavk,bw:=t
12、rue;inc(jink);nextk,jink:=bw; /出去边的指向inc(chubw); end; end;count:=0;h:=1;t:=1;for k:=1 to n do if chuk=0 then begin inc(count); eqt:=k; inc(t); end;count:=0; while ht do begindeal(t-h);/处理队列eq，从h开始的t-h个元素，断他的所有边，产生的无入读的点进队列 inc(count);end;writeln(count); close(input);close(output);end.【此课件下载可自行编辑修改，供参考，感谢你的支持！】14 / 14实用精品文档