CF1290C Prefix Enlightenment 题解

Solution

不难注意到“任意三个子集的交集为空”等价于每盏灯最多同时出现于 \(2\) 个集合中。
设第 \(i\) 盏灯出现在第 \(p_i,q_i\) 两个集合中，若没有则为 \(0\)。设 \(f_k\in \{0,1\}\) 表示是否选集合 \(A_k\)。
然后依据题意从左向右扫，分讨第 \(i\) 盏灯的情况。

• \(p_i=q_i=0\)：一定有 \(s_i=1\)，答案与这盏灯无关。
  
• \(p_i\neq 0,q_i=0\)：仅 \(A_{p_i}\) 影响该灯，故 \(f_{p_i}=\operatorname{not} s_i\)。
  
• \(p_i\neq 0,q_i\neq 0\)：该灯同时受两个集合影响，必有 \(f_{p_i}\operatorname{xor} f_{q_i}=\operatorname{not}s_i\)。
  

考虑图论建模，将约束转化成带权无向边。

• 对于 \(f_{p_i}=c\) 型的约束，新建一个虚点 \(0\)，在 \(p_i,0\) 间建边权为 \(c\) 的无向边。
  
• 对于 \(f_{p_i}\operatorname{xor} f_{q_i}=c\) 型的约束，在 \(p_i,q_i\) 间建边权为 \(c\) 的边。
  

不难发现此时要维护的是一个 01 二分图。每个连通块的代价为左部点和右部点数的较小值。特别地，如果点 \(0\) 在该连通块中，则代价为与 \(0\) 不在同一部分的点数。
然后用带权并查集维护即可，具体细节详见代码。
AC Code

1. #include <bits/stdc++.h>
2. #define rep(i,a,b) for(int i(a);i<b;++i)
3. #define rept(i,a,b) for(int i(a);i<=b;++i)
4. using namespace std;
5. constexpr int N=3e5+5;
6. int fa[N],w[N],siz[N][2];
7. int n,k,c,ans;  // ans：当前总代价
8. char s[N];
9. vector<int> g[N];
10. // w[i]：点i的父边权值
11. // siz[i][0]：和根节点i在同一部分的点数
12. // siz[i][0]：和根节点i在不同部分的点数
13. int find(int x){
14.     if(fa[x]==x) return x;
15.     int t=find(fa[x]);
16.     w[x]^=w[fa[x]];
17.     return fa[x]=t;
18. }
19. int calc(int u){  // u所在连通块的代价
20.     if(find(0)==u) return siz[u][w[0]^1];  // 与 $0$ 不在同一部分的点数
21.     return min(siz[u][0],siz[u][1]);  // 左部点和右部点数的较小值
22. }
23. void merge(int x,int y,int k){
24.     int u=find(x),v=find(y),z=k^w[x]^w[y];
25.     if(u^v){  // 千万别忘了判
26.         ans-=calc(u),ans-=calc(v);
27.         w[u]=z;
28.         siz[v][0]+=siz[u][z];
29.         siz[v][1]+=siz[u][z^1];
30.         fa[u]=v;
31.         ans+=calc(v);
32.     }
33. }
34. signed main(){
35.     scanf("%d%d%s",&n,&k,s+1);
36.     rept(i,1,k) fa[i]=i,siz[i][0]=1;
37.     rept(i,1,k){
38.         cin>>c;
39.         while(c--){
40.             int x;scanf("%d",&x);
41.             g[x].emplace_back(i);
42.         }
43.     }
44.     rept(i,1,n){
45.         if(g[i].size()==2) merge(g[i][0],g[i][1],s[i]=='0');
46.         else if(g[i].size()==1) merge(g[i][0],0,s[i]=='0');
47.         printf("%d\n",ans);
48.     }
49.     return 0;
50. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

不错，里面软件多更新就更好了

感谢，下载保存了