头部背景图片
Decaku 's Blog |
Decaku 's Blog |

CF #616 E.Prefix Enlightenment

题意:你有n位的01串和k个集合,当选择一个集合时,把该集合元素为下标的所有二进制位取反,
输出把前i位变成1所需要选择的最少的集合个数,输出所有的n个答案。题目保证任意三个集合
交为空且一定有答案。


任意三个集合交为空说明每个二进制位最多只被两个集合控制,可以把每个集合
拆成两个点,代表选和不选,并且把选择的点权赋值为1,不选的点权赋值为0
那么如果第i位二进制是1,假设它被两个集合控制,那两个控制它的集合只能同时
选或不选,二进制是0时同理,那么此时有两种情况,较小的连通块点权和就是
答案,被一个集合控制时加一个虚点即可,0个集合控制时不用管它,保证答案
存在所以不用考虑不合法的连边。因为要求所有答案,所以还需要增量维护答案。
以上的所有操作都可以使用并查集来实现。

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
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const int maxn=6e5+10;

int f[maxn],n,k,w[maxn];
vector<int>v[maxn];
int Find(int x)
{
return f[x]==x?x:f[x]=Find(f[x]);
}

int ask(int x)
{
int y=(x<=k)?x+k:x-k;
x=Find(x);y=Find(y);
if(x==0) return w[y];
else if(y==0) return w[x];
else return min(w[x],w[y]);
}

void Merge(int x,int y)
{
x=Find(x),y=Find(y);
if(y==0) swap(x,y);
f[y]=x;
if(x!=0) w[x]+=w[y];
}

int main()
{
IOS
cin>>n>>k;
string s;cin>>s;
rep(i,1,k)
{
int x;cin>>x;
rep(j,1,x)
{
int tem;cin>>tem;
v[tem].pb(i);
}
f[i]=i;f[i+k]=i+k; w[i+k]=1;
}
int ans=0;
rep(i,1,n)
{
if(v[i].size()==1)
{
int x=v[i][0];
if(x){
ans-=ask(x);
if(s[i-1]=='1') f[Find(x+k)]=0;
else f[Find(x)]=0;
ans+=ask(x);
}
}
else {
int x=0,y=0;
if(v[i].size()==2) {x=v[i][0],y=v[i][1];}
if(s[i-1]=='1'){
if(Find(x)!=Find(y))
{
ans-=(ask(x)+ask(y));
Merge(x,y);Merge(x+k,y+k);
ans+=ask(x);
}
}
else{
if(Find(x+k)!=Find(y)){
ans-=(ask(x)+ask(y));
Merge(x+k,y);Merge(x,y+k);
ans+=ask(x);
}
}
}
cout<<ans<<"\n";
}
}
avatar Decaku 菜菜菜