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

Noip 2013 解题报告与参赛总结（pascal版） Noip结束也有一段时间了，网上也能查到很多解题报告。虽然意义不大，但就当做是一点纪念吧，纪念我的第一次Noip。（也很可能是最后一次了） Day1 T1：应该不难看出是快速幂，只要把模板背过就可以轻松AC了。属于例行水题。 T2：首先分析出移动的结果应使得列中最大的数在一起，次大的数在一起，以此类推。因为要使化简下来的式子中两数之积最大。然后就是YY出只要移动一列即可达到效果。在此基础上处理发现实际是求序列中的逆序对数。这也不难，方法有两种，一种是树状数组或线段树，另一种更简单，代码也更容易实现。是通过归并排序求逆序对。只需要在归并排序中加一个计数器ANS。在“并”这一部分中记录一下即可，详细的看代码。T3：本次考试中较难的一道题，SPFA可以做到40-60分。并查集至少60分，听神犇说可以AC。比较常用的方法是树链剖分或树上倍增。还是说一下倍增吧（因为前一种太wo简bu单hui）。首先跑一遍最大生成树。（显然答案都只会是这棵树上边的权值）。然后处理倍增的数据，要记录两个内容，一个是2k的祖先，另一个是到祖先的路上最小权值。我用的是DFS的方法。每处理完一个节点就把信息传递给儿子。中间顺便记录每个节点的深度。倍增时先把询问的两个点处理到同一深度，然后同时向上倍增，直至倍增的祖先恰好相同，同时ANS不断记录更小的权值。Day2T1：竟然不是数论！数学弱渣太感谢出题人了。 方法很简单，从左到右扫一遍，如果当前点的高度大于前一个，就直接给ANS加上差值。T2：竟然也是O(N)！欺骗蒟蒻的感情！ 和T1一样简单，YY出ANS即为拐点的个数。记录拐点时注意一下，处理连续相同的等高的花。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 k0 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:array1.100000,1.2of longint; x,y:array1.100000of longint; n,i,j,k,m,ans:longint; procedure sorta(h,l:longint);var i,j,m:longint; k:array1.2of longint; begin i:=h; j:=l; m:=a(i+j)div 2,1; while ij do begin while ai,1m do dec(j); if i=j then begin k:=ai; ai:=aj; aj:=k; inc(i); dec(j); end; end; if il then sorta(i,l); if hj then sorta(h,j); end;procedure sortb(h,l:longint);var i,j,m:longint; k:array1.2of longint; begin i:=h; j:=l; m:=b(i+j)div 2,1; while ij do begin while bi,1m do dec(j); if i=j then begin k:=bi; bi:=bj; bj:=k; inc(i); dec(j); end; end; if il then sortb(i,l); if hc then begin xi:=bf2,1; inc(f2); inc(k); continue; end; if f2l then begin xi:=bf1,1; inc(f1); inc(ans,k); while ans=99999997 do dec(ans,99999997);continue; end; if bf1,1=99999997 do dec(ans,99999997); end else begin xi:=bf2,1; inc(f2); inc(k); end; end; for i:=h to l do bi,1:=xi; end; begin readln(n); for i:=1 to n do begin read(ai,1); ai,2:=i; end; for i:=1 to n do begin read(bi,1); bi,2:=i; end; sorta(1,n); sortb(1,n); for i:=1 to n do bbi,2,1:=ai,2; ans:=0; bing(1,n); write(ans);gram ss;(day1t3)type edgenode=edge; edge=record adj,w:longint; next:edgenode; end;var dp,mm:array1.10000,0.15of longint; a:array1.10000of edgenode; v:array1.10000of boolean; f,d:array1.10000of longint; e:array1.50000,1.3of longint; n,i,j,k,m,l,q,ans,x,y:longint; c:edgenode;function min(a,b:longint):longint; begin if ab then exit(a) else exit(b); end;procedure sort(h,l:longint);var i,j,m:longint; k:array1.3of longint; begin i:=h; j:=l; m:=e(i+j)div 2,3; while ij do begin while ei,3m do dec(j); if i=j then begin k:=ei; ei:=ej; ej:=k; inc(i); dec(j); end; end; if ih then sort(h,j); end; function find(x:longint):longint; begin if fx=x then exit(x); fx:=find(fx); exit(fx); end;procedure dfs(x,i:longint);var j:edgenode; k:longint; begin vx:=true; dx:=i; j:=ax; while jnil do begin if not vj.adj then begin dpj.adj,0:=x; mmj.adj,0:=j.w; k:=0; while dpdpj.adj,k,k0 do begin dpj.adj,k+1:=dpdpj.adj,k,k; mmj.adj,k+1:=min(mmj.adj,k,mmdpj.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(ei,1,ei,2,ei,3); for i:=1 to n do fi:=i; sort(1,m); k:=0; for i:=m downto 1 do if find(ei,1)find(ei,2) then begin ffind(ei,2):=find(ei,1); new(c); c.adj:=ei,2; c.w:=ei,3; c.next:=aei,1; aei,1:=c; new(c); c.adj:=ei,1; c.w:=ei,3; c.next:=aei,2; aei,2:=c; inc(k); if k=n-1 then break; end; for i:=1 to n do if not vi 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 dxdy then begin l:=x; x:=y; y:=l; end; ans:=maxlongint; l:=dx-dy; k:=0; while l0 do begin if l and 1=1 then begin ans:=min(ans,mmx,k); x:=dpx,k; end; l:=l shr 1; inc(k); end; k:=0; while xy do begin if (dpx,kdpy,k)or(k=0) then begin ans:=min(ans,min(mmx,k,mmy,k); x:=dpx,k; y:=dpy,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 jk 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 (a3a2)and(a2a1)or(a3a1) then inc(k); if a2=a3 then continue; a1:=a2; a2:=a3; end; write(k+2);end. program ss;(day2t2)const dx:array1.4of -1.1=(0,1,-1,0); dy:array1.4of -1.1=(1,0,0,-1); type edgenode=edge; edge=record dir,w:longint; next:edgenode; end; var v1,map:array0.31,0.31of boolean; a:array1.30,1.30,1.4of edgenode; d1:array1.30,1.30of longint; d2:array1.30,1.30,1.4of longint; q1:array1.10000,1.2of integer; q2:array1.100000,1.3of longint; v2:array1.30,1.30,1.4of 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; q11,1:=s1; q11,2:=s2; d1s1,s2:=0; v1s1,s2:=true; while fr do begin inc(f); p:=q1f,1; q:=q1f,2; for i:=1 to 4 do if (mapp+dxi,q+dyi)and(d1p+dxi,q+dyi=-1) then begin d1p+dxi,q+dyi:=d1p,q+1; if (p+dxi=t1)and(q+dyi=t2) then exit; if not v1p+dxi,q+dyi then begin inc(r); q1r,1:=p+dxi; q1r,2:=q+dyi; v1p+dxi,q+dyi:=true; end; end; v1p,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 mapi,j:=true; end; for i:=1 to n do for j:=1 to m do if mapi,j then for k:=1 to 4 do if mapi+dxk,j+dyk then begin mapi,j:=false; for l:=1 to 4 do if (kl)and(mapi+dxl,j+dyl) then begin bfs(i+dxk,j+dyk,i+dxl,j+dyl); if d1i+dxl,j+dyl-1 then begin new(c); c.dir:=l; c.w:=d1i+dxl,j+dyl; c.next:=ai,j,k; ai,j,k:=c; end; end; mapi,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; mapsx,sy:=false; for j:=1 to 4 do if mapsx+dxj,sy+dyj then begin bfs(ex,ey,sx+dxj,sy+dyj); if d1sx+dxj,sy+dyj-1 then begin inc(r); q2r,1:=sx; q2r,2:=sy; q2r,3:=j; d2sx,sy,j:=d1sx+dxj,sy+dyj; v2sx,sy,j:=true; end; end; mapsx,sy:=true; while fr do begin inc(f); c:=aq2f,1,q2f,2,q2f,3; while cnil do begin if (d2q2f,1,q2f,2,c.dir=-1) or(d2q2f,1,q2f,2,c.dird2q2f,1,q2f,2,q2f,3+c.w) then begin d2q2f,1,q2f,2,c.dir:=d2q2f,1,q2f,2,q2f,3+c.w; if not v2q2f,1,q2f,2,c.dir then begin inc(r); q2r,1:=q2f,1; q2r,2:=q2f,2; q2r,3:=c.dir; v2q2f,1,q2f,2,c.dir:=true; end; end; c:=c.next; end; if (d2q2f,1+dxq2f,3,q2f,2+dyq2f,3,5-q2f,3=-1) or(d2q2f,1+dxq2f,3,q2f,2+dyq2f,3,5-q2f,3d2q2f,1,q2f,2,q2f,3+1) then begin d2q2f,1+dxq2f,3,q2f,2+dyq2f,3,5-q2f,3:=d2q2f,1,q2f,2,q2f,3+1; if not v2q2f,1+dxq2f,3,q2f,2+dyq2f,3,5-q2f,3 then begin inc(r); q2r,1:=q2f,1+dxq2f,3; q2r,2:=q2f,2+dyq2f,3;q2r,3:=5-q2f,3; v2q2f,1+dxq2f,3,q