「THUSC 2012」水位 - 并查集+高精度 | Bill Yang's Blog

「THUSC 2012」水位 - 并查集+高精度

题目大意

    给出一个网格图,每个位置有一个地表高度,水面高度必须大于等于地表高度,且在$[0,m]$间,是个整数。
    水按照生活常识流动,如下图(地表高度/水面高度)中左图合法,右图不合法。

求合法的不同水位情况数。


题目分析

这题有一个很明显的状压动规做法。
因为将原图剖分成块,块与块只可能是包含或不相交关系,不可能是相交但不包含关系。
设$f[S]$表示集合$S$的方案数。
可以考虑从$f[S]$扩展到$f[S’]$(集合扩张),方案数累加。
也可以考虑将$f[S]$和$f[T]$合并,方案数累乘。
复杂度高且不好实现。

进一步我们考虑到状态没有必要显示设置出来,因为有明显的阶段顺序(从地表高度低的格子扩展到地表高度高的格子)。
故将每一个块用并查集表示,从水位低的往高的依次合并并查集,按照上面说的方式统计方案数即可。

注意需要高精度。


代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
typedef long long LL;
struct BigInteger {
const static int BASE=100000000,WIDTH=8;
vector<LL>s;
BigInteger() {
*this=0;
}
BigInteger(const LL& num) {
*this=num;
}
//赋值
BigInteger operator = (LL num) {
s.clear();
do {
s.push_back(num%BASE);
num/=BASE;
} while(num>0);
return *this;
}
//+
BigInteger operator + (BigInteger b) {
BigInteger c;
c.s.clear();
LL g=0;
for(int i=0; ; i++) {
if(g==0&&i>=s.size()&&i>=b.s.size())break;
LL x=g;
if(i<s.size())x+=s[i];
if(i<b.s.size())x+=b.s[i];
c.s.push_back(x%BASE);
g=x/BASE;
}
return c;
}
void operator += (BigInteger b) {
*this=*this+b;
}
//*
BigInteger operator * (const BigInteger& b) {
BigInteger a=*this,c;
c.s.resize(a.s.size()+b.s.size());
for(int i=0; i<a.s.size(); i++)
for(int j=0; j<b.s.size(); j++)c.s[i+j]+=a.s[i]*b.s[j];
for(int i=0; i<c.s.size()-1; i++) {
c.s[i+1]+=c.s[i]/BASE;
c.s[i]%=BASE;
}
while(c.s.back()==0&&c.s.size()>1)c.s.pop_back();
return c;
}
void operator *= (const BigInteger& b) {
*this=*this*b;
}
friend ostream& operator << (ostream& output,const BigInteger& x) {
output<<x.s.back();
for(int i=x.s.size()-2; i>=0; i--) {
char buf[20];
sprintf(buf,"%08lld",x.s[i]);
for(int j=0; j<strlen(buf); j++)output<<buf[j];
}
return output;
}
};
const int maxn=105;
const int dx[]= {1,-1,0,0},dy[]= {0,0,1,-1};
int n,m,Height[maxn*maxn],father[maxn*maxn];
BigInteger ans[maxn*maxn];
int get_id(int x,int y) {
return (x-1)*n+y;
}
int Get_Father(int x) {
if(father[x]==x)return x;
return father[x]=Get_Father(father[x]);
}
struct Point {
int x,y,id;
Point(int _x=0,int _y=0):x(_x),y(_y) {
id=get_id(_x,_y);
}
bool operator < (const Point& b) const {
return Height[id]<Height[b.id]||(Height[id]==Height[b.id]&&id<b.id);
}
bool inmap() {
return x>=1&&x<=n&&y>=1&&y<=n;
}
} P[maxn*maxn];
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
Height[get_id(i,j)]=Get_Int();
P[get_id(i,j)]=Point(i,j);
}
for(int i=1; i<=n*n; i++) {
father[i]=i;
ans[i]=1;
}
sort(P+1,P+n*n+1);
for(int i=1; i<=n*n; i++)
for(int d=0; d<4; d++) {
Point Now=P[i];
Point Next=Point(Now.x+dx[d],Now.y+dy[d]);
if(!Next.inmap())continue;
int fx=Get_Father(Now.id),fy=Get_Father(Next.id);
if(fx!=fy&&Height[fx]>=Height[fy]) {
ans[fy]+=Height[fx]-Height[fy];
ans[fx]*=ans[fy];
father[fy]=fx;
}
}
int fx=Get_Father(1);
ans[fx]+=m-Height[fx];
cout<<ans[fx];
return 0;
}
0%