第十九届全国信息学奥林匹克联赛（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 temp>0 do begin 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
要求：1到10134每一位上含1的个数解剖之：10134个位是1？？？？1有1014种可能，前4位是0000到1013十位是1？？？1？前3位102种（000-101）后一位10种（0-9）所以有1020种可能分类讨论前2位10种（00-09）后两位100种前2位1种（10），后两位35种（00-34）分类讨论的相加得1035种前1位1种（1）后三位1000种（000-999）所以1000种后四位135种（0000-0134）所以135种
规律总结（从个位到高位用a[1]..a[i]来表示）：
在第i位上固定x，把原数分成两段，然后考虑a[i]和x大小的关系，对应了上面013的分析，不难发现：
①a[i]>x时，种数=（左段值+1）*（右段位数）
②a[i]=x时，种数=（左段值）*（右段位数）+（右段值+1） ③a[i] 别高兴太早，如果x=0时，规律又有点不一样，最高位不需要考虑、②③中左段值减1就行了，附上代码 var n,x,m,i,count,left,right,ans:longint; a,b:array[0..7] of longint; begin assign(input,'count.in');reset(input); assign(output,'count.out');rewrite(output); readln(m,x); b[0]:=1;n:=m; while m>0 do begin inc(count); b[count]:=b[count-1]*10; a[count]:=m mod 10; m:=m div 10; end; b[count+1]:=b[count]*10; if x=0 then dec(count); 百位是1？？1？？千位是1？1？？？万位是11？？？？以上相加得4204 for i:=1 to count do begin if a[i] left:=n div b[i]; if x=0 then dec(left); right:=b[i-1]; inc(ans,left*right+(n mod b[i-1])+1); end else begin left:=n div b[i]+1; if x=0 then dec(left); right:=b[i-1]; inc(ans,left*right); end; end; if (x=0) and (n<10) then writeln(0) else if x=0 then writeln(ans) else writeln(ans); close(input);close(output); end. 第二题：表达式求值(expr) 【分析】可以说方法很多，又可以说方法很少的题目，万变不离其中的模拟，但实现方法人各有异，我写得很朴素，一边读入一边操作，省得ansistring操作，利用一个栈存放乘法加法，各种地方mod反正都不影响结果，于是代码出炉了，写得比较快，没有美感，请见谅。 var i,j,k:longint; flag:boolean; c:char; tot,temp:qword; a:array[0..100000] of longint; procedure add; begin inc(i); a[i]:=temp; temp:=0; end; procedure jisuan; begin if flag then begin end; a[i-1]:=(a[i-1]*a[i]) mod 10000; dec(i); end; begin assign(input,'expr.in');reset(input); assign(output,'expr.out');rewrite(output); while not eoln do begin read(c); case c of '+':begin add; jisuan; flag:=false; end; '*': begin add; jisuan; flag:=true; end; else begin val(c,k); temp:=temp*10+k; end end; end; inc(i); a[i]:=temp; tot:=0; if flag then begin inc(tot,a[i]*a[i-1]mod 10000); i:=i-2; end; while i>0 do begin inc(tot,a[i]); tot:=tot mod 10000; dec(i); end; writeln(tot); close(input);close(output); end. 第三题：小朋友的数字(number) 【本段吐槽可以无视】联赛赶上自己评职称，没随队过去，回来听说第三题难懂，赶紧瞄了下题目，孩子们啊，我不是和你们说过的吗，联赛普及组就是考读题目的啊，读懂后简单有木有啊，本题就是最好的证明，再普通不过的递推了，状态转移都没有。 【题目简述】 给你n个数，让你求对应的n个特征值（前面的最大连续和，O(n)的扫描，滚瓜烂熟了），根据特征值求分数值（前面的单个(分数值+特征值)的最大值），题目需要输出n个分数值的最大值。 【我的思路】O(n)扫描最大连续和，求出特征值，然后O(n)计算分数值，同时用（分数值+特征值）更新max。 这个思路有一个需要注意的地方，分数值+特征值会超过longint、int64（高精度可以解决），这里采用计算max时执行mod p操作，于是就产生了如下问题： 输入： 5 981 -409 -401 97 -96 -301 特征值：-409 -409 -312 97 97 分数值：-409 -818 -818 -721 -624 max ：-818 不变 -721 -624 最终max停留在了-624，但明显-409才是最大的分数值，这个问题其实就是max初值两个-409惹的祸，必须要在后面所有特征值中判断有没有绝对值大于409的，否则max需要考虑第一个分数值，以免出现这样的错误。 附上代码： var i,n,p:longint; a:array[0..1000000] of longint; f,b:array[0..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 begin read(a[i]); end; max:=-maxlongint; for i:=1 to n do begin inc(temp,a[i]); if temp>max then max:=temp; if temp<0 then temp:=0; b[i]:=max; end; f[1]:=b[1];max:=f[1]+b[1];if b[1]<0 then flag:=false; for i:=2 to n-1 do begin f[i]:=max;
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解
