起床困难综合症(位运算)
起床困难综合症
https://ac.nowcoder.com/acm/problem/17857
前言
太菜了,参考了大佬的思路。
题意
给定一些位运算操作,对于[0,m]中的整数,求经过运算后的最大值。
解题思路
先考虑暴力怎么做,对于[0,m]中的每一个数,分别计算他们经过运算后的值,取最大值。复杂度O(mn),显然会超时。
发现按位与,按位或,异或这种位运算,对于一个二进制位,只会影响其本身,而不会影响其他二进制位。可以将问题转化到二进制位上,对于每个二进制位经过运算后为0,还是为1;当然我们希望它为1。
我们从高到低枚举每一位,若该位选1不会超过m,则说明该位可选1也可选0,计算一下选1和选0经过运算后的值,取最大的。
若该位选1会超过m,则该位只能选0。
这样每一位运算一遍,复杂度O(nlogm)。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct node{ string s; int x; }a[100010]; int n; int calc(int x,int k){ for(int i=1;i<=n;i++){ if(a[i].s[0]=='A') x&=a[i].x>>k; if(a[i].s[0]=='O') x|=a[i].x>>k; if(a[i].s[0]=='X') x^=a[i].x>>k; } return x; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i].s>>a[i].x; int ans=0,cnt=0; //cnt表示所选的[0,m]中的数 for(int i=29;i>=0;i--){ //该位可以选1 if(cnt+(1<<i)<=m){ int x=calc(1,i),y=calc(0,i); //计算选1和选0的贡献 if(x>y){ ans|=x<<i; cnt+=(1<<i); } else ans|=y<<i; } else ans|=calc(0,i)<<i; //该位只能选0 } cout<<ans<<endl; return 0; }