首页 > 编程学习 > CF1715D 2+ doors

CF1715D 2+ doors

发布时间:2022/8/21 4:00:01

简要题意

对于一个数组 \(a\),给定 \(Q\) 个限制条件,每个条件给出 \(i,j,x\) 使得 \(a_i|a_j=x\)

构造数组使其字典序最小。

Solution

以下 \(ans_i\) 表示最后我们构造出来的答案数组。

考虑一个最宽松的限制条件,我们有一个 \(b\) 数组,在最开始,\(b\) 在二进制意义下全是 \(1\)

对于每个条件,我们令 \(b_i=b_i\&x,b_j=b_j\&x\)

显然,\(b\) 数组是答案最宽松的条件,即 \(ans_i\subseteq b_i\)

也就是说,若一定存在解,则 \(b_i\) 必然是一组合法解。

现在要求字典序最小,我们从前往后构造答案。

考虑当前构造位 \(i\)

为了让字典序最小,对于一个限制 \(\{a_i|a_j=x,(i<j)\}\),我们应尽可能的让 \(ans_j\) 完成要求,\(ans_j\) 能完成的部分即为 \(x\&b_j\)

剩余的部分,即 \((x\) \(^\) \((x\&b_j))\),则不得不让 \(ans_i\) 来完成,于是 \(ans_i\) 必须或上这一部分。

但是注意,\(ans_j\) 并不是一定要完成 \(x\&b_j\)

因为 \(ans_i\) 也有可能在其他条件的迫害下不得不完成了一部分 \(x\)

于是我们对于 \(\{a_i|a_j=x,(i>j)\}\),再让 \(ans_i|=(x\&ans_i)\) 来完成剩余的限制即可。

由于每一步都是必要的,所以他是最小的。

至于 \(\{a_i|a_j=x,(i=j)\}\),则 \(ans_i=x\) 是必然的。

复杂度 \(O(n+q)\)

#include<bits/stdc++.h>
#include<vector>
const int N=200010;
int a[N],b[N],ans[N];
struct node{
	int to,val;
};
std::vector<node>p[N];
signed main(){
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)a[i]=(1<<30)-1;
	int x,y,z;
	for(int i=1;i<=q;i++){	
		scanf("%d%d%d",&x,&y,&z);
		a[x]=z&a[x],a[y]=z&a[y];
		p[x].push_back(node{y,z}),p[y].push_back(node{x,z});
	}
	for(int i=1;i<=n;i++){
		for(node j:p[i]){
			if(i==j.to)ans[i]|=j.val;
			else if(j.to>=i){
				ans[i]|=((j.val^(j.val&a[j.to]))&a[i]);
			}
			else {
				ans[i]|=((j.val^(j.val&ans[j.to]))&a[i]);
			}
		}
	}
	for(int i=1;i<=n;i++)printf("%d ",ans[i]);
	return 0;
}
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号