洛谷2114 [NOI2014]起床困难综合症

题意

在 $[0,m]$ 中选一个数，使得它经过给定的 $n$ 个 &、|、^ 操作后得到的数最大。

$2\le m\le 10^{9} \ , \ 2\le n\le 10^{5}$ 。

题解

所有数都 $\le 2^{30}$ ，而且修改都只涉及二进制的修改，所以对每一位进行贪心。

用 $s_0$ 代表最初全为 $0$ 的数在操作后每一位的值；用 $s_1$ 代表最初全为 $1$ 的数在操作后每一位的值。

然后从高到低枚举每一位：

1. 如果 $0$ 能变成 $1$ ， 即 $s_0$ 的当前位为 $1$ ，则加入答案
2. 如果 $1$ 能变成 $1$ ， 即 $s_1$ 的当前位为 $1$ ，也加入答案，因为后面的位对答案的贡献一定比当前小。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

char op[3];
int n,m,x,ans,s0=0,s1=-1;

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        scanf("%s%d",op,&x);
        if (op[0]=='A') s0&=x,s1&=x;
        else if (op[0]=='O') s0|=x,s1|=x;
        else s0^=x,s1^=x;
    }
    for (int i=30;~i;i--)
    {
        if (s0>>i&1) ans|=1<<i;
        else if (s1>>i&1 && (1<<i)<=m) m-=1<<i,ans|=1<<i;
    }
    return !printf("%d",ans);
}