CF1842B 题解

题目大意

给定三个栈，每个栈有 $n$ 个非负数，初始值为 $u=0$，每取一个数 $v$，$u \leftarrow u|v$，问最终结果是否能达到 $x$。

分析

由于是按位或运算，二进制中 0 的部分在或了以后是会根据对方的值来影响结果的。

所以就有贪心策略：只要栈顶的元素在或上 $x$ 以后还等于 $x$，即 $x$ 二进制位上为 0 的部分其二进制位上也为 0 都选。

代码

#include<bits/stdc++.h>
using namespace std;
int stk[3][100000+10],top[3];
//三个栈，以及它们分别的顶 
int main(){
	ios_base::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		int n,x,u=0;
		cin>>n>>x;
		for(int j=0;j<3;++j)
			for(int i=1;i<=n;++i)
				cin>>stk[j][i];
		top[0]=top[1]=top[2]=1;
		//输入以及初始化三个栈
		for(int i=0;i<3;++i)
			while(top[i]<=n&&(stk[i][top[i]]|x)==x)
				u|=stk[i][top[i]++];
		//枚举三个栈分别操作 
		cout<<(u==x?"YES":"NO")<<endl;
	}
}