题目大意:
有n个操作(只包含&,|,^),然后要你从0-m选一个数,使得这个数经过n个操作后数值最大。
思路:
考虑二进制,最后的答案转化为二进制,每一位要么选要么不选,然后我们贪心的从最高位选,能选则选。
我们可以用一个全0bitset和全1bitset去经过n次操作,然后从2的最高位开始枚举,如果全0bitset这位等于1说明这位选0就能得到这个值,加入我们的答案,否则看一下全1bitset,如果这位等于1,说明我们选择的这个数的这位是1就能得到这个值,并且这个值不超过m的取值范围就加入答案。
最终输出答案即可。
代码:
#include<iostream> #include<vector> #include<algorithm> #include<cstdio> #include<bitset> using namespace std; typedef long long int ll; ll n,m; void solved(){ bitset<40>one; bitset<40>zero; one.set(); zero.reset(); cin>>n>>m; for(int i = 1; i <= n; i++){ string s;int x;cin>>s>>x; if(s[0] == 'O')one |= x,zero |= x; if(s[0] == 'X')one ^= x,zero ^= x; if(s[0] == 'A')one &= x,zero &= x; } ll ans = 0; for(int i = 29; i >= 0; i--){ if(zero[i] == 1)ans += (1 << i); else if(one[i] == 1 && (1 << i) <= m)ans += (1 << i); } cout<<ans<<endl; } int main(){ solved(); return 0; }