长沙集训 $ Day 2 $ 2019-08-20
得分： $ 105/300 $
T1 $ mine $
基本思路
此题可以使用 $ Dp $ 解决，设 $ Dp[i,j,k] $ 表示当前处理到第 $ i $ 位，第 $ i $ 位字符为 $ j $ 类型，第 $ i-1 $ 为符号为 $ k $ 类型时的方案数。
$ s_i=* \ \to \ j,k=1 \ \ \ \ \ \ \ \ \ 0 \ \to \ j,k=2 \ \ \ \ \ \ \ \ \ 1 \ \to \ j,k=3 \ \ \ \ \ \ \ \ \ 2 \ \to \ j,k=4 \ \ \ \ \ \ \ \ \ ? \ \to \ j,k=0 $
状态可从 $ Dp[i-1,k,l] $ 转移得到，其中要注意各种细节问题。
程序
program mine;
const p=1000000007;
var
s:array[0..1000005]of longint;
f:array[0..1000005,1..4,1..4]of longint;
n:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;
procedure re;
var s1:ansistring;
i:longint;
begin
readln(s1);
s1:=s1;
n:=length(s1);
for i:=1 to n do
case s1[i] of
'*':s[i]:=1;
'0':s[i]:=2;
'1':s[i]:=3;
'2':s[i]:=4;
'?':s[i]:=0;
end;
end;
procedure main;
var i,j,k:longint;
ans:int64;
begin
ans:=0;
if s[1]=0 then begin
f[1,1,1]:=1;
f[1,2,2]:=1;
f[1,3,2]:=1;
end
else if s[1]=1 then f[1,1,1]:=1
else if s[1]=2 then f[1,2,2]:=1
else if s[1]=3 then f[1,3,2]:=1;
for i:=2 to n do
for j:=1 to 4 do
for k:=1 to 4 do
if ((s[i]=j) or (s[i]=0)) and ((s[i-1]=k) or (s[i-1]=0)) then begin
if (j=1) and (k=1) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,1]+f[i-1,k,3]+f[i-1,k,4]) mod p;
if (j=1) and (k=3) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,2]+f[i-1,k,3]+f[i-1,k,4]) mod p;
if (j=1) and (k=4) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,1]) mod p;
if (j=2) and (k=2) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,2]+f[i-1,k,3]+f[i-1,k,4]) mod p;
if (j=2) and (k=3) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,1]) mod p;
if (j=3) and (k=1) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,1]+f[i-1,k,3]+f[i-1,k,4]) mod p;
if (j=3) and (k=2) and (i<>n) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,2]+f[i-1,k,3]+f[i-1,k,4]) mod p;
if (j=3) and (k=3) and (i<>n) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,1]) mod p;
if (j=4) and (k=1) and (i<>n) then f[i,j,k]:=(f[i,j,k]+f[i-1,k,1]+f[i-1,k,3]+f[i-1,k,4]) mod p;
end;
for i:=1 to 4 do
for j:=1 to 4 do
ans:=(ans+f[n,i,j]) mod p;
writeln(ans);
end;
begin
re;
main;
end.
T2 $ water $
基本思路
这题是一道十分奇妙的图论题。首先考虑一个点的积水深度如何计算，假设这个点开始时有无限的水深，这些多出来的水肯定会沿着一某些路径流走，随着水深不断下降，显然当水深到达所有路径中最大点高度的最小值时，余下的水就无法流走了，这时的水深就是答案。
现在的问题就是如何找出这个最小值。要求出最小值，首先要找到这条路径，所有点的路径是一棵瓶颈生成树。
瓶颈生成树：无向图 $ G $ 的一颗瓶颈生成树是这样的一颗生成树，它最大的边权值在G的所有生成树中是最小的。
无向图 $ G $ 的最小生成树一定是瓶颈生成树（逆命题不成立），因为如果最小生成树不是瓶颈生成树，则最小生成树中一定有一条边可以被更换为更小的权值，不满足最小生成树的性质。
对于此题，将一个点与其上下左右四个点之间连边，边权为两个顶点高度的较大值。对于四周的点，还要将它们向一个 $ 0 $ 号节点连边，边权为 $ 0 $ 和点的高度中的较大值。之后在建成的图上求出最小生成树，就可以求出水流的所有路径。
之后以 $ 0 $ 节点为生成树的根，通过 $ DFS $ 处理答案，其中 $ i $ 节点的水深为从 $ i $ 到根的路径上，边权的最大值减去节点 $ i $ 的高度。
程序
program water;
const x:array[1..4]of longint=(1,0,-1,0);
y:array[1..4]of longint=(0,1,0,-1);
type tp=record
x,y,w:longint;
end;
type tp2=record
l,v,w:longint;
end;
var
map,ans:array[0..305,0..305]of longint;
fa,r,maxx:array[0..1000005]of longint;
e:array[0..200005]of tp2;
a:array[0..500005]of tp;
n,m,tot,i:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
procedure build(x,y,z:longint);
begin
inc(i);
e[i].l:=r[x];
r[x]:=i;
e[i].v:=y;
e[i].w:=z;
inc(i);
e[i].l:=r[y];
r[y]:=i;
e[i].v:=x;
e[i].w:=z;
end;
procedure qsort(l,r:longint);
var i,j,mid:longint;
t:tp;
begin
i:=l;
j:=r;
mid:=a[(i+j) shr 1].w;
repeat
while a[i].w<mid do inc(i);
while a[j].w>mid do dec(j);
if i<=j then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
function find(q:longint):longint;
begin
if fa[q]=q then exit(q);
fa[q]:=find(fa[q]);
exit(fa[q]);
end;
procedure re;
var i,j:longint;
begin
for i:=1 to n do
for j:=1 to m do
read(map[i,j]);
end;
procedure dfs(f,fa:longint);
var i,x,y:longint;
begin
x:=(f-1) div m;
y:=f-x*m;
ans[x,y]:=maxx[f]-map[x,y];
i:=r[f];
while i<>0 do begin
if e[i].v<>fa then begin
maxx[e[i].v]:=max(maxx[f],max(maxx[e[i].v],e[i].w));
dfs(e[i].v,f);
end;
i:=e[i].l;
end;
end;
procedure main;
var i,j,k:longint;
begin
for i:=1 to n do
for j:=1 to m do
for k:=1 to 4 do begin
inc(tot);
a[tot].x:=(i)*m+j;
a[tot].y:=(i+x[k])*m+j+y[k];
if (i+x[k]<1) or (j+y[k]<1) or (i+x[k]>n) or (j+y[k]>m) then a[tot].y:=1;
a[tot].w:=max(map[i,j],map[i+x[k],j+y[k]]);
end;
qsort(1,tot);
for i:=1 to 2*n*m do begin
maxx[i]:=-maxint;
fa[i]:=i;
end;
for i:=1 to tot do begin
if find(a[i].x)<>find(a[i].y) then begin
fa[find(a[i].x)]:=find(a[i].y);
build(a[i].x,a[i].y,a[i].w);
end;
end;
dfs(1,1);
for i:=1 to n do begin
for j:=1 to m do
write(ans[i,j],' ');
writeln;
end;
end;
begin
read(n,m);
re;
main;
end.
T3 $ gcd $
基本思路
咕