[C++] P2114 [NOI2014] 起床困难综合症

发表于 更新于 分类于 ， ，

2121 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因：在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。正是由于 drd 的活动，起床困难综合症愈演愈烈，以惊人的速度在世界上传播。为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来，drd 的防御战线由 nn 扇防御门组成。每扇防御门包括一个运算 opop 和一个参数 tt，其中运算一定是 OR,XOR,AND\text{OR},\text{XOR},\text{AND} 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 xx，则其通过这扇防御门后攻击力将变为 x op tx~op~t。最终 drd 受到的伤害为对方初始攻击力 xx 依次经过所有 nn 扇防御门后转变得到的攻击力。

由于 atm 水平有限，他的初始攻击力只能为 00 到 mm 之间的一个整数（即他的初始攻击力只能在 0,1,…,m0,1,\ldots,m 中任选，但在通过防御门之后的攻击力不受 mm 的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。

输入格式

输入文件的第 11 行包含 22 个整数，依次为 n,mn, m，表示 drd 有 nn 扇防御门，atm 的初始攻击力为 00 到 mm 之间的整数。

接下来 nn 行，依次表示每一扇防御门。每行包括一个字符串 opop 和一个非负整数 tt，两者由一个空格隔开，且 opop 在前，tt 在后，opop 表示该防御门所对应的操作，tt 表示对应的参数。

输出格式

输出一行一个整数，表示 atm 的一次攻击最多使 drd 受到多少伤害。

输入输出样例 #1

输入 #1

1
2
3
4
3 10
AND 5
OR 6
XOR 7

输出 #1

1
1

说明/提示

【样例说明】

atm 可以选择的初始攻击力为 0,1,…,100,1,\ldots ,10。

假设初始攻击力为 44，最终攻击力经过了如下计算

  • 4 AND 5=44 \text{ AND } 5 = 4；
  • 4 OR 6=64 \text{ OR } 6 = 6；
  • 6 XOR 7=16 \text{ XOR } 7 = 1。

类似的，我们可以计算出初始攻击力为 1,3,5,7,91,3,5,7,9 时最终攻击力为 00，初始攻击力为 0,2,4,6,8,100,2,4,6,8,10 时最终攻击力为 11，因此atm的一次攻击最多使drd受到的伤害值为 11。

【数据规模与约定】

  • 特殊性质 A\mathrm A：存在一扇防御门为 AND 0\texttt{AND 0}；
  • 特殊性质 B\mathrm B：所有防御门的操作均相同。

对于所有数据，保证 2≤n≤1052\le n\le 10^5，0≤m≤1090\le m\le 10^9，0≤t≤1090\le t\le 10^9，且 op\mathrm{op} 一定为 AND, OR, XOR 中的一种。

题解

虽然大家都是用真值表法的，但我选择……逆向思维。
反向算出能得出最大值的最小输入，然后砍到范围内，然后再正着算一遍。
有点麻烦，有点牵强，但是容易调试（）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

const size_t N = 1e5;
int n, m, i, t[N], tgt = INT_MAX;
char op[N];
string str;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (i = 0; i < n; i++) {
        cin >> str >> t[i];
        op[i] = str[0];
    }

    if (m){
        for (i = n - 1; i >= 0; i--) {
//        cout << tgt << " R" << op[i] << " " << t[i] << " = ";
            switch (op[i]) {
            case 'A':
                tgt &= t[i];
                break;
            case 'X':
                tgt ^= t[i];
                break;
            case 'O':
                tgt -= tgt & t[i];
                break;
            default:
                break;
            }
//        cout << tgt << endl;
        }
    }else tgt = m;

    if (tgt > m) tgt %= (int)(pow(2, (int)(log2(m)) + 1));
    while (tgt > m) tgt &= tgt - 1;
//    cout << "Caculated input: " << tgt << endl;

    for (i = 0; i < n; i++) {
//        cout << tgt << " " << op[i] << " " << t[i] << " = ";
        switch (op[i]) {
            case 'A':
                tgt &= t[i];
                break;
            case 'X':
                tgt ^= t[i];
                break;
            case 'O':
                tgt |= t[i];
                break;
            default:
                break;
        }
//        cout << tgt << endl;
    };

    cout << tgt;

    return 0;
}