CF1842B 题解

题目大意

给定三个栈，每个栈有 n 个非负数，初始值为 u = 0，每取一个数 v，u ← 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;
	}
}