【题解】LOJ 2244 「NOI2014」起床困难综合症

Problem

给定 $n$ 次操作,分别是 $OR$ $t$ ,$XOR$ $t$ ,或者是 $AND$ $t$ 。其中 $t$ 为非负整数

给定 $m$ ,求 $[1,m]$ 中依次经过 $n$ 次操作后最大的数是多少

Thought

分开考虑每一位

时间复杂度 $O(n\ln m)$

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
int n, m, T[N];
char Opt[N][4];
void solve(bool &one, bool &zero, int bin, char str, int t) {
    bool x = t & (1 << bin);
    if(str == 'O') {
        one |= x;
        zero |= x;
    }
    else if(str == 'X') {
        one ^= x;
        zero ^= x;
    }
    else if(str == 'A') {
        one &= x;
        zero &= x;
    }
}
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i) {
        scanf("%s", Opt[i]);
        scanf("%d", &T[i]);
    }
    int now = 0, ans = 0;
    for(int i = 30; i >= 0; -- i) {
        bool One = 1, Zero = 0;
        for(int j = 1; j <= n; ++ j)
            solve(One, Zero, i, Opt[j][0], T[j]);
        if(now + (1 << i) > m)
            ans += (Zero << i);
        else {
            if(Zero >= One)
                ans += (Zero << i);
            else {
                ans += (One << i);
                now += (1 << i);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
Comments

添加新评论