起床困难综合症[NOI2014]

【题解】

并不算很困难的贪心题。位运算毕竟是针对每一位的，从前向后处理，如果某一位1比0更优且可取1就使它为1。比较0和1的结果要单取这一位来看，但是题目中所给的参数并没有必要全部二进制分解，直接用十进制得到的答案是一样的。预处理出2的前29次方(几乎是正好卡到10^9)，取二进制位就变得更简单了。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int ef[],n,m,cs[],temp,tp,jg,wf;

char a[][];

int main()

{

    //freopen("t.txt","r",stdin);

    freopen("sleep.in","r",stdin);

    freopen("sleep.out","w",stdout);

    ef[]=;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%s%d",a[i],&cs[i]);

    temp=;

    for(int i=;i<=;i++)

    {

      ef[i]=ef[i-]<<;

      if(ef[i]<=m) temp=i;

    }

    for(int i=temp+;i>=;i--)

    {

       if(jg+ef[i]>m)  continue;

       tp=ef[i];

       for(int j=;j<=n;j++)

       {

          if(a[j][]=='X')  tp^=cs[j];

          if(a[j][]=='A')  tp&=cs[j];

          if(a[j][]=='O')  tp|=cs[j];

       }

       wf=;

       for(int j=;j<=n;j++)

       {

          if(a[j][]=='X')  wf^=cs[j];

          if(a[j][]=='A')  wf&=cs[j];

          if(a[j][]=='O')  wf|=cs[j];

       }

       if((wf&ef[i])<(tp&ef[i])) jg+=ef[i];

    }

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

    {

        if(a[i][]=='X')  jg^=cs[i];

        if(a[i][]=='A')  jg&=cs[i];

        if(a[i][]=='O')  jg|=cs[i];

    }

    printf("%d",jg);

    //while(1);

    return ;

}