NOIP2010解题报告(附代码)

.NOIP2010解题报告. 第一题.应该比较简单,因为单词最大是1000，所以只需要设置一个布尔型的数组表示该单词是否被用过即可.初始时队列全部都为-1,每次读入一个数据x时判断flagx是否为true，如果不为true然后inc(ans),接着处理.program translate;varflag:array-10.1000 of boolean;q:array1.1000 of longint;i,n,m,x,mark,ans:longint;function next(x:longint):longint;beginif x=m then exit(1);exit(x+1);end;Beginassign(input,translate.in);reset(input);assign(output,translate.out);rewrite(output);readln(m,n);for i:=1 to m do qi:=-1;fillchar(flag,sizeof(flag),false);mark:=1;ans:=0;for i:=1 to n do begin read(x); if not flagx then begin mark:=next(mark);flagqmark:=false; flagx:=true;qmark:=x;inc(ans); end;end;writeln(ans);close(input);close(output);End.第二题.仔细分析一下就可以出来.这是一个四维DP.如果用fi,j,k,l表示数值为1的用了i个,数值为2的用了j个,数值为3的用了k个,数值为4的用了l个时能够得到的最大得分.那么对于某一个状态,就可以从四个已知的状态的来,即: fi,j,k,l:=max(fi-1,j,k,l,fi,j-1,k,l,fi,j,k-1,l,fi,j,k,l-1)+ai*1+j*2+k*3+l*4+1;初始f0,0,0,0:=a1;用sumi表示i数值的纸片有多少张.那么目标就是fsum1,sum2,sum3,sum4program tortoise;varsum:array1.4 of longint;f:array-1.40,-1.40,-1.40,-1.40 of longint;a:array0.400 of longint;i,j,k,l,n,m,x,mark:longint;function max(a,b,c,d:longint):longint;beginmax:=a;if maxb then max:=b;if maxc then max:=c;if maxd then max:=d;end;procedure init;beginassign(input,tortoise.in);reset(input);assign(output,tortoise.out);rewrite(output);readln(n,m);for i:=1 to n do read(ai);readln;fillchar(sum,sizeof(sum),0);for i:=1 to m do begin read(x);inc(sumx);end;end;procedure main;beginfillchar(f,sizeof(f),0);f0,0,0,0:=a1;for i:=0 to sum1 do for j:=0 to sum2 do for k:=0 to sum3 do for l:=0 to sum4 do begin mark:=i*1+j*2+k*3+l*4+1; fi,j,k,l:=max (fi-1,j,k,l,fi,j-1,k,l,fi,j,k-1,l,fi,j,k,l-1)+amark; end;writeln(fsum1,sum2,sum3,sum4);close(input);close(output);end;Begininit;main;End.第三题,其实这道题有很多种做法.本菜在此说说并查集怎么做.用x0表示x的反集合,y0表示y的反集合,也就是说如果不跟x同集合那就一定跟x0同集合,同理,如果不跟y同集合就一定跟y0同集合.这样先排序,从大到小往里添加边,每次判断是否有冲突,若有冲突,那么就输出,否则合并.program prison;constMAXM=100000;MAXN=20000;vara,b,v:array1.MAXM of longint;f:array1.MAXN*2 of longint;n,m:longint;procedure init;var i:longint;beginassign(input,prison.in);reset(input);assign(output,prison.out);rewrite(output);readln(n,m);for i:=1 to m do readln(ai,bi,vi);end;procedure sort(l,r:longint);var i,j,x,temp:longint;begini:=l;j:=r;x:=v(l+r+r) div 3;repeat while vix do dec(j); if i=j;if lj then sort(l,j);if ir then sort(i,r);end;function find(i:longint):longint;beginif fi=i then exit(i);if ffi=fi then exit(fi);find:=find(fi);fi:=find;end;procedure main;var i,nn,x,y,x0,y0:longint;beginsort(1,m);nn:=n+n;for i:=1 to nn do fi:=i;for i:=m downto 1 do begin x:=ai;y:=bi;x0:=x+n;y0:=y+n; x:=find(x);y:=find(y);x0:=find(x0);y0:=find(y0); if (x=y) or (x0=y0) then begin writeln(vi); close(input);close(output);halt; end; if xy0 then fx:=y0; if yx0 then fy:=x0;end;writeln(0);close(input);close(output);end;Begininit;main;End.第四题.这个问题其实可以分解成两个子问题,先求能否全部覆盖,如果能,就从第一行每一个点向下BFS,容易证明每一个点在最后一行能够覆盖的点是连续的,这样在最后一行就能够算出来一个区间,就可以先按左坐标排序,然后在最后一行进行DP,这样就能够解决了.动态转移方程:fj表示最后一行覆盖前j个需要的最小格数,用r表示右边界,l表示左边界,这样的话fj:=min(fj,fx+1);l-1xr-1;目标:fm;program flow;constdx:array1.4 of integer=(-1,0,1,0);dy:array1.4 of integer=(0,1,0,-1);varx,y:array1.250000 of integer;left,right,f:array0.500 of longint;vis,bor:array0.510,0.510 of boolean;a:array0.510,0.510 of longint;n,m:longint;procedure init;vari,j:longint;beginassign(input,flow.in);reset(input);assign(output,flow.out);rewrite(output);readln(n,m);fillchar(bor,sizeof(bor),false);for i:=1 to n do for j:=1 to m do begin read(ai,j);bori,j:=true; end;end;procedure checkbfs(sta:longint);vari,xx,yy,x0,y0,head,tail:longint;beginif vis1,sta then exit;vis1,sta:=true;x1:=1;y1:=sta;head:=0;tail:=1;while headax0,y0) and (not visx0,y0) and (borx0,y0) then begin visx0,y0:=true; inc(tail);xtail:=x0;ytail:=y0; end; end;end;end;procedure check;vari,num:longint;beginfillchar(vis,sizeof(vis),false);for i:=1 to m do checkbfs(i);num:=0;for i:=1 to m do if not visn,i then inc(num);if num0 then begin writeln(0);writeln(num); close(input);close(output);halt;end;end;procedure bfs(sta:longint);vari,xx,yy,x0,y0,head,tail:longint;beginfillchar(vis,sizeof(vis),false);leftsta:=maxlongint;rightsta:=0;x1:=1;y1:=sta;head:=0;tail:=1;while headtail do begin inc(head);xx:=xhead;yy:=yhead; if xx=n then begin if yyrightsta then rightsta:=yy; end; for i:=1 to 4 do begin x0:=xx+dxi;y0:=yy+dyi; if (axx,yyax0,y0) and (not visx0,y0) and (borx0,y0) then begin visx0,y0:=true; inc(tail);xtail:=x0;ytail:=y0; end; end;end;end;procedure sort(l,r:longint);var i,j,x,temp:longint;begini:=l;j:=r;x:=right(l+r+r) div 3;repeat while rightix do dec(j); if i=j;if lj then sort(l,j);if ir then sort(i,r);end;function min(a,b:longint):longint;beginif ab then exit(a);exit(b);end;procedure main;vari,j,l,r,mark:longint;begincheck;for i:=1 to m do bfs(i);sort(1,m);f0:=0;mark:=maxlongint shr 1;for i:=1 to