NC17857 起床困难综合症

题意：

给定了所有的防御门运算符op和参数t，限定最大的初始攻击力为m，求经过防御门转变后最大一次能对恶龙造成多少伤害

思路：

为了方便描述，我们记初始伤害为， 经过防御门以后的伤害为。

既然防御门涉及到位运算，那干脆把 也表达为二进制，把问题转换成找到如何安排每一个bit的值，让的值最大

首先我们清楚：二进制中（如 0110 1001），越靠左的bit权值越大，其转换成十进制时对数的大小影响也越大。

为了能让最大，我们应尽可能让中靠左的bit为1，且1的数量尽可能多。
如果我们从最右的bit开始遍历，那么会容易让超出范围，带来很多不必要的计算，所以我们应该先让从 开始，向下递减计算。

在写代码的时候，为了方便，我让从1<<30 (大于 )开始，让不断右移，直到 ，并记录最高位1的位置

接下来，从最高位1开始，先判断如果将当前位的bit取反以后会不会超出限制（可能这步赘余了，我没仔细想，但思路是这么个思路），在确保不超出限制的情况下，再判断将bit取反以后是否能让变大，如果可以，就对该位的bit取反，对所有的bit进行相同操作。

对所有bit操作完以后，我们就得到了一个最大的

代码：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

//计算并返回num经过所有的防御门后的值
inline int crossTheDoors(int num, vector<vector<int>> &door) {
    for (auto &i : door) {
        if (i[0] == 1) {
            num |= i[1];
        } else if (i[0] == 2) {
            num ^= i[1];
        } else if (i[0] == 3) {
            num &= i[1];
        }
    }
    return num;
}

int main() {
    string temp;   //工具人变量
    int n;  //防御门的数量
    int m;  //攻击力的最大值
    cin >> n >> m;
    /*二维数组door
    door[i][0]表示运算符，1为OR，2为XOR，3为AND
    door[i][1]表示对应的t*/
    vector<vector<int>> door(n, vector<int>(2));
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        if (temp == "OR") {
            door[i][0] = 1;
            cin >> door[i][1];
        } else if (temp == "XOR") {
            door[i][0] = 2;
            cin >> door[i][1];
        } else if (temp == "AND") {
            door[i][0] = 3;
            cin >> door[i][1];
        }
    }
    int x = (1 << 30);
    int bitCount = 30;  //用于找到x中bit为1的最高位
    while (x > m) {
        x >>= 1;
        bitCount--;
    }
    while (bitCount >= 0) {
        //如果当前bit是0，且把他改成1后会大于m，则跳过
        if ((x & (1 << bitCount)) == 0) {
            if ((x | (1 << bitCount)) > m) {
                bitCount--;
                continue;
            }
        }
        //看看当前bit取反以后攻击会不会更大
        if (crossTheDoors((x ^ (1 << bitCount)), door) > crossTheDoors(x, door)) {
            x ^= (1 << bitCount);
        }
        bitCount--;
    }
    cout << crossTheDoors(x, door);
}