LOJ#2014「SCOI2016」萌萌哒（倍增，并查集优化连边）
题面
题意很明白，就不转述了吧。
题解
题目相当于告诉了我们若干等量关系，每个限制
l
1
,
r
1
,
l
2
,
r
2
\tt l_1,r_1,l_2,r_2
l1,r1,l2,r2 相当于
S
l
1
=
S
l
2
,
S
l
1
+
1
=
S
l
2
+
1
,
…
,
S
r
1
=
S
r
2
\tt S_{l_1}=S_{l_2},S_{l_1+1}=S_{l_2+1},\dots,S_{r_1}=S_{r_2}
Sl1=Sl2,Sl1+1=Sl2+1,…,Sr1=Sr2 这
r
1
−
l
1
+
1
r_1-l_1+1
r1−l1+1 个等量关系，每个等量关系把两个点绑在了一起。用并查集，把相等的点并起来，最终每个连通块内值相等，不同的块两两独立。
这样建边无疑是
n
2
\tt n^2
n2 级别的，远不能通过。但，一个有趣的现象是，最终实际存在在并查集中的边最多只有
n
−
1
\tt n-1
n−1 条。别的边到哪里去了呢？别的边的确没用，因此，如果能够尽量舍弃掉没用的边，那么解决这题就不在话下。
问题是，我们是不能提前知道每一条边是不是废边的。但同时，我们知道，经过并查集的算法过程，它会自然地并且神奇地把有用的边都给你留下来。
于是就有了这么一个做法：慢节奏合并并查集，过程中充分利用并查集筛选边的性质。
我们先用倍增思想，把每个限制
{
l
1
,
r
1
,
l
2
,
r
2
}
\tt \{l_1,r_1,l_2,r_2\}
{l1,r1,l2,r2} 变成两个长度为
2
k
\tt2^k
2k(选取使其不超过
[
l
1
,
r
1
]
\tt[l_1,r_1]
[l1,r1] 的长度并且最大化的
k
\tt k
k) 的限制：
{
l
1
,
r
1
,
l
1
+
2
k
−
1
,
r
1
+
2
k
−
1
}
\tt\{l_1,r_1,l_1+2^k-1,r_1+2^k-1\}
{l1,r1,l1+2k−1,r1+2k−1} 和
{
l
2
−
2
k
+
1
,
r
2
−
2
k
+
1
,
l
2
,
r
2
}
\tt\{l_2-2^k+1,r_2-2^k+1,l_2,r_2\}
{l2−2k+1,r2−2k+1,l2,r2} ，虽然有重，但是不影响。接着，把它们都放在限制集
b
u
[
k
]
\tt bu[k]
bu[k] 里待命。
然后，从大到小枚举
k
\tt k
k （
k
≤
log
n
\tt k\leq\log n
k≤logn）。每次，我们假定每个序列中的点
i
\tt i
i 代表着
[
i
,
i
+
2
k
−
1
]
\tt[i,i+2^k-1]
[i,i+2k−1] 这个大数区间，读取
b
u
[
k
]
\tt bu[k]
bu[k] 里每个元素
{
x
,
y
,
x
+
2
k
−
1
,
y
+
2
k
−
1
}
\tt\{x,y,x+2^k-1,y+2^k-1\}
{x,y,x+2k−1,y+2k−1} ，将点
x
\tt x
x 和点
y
\tt y
y 在并查集里合并，也就是意味着
[
x
,
x
+
2
k
−
1
]
\tt[x,x+2^k-1]
[x,x+2k−1] 和
[
y
,
y
+
2
k
−
1
]
\tt[y,y+2^k-1]
[y,y+2k−1] 两个区间的大数都对应相等。
在枚举到
k
′
\tt k'
k′ 之前，并查集里已经有的边，就是精简后的了。一开始，并查集里形如
(
x
,
y
)
\tt(x,y)
(x,y) 的边还代表着
[
x
,
x
+
2
k
′
+
1
−
1
]
\tt[x,x+2^{k'+1}-1]
[x,x+2k′+1−1] 和
[
y
,
y
+
2
k
′
−
1
−
1
]
\tt[y,y+2^{k'-1}-1]
[y,y+2k′−1−1] 相等，到这一层，就得代表
[
x
,
x
+
2
k
′
−
1
]
\tt[x,x+2^{k'}-1]
[x,x+2k′−1] 和
[
y
,
y
+
2
k
′
−
1
]
\tt[y,y+2^{k'}-1]
[y,y+2k′−1] 相等了，因此我们把它分裂为两条边
(
x
,
y
)
\tt(x,y)
(x,y) 和
(
x
+
2
k
′
,
y
+
2
k
′
)
\tt(x+2^{k'},y+2^{k'})
(x+2k′,y+2k′) ，再把多出的这条
(
x
+
2
k
′
,
y
+
2
k
′
)
\tt(x+2^{k'},y+2^{k'})
(x+2k′,y+2k′) 连到并查集里。
这样一来，一开始加的边是
O
(
n
)
\tt O(n)
O(n) 级别的，枚举时每一层加的边也是
O
(
n
)
\tt O(n)
O(n) 级别的，保留下来的边还是小于等于
n
−
1
\tt n-1
n−1 条。总共加的边最多就
n
log
n
\tt n\log n
nlogn 条，优化得非常到位。
这么个巧妙的做法，不知道当初第一个 AC 的人是怎么想出来的。这估计算是怎样解题里面说的U
[
n
b
e
l
i
e
v
a
b
l
e
!
\tt Unbelievable!
](https://blog.csdn.net/qq_42101694/article/details/102710338#0tt_Unbelievable_7)
Unbelievable!一类题吧。
CODE
巧妙的做法往往代码简单。
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k;
struct it{
int l,r;it(){l=r=0;}
it(int L,int R){l=L;r=R;}
};
vector<it> bu[105];
int fa[MAXN];
int findf(int x) {return fa[x] == x ? x:(fa[x] = findf(fa[x]));}
void unionSet(int a,int b) {
int u = findf(a),v = findf(b);
if(u > v) swap(u,v);
fa[u] = v; return ;
}
bool ct[MAXN];
int main() {
n = read();m = read();
for(int i = 1;i <= n;i ++) {
fa[i] = i;
}
for(int i = 1;i <= m;i ++) {
s = read();int le = read() - s + 1;
o = read(); read();
int l2 = 0;
for(int j = 0;(1<<j) <= le;j ++) l2 = j;
bu[l2].push_back(it(s,o));
bu[l2].push_back(it(s+le-(1<<l2),o+le-(1<<l2)));
}
for(int i = 20;i >= 0;i --) {
for(int j = n;j > 0;j --) {
if(findf(j) != j) {
int k = findf(j);
if(k+(1<<i) <= n)
bu[i].push_back(it(j+(1<<i),k+(1<<i)));
}
}
for(int j = 0;j < (int)bu[i].size();j ++) {
s = bu[i][j].l,o = bu[i][j].r;
unionSet(s,o);
}
}
int ans = 1;
for(int i = 1;i <= n;i ++) {
if(!ct[findf(i)]) {
ct[findf(i)] = 1;
if(i == 1) ans = ans *9ll % MOD;
else ans = ans *10ll % MOD;
}
}
printf("%d\n",ans);
return 0;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章