(题目链接)
题意
给出n个操作包括And,or,xor,求从0~m中的一个数使得经过这些操作后得到的值最大。
Solution
大水题。。贪心由高到低枚举二进制上每一位:这一位为0,经过操作后当前位变为1,那么就把这一位定为0;这一位为1,经过操作后仍然为1,且当前答案加上这一位后不超过m,那么就把这一位定为1;无论是0还是1经过操作后都为0,那么当然是选0,保证答案尽可能小。
细节
数组开小?
代码
// uoj2#include#include #include #include #include #include #include #define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;const int maxn=100010;struct data {int t,op;}a[maxn];int bin[31],n,m,x;char s[10];int cal(int x,int val) { for (int i=1;i<=n;i++) { if (a[i].op==0) val&=a[i].t; else if (a[i].op==1) val|=a[i].t; else val^=a[i].t; } if (val&x) return 1; else return 0;}int main() { bin[0]=1;for (int i=1;i<=30;i++) bin[i]=bin[i-1]<<1; scanf("%d%d",&n,&m); char s[10]; for (int i=1;i<=n;i++) { scanf("%s%d",s,&a[i].t); if (s[0]=='A') a[i].op=0; else if (s[0]=='O') a[i].op=1; else a[i].op=2; } int l=30,ans=0; if (m!=0) { for (;bin[l]>m;l--); for (int i=l;i>=0;i--) { if (cal(bin[i],0)) continue; else if (cal(bin[i],bin[i]) && ans+bin[i]<=m) ans+=bin[i]; } } for (int i=1;i<=n;i++) { if (a[i].op==0) ans&=a[i].t; else if (a[i].op==1) ans|=a[i].t; else ans^=a[i].t; } printf("%d",ans); return 0;}