题目传送门(BZOJ)
>原文链接<

题解 :

由于位运算位与位之间相互不影响, 考虑按位做.

又因为要求一个最大值, 所以我们从高位开始贪心,

对于某位, 先试一下$0$能否让它最后变成$1$ , 如果不行, 就试一下$1$能否让这位最后变成1.

如果$0$可以, 显然是发出的攻击力小不会比大更差(更有可能在$m$的范围内), 所以我们选$m$

注意在尝试$1$之前,要先判断之前的$1$加上这位是否大于$m$了, 如果大于就不能尝试.

如果无论用$1$或$0$使最后的结果都是$0$,我们也同样选择$0$,理由讲过了.

这样每位贪心下去, 最后的答案一定是最优的, 因为若某个高位为1, 低位再多的1加起来也不如高位贡献的多

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cctype>using namespace std;int opt[110000], num[110000];int n, m;int ans[40];bool check(int idx) { int x=0; for(int i=0;i<=30;i++) { x|=(ans[i]<<i); } x|=(1<<idx); return x<=m;}int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { char s[6]; int x; scanf("%s%d",s ,&x); if(s[0]=='A') { opt[i] = 1; num[i] = x; } if(s[0]=='O') { opt[i] = 2; num[i] = x; } if(s[0]=='X') { opt[i] = 3; num[i] = x; } } int i; for(i=0;(1<<i)<=m;i++); i--; for(;i>=0;i--) { if(check(i)) { int now=1<<i; for(int j=1;j<=n;j++) { if(opt[j]==1) { now&=num[j]; } if(opt[j]==2) { now|=num[j]; } if(opt[j]==3) { now^=num[j]; } } now>>=i; if(now&1) { ans[i]=1; } } int now=0; for(int j=1;j<=n;j++) { if(opt[j]==1) { now&=num[j]; } if(opt[j]==2) { now|=num[j]; } if(opt[j]==3) { now^=num[j]; } } now>>=i; if(now&1) { ans[i]=0; } } int x=0; for(int i=0;i<=30;i++) { x|=(ans[i]<<i); } int now=x; for(int j=1;j<=n;j++) { if(opt[j]==1) { now&=num[j]; } if(opt[j]==2) { now|=num[j]; } if(opt[j]==3) { now^=num[j]; } } printf("%d\n",now);}