NOIP2010解题报告(附代码)

1、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;B

2、eginassign(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  

3、60;   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个时能够得到的最大得分.那么对于某一个状态,就可以从四个已知的状态的来,即:

4、0; 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:lo

5、ngint):longint;beginmax:=a;if max<b then max:=b;if max<c then max:=c;if max<d 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);f

6、or 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&#

7、160;         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;w

8、riteln(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.M

9、AXN*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;repe

10、at    while vi<x do inc(i);    while vj>x do dec(j);    if i<=j then begin      temp:=ai;ai:=aj;aj:=temp;      temp:=bi;bi:=bj;bj:=temp;      temp:=vi;vi:=vj;vj:=temp;

11、0;     inc(i);dec(j);    end;until i>=j;if l<j then sort(l,j);if i<r 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);

12、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

13、(input);close(output);halt;    end;    if x<>y0 then fx:=y0;    if y<>x0 then fy:=x0;end;writeln('0');close(input);close(output);end;Begininit;main;End.第四题.这个问题其实可以分解成两个子问题,先求能否全部覆盖,如果能,就从第一行每一个点向下BFS,容易证明每一个点在最后一行能够覆盖的点是连续的,这样在最后一行就能够

14、算出来一个区间,就可以先按左坐标排序,然后在最后一行进行DP,这样就能够解决了.动态转移方程:fj表示最后一行覆盖前j个需要的最小格数,用r表示右边界,l表示左边界,这样的话fj:=min(fj,fx+1);l-1<x<r-1;目标:fm;program flow;const  dx:array1.4 of integer=(-1,0,1,0);  dy:array1.4 of integer=(0,1,0,-1);var  x,y:array1.250000 of integer;  left,rig

15、ht,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;var  i,j:longint;begin  assign(input,'flow.in');reset(input);  assign(output,'flow.out');rewrite(o

16、utput);  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);var  i,xx,yy,x0,y0,head,tail:longint;begin &

17、#160;if vis1,sta then exit;  vis1,sta:=true;x1:=1;y1:=sta;  head:=0;tail:=1;  while head<tail do begin    inc(head);xx:=xhead;yy:=yhead;    for i:=1 to 4 do begin      x0:=xx+dxi;y0:=yy+dyi;      i

18、f (axx,yy>ax0,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;var  i,num:longint;begin&

19、#160; fillchar(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 num<>0 then begin    writeln(0);writeln(num);    close(input);close(out

20、put);halt;  end;end;procedure bfs(sta:longint);var  i,xx,yy,x0,y0,head,tail:longint;begin  fillchar(vis,sizeof(vis),false);  leftsta:=maxlongint;rightsta:=0;  x1:=1;y1:=sta;head:=0;tail:=1;  while head<tail do begin    inc

21、(head);xx:=xhead;yy:=yhead;    if xx=n then begin      if yy<leftsta then leftsta:=yy;      if yy>rightsta then rightsta:=yy;    end;    for i:=1 to 4 do begin      x0:=xx+dxi;y0:=yy+dyi;&#

22、160;     if (axx,yy>ax0,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

23、);var i,j,x,temp:longint;begin  i:=l;j:=r;x:=right(l+r+r) div 3;  repeat    while righti<x do inc(i);    while rightj>x do dec(j);    if i<=j then begin      temp:=righti;righti:=rightj;rightj:=temp;      temp:=lefti;lefti:=leftj;leftj:=temp;      inc(i);dec(j);