起床困难综合症

题意

给你N个门，每个门的操作为AND,XOR,OR中的一种，每个门有一个操作数，现在让一个[0,m]的数字x依次通过这n扇门，问最大的结果是多少

思路

位运算没有进位，所以可以每一位单独运算

所以我们让在[0,m]范围的每一位去通过这n道门，查看结果即可

因为x有[0,m]范围的限制，所以我们要尽可能的让x最小

即对于x的第i位当且仅当

x的第i位为0时通过n道门得到的结果不为1

且x的第i位为1时通过n道门得到的结果为1时

x的第i位才为1，否则都是0

最后获得x跑一边n道门就是答案啦

代码

#include<cstdio>
#include<utility>
#include<iostream>
#include<string>
using namespace std;
long long n, m;
pair<string, long long>gates[100005];
long long pow(long long a, long long b) {
    long long ans = 1;
    long long base = a;
    while (b > 0) {
        if (b & 1) {
            ans *= base;
        }
        base *= base;
        b >>= 1;
    }
    return ans;
}
bool fun(long long k) {
    bool ans = 0;
    for (long long i = 0; i < n; i++) {
        long long nu = gates[i].second >> k & 1;
        if (gates[i].first == "AND") {
            ans &= nu;
        }
        else if (gates[i].first == "OR") {
            ans |= nu;
        }
        else {
            ans ^= nu;
        }
    }
    if (ans) {
        return false;
    }
    else {
        ans = 1;
        for (long long i = 0; i < n; i++) {
            long long nu = gates[i].second >> k & 1;
            if (gates[i].first == "AND") {
                ans &= nu;
            }
            else if (gates[i].first == "OR") {
                ans |= nu;
            }
            else {
                ans ^= nu;
            }
        }
        if (ans) {
            return true;
        }
        else {
            return false;
        }
    }
}
string s;
long long t1;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    long long temp = 1;
    for (long long i = 0; i < n; i++) {
        cin >> s >> t1;
        gates[i] = make_pair(s, t1);
    }
    long long ans = 0;
    long long x = 0;
    //获取位的上限
    for (long long i = 0; i < 999; i++) {
        if ((1 << i) == m) {
            x = i;
            break;
        }
        else if ((1 << i) > m) {
            x = i-1;
            break;
        }
    }
    long long base = pow(2, x);
    //优先使高位开始贪心
    for (long long i = x; i >= 0; i--) {
        if (fun(i)) {
            ans += base;
        }
        if (ans > m) {
            ans -= base;
            break;
        }
        base /= 2;
    }
    //得到的ans跑一边n道门
    for (long long i = 0; i < n; i++) {
        long long nu = gates[i].second;
        if (gates[i].first == "AND") {
            ans &= nu;
        }
        else if (gates[i].first == "OR") {
            ans |= nu;
        }
        else {
            ans ^= nu;
        }
    }
    printf("%lld\n", ans);
    return 0;
}