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

发表于 分类于

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1
1

说明/提示

【样例说明】

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

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

  • 4 AND 5 = 4；
  • 4 OR 6 = 6；
  • 6 XOR 7 = 1。

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

【数据规模与约定】

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

对于所有数据，保证 2 ≤ n ≤ 105，0 ≤ m ≤ 109，0 ≤ t ≤ 109，且 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;
}