当前位置:首页 >> 学科竞赛 >> Noip 2013 解题报告与参赛总结(PASCAL版)

Noip 2013 解题报告与参赛总结(PASCAL版)


Noip 2013 解 题 报 告 与 参 赛 总 结 (pascal 版)
Noip 结束也有一段时间了,网上也能 查到很多解题报告。虽然意义不大,但 就当做是一点纪念吧,纪念我的第一次 Noip。 (也很可能是最后一次了)
Day1 T1:应该不难看出是快速幂,只要把模板 背过就可以轻松 AC 了。属于例行水题。 T2: 首先分析出移动的结果应使得列中最

大的数在一起, 次大的数在一起, 以此类推。 因为要使化简下来的式子中两数之积最大。 然后就是 YY 出只要移动一列即可达到效 果。在此基础上处理发现实际是求序列中的 逆序对数。这也不难,方法有两种,一种是 树状数组或线段树,另一种更简单,代码也 更容易实现。是通过归并排序求逆序对。只 需要在归并排序中加一个计数器 ANS。在 “并”这一部分中记录一下即可,详细的看

代码。 T3:本次考试中较难的一道题,SPFA 可 以做到 40-60 分。 并查集至少 60 分, 听神犇 说可以 AC。比较常用的方法是树链剖分或 树上倍增。还是说一下倍增吧(因为前一种 太 wo 简 bu 单 hui)首先跑一遍最大生成树。 。 (显然答案都只会是这棵树上边的权值) 。 然后处理倍增的数据,要记录两个内容,一 个是 2^k 的祖先,另一个是到祖先的路上最 小权值。 我用的是 DFS 的方法。 每处理完一 个节点就把信息传递给儿子。中间顺便记录 每个节点的深度。倍增时先把询问的两个点 处理到同一深度,然后同时向上倍增,直至 倍增的祖先恰好相同,同时 ANS 不断记录 更小的权值。 Day2 T1:竟然不是数论!数学弱渣太感谢出题 人了。 方法很简单,从左到右扫一遍,如果 当前点的高度大于前一个,就直接给 ANS 加上差值。 T2:竟然也是 O(N)!欺骗蒟蒻的感情!

和 T1 一样简单, 出 ANS 即为拐点 YY 的个数。记录拐点时注意一下,处理连续相 同的等高的花。 T3:我认为是这次比赛最难的一道题,因 为我写的时间最长。 (其实是自己代码能力 太渣) 。 这题看了大神的题解才算有点眉目, 朴素的 BFS 在大数据上明显超时, 如果你不 满足于 60 分的话就要压缩搜索中的冗余状 态。很明显,只需要知道目标方块和空白格 子的位置,这个局面就被确定了,而为了移 动目标方块必须使空白格子在它的周围。所 以我们可以这样处理:仅记录目标格子坐标 和紧挨的空白格子的方向。把它当做一个 点,然后预处理出每个点的距离,最后跑一 遍 SPFA 或 DIJ 就可以了。注意处理 S=T 的 情况。 另附全部 AC 代码(蒟蒻原创,必然 槽点多多,求轻喷)
program ss;(day1t1) var a,n,y,k,m,x:longint; begin readln(n,m,k,x);

a:=m; y:=10; while k<>0 do begin if k and 1=1 then a:=(a*y) mod n; y:=y*y mod n; k:=k shr 1; end; write((a+x)mod n); end.

program ss;(day1t2) var a,b:array[1..100000,1..2]of longint; x,y:array[1..100000]of longint; n,i,j,k,m,ans:longint; procedure sorta(h,l:longint); var i,j,m:longint; k:array[1..2]of longint; begin i:=h; j:=l; m:=a[(i+j)div 2,1]; while i<j do begin while a[i,1]<m do inc(i); while a[j,1]>m do dec(j); if i<=j then begin k:=a[i]; a[i]:=a[j]; a[j]:=k; inc(i); dec(j); end; end;

if i<l then sorta(i,l); if h<j then sorta(h,j); end; procedure sortb(h,l:longint); var i,j,m:longint; k:array[1..2]of longint; begin i:=h; j:=l; m:=b[(i+j)div 2,1]; while i<j do begin while b[i,1]<m do inc(i); while b[j,1]>m do dec(j); if i<=j then begin k:=b[i]; b[i]:=b[j]; b[j]:=k; inc(i); dec(j); end; end; if i<l then sortb(i,l); if h<j then sortb(h,j); end; procedure bing(h,l:longint); var i,k,c,f1,f2:longint; begin if h=l then exit; c:=(h+l)div 2; bing(h,c); bing(c+1,l); f1:=h; f2:=c+1; k:=0; for i:=h to l do

begin if f1>c then begin x[i]:=b[f2,1]; inc(f2); inc(k); continue; end; if f2>l then begin x[i]:=b[f1,1]; inc(f1); inc(ans,k); while ans>=99 999997 do dec(ans,99999997);continue; end; if b[f1,1]<b[f2,1] then begin x[i]:=b[f1,1]; inc(f1); inc(ans,k); while ans>=99999997 d o dec(ans,99999997); end else begin x[i]:=b[f2,1]; inc(f2); inc(k); end; end; for i:=h to l do b[i,1]:=x[i]; end; begin readln(n); for i:=1 to n do begin read(a[i,1]); a[i,2]:=i; end; for i:=1 to n do begin read(b[i,1]); b[i,2]:=i; end; sorta(1,n); sortb(1,n); for i:=1 to n do b[b[i,2],1]:=a[i,2]; ans:=0; bing(1,n); write(ans); end.

program ss;(day1t3) type edgenode=^edge; edge=record adj,w:longint; next:edgenode; end; var dp,mm:array[1..10000,0..15]of longint; a:array[1..10000]of edgenode; v:array[1..10000]of boolean; f,d:array[1..10000]of longint; e:array[1..50000,1..3]of longint; n,i,j,k,m,l,q,ans,x,y:longint; c:edgenode; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure sort(h,l:longint); var i,j,m:longint; k:array[1..3]of longint; begin i:=h; j:=l; m:=e[(i+j)div 2,3]; while i<j do begin while e[i,3]<m do inc(i); while e[j,3]>m do dec(j); if i<=j then begin

k:=e[i]; e[i]:=e[j]; e[j]:=k; inc(i); dec(j); end; end; if i<l then sort(i,l); if j>h then sort(h,j); end; function find(x:longint):longint; begin if f[x]=x then exit(x); f[x]:=find(f[x]); exit(f[x]); end; procedure dfs(x,i:longint); var j:edgenode; k:longint; begin v[x]:=true; d[x]:=i; j:=a[x]; while j<>nil do begin if not v[j^.adj] then begin dp[j^.adj,0]:=x; mm[j^.adj,0]:=j^.w; k:=0; while dp[dp[j^.adj,k],k]<>0 do begin dp[j^.adj,k+1]:=dp[dp[j^.adj,k],k]; mm[j^.adj,k+1]:=min(mm[j^.adj,k],mm[dp[j^.adj,k],k]); inc(k);

end; dfs(j^.adj,i+1); end; j:=j^.next; end; end; begin readln(n,m); for i:=1 to m do read(e[i,1],e[i,2],e[i,3]); for i:=1 to n do f[i]:=i; sort(1,m); k:=0; for i:=m downto 1 do if find(e[i,1])<>find(e[i,2]) then begin f[find(e[i,2])]:=find(e[i,1]); new(c); c^.adj:=e[i,2]; c^.w:=e[i,3]; c^.next:=a[e[i,1]]; a[e[i,1]]: =c; new(c); c^.adj:=e[i,1]; c^.w:=e[i,3]; c^.next:=a[e[i,2]]; a[e[i,2]]: =c; inc(k); if k=n-1 then break; end; for i:=1 to n do if not v[i] then dfs(i,0); readln(q); for i:=1 to q do

begin readln(x,y); if find(x)<>find(y) then begin writeln(-1); continue; end; if d[x]<d[y] then begin l:=x; x:=y; y:=l; end; ans:=maxlongint; l:=d[x]-d[y]; k:=0; while l<>0 do begin if l and 1=1 then begin ans:=min(ans,mm[x,k]); x:=dp[x,k]; end; l:=l shr 1; inc(k); end; k:=0; while x<>y do begin if (dp[x,k]<>dp[y,k])or(k=0) then begin ans:=min(ans,min(mm[x,k],mm[y,k])); x:=dp[x,k]; y:=dp[y,k]; inc(k);

end else dec(k); end; writeln(ans); end; end.

program ss;(day2t1) var n,k,i,j:longint; ans:int64; begin readln(n); k:=0; for i:=1 to n do begin read(j); if j>k then inc(ans,j-k); k:=j; end; write(ans); end.

program ss;(day2t2) var n,i,j,k,l,m,a1,a2,a3:longint; begin readln(n); if n=1 then begin write(1); halt; end; read(a1,a2); if n=2 then begin if a1=a2 then write(1) else write(2); halt; end; for i:=3 to n do begin read(a3); if ((a3>a2)and(a2<a1))or((a3<a2)and(a2>a1))

then inc(k); if a2=a3 then continue; a1:=a2; a2:=a3; end; write(k+2); end.

program ss;(day2t2) const dx:array[1..4]of -1..1=(0,1,-1,0); dy:array[1..4]of -1..1=(1,0,0,-1); type edgenode=^edge; edge=record dir,w:longint; next:edgenode; end; var v1,map:array[0..31,0..31]of boolean; a:array[1..30,1..30,1..4]of edgenode; d1:array[1..30,1..30]of longint; d2:array[1..30,1..30,1..4]of longint; q1:array[1..10000,1..2]of integer; q2:array[1..100000,1..3]of longint; v2:array[1..30,1..30,1..4]of boolean; ans,f,r,ex,ey,sx,sy,tx,ty,n,m,q,i,j,k,l:longint; c:edgenode; procedure bfs(s1,s2,t1,t2:integer); var r,f,i,p,q:longint; begin fillchar(d1,sizeof(d1),255); fillchar(v1,sizeof(v1),0); fillchar(q1,sizeof(q1),0);

f:=0; r:=1; q1[1,1]:=s1; q1[1,2]:=s2; d1[s1,s2]:=0; v1[s1,s2]:=true; while f<r do begin inc(f); p:=q1[f,1]; q:=q1[f,2]; for i:=1 to 4 do if (map[p+dx[i],q+dy[i]])and(d1[p+dx[i],q+dy[i]]=-1) then begin d1[p+dx[i],q+dy[i]]:=d1[p,q]+1; if (p+dx[i]=t1)and(q+dy[i]=t2) then exit; if not v1[p+dx[i],q+dy[i]] then begin inc(r); q1[r,1]:=p+dx[i]; q1[r,2]:=q+dy[i]; v1[p+dx[i],q+dy[i]]:= true; end; end; v1[p,q]:=false; end; end; begin readln(n,m,q); for i:=1 to n do for j:=1 to m do begin read(k); if k=1 then map[i,j]:=true; end; for i:=1 to n do for j:=1 to m do

if map[i,j] then for k:=1 to 4 do if map[i+dx[k],j+dy[k]] then begin map[i,j]:=false; for l:=1 to 4 do if (k<>l)and(map[i+dx[l],j+dy[l]]) then begin bfs(i+dx[k],j+dy[k],i+dx[l],j+dy[l]); if d1[i+dx[l],j+dy[l]]<>-1 then begin new(c); c^.dir:=l; c^.w:=d1[i+dx[l],j+dy[l]]; c^.next:=a[i,j, k]; a[i,j,k]:=c; end; end; map[i,j]:=true; end; for i:=1 to q do begin fillchar(q2,sizeof(q2),0); fillchar(d2,sizeof(d2),255); fillchar(v2,sizeof(v2),0); f:=0; r:=0; readln(ex,ey,sx,sy,tx,ty); if ((ex=sx)and(ey=sy))or((ex=0)or(ey=0)) then begin writeln(-1); continue; end; if(sx=tx)and(sy=ty)

then begin writeln(0); continue; end; map[sx,sy]:=false; for j:=1 to 4 do if map[sx+dx[j],sy+dy[j]] then begin bfs(ex,ey,sx+dx[j],sy+dy[j]); if d1[sx+dx[j],sy+dy[j]]<>-1 then begin inc(r); q2[r,1]:=sx; q2[r,2]:=sy; q2[r,3]:=j; d2[sx,sy,j]:=d1[sx+dx[j],sy+dy[j]]; v2[sx,sy,j]:=true; end; end; map[sx,sy]:=true; while f<r do begin inc(f); c:=a[q2[f,1],q2[f,2],q2[f,3]]; while c<>nil do begin if (d2[q2[f,1],q2[f,2],c^.dir]=-1) or(d2[q2[f,1],q2[f,2],c^.dir]>d2[q2[f,1],q2[f,2],q2[f,3]]+c^. w) then begin d2[q2[f,1],q2[f,2],c^.dir]:=d2[q2[f,1],q2[f,2],q2[f,3]]+c^.w; if not v2[q2[f,1],q2[f,2],c^.dir]

then begin inc(r); q2[r,1]:=q2[f,1]; q2[r,2]:=q2[f,2]; q2[r,3]:=c^.dir; v2[q2[f,1],q2[f,2],c^.dir]:=true; end; end; c:=c^.next; end; if (d2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]=-1) or(d2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]>d2[q2[f, 1],q2[f,2],q2[f,3]]+1) then begin d2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]:=d2[q2[f,1], q2[f,2],q2[f,3]]+1; if not v2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]] then begin inc(r); q2[r,1]:=q2[f,1]+dx[q2[f,3]]; q2[r,2]:=q2[f,2]+dy[q2[f, 3]];q2[r,3]:=5-q2[f,3]; v2[q2[f,1]+dx[q2[f,3]],q2[f,2]+dy[q2[f,3]],5-q2[f,3]]:=true; end; end; v2[q2[f,1],q2[f,2],q2[f,3]]:=false; end; ans:=maxlongint; for j:=1 to 4 do if (d2[tx,ty,j]<>-1)and(d2[tx,ty,j]<ans) then ans:=d2[tx,ty,j]; if ans=maxlongint then writeln(-1) else writeln(ans);

end; end.

总结:客观的讲 425 分已经是很接近自己 理想的状态了,毕竟会做的题一分也没有 失, 至于不会做的, 那早该是意料之中的事。 虽然被各路 AK 神犇碾成狗,但也算对得起 自己 3 个月来的付出了。身在陕西,一等足 矣。但还是不得不承认,自己暴露的不足还 是很多,例如 D2T2,明显有 O(N)的解法, 但却因想出了 NLogN 的 DP 而冲昏了头脑。 还有两天的两道压轴,本来都能骗更多得 分,但或许是定式思维太重,或许是平时训 练的太少,加起来也只的了 55 分。可无论 如何 Noip2013 已经结束了, 我面临的是滚 回去高考还是冲击省队的抉择。但这些都不 是最重要的,虽然前路不是加分,更不会是 报送,但自从我选择这条路就没有后悔过。 这 6 道题或许会是我 OI 生涯的句号,或许 是另一段历程的开始。一直很喜欢一句话, 很多事情假如没有开始,也不会有结束。我 不会伤感自己的高中只是在机房中逝去,相 反,OI 已经让我懂得,无悔的付出才是最

美的回忆。只是有一点遗憾,不太可能为附 中创造 NOI 零的突破了, 有点力不从心的味 道,当然,我不会轻言放弃,但更多的还是 期待更有天赋的学弟学妹们,陕西的学生并 不比南方差,我们中的很多只是欠缺优秀教 育资源与一个发现自己的机会。但愿陕西 O I 从此崛起。 PS:唯一一次写解题报告,很多问题都 说的不太清楚,废话也说多了。都怪我表达 能力太差了,望见谅。 By SDFZ HYF


更多相关文档:

Noip 2013 解题报告与参赛总结(PASCAL版)

Noip 2013 解题报告与参赛总结(PASCAL版)_学科竞赛_高中教育_教育专区。noip2013Noip 2013 解题报告与参赛总结(pascal 版) Noip 结束也有一段时间了,网上也能 查...

CCF NOIP2013 解题报告&心得

CCF NOIP2013 解题报告&心得_学科竞赛_高中教育_教育...pascal 语 fpc -lm fpc lm match.pas 言 circle...积木大赛 bloc k bloc k block.in 花匠 flowe r...

NOIP2013解题报告

NOIP2013解题报告_计算机软件及应用_IT/计算机_专业资料。NOIP2013解题报告 第一题 计数问题(count.pas/c/cpp) 题目大意: 给出两个数n,x,让你求1...n之间的...

Pascal 2013解题报告和心得文档

Pascal 2013解题报告和心得文档_调查/报告_表格/模板_实用文档。搞笑心得!!!计数...如果读者尝试过NOIp2005 提高组《等价表 达式》, 那么这道题目其实非常轻松。 ...

NOIP2013复赛模拟8解题报告

NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育专区。NOIP2008 模拟试题 1(...【pascal 程序】 var a,f:array [0..100000] of longint;//a 是压缩后...

Noip 2013 Day1 解题报告

Noip 2013 Day1 解题报告 --By GreenCloudS 第一题:转圈游戏(快速幂)根据题目,答案明显是(x+10^km) mod n,化简一下,就成了(x + m (10^k mod n) ...

NOIP2013复赛模拟8解题报告

NOIP2013复赛模拟8解题报告_韩语学习_外语学习_教育专区。NOIP2013复赛模拟8解题报告 NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟...

NOIP2013普及组第二题解题报告(汇文客原创)

NOIP2013普及组第二题解题报告(汇文客原创)_学科竞赛_初中教育_教育专区。2.表达式求值 (expr.cpp/c/pas) 【问题描述】 给定一个只包含加法乘法的算术表达式...

NOIP2013初赛提高组Pascal试题及答案

NOIP2013初赛提高组Pascal试题及答案_学科竞赛_高中教育_教育专区。NOIP2013初赛提高组Pascal试题及答案 完美word版第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pas...
更多相关标签:
noip2015跳石头pascal | noip pascal | noip提高组初赛pascal | noip2016初赛pascal | noip 取消pascal | noip矩形覆盖pascal | noip普及组初赛pascal | noip2015 幻方 pascal |
网站地图

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