洛谷 P2114 [NOI2014] 起床困难综合症

// P2114 ★ 第 ① 版：把 x = 0 .. m 全试一遍 —— 答案永远对，它只挂在时间上
//
// ★ 复杂度 O(nm)，顶格 10⁵ × 10⁹ = 10¹⁴ ⇒ 这次「肯定超时」是真的。
// ★★ 而题面的**测试点表**把它能拿多少分写得清清楚楚：
//     测试点 1（n = 100, m = 0）／ 2、3（n = 1000, m = 1000）⇒ **稳拿 30 分**。
//   ⇒ [「出题人把暴力那一档也写好了」](/sol/p1776/)的又一次。
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; long long m;
    if (scanf("%d %lld", &n, &m) != 2) return 0;
    vector<char> op(n); vector<unsigned> t(n);
    for (int i = 0; i < n; i++) {
        char s[8]; unsigned v;
        if (scanf("%7s %u", s, &v) != 2) return 0;
        op[i] = s[0]; t[i] = v;
    }
    long long best = 0;
    for (long long x = 0; x <= m; x++) {
        unsigned cur = (unsigned)x;
        for (int i = 0; i < n; i++) {
            if (op[i] == 'A') cur &= t[i];
            else if (op[i] == 'O') cur |= t[i];
            else cur ^= t[i];
        }
        best = max(best, (long long)cur);
    }
    printf("%lld\n", best);
    return 0;
}

// P2114 [NOI2014] 起床困难综合症 —— 正解：按位拆开，一位一位贪心
//
// ★★★ 全部立论只有一句话：**AND / OR / XOR 都是「逐位」的运算** ——
//   输出的第 b 位只由输入的第 b 位决定，和别的位一点关系都没有。
//   ⇒ 于是「选一个 x ≤ m 让结果最大」这个看起来要枚举 10⁹ 种可能的问题，
//     拆成 30 个**互不相干**的小问题：这一位填 0 还是填 1。
//
// ★★ 怎么一次问完 30 位：把 **x = 0** 和 **x = 全 1** 各推过一遍所有门。
//   因为逐位独立，`f(0)` 的第 b 位就是「第 b 位填 0 的结果」，
//   `f(全1)` 的第 b 位就是「第 b 位填 1 的结果」。⇒ 两趟 O(n)，不是 30 趟。
//
// ★ 然后从高位往低位贪心（高位的 2^b 比它下面所有位加起来还大，所以能拿就拿）：
//   · 填 0 就能得 1 ⇒ **白拿**，一分钱预算不花；
//   · 只有填 1 才得 1 ⇒ 看预算：`used + 2^b ≤ m` 才拿。
//   ⚠ 第二条必须是**累计**的 `used + 2^b ≤ m`，不是 `2^b ≤ m`（见 p2114Bit.cpp）。
//
// ⚠ 位宽：t、m ≤ 10⁹ < 2³⁰ ⇒ 从 0 出发、只做 AND/OR/XOR，结果永远 < 2³⁰
//   ⇒ 第 0~29 位就够，`int` 完全装得下（这道题不需要 long long）。
#include <bits/stdc++.h>
using namespace std;

static const int B = 30;                      // 0 ~ 29 位

int main() {
    int n; long long m;
    if (scanf("%d %lld", &n, &m) != 2) return 0;
    unsigned a = 0, b = ~0u;                  // a = f(0)，b = f(全 1)
    for (int i = 0; i < n; i++) {
        char op[8]; unsigned t;
        if (scanf("%7s %u", op, &t) != 2) return 0;
        if (op[0] == 'A')      { a &= t; b &= t; }
        else if (op[0] == 'O') { a |= t; b |= t; }
        else                   { a ^= t; b ^= t; }
    }
    long long used = 0, ans = 0;
    for (int k = B - 1; k >= 0; k--) {
        unsigned bit = 1u << k;
        if (a & bit) ans += bit;                                  // ★ 填 0 就有 —— 白拿
        else if ((b & bit) && used + (long long)bit <= m) {       // ⚠ 累计预算
            used += bit; ans += bit;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

// P2114 解析页上所有数字的出处。
//   ./p2114Count          人话版
//   ./p2114Count csv      给 check:viz 用
//
// 三件事：
//   ① ★★★ **验「按位独立」这个立论本身** —— 正解、四个错法**全都**建立在
//      「输出的第 b 位只由输入的第 b 位决定」上，所以它们互相对拍验不了这句话
//      （[第 37 章 P2085](/sol/p2085/) 那条）。这里拿「真把 x 推一遍」当参照物，
//      和「用 f(0) / f(全1) 逐位拼出来的预测值」比。
//      ⚠ 而这个 0 **配了自检**：把其中一扇门换成一个**不是逐位**的运算（加法），当场对不上。
//   ② 位宽和类型账：t、m ≤ 10⁹ < 2³⁰ ⇒ 第 0~29 位就够，`int` 装得下。
//   ③ 暴力值多少分（题面的测试点表直接给了答案），以及顶格的两把尺子。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;

int main(int argc, char** argv) {
    bool csv = (argc > 1 && argv[1][0] == 'c');
    mt19937 rng(20260906u);

    /* ---------- ① 逐位独立：预测 vs 真跑 ---------- */
    int trials = 200000, badPredict = 0, badSelf = 0;
    for (int r = 0; r < trials; r++) {
        int n = 1 + (int)(rng() % 8u);
        vector<int> op(n); vector<unsigned> t(n);
        for (int i = 0; i < n; i++) { op[i] = (int)(rng() % 3u); t[i] = rng() % 1073741824u; }
        auto apply = [&](unsigned x) {
            for (int i = 0; i < n; i++) {
                if (op[i] == 0) x &= t[i]; else if (op[i] == 1) x |= t[i]; else x ^= t[i];
            }
            return x;
        };
        /* ⚠ 自检用的「假门」：把最后一扇换成加法（**不是**逐位运算）*/
        auto applyFake = [&](unsigned x) {
            for (int i = 0; i < n; i++) {
                if (i + 1 == n) x += t[i];
                else if (op[i] == 0) x &= t[i]; else if (op[i] == 1) x |= t[i]; else x ^= t[i];
            }
            return x;
        };
        unsigned a = apply(0u), b = apply(~0u);
        unsigned fa = applyFake(0u), fb = applyFake(~0u);
        unsigned x = rng() % 1073741824u;
        unsigned pred = 0, predF = 0;
        for (int k = 0; k < 30; k++) {
            unsigned bit = 1u << k;
            if (((x & bit) ? b : a) & bit) pred |= bit;
            if (((x & bit) ? fb : fa) & bit) predF |= bit;
        }
        if ((pred & 0x3FFFFFFFu) != (apply(x) & 0x3FFFFFFFu)) badPredict++;
        if ((predF & 0x3FFFFFFFu) != (applyFake(x) & 0x3FFFFFFFu)) badSelf++;
    }

    /* ---------- ② 位宽 ---------- */
    long long tMax = 1000000000LL, pow30 = 1LL << 30;
    int bitsNeeded = 0; while ((1LL << bitsNeeded) <= tMax) bitsNeeded++;   // 需要多少位才装得下 10⁹

    /* ---------- ③ 顶格：正解走几步 vs 暴力走几步 ---------- */
    long long nMax = 100000, mMax = 1000000000LL;
    long long okOps = 2 * nMax + 30;                 // 两趟 O(n) ＋ 30 位贪心
    long long bruteOps = nMax * (mMax + 1);          // O(nm)
    /* 正解顶格实测（自己造一组 n = 10⁵ 的门，跑 1000 遍取平均）*/
    vector<int> op(nMax); vector<unsigned> tt(nMax);
    for (long long i = 0; i < nMax; i++) { op[i] = (int)(rng() % 3u); tt[i] = rng() % 1073741824u; }
    static volatile unsigned sink = 0;
    auto t0 = chrono::steady_clock::now();
    for (int rep = 0; rep < 1000; rep++) {
        unsigned a = 0, b = ~0u;
        for (long long i = 0; i < nMax; i++) {
            if (op[i] == 0) { a &= tt[i]; b &= tt[i]; }
            else if (op[i] == 1) { a |= tt[i]; b |= tt[i]; }
            else { a ^= tt[i]; b ^= tt[i]; }
        }
        sink = a ^ b;
    }
    (void)sink;
    double okMs = chrono::duration<double, milli>(chrono::steady_clock::now() - t0).count() / 1000.0;

    if (csv) {
        printf("trials,%d\nbadPredict,%d\nbadSelf,%d\n", trials, badPredict, badSelf);
        printf("bitsNeeded,%d\n", bitsNeeded);
        printf("tFitsIn30,%d\n", tMax < pow30 ? 1 : 0);
        printf("okOps,%lld\nbruteOps,%lld\n", okOps, bruteOps);
        printf("opsRatio,%lld\n", bruteOps / okOps);
        printf("okFast,%d\n", okMs < 20.0 ? 1 : 0);
        printf("bruteScore,30\n");
        return 0;
    }

    printf("P2114：全部立论压在「AND / OR / XOR 都是逐位的」这一句上\n\n");
    printf("  ① 逐位独立验一遍（%d 组随机门序列 + 随机 x）：\n", trials);
    printf("     用 f(0) / f(全1) 逐位拼出来的预测值 ≠ 真跑一遍的结果：%d 组\n", badPredict);
    printf("     ⚠ 自检：把最后一扇门换成加法（不是逐位运算）⇒ 对不上 %d 组\n\n", badSelf);
    printf("  ② 位宽：t、m ≤ 10⁹ 要 %d 位（< 2³⁰）⇒ 第 0~29 位就够，int 装得下，不用 long long\n\n", bitsNeeded);
    printf("  ③ 顶格 n = 10⁵、m = 10⁹：\n");
    printf("     ★ 正解  两趟 O(n) ＋ 30 位贪心 = %lld 次基本操作，实测 %.3f 毫秒\n", okOps, okMs);
    printf("     ✗ 暴力  O(nm) = %lld 次 ⇒ 差 %lld 倍（而题面测试点表给了它 30 分）\n",
           bruteOps, bruteOps / okOps);
    return 0;
}