首页 > 代码库 > 【Nescafé 31】杯NOIP模拟赛
【Nescafé 31】杯NOIP模拟赛
t1
题意：n*m的棋盘上从(1,1)走到(n,m)，只能向下或向右，一些格子有老鼠，每个老鼠互不相同，当处于与老鼠有重边的格子时，视为看见了这只老鼠，求到终点看到最少的不同老鼠数。
分析：DP 由于求得是看到的不同的老鼠数目，不能直接用过河卒做，因为同一个位置的老鼠可能会统计多次，我们还需要增加一维即方向。
f[i,j,0]表示到从上面一个格子走到(i,j)时最少老鼠数,f[i,j,1]表示左边。
f[i,j,0]:=min(f[i-1,j,0]+a[i,j-1],f[i-1,j,1])+a[i+1,j]+a[i,j+1];
f[i,j,1]:=min(f[i,j-1,1]+a[i-1,j],f[i,j-1,0])+a[i+1,j]+a[i,j+1];
对于(i,j)如果左边有老鼠，那么从(i-1,j-1)走到(i-1,j)再到(i,j)会看到该老鼠两次但只能记为1次，(i-2,j)走到(i-1,j)再到(i,j)时只看到该老鼠一次，故要加上这一次。上边有老鼠也同理。
代码：
program mouse;var a:array[0..1001,0..1001]of longint; f:array[0..1001,0..1001,0..1]of longint; n,i,m,j:longint;function min(x,y:longint):longint;begin if x<y then min:=x else min:=y;end;begin assign(input,‘mouse.in‘);reset(input);assign(output,‘mouse.out‘);rewrite(output); readln(n,m); for i:=1 to n do begin for j:=1 to m do read(a[i,j]); readln; end; for i:=0 to n do for j:=0 to m do begin f[i,j,0]:=maxlongint div 3;f[i,j,1]:=maxlongint div 3; end; f[1,1,1]:=a[1,1]+a[2,1]+a[1,2]; f[1,1,0]:=a[1,1]+a[2,1]+a[1,2]; for i:=1 to n do for j:=1 to m do if (i<>1)or(j<>1) then begin f[i,j,0]:=min(f[i-1,j,0]+a[i,j-1],f[i-1,j,1])+a[i+1,j]+a[i,j+1]; f[i,j,1]:=min(f[i,j-1,1]+a[i-1,j],f[i,j-1,0])+a[i+1,j]+a[i,j+1]; end; writeln(min(f[n,m,1],f[n,m,0])); close(input); close(output);end.
t2
题意：给出一个无向有权图，图的每个点为一个城市，我们说城市B愿意与城市A建立合作关系，当且仅当对于所有满足d(A,C)<=d(A,B)的城市C，都有R(C)<=R(B)。一个城市的受欢迎程度Bi定义为愿意与其建立合作关系的城市数量，求所有城市受欢迎度和（可以和自己建立关系）
分析：最短路，我们可以将条件转化为对于所有R(c)>R(B)的城市C，都有d(A,C)>d(A,B),我们设l[i]为满足R(x)>R(i)的点到i的最短路，从大到小枚举r的值，然后对R(i)=r的点做最短路，如果在这一过程中某个点d(i,j)<=l[j]说明不可行，则不去松弛。
代码：
program work;type point=^node; node=record x,v:longint; next:point; end;var a:array[0..30000]of point; l,r,d,g,w,d1:array[0..30000]of longint; q:array[0..110000]of longint; n,i,m,ans,x,y,v,j:longint;procedure add(x,y,v:longint);var p:point;begin new(p); p^.x:=y; p^.v:=v; p^.next:=a[x]; a[x]:=p;end;procedure spfa(s:longint);var h,t,x,y,k:longint; p:point;begin h:=0; t:=1; q[1]:=s; d[s]:=0; d1[s]:=0; g[s]:=s;w[s]:=s; inc(ans); while h<t do begin inc(h); x:=q[h]; new(p); p:=a[x]; g[x]:=0; if h>=100000 then h:=0; while p<>nil do begin y:=p^.x; k:=d1[x]+p^.v; if k<l[y] then if (w[y]<>s)or(k<d1[y]) then begin d1[y]:=k; if d1[y]<d[y] then d[y]:=d1[y]; if w[y]<>s then begin w[y]:=s; inc(ans); end; if g[y]<>s then begin g[y]:=s; inc(t); q[t]:=y; if t>=100000 then t:=0; end; end; p:=p^.next; end; end;end;begin readln(n,m); for i:=1 to n do readln(r[i]); for i:=1 to m do begin readln(x,y,v); add(x,y,v); add(y,x,v); end; ans:=0; for i:=1 to n do l[i]:=maxlongint; for i:=10 downto 1 do begin for j:=1 to n do begin d[j]:=maxlongint div 3; g[j]:=0; w[j]:=0; end; for j:=1 to n do if r[j]=i then spfa(j); for j:=1 to n do if d[j]<l[j] then l[j]:=d[j]; end; writeln(ans);end.
【Nescafé 31】杯NOIP模拟赛