当前位置:首页 >> 学科竞赛 >> 第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解

第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解


第十九届全国信息学奥林匹克联赛(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的个数 解剖之: 1 0 1 3 4 个位是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种

百位是1

?? 1??

千位是1

? 1???

万位是1

1????

以上相加得4204
规律总结(从个位到高位用 a[1]..a[i]来表示) : 在第 i 位上固定 x,把原数分成两段,然后考虑 a[i]和 x 大小的关系,对应了上面 013 的分 析,不难发现: ①a[i]>x 时,种数=(左段值+1)*(右段位数) ②a[i]=x 时,种数=(左段值)*(右段位数)+(右段值+1) ③a[i]<x 时,种数=(左段值)*(右段位数) 别高兴太早,如果 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);

for i:=1 to count do begin if a[i]<x then begin left:=n div b[i]; right:=b[i-1]; inc(ans,left*right); end else if a[i]=x then begin 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

a[i-1]:=(a[i-1]*a[i]) mod 10000; dec(i); end; 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;

if b[i]>0 then begin if not flag and (b[i]>-b[1]) then flag:=true; max:=(f[i]+b[i]) mod p; end; end; if not flag and (max<f[1]) then max:=f[1]; writeln(max); close(input);close(output); end.

第四题:车站分级(level)
【本段吐槽可以无视】 很基础的拓扑排序啊,我看完题目首先想了个贪心,发现有反例,于是画了下图就知道 是用拓扑做了, 但脑中的思维定式 (普及组貌似从来没有过绝对的图论题) 让我纠结了一下, 想想有没有其他巧方法,这个问题也留给大家。 【分析略带吐槽】 这个程序没什么难点, 第一遍就过了样例, 但为什么只有我校念祖一人做对?难道是拓 扑写残了,没有用队列存储?这要问几个 90 分的同学了,应该是超时丢的分吧。 【解题思路】画个图,我手稿找不到了(估计是评完职称后随那一大堆纸进了垃圾桶了) , 不然可以扫描下省得画

车站编号 1

2

3

4

5

6

7

8

9

1 3 5 6 车次一 2和4级别一定比1356低 3 5 6 车次二 4级别比356低,等价于上面了,所以这个车次是多余的 1 5 9 车次三 2、3、4、6、7、8级别比159低,画线省略 车站为点,级别低到高为有向线段,形成对应图如下:
1 9 2 3

找入度为0的点进队 2 4 7 8

8 7 6 5

4

重复以下步骤: 遍历队列的点断它们的出边 这些点出队 新形成的入度0的点进队列 最终的解就是上面的循环次数 详细内容参见代码

var n,m,i,j,count,k,w,h,t:longint;

get:array[0..1000] of boolean; hav:array[0..1000,0..1000] of boolean; jin,b,chu,a:array[0..1000] of longint; next:array[0..1000,0..1000] of longint; eq:array[0..2000] of longint; procedure deal(j:longint); var i,k,te:longint; begin for i:=1 to j do begin te:=jin[eq[h]]; for k:=1 to te do begin dec(chu[next[eq[h],k]]);//断边 if chu[next[eq[h],k]]=0 then begin eq[t]:=next[eq[h],k]; inc(t); end end; inc(h); end; end; begin assign(input,'level.in');reset(input); assign(output,'level.out');rewrite(output); readln(n,m); for i:=1 to m do begin read(j); count:=0; fillchar(get,sizeof(get),false); for k:=1 to j do begin read(a[k]); get[a[k]]:=true; inc(count); b[count]:=a[k]; end; readln; for k:=b[1] to b[count] do if not get[k] then for w:=1 to count do if not hav[k,b[w]] then begin hav[k,b[w]]:=true; inc(jin[k]); next[k,jin[k]]:=b[w]; //出去边的指向 inc(chu[b[w]]); end;

end; count:=0;h:=1;t:=1; for k:=1 to n do if chu[k]=0 then begin inc(count); eq[t]:=k; inc(t); end; count:=0; while h<t do begin deal(t-h);//处理队列 eq,从 h 开始的 t-h 个元素,断他的所有边,产生的无入 读的点进队列 inc(count); end; writeln(count); close(input);close(output); end.


更多相关文档:

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++...指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束...(第 1 题 15 分,第 2 题 13 分,共计 28 ...

NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组Pascal试题【整理版附答案】

NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组Pascal试题【整理版附答案】_学科竞赛_高中教育_教育专区。NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及...

NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案

NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案_学科竞赛_高中教育_教育专区。NOIP2013第十九届信息学奥赛提高组答案NOIP2013第十九届全国青少年信息学奥林...

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析_学科竞赛_高中教育_教育...5、ABCD,此题完全不会,因为是第一次带学生参赛,对复赛什么情况完全不了 解,...

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_...任何一个在(输入规模的)指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束后...

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题

单项选择题(共 20 题,每题 1.5 分,共计 30 分;每题有且仅有一个正确...2013信息学奥林匹克联赛... 8页 1下载券 NOIP2013第十九届全国青... 2页 ...

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_学科竞赛_初中教育_教育...CCF NOIP2013 第十九届 初赛普及组 Pascal 语言试题 输入:3 5 输出:___ 2...

CCF NOIP2013 解题报告&心得

CCF NOIP2013 解题报告&心得_学科竞赛_高中教育_教育...坑爹地传错了一题, ( 还是最简单的 Day2 的 ...第5 页共5 页 全国信息学奥林匹克联赛(NOIP2013)...

2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题

2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题_自我管理与提升_求职...; end. CCF NOIP2013 初赛提高组 Pascal 语言试题 第 11 页,共 11 页 ...
更多相关标签:
信息学奥林匹克联赛 | noip2016解题报告 | noip2015解题报告 | noip2015day2解题报告 | noip2014解题报告 | noip2015复赛解题报告 | noip2016复赛解题报告 | noip2013解题报告 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com