当前位置：文档库 › NOIP经验总结

NOIP经验总结

?
-------总结bfs：
==============================搜索=========================

--八数码难题(加上优化)

--引水入城
--骑士巡游BFS
CONST
DX:ARRAY[1..8]OF INTEGER=(2,-1,-2,-2,-1,1,2,1);
DY:ARRAY[1..8]OF INTEGER=(1,2,1,-1,-2,-2,-1,2);
TYPE
REC=RECORD
X,Y : INTEGER;
MAP : ARRAY[1..5,1..5]OF INTEGER;
END;

VAR
Q:ARRAY[0..1000000]OF REC;
I,J,K,M,N,S,XX,YY:LONGINT;
HEAD,TAIL:LONGINT;
TEMP:ARRAY[1..5,1..5]OF INTEGER;
F:BOOLEAN;

PROCEDURE PRINT;
BEGIN
FOR i:=1 TO 5 DO BEGIN
FOR J:=1 TO 5 DO WRITE(Q[TAIL].MAP[I,J]:3);
WRITELN;
END;
WRITELN(TAIL);
END;

BEGIN
HEAD:=0; TAIL:=0;
Q[TAIL].MAP[1,1]:=1;
Q[TAIL].X:=1;
Q[TAIL].Y:=1;
F:=FALSE;
REPEAT
INC(HEAD);
XX:=Q[HEAD].X;
YY:=Q[HEAD].Y;
TEMP:=Q[HEAD].MAP;
FOR I:=1 TO 8 DO
IF (XX+DX[I]<=5) AND(XX+DX[I]>=1) AND
(YY+DY[I]<=5) AND(YY+DY[I]>=1) AND
(TEMP[XX+DX[I],YY+DY[I]]=0) THEN BEGIN
INC(TAIL);
Q[TAIL].MAP:=TEMP;
Q[TAIL].X:=XX+DX[I];
Q[TAIL].Y:=YY+DY[I];
Q[TAIL].MAP[XX+DX[I],YY+DY[I]]:=Q[HEAD].MAP[XX,YY]+1;
IF Q[TAIL].MAP[XX+DX[I],YY+DY[I]]=25 THEN BEGIN
PRINT;
F:=TRUE;
BREAK;
END;
END;
UNTIL (HEAD>=TAIL)OR F;
READLN;
END.

=====================并查集==============================
解题步骤
-建立集合 -makeset
-查找某个元素是否在一个给定的集合内 -find
-合并两个集合 -union

function find(x:integer):integer;//find用于查找该元素的father值
begin
if father[x]=x then exit(x);
father[x]:=find(father[x]);
exit(father[x]);
end;
peocedure union(x,y:integer):integer;//rank用于记录集合中的元素数
var fx,fy:integer;
begin
fx:=find(x);
fy:=find(y);
if fx=fy then exit;
if rank[fx]=rank[fy] then begin
father[fx]:=fy;
inc(rank[fy]);
exit;
end;
if rank[fx]>rank[fy] then begin
father[fy]:=fx;
exit;
end else father[fx]:=fy;
end;

--bug`s life
const maxn=2001;
var father,kind:array[1..maxn] of integer;
n,m,t,i,a,b,j:integer; flag:boolean;
function find(v:integer):integer;
var f:integer;
begin
if father[v]=v then exit(v);
f:=find(father[v]);
kind[v]:=(kind[v]+kind[father[v]]) mod 2;
father[v]:=f;
exit(father[v]);
end;
function union(x,y:integer):boolean;
var fa,fb:integer;
begin
fa:=find(x);
fb:=find(y);
if fa=fb then begin
if kind[x]=kind[y] then exit(true)
end

else begin
father[fa]:=fb;
kind[fa]:=(kind[x]+kind[y]+1) mod 2;
end;
exit(false);
end;
begin
readln(t);
for i:=1 to t do begin
flag:=false;
readln(n,m);
for j:=1 to n do begin
father[j]:=j;
kind[j]:=0;
end;
for j:=1 to m do begin
readln(a,b);
if union(a,b) then flag:=true;
end;
if flag then begin writeln('Scenario #',i,':');writeln('Suspicious bugs found!');
end
else begin writeln('Scenario #',i,':');writeln('No Suspicious bugs found!');
end;
end;
readln;
end.

--食物链
CONST MAXN=50005;
VAR FATHER,KIND:ARRAY[1..MAXN]OF LONGINT;
I,J,K,X,Y,N,D,ANS,A,B:LONGINT;
FUNCTION FIND(X:LONGINT):LONGINT;
VAR T:LONGINT;
BEGIN
IF FATHER[X]=X THEN EXIT(X);
T:=FATHER[X];
FATHER[X]:=FIND(T);
KIND[X]:=(KIND[T]+KIND[X]) MOD 3;
EXIT(FATHER[X]);
END;
PROCEDURE UNION(D,X,Y:LONIGNT);
VAR XX,YY:LOINGINT
BEGIN
XX:=FIND(X);
YY:=FIND(Y);
FATHER[XX]:=YY;
KIND[XX]:=(KIND[Y]-KIND[X]+2+D) MOD 3;
END;
BEGIN {main}
READLN(N,K);
FOR I:=1 TO N DO BEGIN
FATHER[I]:=I;
KIND[I]:=0;
END;
FOR I:=1 TO K DO BEGIN
READLN(D,X,Y);
IF (D=2)AND(X=Y) THEN BEGIN
INC(ANS);
CONTINUE;
END;
IF (X>N)OR (Y>N) THEN BEGIN
INC(ANS);
CONTINUE;
END;
A:=FIND(X);
B:=FIND(Y);
IF A=B THEN BEGIN
IF (D=1)AND(KIND[X]<>KIND[Y]) THEN INC(ANS);
IF (D=2)AND(KIND[X]<>(KIND[Y]+1) MOD 3) THEN INC(ANS);
END
ELSE UNION(D,X,Y);
END;
WRITELN(ANS);
END.

==========================================动态规划============================
--装箱问题
FOR I:=1 TO N DO READLN(VOLUME[I]);
FILLCHAR(H,SIZEOF(H),FALSE); H[0]:=TRUE;
FOR I:=1 TO N DO
FOR K:=V DOWNTO VOLUME[I] DO
H[K]:=H[K] OR H[K-VOLUME[I]];

--01PACK
FOR I:=1 TO N DO
FOR J:=M DOWNTO W[I] DO
F[J]:=MAX(F[J],F[J-W[I]]+C[I]);

--ALL PACK
FOR I:=1 TO N DO
FOR J:=W[I] TO M DO
F[J]:=MAX(F[J],F[J-W[I]]+C[I]) ;

--MULTIPIE PACK
FOR I:=1 TO N DO READLN(W[I],C[I],M[I]);
FOR I:=1 TO N DO
FOR K:=1 TO M[I] DO
IF K*W[I]<=V THEN
FOR J:=V DOWNTO K*W[I] DO
F[J]:=MAX(F[J],F[J-W[I]]+C[I]);

--MIX PACK
READLN(N,V);
FOR I:=1 TO N DO READLN(M[I],W[I],C[I]);
FOR I:=1 TO N DO BEGIN
IF M[I]=1 THEN BEGIN
FOR J:=V DOWNTO W[I] DO
F[J]:=MAX(F[J],F[J-W[I]]+C[I]);
CONTINUE;
END;
IF M[I]=-1 THEN BEGIN
FOR J:=W[I]TO V DO
F[J]:=MAX(F[J],F[J-W[

I]]+C[I]);
CONTINUE;
END;
K:=1;
WHILE K<=M[I] DO BEGIN
FOR J:=V DOWNTO K*W[I] DO
F[J]:=MAX(F[J],F[J-W[I]]+C[I]);
DEC(M[I],K);
K:=K SHL 1;
END;
IF M[I]<>0 THEN
FOR J:=V DOWNTO M[I]*W[I] DO
F[J]:=MAX(F[J],F[J-M[I]*W[I]]+M[I]*C[I]);
END;

--最长不下降子序
FOR I:=1 TO N DO F[I]:=1;
FOR I:=N-1 DOWNTO 1 DO
FOR J:=I+1 TO N DO
IF (M[J]<=M[I])AND F[I]
--滑雪
//求最长下降子序的最长的子段
READLN(N,M);
FOR I:=1 TO N DO
FOR J:=1 TO M DO BEGIN
Z:=(I-1)*M+J;
READ(A[Z]);
X[Z]:=I; Y[Z]:=J;
END;
--快排
FOR I:=1 TO N DO F[I]:=1;
FOR I:=N-1 DOWNTO 1 DO
FOR J:=I+1 TO N DO
IF (ABS(X[I]-X[J])+ABS(Y[I]-Y[J])=1) AND(A[I]>A[J]) THEN F[I]:=F[J]+1;
--FIND MAX IN F & OUTPUT

--打鼹鼠 HNOI 2004
//排序后求最长不下降的最长子段
READLN(N,M);
FOR I:=1 TO M DO BEGIN
READLN(TIME,XX,YY);
Q[I].T:=TIME; Q[I].X:=XX; Q[I].Y:=YY;
END;
--快排注意要交换坐标
FOR I:=2 TO M DO //--!!注意求最长不下降子段
FOR J:=1 TO I-1 DO BEGIN
XXX:=ABS(Q[I].X-Q[J].X)+ABS(Q[I].Y-Q[J].Y); YYY:=ABS(Q[I].T-Q[J].T);
IF (XXX<=YYY) AND (LEN[j]+1>LEN[i]) //当一直时间内可以到达的距离均可以被逮到
THEN LEN[i]:=LEN[j]+1;
END;

--花店橱窗 TYVJ 1124

--NOIP2008普及03 传球游戏TYVJ 1008

--盖房子 TYVJ 1189
READLN(N,M);
FOR I:=1 TO N DO
FOR J:=1 TO M DO READ(F[I,J]);
FOR I:=1 TO N DO
FOR J:=1 TO M DO BEGIN
IF F[I,J]<>0 THEN F[I,J]:=MIN(MIN(F[I-1,J],F[I,J-1]),F[I-1,J-1])+1;
IF F[I,J]>MAX THEN MAX:=F[I,J];
END;
WRITELN(MAX);

--积木城堡 TYVJ 1190
var i,n:integer;
max,high,j,x:longint;
f:array[0..10100] of boolean;
ans:array[0..10100] of longint;
begin
readln(n);;
for i:=1 to n do begin
read(x);
high:=0;
fillchar(f,sizeof(f),false);
f[0]:=true;
while x<>-1 do begin
high:=high+x;
for j:=high downto x do
if f[j-x] then f[j]:=true;
read(x);
end;
if maxfor j:=0 to max do
if f[j] then inc(ans[j]);
end;
for i:=max downto 0 do
if ans[i]=n then begin
writeln(i);
break;
end;
end.

--合唱队形 TYVJ1702 最长不下降子序
var i,j,n,max:longint;
f,len1,len2,a:array[1..110] of longint;
begin
readln(n);
for i:=1 to n do begin
read(a[i]);
len1[i]:=1; len2[i]:=1;
end;

for i:=2 to n do
for j:=1 to i-1 do
if (a[j]len1[i])

then len1[i]:=len1[j]+1;
for i:= n-1 downto 1 do
for j:=i+1 to n do
if (a[j]
for i:=1 to n do
if len1[i]+len2[i]-1>max then max:=len1[i]+len2[i]-1;
writeln(n-max);
end.

--扫雷
var
f:array[0..1000,0..1,0..1]of integer;
a:array[1..1000]of integer;
n,i,j,k1,k2,k3:integer;
begin
readln(n);
for i:=1 to n do read(a[i]);
fillchar(f,sizeof(f),0);
f[0,0,0]:=1; f[0,0,1]:=1;
for i:=1 to n do
for k1:=0 to 1 do
for k2:=0 to 1 do
for k3:=0 to 1 do
if (k1+k2+k3)=a[i] then inc(f[i,k2,k3],f[i-1,k1,k2]);
writeln(f[n,1,0]+f[n,0,0]);
end.

--过河 TYVJ1059
var l,i,j,x:longint; m,s,t,max,ans:integer;
a:array[0..110] of longint;
f:array[-10..30000] of integer; v:array[-10..30000] of boolean;
procedure sort;
var i,j,t:longint;
begin
for i:=1 to m-1 do
for j:=i+1 to m do
if a[i]>a[j] then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end;
end;
procedure work; //DP
var i,j:longint;
begin
for i:=1 to a[m]+t do f[i]:=110;
for i:=1 to a[m]+t do
for j:=s to t do begin
if (v[i]=true) and (f[i-j]+1=0) then f[i]:=f[i-j]+1;
if (v[i]=false) and (f[i-j]=0) then f[i]:=f[i-j];
end;
ans:=maxint;
for i:=a[m] to a[m]+t do if f[i]end;
begin
readln (l); readln (s,t,m);
for i:=1 to m do read (a[i]);
if s<>t then begin
a[0]:=0; max:=100+2*t; {also: 100 or s*t is right s*t的时间效率更好?}
sort;
fillchar (v,sizeof(v),false);
for i:=1 to m do begin //此循环为状态压缩
if a[i]-a[i-1]>=max then begin
x:=a[i]-a[i-1]-max;
for j:=i to m do a[j]:=a[j]-x; //注意：若两个石子间距缩小后，后面的石子要前移
end;
v[a[i]]:=true;
end;
work;
end
else begin
for i:=1 to m do if a[i] mod t=0 then ans:=ans+1; //s=t时
end;
writeln (ans);
end.

--能量项链 TYVJ1056

--删数 TYVJ1078 （类似矩阵取数的动态规划）
var f:array[0..1000,0..1000] of longint;
i,j,k,n,h,t,sum:longint;
a:array[1..1000] of longint;
function max(aa,bb:longint):longint;
var x:longint;
begin
if aa>bb then exit(aa) else exit(bb);
end;
begin
readln(n);
for i:=1 to n do begin
read(a[i]);
f[i,i]:=a[i];
end;
for h:=2 to n do
for i:=1 to n-h+1 do begin
j:=i+h-1;
sum:=abs(a[i]-a[j])*(j-i+1);
for k:=i to j-1 do
f[i,j]:=max(f[i,j],f[i,k]+f[k+1,j]);
f[i,j]:=max(f[i,j],sum);

end;
writeln(f[1,n]);
end.

--搭建双塔 TYVJ 1114
FOR I:=1 TO K DO BEGIN
READ(T);
INC(A[T,0]);
READ(A[T,A[T,0]]);
END;

FOR I:=1 TO N+1 DO F[I]:=N;
FOR I:=N DOWNTO 1 DO BEGIN
IF A[I,0]=0 THEN F[I]:=F[I+1] ELSE F[I]:=0;
FOR J:=1 TO A[I,0]DO F[I]:= MAX(F[I],F[I+A[I,J]]-A[I,J]); ///////
END;
WRITELN(F[1]);

--nick的任务 TYVJ1034
var i,j,k,n,num:longint;
f:array[1..10001] of longint;
a:array[1..10000,0..1000] of longint;

function max(aa,bb:longint):longint;
begin
if aa>bb then exit(aa) else exit(bb);
end;
begin
readln(n,k);
for i:=1 to k do begin
read(num);
inc(a[num,0]);
read(a[num,a[num,0]]);
end;
for i:=1 to n+1 do
f[i]:=n;
for i:=n downto 1 do begin
if a[i,0]=0 then f[i]:=f[i+1]
else f[i]:=0;
for j:=1 to a[i,0] do
f[i]:=max(f[i],f[i+a[i,j]]-a[i,j]);

end;
writeln(f[1]);
readln;
end.

--乌龟棋 TYVJ1402
var f:array[-1..40,-1..40,-1..40,-1..40]of longint;
a:array[1..400]of longint;
b:array[1..4]of longint;
n,m,i,j,k,l,o,p:longint;
function max(a,b:longint):longint;
begin
if(a>b)then exit(a) else exit(b);
end;
begin
readln(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to m do begin
read(j);
inc(b[j]);
end;
for i:=0 to b[1] do
for j:=0 to b[2] do
for k:=0 to b[3] do
for l:=0 to b[4] do begin
f[i,j,k,l]:=max(f[i-1,j,k,l],f[i,j-1,k,l]);
f[i,j,k,l]:=max(f[i,j,k,l],f[i,j,k-1,l]);
f[i,j,k,l]:=max(f[i,j,k,l],f[i,j,k,l-1]);
f[i,j,k,l]:=a[i+j*2+k*3+l*4+1]+f[i,j,k,l];
end;
writeln(f[b[1],b[2],b[3],b[4]]);
end.

--USACO 3.3.4 Home on the Range 家的范围
VAR
F:ARRAY[0..250,0..250]OF LONGINT;
A:ARRAY[0..250]OF LONGINT;
I,J,K,M,N,L,P:longint;
X:CHAR;
FUNCTION MIN(A,B:LONGINT):LONGINT;
BEGIN
IF (AEND;
BEGIN
READLN(N);
FOR I:=1 TO N DO BEGIN
FOR J:=1 TO N DO BEGIN
READ(X); F[I,J]:=ORD(X)-48;
END;
READLN;
END;
FOR I:=1 TO N DO
FOR J:=1 TO N DO
IF F[I,J]<>0 THEN F[I,J]:=MIN(MIN(F[I-1,J],F[I,J-1]),F[I-1,J-1])+1;
FOR I:=1 TO N DO
FOR J:=1 TO N DO INC(A[F[I,J]]);
FOR I:=2 TO N DO
FOR J:=I+1 TO N DO A[I]:=A[I]+A[J];
FOR I:=2 TO N DO IF A[I]<>0 THEN WRITELN(I,' ',A[I]);
END.

--道路游戏 NOIP2009P4 **********not pass****************************
program game; {AC 100/1675ms}
var price:array[1..1000]of longint; f:array[0..1000]of longint; n,m,p:longint;
c:array[0..1000,0..1000]of longint; cash:array[0..1000,0..1000]of longint;
procedure init;
var i,j,k,temp:longint;
begin
read(n,m,p);
for i:=1 to n

do
for j:=1 to m do read(c[i,j]);
for i:=1 to n do read(price[i]);
for i:=1 to n do begin
cash[i,1]:=c[i,1];
for j:=2 to m do begin
temp:=(i+j-1)mod n;
if temp=0 then temp:=n;
cash[i,j]:=cash[i,j-1]+c[temp,j];
end;
end;
end;
procedure Main;
var i,j,k,max,temp,FactroyPosition:longint;
begin
f[0]:=0;
for i:=1 to m do begin
max:=-1;
for k:=1 to n do
for j:=1 to p do begin
if i-j<0 then break;
FactroyPosition:=(k+i-j)mod n;
if FactroyPosition=0 then FactroyPosition:=n;
temp:=f[i-j]+cash[k,i]-cash[k,i-j]-price[FactroyPosition];
if temp>max then max:=temp;
end;
f[i]:=max;
end;
end;
begin Init; Main; writeln(f[m]); end.

--最长公共子序列（最长共公子串） TYVJ1050 *****************not pass**************
const maxlen=2000;
var i,j,p,l1,l2:longint;
F:array[0..maxlen,0..maxlen] of longint;
s1,s2,z:string;
function max(aa,bb:longint):longint;
begin
if aa>bb then exit(aa) else exit(bb);
end;
begin
readln(s2);
p:=pos(' ',s2);
s1:=copy(s2,1,p-1) ;
delete(s2,1,p);
l1:=length(s1);
l2:=length(s2);
for i:=1 to l1 do
for j:=1 to l2 do {F[i,j]=s1截止到第i个位置为止}
if s1[i]=s2[j] {s2截止到第j个位置为止公共子序的长度}
then F[i,j]:=F[i-1,j-1]+1
else F[i,j]:=max(f[i-1,j],F[i,j-1]) ;
writeln(F[l1,l2]);
z:='';
i:=length(s1); j:=length(s2); {构造最长公共子串准备}
while (i>0) and (j>0) do
if s1[i]=s2[j]
then begin z:=s1[i]+z;i:=i-1;j:=j-1 end
else if F[i-1,j]>F[i,j-1]
then i:=i-1
else j:=j-1;
if z<>'' then writeln(z);
end.

--矩阵取数
program game; {没有使用高精度的简易代码= 60分 8个数据过6个 }
const maxn=100;
var a:array[1..maxn,1..maxn] of integer;
f:array[0..maxn,0..maxn] of int64;
i,j,k,n,m,l:longint;
sum:int64;
function max(a,b:int64):int64;
begin if a>b then exit(a) else exit(b);
end;
begin
readln(n,m);
for i:=1 to n do begin
for j:=1 to m do read(a[i,j]); readln;
end;
for l:=1 to n do begin
fillchar (f,sizeof(f),0);
for k:=1 to m do
for i:=1 to m+1-k do begin
j:=i+k-1;
f[i,j]:=max(2*(a[l,i]+f[i+1,j]),2*(a[l,j]+f[i,j-1]))
end;
sum:=sum+f[1,m];
end;
writeln(sum);
end.
f[i,j]表示这一行左边取到第i位，右边取到第j位时的最大得分，
N=4的时候先计算f[1,1] f[2,2] f[3,3] f[4,4] 然后 f[1,2] f[2,3] f[3,4] 再f[1,3] f[2,4] 再 f[1,4] 即结果

--最大算式 TYVJ1045
--没有上司的舞会 TYVJ1052
--选课 TYVJ1051