POI2018 水箱 题解

POI2018 水箱 题解

$\text{Description}$

已知有一个 $n\times m\times H$ 的长方体,对于水平面上的相邻两格间,会有一堵厚度忽略不计的墙,从最低一层开始,到第 $h_{i,j}\ge 1$ 层。

定义一种装水方式是合法的,当且仅当:

  1. 某一个格子装了水,则它是最低一层的格子或者其竖直向下的格子装了水。
  2. 某一个格子装了水,则它在水平面上的相邻四个格子要么是水,要么中间有堵墙。

求有多少种合法的装水方式,对 $10^9+7$ 取模。

$n\times m\le 5\times 10^5,H\le 10^9$

$\text{Solution}$

考虑某一个位置有墙,则它的正下方必然有墙(或者是最底一层),那么从下向上计算的过程实际上可以看成不断去掉一堵墙,其实就是让两个格子连通的操作,由于墙的高度至少为 $1$,故一开始所有格子都不连通。对于某一层 $h$,我们发现高度大于等于 $h$ 的墙会将该平面分成若干个连通块,对于某个连通块,若某一个装的水高度大于等于 $h$,则该连通块内的所有格子装的水都相等。

换言之,我们设某个连通块装水的方案数为 $f_i$,该连通块内的最高的墙高度 $h_i$,则某次去掉一堵高度为 $h$ 的墙时,不妨设它让 $x,y$ 两个连通块连通了(若两者已连通则无需考虑),那么新连通块 $t$ 的方案数正是 $f_t=f_xf_y+f_x(h-h_y)+f_y(h-h_x)+(h-h_x)(h-h_y)=(f_x+h-h_x)\times(f_y+h-h_y)$,即两者装的水高度都不超过各自内部最高的墙,某一个超过了,两者都超过了的方案数之和。

注意到我们只需让两个连通块连通,故采用并查集,并在代表元处维护 $f$ 即可。

最后需将所有连通块的答案加上 $H-h_x$ 后再相乘,具体实现细节见代码。

时间复杂度 $\mathcal O(nm\log(nm))$。

$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define REG register
using namespace std;
const int Mod=1000000007,N=500005;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void Add(int& a,int b){(a+=b)>=Mod?a-=Mod:a;}

int n,m,H,tot,w;
struct Wal{int P1,P2,Hi;}W[N<<1];
inline bool cmp(Wal x,Wal y){return x.Hi<y.Hi;}

int Val[N],Fat[N],L1[N];
inline void Init(){for(REG int i=1;i<=n*m;++i)Fat[i]=i,Val[i]=1,L1[i]=0;}
int GetF(int now){return now==Fat[now]?now:Fat[now]=GetF(Fat[now]);}

inline void Work(){
read(n),read(m),read(H),Init();
for(REG int i=1;i<=n;++i)
for(REG int j=1;j<m;++j)
read(w),W[++tot]=(Wal){(i-1)*m+j,(i-1)*m+j+1,w};
for(REG int i=1;i<n;++i)
for(REG int j=1;j<=m;++j)
read(w),W[++tot]=(Wal){(i-1)*m+j,i*m+j,w};
sort(W+1,W+tot+1,cmp);
for(REG int i=1;i<=tot;++i){
int x=W[i].P1,y=W[i].P2,h=W[i].Hi;
int Fx=GetF(x),Fy=GetF(y);
if(Fx==Fy) continue;
Add(Val[Fx],h-L1[Fx]),Add(Val[Fy],h-L1[Fy]);
Fat[Fx]=Fy,Val[Fy]=1ll*Val[Fy]*Val[Fx]%Mod,L1[Fy]=h;
}
int Ans=1;
for(REG int i=1;i<=n*m;++i)
if(Fat[i]==i) Add(Val[i],H-L1[i]),Ans=1ll*Ans*Val[i]%Mod;
printf("%d\n",Ans);
}

int main(){Work();}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×