首页 > 代码库 > 【uoj2】 NOI2014—起床困难综合症

【uoj2】 NOI2014—起床困难综合症

2024-08-15 00:16:03   221人阅读

题意：给出n个操作包括And，or，xor，求从0~m中的一个数使得经过这些操作后得到的值最大。

Solution 
　　大水题。。贪心由高到低枚举二进制上每一位：这一位为0，经过操作后当前位变为1，那么就把这一位定为0；这一位为1，经过操作后仍然为1，且当前答案加上这一位后不超过m，那么就把这一位定为1；无论是0还是1经过操作后都为0，那么当然是选0，保证答案尽可能小。

代码：

// uoj2#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<queue>#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;}

　　

 

【uoj2】 NOI2014—起床困难综合症


联系
我们