起床困难综合症

  • 分析

    为什么有人说他是dp呢
    可以发现直接枚举m可以得到30分的好成绩ヽ( ̄▽ ̄)ノ
    图片说明
    虽然m不能枚举完,但是把其表示成二进制枚举每一位还是可以做到的。因为每一位只有0|1的情况,根据贪心,从高位开始,判定每一位为0|1能否造成伤害,肯定是先判定0能否使这一位最终答案为1,否则去判断1能否使这一位为1

  • 代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n,m;
char s[10];
int id[N],a[N],f[31][N];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1,x;i<=n;i++)
    {
        scanf("%s%d",s,&x);
        if(s[0]=='A') id[i]=1;
        else if(s[0]=='O') id[i]=2;
        else id[i]=3;

        for (int j=0;j<=30;j++)
        {
            if(!(x>>j)) break;
            if(x&(1<<j)) f[j][i]=1;
        }
    }

    int las=0,now=0;
    for (int j=30;j>=0;j--)
    {
        int oj=0;
        for (int i=1;i<=n;i++)
        {
            if(id[i]==1) oj&=f[j][i];
            else if(id[i]==2) oj|=f[j][i];
            else oj^=f[j][i];
        }

        if(oj) las+=(1<<j);
        else
        {
            if(now+(1<<j)>m) continue;
            oj=1;
            for (int i=1;i<=n;i++)
            {
                if(id[i]==1) oj&=f[j][i];
                else if(id[i]==2) oj|=f[j][i];
                else oj^=f[j][i];
            }
            if(oj) las+=(1<<j),now+=(1<<j);
        }
    }

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

    return 0;
}