起床困难综合症

AcWing-998-起床困难综合症

分析

见《进阶指南》第8页。

实现

#include <iostream>
using namespace std;

typedef pair<string, int> PSI;
const int N = 100010;
int n, m;
PSI a[N];

int solve (int k, int x0_k) {
    int res = x0_k;
    for (int i = 1; i <= n; ++ i) {
        int bit = (a[i].second >> k) & 1;
        if (a[i].first[0] == 'O') // OR
            res |= bit;
        else if (a[i].first[0] == 'X') // XOR
            res ^= bit;
        else // AND
            res &= bit;
    }
    return res; // 0 或 1
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1, t; i <= n; ++ i) {
        char opt[5];
        scanf("%s%d", opt, &t);
        a[i] = { opt, t };
    }

    int res = 0, val = 0;
    for (int i = 29; i >= 0; -- i) {
        int ans_0 = solve(i, 0);
        int ans_1 = solve(i, 1);
        if (val + (1 << i) <= m && ans_0 == 0 && ans_1 == 1)
            val += (1 << i), res += (ans_1 << i);
        else
            res += (ans_0 << i);
    }
    printf("%d", res);
    return 0;
}