给定n个位运算操作，和每次运算的数，在[0,m]范围内找一个数使得最后操作出来的数最大。
2≤n≤105 ,2≤m≤230
这道题当时是我做的，最初可以想到暴力枚举，可是ACM又不看部分分，过了一会突然想到位运算：顾名思义，就是一位一位计算，在二进制下每一位的计算互不影响。
所以就想到预处理出每一位我们取0或1时在这一位最后得到的数，然后跑一遍贪心就好，当取0这一位可以得到1肯定是最好的(空手套白狼)，取1可以得到也是极好的(花一分钱买一分货,不过要看自己是否有这个本钱)，最后就是不管取什么都得不到1（那么就不要浪费钱啊，后面还要用），这就是贪心步骤。我做的题好简单，而且我好像就只做了这个，还错了一堆小东西
#include<bits/stdc++.h> using namespace std; const int maxn=100005; int n,m; int yuan[35]; int num[maxn][35]; int f[35][2]; int opt[maxn]; int ans; template <class T> void read(T &x) { char c;int sign=1; while((c=getchar())>‘9‘||c<‘0‘) if(c==‘-‘) sign=-1; x=c-48; while((c=getchar())>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+c-48; x*=sign; } void nice(int x,int j){ for(int i=0;i<=30;i++,x>>=1)num[j][i]=x&1; } void get(int j,int xx){ int x=xx; for(int i=1;i<=n;i++) if(opt[i]==0) x&=num[i][j]; else if(opt[i]==1) x|=num[i][j]; else x^=num[i][j]; f[j][xx]=x; } void dfs(int s,bool lim){ if(s<0) return ; if(f[s][0]==1) ans+=1<<s,dfs(s-1,lim&&yuan[s]==0); else if(f[s][1]==1&&(!lim||yuan[s]==1)) ans+=1<<s,dfs(s-1,lim&&yuan[s]==1); else dfs(s-1,lim&&yuan[s]==0); } int main() { read(n);read(m); for(int i=1;i<=n;i++){ char s[5];scanf("%s",s); if(s[0]==‘A‘) opt[i]=0; else if(s[0]==‘O‘) opt[i]=1; else opt[i]=2; int x; scanf("%d",&x); nice(x,i); } // for(int i=1;i<=n;i++,putchar(10)) // for(int j=5;j>=0;j--) // printf("%d",num[i][j]); for(int i=0;i<=30;i++) get(i,0),get(i,1); for(int i=0;i<=30;i++,m>>=1) yuan[i]=m&1; // for(int i=0;i<=5;i++) // printf("%d %d\n",f[i][0],f[i][1]); dfs(30,true); printf("%d",ans); }
不过他们就用了两个数，全0和全1就预处理出来了，我佛了，想一想自己慢了好多
[NOI2014]起床困难综合症（贪心+位运算）（暑假ACM1 A）
原文：https://www.cnblogs.com/sto324/p/11222345.html
