P2114 [NOI2014]起床困难综合症

题目地址

经典状态压缩题，思路挺巧妙的。（也可能是我太蒻了吧）、、、

题解

我们要从 \([0-m]\) 中间选一个数 \(x_0\) 使得最后的攻击力最大。

如果从二进制的角度来观察 \(x_0\) ，你就会发现一系列的 \(\text{xor}\)、 \(&\) 、 \(|\) 操作只不过是 \(x_0\) 二进制下的每一位在进行这一系列操作，使得最后的答案最大。

“换言之，对于任意的 k（0<=k<=30）,‘ans 的第 k 位是几’只与‘ \(x_0\) 的第 k 位是几’有关”

于是考虑二进制下填位的方法，从高位到低位依次填 \(1\) 或 \(0\)

\(x_0\) 的 \(k\) 位上填 1 ，当且仅当

• \(x_0\) 的 \(k\) 位上填 1 ，值不会超过 \(m\)

• \(x_0\) 的 \(k\) 位上填 1 比填 0 要优

知道什么时候太填 \(1\) 什么时候填 \(0\)，你就可以轻轻松松切掉这道题了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int n,m;
int t[N];
string op[N];
inline int calc(int k,int now) {
    for(int i=1;i<=n;++i) {
        int x = (t[i]>>k) & 1;
        if(op[i] == "AND") now &= x;
        else if(op[i] == "OR") now |= x;
        else now ^= x;
    }
    return now;
}   //运算n次后看返回 1 还是 0 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) {
        char str[5];
        scanf("%s%d",str,&t[i]); op[i] = str;
    }
    int val = 0 ,ans = 0;   //ans来保存最后攻击力 
    for(int i=29;i>=0;--i) {    //位运算学着学着就从零开始计数了qwq 
        int res0 = calc(i,0) ,res1 = calc(i,1); //分别处理看一下填0和填一会怎么样
        if(val+(1<<i)<=m && res0<res1)
            val += (1<<i) ,ans += (res1<<i);
        else
            ans += (res0<<i);
    }
    printf("%d\n",ans);
    return 0;
}

刚刚看了一下洛谷题解，发现题解的大佬们都吊打我，还说这是一道大水题。