当前位置:首页 >> 计算机软件及应用 >>

NOIP2009提高组解题报告


[原创]NOIP2009 提高组解题报告{继续供大牛 BS} 2009-11-21 10:46 P.M. 第一题: 水题,按照题目要求去枚举。 注意, 同一个字母加密后的字母是一样的, 加密后一样的字母原字母也是一样的。 var s1,s2,s3:string; a,b:array['A'..'Z']of char; i:longint; c:char; procedure main; begin readln(s1); readln(s2); readln(s3); fillchar(a,sizeof(a),' '); fillchar(b,sizeof(b),' '); for i:=1 to length(s1) do if ((a[s1[i]]<>' ')and(a[s1[i]]<>s2[i])) or((b[s2[i]]<>' ')and(b[s2[i]]<>s1[i])) then begin writeln('Failed'); exit; end else begin a[s1[i]]:=s2[i]; b[s2[i]]:=s1[i]; end; for c:='A' to 'Z' do if a[c]=' ' then begin writeln('Failed'); exit; end; for i:=1 to length(s3) do write(a[s3[i]]); writeln; end; begin assign(input,'spy.in');

reset(input); assign(output,'spy.out'); rewrite(output); main; close(input); close(output); end. 第二题: 数论题, 分解质因数。通过 a0,a1,b0,b1 确定 X 中每项质因子的最大幂数和最小 幂数。然后再把每个质因子的幂数范围乘起来。 PS:参考程序过 10 个点的总耗时为 0.23 秒,评测环境为 2.10GHz 2.00GB const maxn=100; maxm=46341; type data = record n,c : longint; end; ans = record n,min,max : longint; end; arr = array[0..maxn]of data; var a0,a1,b0,b1 : longint; fa0,fa1,fb0,fb1 : arr; xmin,xmax,xn : array[0..maxn]of longint; bool : array[1..maxm]of boolean; next : array[1..maxm]of longint; procedure change( n : longint;var a:arr); var i,k,t : longint; begin fillchar(a,sizeof(a),0); t:=0; i:=2; while n>1 do begin if (i>trunc(sqrt(n)))and(t=0) then break; if i=-1 then break;

if n mod i=0 then begin inc(t); n:=n div i; end else begin if t>0 then begin inc(a[0].n); with a[a[0].n] do begin n:=i; c:=t; end; t:=0; end; i:=next[i]; end; end; if t>0 then begin inc(a[0].n); a[a[0].n].n:=i; a[a[0].n].c:=t; end; if n>1 then begin inc(a[0].n); a[a[0].n].n:=n; a[a[0].n].c:=1; end; end; { change } function get(var a : arr;n:longint):longint; var i : longint; begin for i:=1 to a[0].n do if a[i].n=n then exit(a[i].c); exit(0); end; { get } function min_(a,b : longint):longint; begin if a<b then exit(a) else exit(b);

end; { min } function max_(a,b : longint):longint; begin if a>b then exit(a) else exit(b); end; procedure cmin(n ,c : longint); var i : longint; begin for i:=1 to xn[0] do if xn[i]=n then begin xmin[i]:=max_(xmin[i],c); exit; end; inc(xn[0]); xn[xn[0]]:=n; xmin[xn[0]]:=c; xmax[xn[0]]:=maxlongint; end; { cmin } procedure cmax(n ,c : longint); var i : longint; begin for i:=1 to xn[0] do if xn[i]=n then begin xmax[i]:=min_(xmax[i],c); exit; end; inc(xn[0]); xn[xn[0]]:=n; xmax[xn[0]]:=c; xmin[xn[0]]:=0; end; { cmin } procedure init; var i,j:longint; begin fillchar(bool,sizeof(bool),true); for i:=2 to trunc(sqrt(maxm)) do if bool[i] then for j:=2 to maxm div i do

bool[i*j]:=false; j:=-1; fillchar(next,sizeof(next),255); for i:=maxm downto 1 do begin next[i]:=j; if bool[i] then j:=i; end; end; procedure main; var i,j,k,t: longint; begin readln(a0,a1,b0,b1); change(a0,fa0); change(a1,fa1); change(b0,fb0); change(b1,fb1); fillchar(xn,sizeof(xn),0); fillchar(xmax,sizeof(xmax),0); fillchar(xmin,sizeof(xmin),0); for i:=1 to fa1[0].n do cmin(fa1[i].n,fa1[i].c); for i:=1 to fb1[0].n do cmax(fb1[i].n,fb1[i].c); for i:=1 to fb1[0].n do begin k:=get(fb0,fb1[i].n); if k<fb1[i].c then cmin(fb1[i].n,fb1[i].c); end; for i:=1 to fa0[0].n do begin k:=get(fa1,fa0[i].n); if k<fa0[i].c then cmax(fa0[i].n,k); end; for i:=1 to xn[0] do begin if xmin[i]>xmax[i] then begin writeln(0);exit;end; if xmax[i]=maxlongint then begin writeln(0);exit;end; end; t:=1

; for i:=1 to xn[0] do t:=t*(xmax[i]-xmin[i]+1); writeln(t); end; { main } var tt:longint; begin assign(input,'son.in'); reset(input); assign(output,'son.out'); rewrite(output); readln(tt); init; for tt:=tt downto 1 do begin main end; close(input); close(output); end. 第三题: 图论题,两次 SPFA,用 a[i]表示从起点开始到 i 结点能经过的最小值,用 b[i] 表示从终点延反向边到达 i 结点能经过的最大值。Ans=max(b[i]-a[i])。 const maxn=100010; maxm=1000010; type data=record t,f,next:longint; end; var n,m,ls:longint; a,c,d,stack,v:array[0..maxn]of longint; f:array[1..maxn]of boolean; seg:array[1..maxm]of data; procedure insert_e(s,t,f1,f2:longint); begin inc(ls); seg[ls].t:=t;

seg[ls].f:=f1; seg[ls].next:=a[s]; a[s]:=ls; inc(ls); seg[ls].t:=s; seg[ls].f:=f2; seg[ls].next:=a[t]; a[t]:=ls; end; procedure init; var i,j,k,l:longint; begin readln(n,m); fillchar(a,sizeof(a),255); ls:=0; for i:=1 to n do read(v[i]); for i:=1 to m do begin readln(j,k,l); if l=1 then insert_e(j,k,1,2) else insert_e(j,k,3,3); end; end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure spfa1; var i,k,open,closed:longint; begin fillchar(c,sizeof(c),127); fillchar(f,sizeof(f),0); f[1]:=true; open:=0; closed:=1; stack[1]:=1; c[1]:=v[1]; while open<closed do

begin inc(open); k:=stack[open mod maxn]; f[k]:=false; i:=a[k]; while i<>-1 do begin if (seg[i].f and 1=1)and(min(c[k],v[seg[i].t])<c[seg[i].t]) then begin c[seg[i].t]:=min(c[k],v[seg[i].t]); if not f[seg[i].t] then begin f[seg[i].t]:=true; inc(closed); stack[closed mod maxn]:=seg[i].t; end; end; i:=seg[i].next; end; end; end; procedure spfa2; var i,k,open,closed:longint; begin fillchar(d,sizeof(d),0); fillchar(f,sizeof(f),0); f[n]:=true; open:=0; closed:=1; stack[1]:=n; d[n]:=v[n]; while open<closed do begin inc(open); k:=stack[open mod maxn]; f[k]:=false; i:=a[k]; while i<>-1 do begin if (seg[i].f and 2=2)and(max(d[k],v[seg[i].t])>d[seg[i].t]) then begin

d[seg[i].t]:=max(d[k],v[seg[i].t]); if not f[seg[i].t] then begin f[seg[i].t]:=true; inc(closed); stack[closed mod maxn]:=seg[i].t; end; end; i:=seg[i].next; end; end; end; procedure main; var i,ans:longint; begin spfa1; spfa2; ans:=0; for i:=1 to n do ans:=max(ans,d[i]-c[i]); writeln(ans); end; begin assign(input,'trade.in'); reset(input); assign(output,'trade.out'); rewrite(output); init; main; close(input); close(output); end. 第四题: 搜索题,有时候这个世界需要些暴力。DFS 搜索,每次选取填入的数的方案数进 行枚举。PS:据说从右下角直接枚举到左上角,比加剪枝也能拿 95 分。 var n,ans,l,time:longint; a:array[1..81,1..3]of longint; c:array[1..27,0..9]of boolean; v:array[1..81]of longint;

d,d2,d3:array[1..81]of longint; o:array[1..81]of longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure init; var i,j,k:longint; begin for i:=1 to 9 do for j:=1 to 9 do begin k:=(i-1)*9+j; a[k,1]:=i; a[k,2]:=j+9; a[k,3]:=(i-1)div 3*3+(j-1)div 3+1+18; v[k]:=10-max(abs(i-5),abs(j-5)); end; fillchar(c,sizeof(c),1); for i:=1 to 81 do begin read(d[i]); c[a[i,1],d[i]]:=false; c[a[i,2],d[i]]:=false; c[a[i,3],d[i]]:=false; end; end; procedure check; var i,t:longint; begin t:=0; for i:=1 to 81 do inc(t,d[i]*v[i]); if t>ans then ans:=t; end; procedure dfs(dep:longint); var

i,k:longint; begin if dep>l then begin check;exit;end; { if dep<1 then begin check;exit;end;} inc(time); if time>10000000 then begin writeln(ans);close(input); close(output);halt;end; k:=o[dep]; for i:=1 to 9 do if c[a[k,1],i] and c[a[k,2],i] and c[a[k,3],i] then begin c[a[k,1],i]:=false; c[a[k,2],i]:=false; c[a[k,3],i]:=false; d[k]:=i; dfs(dep+1); d[k]:=0; c[a[k,1],i]:=true; c[a[k,2],i]:=true; c[a[k,3],i]:=true; end; end; procedure main; var i,j,k,t:longint; begin d2:=d; for i:=1 to 81 do d3[i]:=9; for i:=1 to 81 do if d2[i]>0 then begin for j:=1 to 81 do if (a[i,1]=a[j,1])or(a[i,2]=a[j,2])or(a[i,3]=a[j,3]) then dec(d3[j]); end; l:=0; while true do begin k:=maxlongint; for i:=1 to 81 do if (d2[i]=0)and(d3[i]<k) then begin

k:=d3[i]*11+v[i]; j:=i; end; if k=maxlongint then break; inc(l); o[l]:=j; d2[j]:=10; for i:=1 to 81 do if (a[i,1]=a[j,1])or(a[i,2]=a[j,2])or(a[i,3]=a[j,3]) then dec(d3[j]); end; time:=0; ans:=-1; dfs(1); writeln(ans); end; begin assign(input,'sudoku.in'); reset(input); assign(output,'sudoku.out'); rewrite(output); init; main; close(input); close(output); end.

类别:oi 资料原创] | 评论 (20)

| 添加到搜藏 | 分享到 i 贴吧 | 浏览(1498) |

上一篇:Crafting Winning Solutions [Pa... 相关文章: 汇总]搜索题目推荐及解题报告 ? (转... ? 大牛 ZZX《奇怪问题》解题报告 最近读者:

下一篇:Derivatives

? POJ PKU 3705 解题报告(自己没有...

登 录 后 , 您 就 出 现 在 这 里 。 shihaoz 82341 薇薇 潍清 popso qq10135 colinlee_ renluyao e454 8475 安 fly ng01 51569 colin 12345 网友评论: 1 novosbirsk 2 2009-11-22 09:44 A.M. | 回复 回复 novosbirsk:是啊!比完赛后我突然间发现,怎么没 有 DP overture_wy 3 2009-11-22 09:58 A.M. | 回复 悲剧了,第二题枚举竟然写错了 qyjubriskxp 4 网 友:Lc 2009-11-22 07:39 P.M. | 回复 第二题最大数据是 20 亿,怎么分解? 如果筛法预处理质数表,时间明显超了。

2009-11-21 11:55 P.M. | 回复 不会吧。竟然没有出 DP!历年罕见啊。

5 2009-11-22 08:40 P.M. | 回复 回复 Lc: 素数表只需要到 O(n^0.5) overture_wy

6 2009-11-23 09:23 P.M. | 回复 源代码会在近期内补上 overture_wy 7 匿名 网友 2009-11-24 09:08 A.M. | 回复 有没有 c 语言版的啊!

8 2009-11-24 01:44 P.M. | 回复 考前全力 dp,于是杯具了…… pas_zoujp 9 2009-11-25 08:11 P.M. | 回复 我真的无语了,我好顿好顿练 DP 啊!!!竟然没有! 虽然一等,但是不爽!纠结中...

xiaohulihutu 10 网 友:...

2009-11-25 09:15 P.M. | 回复 有没有搞错啊,LZ。。。第三题分明是强连通分量+DP。。。很 明显的。。。虽然你这样子 SPFA 也可以做。。。但是时间方面 可能会很不优。。。。标程:强连通分量+DP。。。。。。时间: O(m)。 。 。 这才是最优解啊。 。 。 我就是强连通+dp 写的。 。 。 。 。 。 考试的时候。。。结果轻松 AC 了 2009-11-25 09:41 P.M. | 回复 回复...: 坚持 KISS 原则: SPFA 的平均时间复杂度是 O(E),也能轻松秒杀全部的数 据, 并且编程复杂度比较低, 两个 SPFA 的代码是可以直接 copy 再做修改的。

11

overture_wy

12

匿 名网友

2009-11-26 01:31 P.M. | 回复 最后一题果断 dancing links,100.。 但是有一位神牛,前 3 题花 1h 得 300,最后一题 dancing links 调了 2h 没出来得 5 分。。

13 2009-11-26 09:23 P.M. | 回复 回复匿名网友:Orz... overture_wy

14

匿 名网友

2009-11-26 10:16 P.M. | 回复 angwuy 好久不见了啊 果然更强大了

15 2009-11-27 05:36 P.M. | 回复 回复匿名网友:您牛是...? overture_wy 16 网 友:... 2009-12-02 10:38 P.M. | 回复 我又想说点什么了。 。 。 首先声明, 这个 SPFA 理论复杂度 O (kE) , k 是进队次数。不知 LZ 大牛是否做过一些 BT 的题目,数据故意 让你反复进队,以至于 SPFA 退化成 V^2。。。当然 noip 不可能 出如此猥琐数据哈。 纠正 LZ 两点: 1.SPFA 的编程复杂度约等于强连通分量。强连通分量,LZ 知道 的,DFS*2,甚至可以复制,只修改一点点。大概写得好就是 10 行*2 吧。至少我就是 12 行。同样的编程复杂度,强连通远优于 SPFA,何乐而不为? 2.不需要 2 次 SPFA。一次即可。第二次只是一个赤裸裸的广搜判 断是否到达。 LZ 不否认你的算法比较好想,比较适合于新手。但是本着科学严 谨的态度,我认为,强连通更好。而且如果强连通写的很熟练, 也是很好想以及很好写的方法。不知 LZ 是否同意? 不多说了,LZ 回一句吧 2009-12-03 06:49 P.M. | 回复 回复...: 请你给我构造一个这样的数据出来?难道你做过 ls 这样 BT 的题目?反正我没做过。 SPFA 编程复杂度约等于强连通???你强连通不让边反向? 难道你的强连通能在 80 行以内解决? 还有强连通是 DFS 而 spfa 是 BFS,如果数据是链还有可能爆 栈。 强连通理论复杂度 O(E)看起来很美妙,但是两次 DFS 加最后 一个 DP 总共三次 DFS 以及若干次对边的操作使它的常数远远 高于 SPFA。 当然不否认,强连通的算法很直观,考试时我也写的强连通, 也确实写得很快,但写了 100+行。我认为无论从出题人的本 意(NOIP 不考强连通),还是实际运行效果,以及编程复杂

17 春天的蛋

度和算法的美妙性来说,SPFA 都要强于强连通。 18 网 友:... 2009-12-03 10:17 P.M. | 回复 DP 是写在第二次 DFS 里面的。。。 2009-12-04 08:56 A.M. | 回复 回复...: 首先,SPFA 的 k 已被证明平均情况下是小于等于 2。 那种 bt 的数据也遇到过,但是这次再遇到也没办法。 不知道 16L 有没有遇到一种数据,大小大概是 100000 左右 的,能硬把折中取数的 qsort 卡到超时。 一般来说,这种 bt 的数据,除了省赛,其他比赛基本没发 现。 我们再假设一下,如果这题最大的数据点是一条长链,那 用递归写的 DFS 肯定会爆栈。 至于非递归的 DFS,恐怕编程复杂度。。。 最后我要说一句,不管黑猫白猫,只要能抓住老鼠的就是 好猫;不管是 SPFA 还是强连通块,只要能 AC 的就是好算 法。

19

overture_wy


相关文章:
NOIP2009提高组解题报告.doc
NOIP2009提高组解题报告NOIP2009提高组解题报告隐藏>>
QfhygeNOIP2009提高组解题报告.doc
QfhygeNOIP2009提高组解题报告 - | ||生活| 一个人总要走陌生
NOIP2009提高组解题报告.doc
NOIP2009提高组解题报告 - 满意答案第二题(Hankson 的趣味题,
2009noip提高组复赛题解.doc
2009noip提高组复赛题解_企业管理_经管营销_专业资料。NOIP2009 提高解告 NOIP2009 提高解告 一、伏者(spy) 描述: 出密文及...
sxnbgnNOIP2009提高组解题报告.doc
sxnbgnNOIP2009提高组解题报告_英语学习_外语学习_教育专区。Kpp
Bf-bcpyoNOIP2009提高组解题报告.doc
Bf-bcpyoNOIP2009提高组解题报告 - 、 .~ ① 我们‖打〈败〉了敌人。 ②我们‖〔把敌人〕打〈败〉了。 [原创]NOIP2009 提高组解题报告{继续供大牛 BS} ...
CabfzanNOIP2009提高组解题报告.doc
CabfzanNOIP2009提高组解题报告 - Time will pierc
IthneaNOIP2009提高组解题报告.doc
IthneaNOIP2009提高组解题报告 - 秋风清,秋月明,落叶聚还散,寒鸦栖复惊。 [原创]NOIP2009 提高组解题报告{继续供大牛 BS} 2009-11-21 10:46 P.M...
Cabfzan_aNOIP2009提高组解题报告.doc
Cabfzan_aNOIP2009提高组解题报告 - 、| !_ 一个人总要走陌
NOIP2009提高组复赛题解.doc
NOIP2009提高组复赛题解 - NOIP2009 提高组复赛题解(1) 20
noip2010提高组解题报告.doc
Noip2010 反观 2010 年的提高组题目:第一题机器翻译是一道纯模拟的题目, 第...NOIP2009提高组解题报告 16页 免费 NOIP2008提高组解题报告 13页 1下载券 喜欢...
NOIP2009提高组初赛试题及答案.doc
C) 通过互联网搜索取得解题思路。 D) 在提交的程序中启动多个进程以提高程序的执行效率。 NOIP2009 初赛 提高组 Pascal 3 三.问题求解(共 2 题,每空 5 分...
NOIP2009提高组复赛题解.doc
NOIP2009提高组复赛题解 - 1、潜伏者 program spy; var
NOIP2009_提高答案.doc
NOIP2009_提高答案 - 第十五届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 Pascal 语言 二小时完成 )○○ 全部试题答案均要求写在答卷纸上,写在试卷纸上一律...
Noip 2013 提高组 Day2 解题报告.doc
Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告 Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛...
NOIP2000-2009提高组解题报告(c语言).doc
noip2004 提高组解题报告(1)津津的储蓄计划(2009-08-25 21:42:12) 标签:pascal noip2004 提高组 津津的储蓄计划 解题报告 分类:解题报告 题目: 津津的储蓄...
noip2010提高组解题报告.doc
NOIP2010 解题报告(提高) 作者:张宇昊所有见解仅供参考 考试时。。。发挥 1/3...Noip 2013 提高组 解题报... 21页 1下载券 NOIP2000-2009提高组解题... ...
NOIP2009提高组C++初赛试题与答案.doc
NOIP2009提高组C++初赛试题与答案_学科竞赛_高中教育_教育专区。2009 第十五届...C) 通过互联网搜索取得解题思路。 D) 在提交的程序中启动多个进程以提高程序...
NOIP2010提高组解题报告.doc
NOIP2010提高组解题报告 - 1:机器翻译 var m,n,i,j,k,p
NOIP2009提高组复赛试题.pdf
NOIP2009提高组复赛试题 - 全国信息学奥林匹克联赛(NOIP2009)复
更多相关标签: