【题解】Acwing 998 起床困难综合症

起床困难综合症

题目传送门

题目太长了就不复制了自己看去

输入格式

第 1 行包含 2 个整数，依次为n, m，表示 drd 有n扇防御门，atm 的初始攻击力为0到m之间的整数。

接下来n行，依次表示每一扇防御门。每行包括一个字符串op和一个非负整数t，

两者由一个空格隔开，且op在前，t在后，op表示该防御门所对应的操作，t表示对应的参数。

输出格式

输出一个整数，表示atm的一次攻击最多使drd受到多少伤害。

输入样例：

3 10
AND 5
OR 6
XOR 7

输出样例：

1

思路分析：

题目是让我们选择([0,m])之间的整数(x_0)，经过给定的n次位运算，使结果ans最大

位运算的主要特点之一是在二进制表示下不进位。

所以ans的第k位至与(x_0)的第k位是几有关。

(x_0)的第k位填1的条件：

1. 加上 1<<k 以后不超过m
2. 第k位。若初值为1，结果为1；若k位为0，结果为0。

换句话说就是：

1. 可以选1
2. 填1 比 填0 优。若 1 与 0 相同 填0 在之后有更大可能 填1 。

代码展示：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll; typedef unsigned long long ull;

const int N = 1e5 + 10;
int n, m, res1, res0, val, ans, a[N]; // val 不超过m, ans 最大伤害
string op[N];

inline int calc(int k, int x){
    for(int i = 0; i < n; i ++) {
        int ttt = (a[i] >> k) & 1;
        if(op[i] == "AND") x &= ttt;
        else if(op[i] == "OR") x |= ttt;
        else x ^= ttt;
    }
    return x;
}

int main()
{
    //freopen("data1.in", "r", stdin);
    //freopen("data1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        cin >> op[i] >> a[i];
    for(int bit = 29; bit >=0; bit --) {
        res0 = calc(bit, 0);
        res1 = calc(bit, 1);
        if(res1 > res0 && val + (res1<<bit) <= m)
            val += res1<<bit, ans += res1<<bit;
        else ans += res0<<bit;
    }
    cout << ans << endl;
    return 0;
}