当前位置:首页 >> 学科竞赛 >>

NOIP2013复赛模拟8解题报告


NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟试题 4(4P36) [题目描述] CG 同学又弄到一批新牛,新牛到了农场以后,首先要学习汉语,数的朗读成为新牛的 一个难题,朗读绝对值小于 10 亿的数。 新牛们知道汉语中有如下的读数规则: 1.首先读符号位,然后读整数部分,整数部分之后可能出现小数点,如果有小数部分

则 小数点一定出现,并且读出小数点之后读小数部分。 2.符号位的读法是: ⑴正数,不论正号”+”是否出现,都不必读出符号位; ⑵负数的最左边的符号是”-“,读成”负”(以“F”来表示“负” ) 。 3.整数部分的读法是: ⑴ 如果整数部分不存在或者整数部分全是零则直接读成“零” (以“0” 来表示“零” ) ; ⑵ 否则从整数部分中最左边的非零数字开始读起,然后以十、百、千、万、亿(分别 以”S”、”B”、”Q”、”W”、 “Y”来表示)等数量单位来拼读整数部分。 4.整数部分中: ⑴每一个非零数字都 必须结合各个相应的数量单位读出来; ⑵每一段连续的“零”只能读成一个“零” ,但是某一段连续的“零”的左侧或者右侧 不存在非零数字(这里只考虑整数部分)则这一段“零”不应该读出来; 5.如果有小数部分,则首先读“点” (以“D”来表示“点” ) ,然后从左至右有顺序地读 出各个小数位。在读小数部分的时候不可以使用十、百、千、万、亿等数量单位;但是小数 部分的每一个数字都需要读出来,连续的零不可以读成一个“零” ,而应该分别读出。 6.如果数中有小数点而没有小数部分,则不应该把小数点读出来。 例如: -0020030004.567 应该读成”F2Q03W04D567”,000.89 应该读成”0D89”。 请你编写程序帮助新牛把给定的数正确地读出来。 [输入数据] 输入文件仅一行,存放了一个数(不超过 50 字符) ,其绝对值小于 10 亿. [输出数据] 输出文件仅一行,输出这个数的正确读法。 [样例输入] -0020030004.567 [样例输出] F2Q03W04D567 program cz; var st,s,t:string; p,i:integer; begin assign(input,'read.in');reset(input); assign(output,'read.out');rewrite(output); readln(st); if st[1]='-' then begin

delete(st,1,1); i:=1; while (i<length(st)) do begin if (st[i]<>'0') then begin write('F'); break; end; inc(i); end; end; p:=pos('.',st); if (p=0) then p:=length(st); i:=1; while (st[i]='0') and (i+1<p) do inc(i); delete(st,1,i-1); p:=pos('.',st)-1; if (p=-1) then p:=length(st); s:=''; i:=(p-1) mod 4+1; while (i>0) and (i<=p) do begin t:=''; if (i>3) then if (st[i-3]>'0') then t:=t+st[i-3]+'Q' else if (s<>'') and (s[length(s)]<>'0') then t:=t+'0'; if (i>2) then if (st[i-2]>'0') then t:=t+st[i-2]+'B' else if (t<>'') and (t[length(t)]<>'0') then t:=t+'0'; if (i>1) then if (st[i-1]>'0') then t:=t+st[i-1]+'S' else if (t<>'')and(t[length(t)]<>'0') then t:=t+'0'; if (i>0) then if (st[i]>'0') then t:=t+st[i]+''; if (t[length(t)]='0') then delete(t,length(t),1); if (t<>'') then begin s:=s+t; case (p-i) div 4 of 1:s:=s+'W';

2:s:=s+'Y'; end; end; inc(i,4); end; if (s='') then s:='0'; write(s); if (pos('.',st)>0)and(length(st)>pos('.',st)) then write('D',copy(st,p+2,length(st)-p-1)); writeln; close(input); close(output); end.

2.背单词(words) 源程序名:words.pas/c/cpp 输入文件名:word.in 输出文件名:word.out 时限:1 秒 问题描述: 英语四级考试临近了, 小 Y 却发现他已经把以前学的单词几乎忘光了。 好在现在离考试 还有一段时间,小 Y 决定从现在开始夜以继日地背单词。也就是说小 Y 废寝忘食,一天二十 四小时地北单词。 今天的日期(时间)是 yyyy 年 mm 月 dd 日 hh 时 min 分,考试的时间是 yyyy ’年 mm’ 月 dd’日 hh’时 min’分。这之间的所有时间小 Y 都用来背单词了,那么考试之前他最多能背 多少个单词呢? 时间紧张,小 Y 只管数量不管质量。当然有的单词长一些,有的单词短一些。长的单词 难背一些,短的单词好背一些。根据小 Y 的经验,他能一眼看出背某一个单词需要的时间, 以分钟为记。 现在给你一个字典,请你挑出最多的单词使小 Y 能在考试前背出来。 输入格式: 第一行一个整数 N,表示字典中的单词数,N<=5000。 接下来 N 行, 每行一个整数表示背这个单词需要用的时间, 以分钟记, 小于等于 10000。 (这个单词本身是什么并不重要,不是吗?当前小 Y 已经认识的单词数为 0 个) 。 接下来两行依次是当前时间和考试时间。时间给出的格式是:yyyy-mm-dd-hh:min,例 如 2007-06-23-02:00,采用 24 小时制,每天从 00:00~23:59,年份从 0000 到 9999。 输出格式: 一行一个数,表示考试前小 Y 最多能背出的单词数。 输入样例: 2 1 1

2007-06-23-11:59 2007-06-23-12:00 样例输出: 1 const monthday:array[1..12] of integer=(31,28,31,30,31,30,31,31,30,31,30,31); var s:string; n,i,total:longint; time1,time2,time,year1,year2,month1,month2,day1,day2,hour1,hour2,min1,min2:int64; a:array[0..5000] of longint; procedure sort; var i,j,t:longint; begin for i:=1 to n-1 do for j:=i+1 to n do if (a[i]>a[j]) then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; end; function getyearday(x:longint):longint; begin if x mod 400=0 then exit(366); if x mod 100=0 then exit(365); if x mod 4=0 then exit(366); exit(365); end; begin assign(input,'words.in'); assign(output,'words.out'); reset(input); rewrite(output); readln(n); for i:=1 to n do readln(a[i]); sort; readln(s); val(copy(s,1,4),year1); val(copy(s,6,2),month1); val(copy(s,9,2),day1);

val(copy(s,12,2),hour1); val(copy(s,15,2),min1); time1:=min1; time1:=time1+hour1*60; for i:=1 to day1-1 do time1:=time1+24*60; for i:=1 to month1-1 do begin time1:=time1+monthday[i]*60*24; if (getyearday(year1)=366)and(i=2) then time1:=time1+24*60; end; readln(s); val(copy(s,1,4),year2); val(copy(s,6,2),month2); val(copy(s,9,2),day2); val(copy(s,12,2),hour2); val(copy(s,15,2),min2); time2:=min2; time2:=time2+hour2*60; for i:=1 to day2-1 do time2:=time2+24*60; for i:=1 to month2-1 do begin time2:=time2+monthday[i]*60*24; if (getyearday(year2)=366)and(i=2) then time2:=time2+24*60; end; time:=time2-time1; for i:=year1 to year2-1 do time:=time+getyearday(i)*24*60; total:=0; while (total<n)and(time-a[total+1]>=0) do begin inc(total); time:=time-a[total]; end; writeln(total); close(input);close(output); end.

3.

过河

【解题思路】 这道题的 DP 方程很容易想, 用 f[i]表示青蛙跳到坐标为 i 的点时最少踩到的石子个数, 则有: f[i]=min(f[i-j]+a[i]),a[i]=1 表示坐标为 i 的点有石子。 但是,“对于全部的数据,L<=10^9”……数组是不可能了……

再一看,“1<=M<=100”,偌大一个长 10 亿的桥,上面的石子竟然只有 100 个,这就不可避 免的使桥上出现了大片大片的空当。 已知 1<=S<=T<=10,但是可以发现,如果青蛙当前在 i,那么下一次青蛙可以跳到[i+s,i+t] 之间,继续跳,则可以跳到[i+2s,i+2t]之间……这样跳下去,青蛙一定能达到[i+s^2,i+t^2]之 间的一个点。若在 s^2 到 t^2 这段路中间没有任何石子,完全可以把这段路忽略掉,而忽略 的方法是进行压缩。 压缩部分伪代码如下: if 两块石头之间的距离不小于 100 then 将下一块石头的坐标存储为:上一存储的石头的坐标+100 else 下一块石头的坐标存储为:上一存储的石头的坐标+两块石头之间的距离; 这样可以成功的压缩石头之间的空白,减少数组长度到 100000。【pascal 程序】 var a,f:array [0..100000] of longint;//a 是压缩后的石头位置,f 是 DP 数组 stone,cp_stone:array [0..150] of longint; //stone 是初始石头坐标,cp_stone,即 compact_stone 是压缩后石头的坐标 s,t,m,l:longint;//如题意所描述 i,j,ans:longint;//ans 是答案 procedure swap(var a,b:longint);//交换石头坐标的位置,排序用 var t:longint; begin t:=a; a:=b; b:=t; end; begin assign(input,'river.in');reset(input); assign(output,'river.out');rewrite(output); fillchar(a,sizeof(a),0); readln(l); readln(s,t,m); for i:=1 to m do read(stone[i]); ans:=0; if s=t then begin for i:=1 to m do if stone[i] mod s=0 then inc(ans); writeln(ans); close(input);close(output); halt; end;//特殊情况的处理,当 s=t 时青蛙的跳跃长度被固定,所以踩到的石子数也是固定的 for i:=1 to m-1 do for j:=i+1 to m do if stone[i]>stone[j] then swap(stone[i],stone[j]); //排序。不用快排是因为懒得敲代码了?? stone[m+1]:=l; for i:=1 to m+1 do if stone[i]-stone[i-1]>=100 then cp_stone[i]:=cp_stone[i-1]+100 else cp_stone[i]:=cp_stone[i-1]+stone[i]-stone[i-1];//空白压缩 l:=cp_stone[m+1];//压缩后的桥长需要变更 for i:=1 to m do a[cp_stone[i]]:=1;//压缩后有石头的地方标记为 1 f[0]:=0;//边界 for i:=1 to l+t do begin f[i]:=maxlongint-1;

for j:=t downto s do if i<j then break else if f[i-j]+a[i]<f[i] then f[i]:=f[i-j]+a[i]; end;//DP ans:=maxlongint; for i:=l to l+t do if ans>f[i] then ans:=f[i];//寻找答案,注意循环用 L~L+t 可以避免很大的时间消耗 writeln(ans); close(input);close(output); end. 4.图形复原(resume) 源程序名:resume.pas/c/cpp 输入文件名:resume.in 输出文件名:resume.out 时限:1 秒 问题描述: 小 y 是个几何迷。有一天,他画了一个 n 边形,且将 n 个顶点用 1,2,?,n 这 n 个连续自 然数随手编了一下号。然后他又画了一些不相交的对角线。如下图:

他把所有的边和对角线都写在一张纸上。对于上图,他写了 : (1,3),(3,2),(2,4),(4,5),(5,1),(1,4),(3,4)。 过了几个星期,他无意中发现了这张写着字的纸,可是怎么也找不着那个几何图形了。 他很想把 n 边形的编号复原,可是试了一天也没弄出来。你能帮助他吗? 输入格式 : 第一行 n(n<=50)。 下面的若干行,每行两个数 a,b,表示纸上写着(a,b)。 输出格式: 仅一行,按顺序依次输出顶点的编号。对于上面的例子,你的输出应该是 1 3 2 4 5。 1 5 4 2 3 也是符合题目要求的。两者区别只是逆时针和顺时针而已。 但是, 你的输出只能是 1 3 2 4 5!也就是说你必须把两个符合要求的输出比较大小 (先比 较第一位;第一位相等,就比较第二位;第二位相等??,依此类推) ,你的输出应该是较 小者! (这只是为了评测的方便) 输入样例: 5 13 32

24 45 51 14 34 输出样例: 13245 const maxn=50; var n:integer; a:array[1..maxn] of integer;{状态} g:array[1..maxn,1..maxn] of boolean; {i,j 之间是否有边} vis:array[1..maxn] of boolean; procedure init; var u,v:integer; begin assign(input,'resume.in'); reset(input); readln(n); fillchar(g,sizeof(g),false); while not eof()do {判断文件是否结束} begin readln(u,v); g[u,v]:=true; g[v,u]:=true; end; close(input); end; procedure search(depth:integer); var i:integer; begin if (depth>n) then begin if (g[a[1]][a[n]]) then begin for i:=1 to n-1 do write(a[i],' ');{输出结果} writeln(a[n]); close(output); halt; end; exit; end; for i:=1 to n do{枚举下一个点的编号-产生新状态}

if (not vis[i]) and (g[a[depth-1]][i]) then{约束条件} begin a[depth]:=i;{记下状态} vis[i]:=true; search(depth+1); vis[i]:=false; end; end; begin init; fillchar(vis,sizeof(vis),false); a[1]:=1; vis[1]:=true; assign(output,'resume.out'); rewrite(output); search(2); end.


相关文章:
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育专区。NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟试题 4(4P36) [题目描述]...
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_韩语学习_外语学习_教育专区。NOIP2013复赛模拟8解题报告 NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟...
CCF NOIP2013 解题报告&心得
复赛 提高组 day1 CCF NOIP2013 解题报告&心得虽然...第8 页共5 页 全国信息学奥林匹克联赛(NOIP2013)...模拟也写得装模作样 刚解禁 STL 封装 动态规划又...
noip2013复赛模拟5
noip2013 复赛模拟 5 试题名称 提交文件名 输入文件名 输出文件名 满分 限时 ...(142857) 2/2=1.0 3/8=0.375 45/56=0.803(571428) [输入格式] ...
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解
(count) 【分析】直接用最朴素的模拟来做,时间复杂度小于(数的个数*每个数...noip2013普及组复赛试题... 4页 免费 NOIP2013提高组解题报告 8页 免费 第...
Noip 2013 解题报告与参赛总结(PASCAL版)
Noip 2013 解题报告与参赛总结(PASCAL版)_学科竞赛_高中教育_教育专区。noip2013Noip 2013 解题报告与参赛总结(pascal 版) Noip 结束也有一段时间了,网上也能 查...
2014noip复赛模拟练习13(答案)
2014noip复赛模拟练习13(答案)_学科竞赛_初中教育_教育...输入 6 12 9 36 60 45 24 输出 3 输入 8 2...2013年注会经济法统考真题 2013年注会设计统考真题及...
NOIP2015普及组复赛解题报告
【思路】 模拟 【时空复杂度】 O(k),O(1) 2、扫雷游戏(mine.cpp/c/pas...NOIP2004普及组复赛解题... 8页 免费 NOIP2010普及组解题报告 9页 免费 NOIP...
NOIP2015提高组解题报告
解题说明】 直接模拟即可 【代码】 #include<...(n^2) 【思想难度】 6 【编程难度】 8 【总用...NOIP2015提高组复赛试题... 6页 免费 NOIP2015提高...
更多相关标签:
noip2016复赛解题报告 | noip2015复赛解题报告 | noip复赛模拟题 | noip普及组复赛模拟题 | noip提高组复赛模拟题 | noip2016解题报告 | noip2015解题报告 | noip2015day2解题报告 |