[luogu2114][起床困难综合症]

luogu2114

思路

因为位运算对于每一位是独立的，所以对每一位都对这n个数进行操作，然后观察最后得出的是1还是0。并且保证每一位拼起来之后要比m小。

代码

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=100000+100;

ll read() {

    ll x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') {

        if(c=='-') f=-1;

        c=getchar();

    }

    while(c>='0'&&c<='9') {

        x=x*10+c-'0';

        c=getchar();

    }

    return x*f;

}

int n,m;

char s[10];

int pd[N],a[N];

int solve(int x) {

    int now=0;

    for(int i=1;i<=n;++i) {

        int z=(1&(a[i]>>x));

        if(pd[i]==1) now&=z;

        if(pd[i]==2) now|=z;

        if(pd[i]==3) now^=z;

    }

    if(now==1) return 0;

    now=1;

    for(int i=1;i<=n;++i) {

        int z=(1&(a[i]>>x));

        if(pd[i]==1) now&=z;

        if(pd[i]==2) now|=z;

        if(pd[i]==3) now^=z;

    }

    if(now==1) return 1;

    return 0;

}

int main() {

    n=read(),m=read();

    for(int i=1;i<=n;++i) {

        scanf("%s",s);

        if(s[0]=='A') pd[i]=1;

        else if(s[0]=='O') pd[i]=2;

        else pd[i]=3;

        a[i]=read();

    }

    int bz=0;

    int ans=0;

    for(int i=31;i>=0;--i) {

        int k=solve(i);

        if(bz==1) ans|=(k<<i);

        else {

            if(m&(1<<i)) {

                if(k==0)

                    bz=1;

                ans|=(k<<i);

            }

        }

    }

    for(int i=1;i<=n;++i) {

        if(pd[i]==1) ans&=a[i];

        if(pd[i]==2) ans|=a[i];

        if(pd[i]==3) ans^=a[i];

    }

    printf("%d\n",ans);

    return 0;

}