[NOI2014]起床困难综合征

Description:

有n扇门,每扇门上有一个位运算符(&,|,^) 和一个权值,要求合理的选择一个不超过m的数,使其按顺序经过这些门的运算后最大

Hint:

\(n \le 10^5\)

Solution:

考虑拆位,分别令每一位一开始是0/1,经过运算后得到的是什么

然后从高位贪心,若运算后为1,则考虑选对应开始时这一位

若此时对应初始值为0,则直接更新答案

若为1,要检验是否还能选,若能,就把m减去它

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ls p<<1

#define rs p<<1|1

using namespace std;

typedef long long ll;

int n,m,val,ans;

char s[10];

inline int read() {

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

    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}

    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

    return x*f;

}

inline int chkmax(int &x,int y) {if(x<y) x=y;}

inline int chkmin(int &x,int y) {if(x>y) x=y;}

int main()

{

    n=read(); m=read(); int x=0,y=-1;

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

        scanf("%s",s); val=read();

        if(s[0]=='A') x&=val,y&=val;

        else if(s[0]=='O') x|=val,y|=val;

        else x^=val,y^=val;

    }

    for(int i=30;i>=0;--i)

        if(x>>i&1) ans|=1<<i;

        else if(y>>i&1&&(1<<i)<=m) ans|=1<<i,m-=1<<i;

    printf("%d",ans);

    return 0;

}