luogu P2114 [NOI2014]起床困难综合症 位运算 二进制

建议去uoj那里去测，数据比较强

位运算的题目，就得一位一位的分开考虑

然后枚举初始值的最高位是0 是1 的最终攻击

(二进制内)最高位是1肯定比次位是1次次位是1次次次位是1···的大吧，显然

然后贪心O(N)就能过去啦

感觉自己是学傻了，看到n=5w就写了个nlog

情况好像有某一位的初始值是0最终那一位是1,初始值是1，最终那一位也是1的，所以要注意一下

代码：
(咦，好像别人家的代码呀)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#define ll long long
using namespace std;
const int maxn = 1e5 + 7;

int n, m, one, ling, ans, end, cz[maxn], num[maxn];

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

int check(int ans) {
    for (int i = 1; i <= n; ++ i) {
        if (cz[i] == 1) {
            ans = ans & num[i];
        } else if (cz[i] == 2) {
            ans = ans | num[i];
        } else if (cz[i] == 3) {
            ans = ans ^ num[i];
        }
    }
    return ans;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i) {
        char s = getchar();
        while (s == '\n' || s == ' ') s = getchar();
        if (s == 'A') cz[i] = 1;
        else if (s == 'O') cz[i] = 2;
        else cz[i] = 3;

        num[i] = read();
    }
    one = check((1 << 30) - 1), ling = check(0);
    for (int i = 30 ; i >= 0; --i) {
        if (!(ling & (1 << i)) && (one & (1 << i)) && (ans + (1 << i) <= m))
            ans += 1 << i, end += 1 << i;
        else if (ling & (1 << i))
            end += 1 << i;

    }
    cout << end << "\n";
    return 0;
}