1380E - Merging Towers
题意
汉诺塔背景下
n个柱子，m个圆盘，半径为[1,m] ，m<=n<=2e5
m次询问
每次将b柱上的圆盘并入a住上
之后求把所有 盘子移动到一个柱子上需要的最少操作次数
题解
由于每种半径的盘子只有一个
想要把所有盘子移动道一个柱子上
只用重复一种操作 将半径=i的盘子a和上方半径小于a的盘子一起
放到半径=i+1的盘子b上
反复操作最后一定能在最少步数内放到一个柱子上
如:[3,2,1],[8,7,6],[5,4] ->[8,7,6],[5,4,3,2,1] ->[8,7,6,5,4,3,2,1]
所以可以从最初状态得到第一个移动步数cnt
每次询问合并两个区间后的cnt都是上一次的cnt-sum
sum= (for r[i] in b柱子: r[i] -1 or r[i] +1 为半径的盘子出现在a柱子中 的个数)
如果直接暴力 每次询问将b柱子的并入a柱子
复杂度On*m 超时
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
ll x,k,y,cnt;
const int mod=2e3;
const int Max=2e5+5;
set<int> group[Max];
int belong[Max];
int main(){
int n,m,cnt=0;cin>>n>>m;
for(int i=1;i<=n;i++){
int temp;cin>>temp;
group[temp].insert(i);
belong[i]=temp;
}
for(int i=1;i<n;i++){
if(belong[i]!=belong[i+1])cnt++;
}
cout<<cnt<<endl;m--;
while(m--){
int a,b;cin>>a>>b;
for(auto i:group[a])if(belong[i+1]==b)cnt--;
for(auto i:group[b]){
if(belong[i+1]==a)cnt--;
belong[i]=a;
group[a].insert(i);
}
group[b].clear();
cout<<cnt<<endl;
}
return 0;
}
|
用启发式合并的思想优化合并过程
即将小的集合并入大的集合 复杂度为O(n logn logn )
均摊的情况：
1：每次合并两个集合O(N)
2：每次合并后，队列长度一定大于等于原来短的长度的两倍。
这样相当于每次合并都会让短的长度扩大一倍以上，
最多扩大logN次，所以总复杂度O(NlogN)，每次O(logN)
两个集合合并时用set维护 .count() 和 .insert() 复杂度×logn
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int mod=2e3;
const int Max=2e5+5;
set<int> group[Max];
int belong[Max],cnt=0;
int siz[Max];
int n,m;
inline found(int x){return belong[x]!=x?belong[x]=found(belong[x]):x;}
inline void unite(int a,int b){
if(siz[b]>siz[a])group[b].swap(group[a]);
siz[a]+=siz[b];
for(auto i:group[b]){
if(i-1>0&&group[a].count(i-1))cnt--;
if(i+1<=n&&group[a].count(i+1))cnt--;
}
for(auto i:group[b])group[a].insert(i);
group[b].clear();
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int temp;cin>>temp;
group[temp].insert(i);
belong[i]=temp;
siz[temp]++;
}
for(int i=1;i<n;i++){
if(belong[i]!=belong[i+1])cnt++;
}
cout<<cnt<<endl;m--;
while(m--){
int a,b;cin>>a>>b;
unite(a,b);
cout<<cnt<<endl;
}
return 0;
}
|
官方题解用并查集维护两集合合并操作
将一个柱子上的圆盘视作一个集合i
初始化 每个集合的父节点p[i]=i
合并操作: b并入a 则p[find(b)] =p[find(a)]
可以知道 find 的次数不超过 nlogn，且 find 复杂度平均为 O(α(n))，复杂度就不会超过 O(nlognα(n))。实际上，由于并查集的 find 函数有时只要 O(1) 时间，可能跑不满这个上界。
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
| #include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n, m;
vector<int> p;
vector<vector<int>> val;
vector<int> who;
int getp(int a){
return a == p[a] ? a : p[a] = getp(p[a]);
}
int main(){
scanf("%d%d", &n, &m);
p.resize(m);
val.resize(m);
who.resize(n);
int ans = n - 1;
forn(i, m)
p[i] = i;
forn(i, n){
int x;
scanf("%d", &x);
--x;
who[i] = x;
ans -= (i && who[i] == who[i - 1]);
val[who[i]].push_back(i);
}
printf("%d\n", ans);
forn(i, m - 1){
int v, u;
scanf("%d%d", &v, &u);
v = getp(v - 1), u = getp(u - 1);
if (val[v].size() < val[u].size())
swap(v, u);
for (int x : val[u]){
if (x) ans -= who[x - 1] == v;
if (x < n - 1) ans -= who[x + 1] == v;
}
for (int x : val[u]){
val[v].push_back(x);
who[x] = v;
}
p[u] = v;
printf("%d\n", ans);
}
return 0;
}
|