题解 P2114 【[NOI2014]起床困难综合症】

2018-11-24 19:16:25


老年退役选手发来问候

二进制相关,考虑拆位。

这个题中,我们要做的就是钦定初始攻击力,经过^&|操作之后得到的值最大。

我们从高位向低位枚举二进制每一位,判断加上当前位之后的答案是否会更优

最后输出初始攻击力经过传送门之后的值即可。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define R register

using namespace std;

const int gz=1e5+8;

inline void in(R int &x)
{
    R int f=1;x=0;char s=getchar();
    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
    while(isdigit(s)){x=x*10+s-'0';s=getchar();}
    x*=f;
}

char op[15];

int t[gz],ans,n,m,ot[gz];

inline int c(R int x)
{
    for(R int i=1;i<=n;i++)
    {
        if(ot[i]==1)x&=t[i];
        else if(ot[i]==3)x^=t[i];
        else x|=t[i];
    }
    return x;
}

int main()
{
    in(n),in(m);
    for(R int i=1;i<=n;i++)
    {
        scanf("%s",op+1);
        if(op[1]=='A')ot[i]=1;
        else if(op[1]=='X')ot[i]=3;
        else ot[i]=2;
        in(t[i]);
    }
    for(R int i=30;~i;i--)
    {
        if((ans+(1<<i))>m)continue;
        if( c(ans) < c(ans+(1<<i)))
                ans+=(1<<i);
    }
    printf("%d",c(ans));
}