2020 动物园 · 方案二位或统计加计数公式

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 2705 字
数集合并不会引入新特征，答案只看缺失的位数
2020
位运算
正文

// CSP-S 2020 复赛 T2 · 动物园（方案二：位或统计 + 计数公式，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2020B
// 题意：同方案一（n, m ≤ 1e6，k ≤ 64，需满分）。
// 思路（一步到位的计数）：
//   关键转化：饲料规则只与"特征位是否出现过"有关。设 appear = 所有
//   原有动物特征位的 OR（k 位掩码）。对规则 (p, q)：若位 p ∈ appear
//   则饲料 q 必买。而"新动物 S 合法" ⟺ S 中出现的每个位 p 所触发的
//   饲料都已买。注意：饲料 q 是否已买只取决于 appear 是否含"触发它的
//   位"。定义 goodMask = appear 本身？——正确结论（题面保证规则与
//   动物相容）：S 合法 ⟺ S ⊆ appear ∪ Safe，其中 Safe = "位 p ∈ Safe
//   当且仅当 p 触发的饲料全部由 appear 触发的饲料覆盖"。
//   更直接的等价（官方口径）：合法 S 的集合 = appear 的"扩充闭包"，
//   计数 = 2^(k - popcount(appear)) × 2^0 ... 不对——正解：
//   S 只要在"触发饲料 ⊆ 已买饲料"意义下合法，而已买饲料由 appear
//   决定 → 枚举 appear 的每个 0 位 p：加入 p 会新增触发饲料 R(p)。
//   R(p) ⊆ 已买 ⟺ p 可自由加入。设 freeCnt = 可自由加入的 0 位个数，
//   则合法 S 数 = 2^freeCnt × 2^(受限位的组合) —— 只有当所有"不可
//   自由加入"的 0 位都不能加入时（每条规则要么已由 appear 满足，
//   要么对应位不可用），合法 S = 子集 of {appear 的 1 位} ∪ {free 位}：
//   总数 = 2^(popcount(appear) + freeCnt)。
//   答案 = 2^(该值) − n。
//   freeCnt 的计算：0 位 p 可用 ⟺ 触发它的所有饲料 q 都已买；饲料
//   已买 ⟺ 至少一个 appear 中的位触发它。逐规则把 q 挂到 p 上，
//   再检查 p 的所有 q 是否被 appear 中的位触发。
// 复杂度：O(n + m)。
// 易错点：
//   1. 2^64 溢出：freeCnt + ones 可达 64 → 用 unsigned long long 且
//      特判 1ULL << 64 未定义（拆成两次乘或用 __int128 / 特判 64）；
//   2. 饲料编号 q ≤ 1e8 无法直接位压 → 用哈希表/排序去重判存在；
//   3. appear 全 1 时答案 = 2^k − n。
#include <cstdio>
#include <algorithm>
using namespace std;

int n, m, k, c;
unsigned long long a[1000005];
unsigned long long rp[1000005], rq[1000005];
unsigned long long boughtList[1000005];
int boughtN = 0;

int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &k, &c);
    unsigned long long appear = 0;
    for (int i = 0; i < n; i++) {
        scanf("%llu", &a[i]);
        appear |= a[i];
    }
    for (int j = 0; j < m; j++) scanf("%llu%llu", &rp[j], &rq[j]);
    // 已买饲料 = appear 含位 p 的规则的 q
    for (int j = 0; j < m; j++)
        if ((appear >> (rp[j] % 64)) & 1ULL)
            boughtList[boughtN++] = rq[j];
    sort(boughtList, boughtList + boughtN);
    // 对每个 0 位 p：其触发的 q 是否全部已买
    int freeCnt = 0;
    for (int b = 0; b < k; b++) {
        if ((appear >> b) & 1ULL) continue;
        bool ok = true;
        for (int j = 0; j < m && ok; j++) {
            if (rp[j] % 64 != b) continue;
            if (!binary_search(boughtList, boughtList + boughtN, rq[j])) ok = false;
        }
        if (ok) freeCnt++;
    }
    int ones = 0;
    for (int b = 0; b < k; b++) ones += (int)((appear >> b) & 1ULL);
    int e = ones + freeCnt;            // 合法 S 数 = 2^e（每一位独立可选）
    unsigned long long ans;
    if (e >= 64) ans = 0ULL - (unsigned long long)n;   // 2^64 − n 的无符号回绕恰好正确
    else ans = (1ULL << e) - (unsigned long long)n;
    printf("%llu\n", ans);
    return 0;
}
2020 动物园 · 方案二 位或统计加计数公式

正文

CSP-S 标程 · 复赛真题的其它内容

2020 动物园 · 方案二位或统计加计数公式
