题目链接

算法竞赛进阶指南-4.起床困难综合症

Method : 位运算-贪心

首先，很容易想到暴力的做法：枚举每一个m，进行n次操作，然后记录最大值:

for (int i = 1; i <= m; i ++) {
    for (int j = 1; j <= n; j ++) {
        if (op[j] == "XOR") {
            i = i ^ t[j];
        }
        else if (...) {
            // ...
        }
    }
    if (i > max_i) // ...
}

但是这样时间复杂度是$O(mn)$，是不可取的。

---

而不难发现${AND,XOR, OR}$这三个操作，参与位运算时，各个位之间是独立无关的。
因此，为了保证res取最大值，可以从高位到低位考虑，输入的x的每一位填0还是1，并且要尽量保证操作完后的数的高位是1(贪心)。

#include <bitset>
#include <string>
#include <iostream>

using namespace std;

const int M = 31;

int n , m ;

int main() {
    bitset<M> zero , one ;
    zero.reset(); // 一个初始化每一位都是0
    one.set();    // 一个初始化每一位都是1
    cin >> n >> m ;
    
    while(n --) {
        string x ;
        int y ;
        cin >> x >> y ;
        
        if (x == "AND") zero &= y , one &= y ;
        else if (x == "OR") zero |= y , one |= y ;
        else if (x == "XOR") zero ^= y , one ^= y ;
    }
    
    int ans = 0; int val = 0;
    for(int i = M ; i >= 0 ; i --) {
        if(zero[i] == 1) {
            ans += (1 << i);  
        }
        else if(one[i] == 1 && val + (1 << i) <= m) {
            val += (1 << i);
            ans += (1 << i); 
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度${O(nlog_2m)}$， 其中$log_2m$为对$m$逐位判断的时间复杂度，$n$为$n$次操作。

• 空间复杂度${O(1)}$。