2020 动物园 · 方案一子集枚举

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 2567 字
逐位预处理 + 枚举 2^k 子集计数
2020
位运算
正文

// CSP-S 2020 复赛 T2 · 动物园（方案一：预处理 + 2^k 子集计数，k ≤ 20）
// 原题：https://oj.yecheng.tv/p/CSPS2020B
// 题意：n 只动物各有 k 位特征掩码；m 条规则 (p, q)：动物若有第 p 位
//       特征，就必须买 q 号饲料。已买饲料 = 原有动物触发规则的并集。
//       合法新动物 S：S 中每位触发的饲料都已买。求合法 S 总数 − n。
// 思路（逐位预处理 + 子集枚举）：
//   1. appear = 所有原有动物掩码的 OR；已买饲料 = appear 中位触发的 q。
//   2. 对每个特征位 b（0..k-1）：b 是否"可自由使用"？——若 b ∈ appear，
//      它触发的饲料必然已买 → 安全；若 b ∉ appear，检查它触发的每条
//      规则的 q 是否都在已买集合中（q 用排序数组 + 二分查找）。
//      不可用的位记 bad[b] = true。
//   3. 合法 S = 只由"安全位"组成的掩码 → 个数 = 2^(安全位数)。
//   4. 答案 = 2^(安全位数) − n。
//   本方案用 2^k 枚举来"数"合法 S（k ≤ 20 才可行），逻辑与方案二
//   完全一致，方便对照理解；方案二用公式直接算。
// 复杂度：O(n + m·d + 2^k)（d 为每位的平均规则数）。
// 易错点：
//   1. 饲料编号 q ≤ 1e8，不能位压，用数组 + 排序 + 二分；
//   2. appear 中的 1 位永远安全，别误标 bad；
//   3. 答案与总数用 unsigned long long。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, k, c;
unsigned long long a[1000005];
vector<unsigned long long> feedOf[65]; // 位 b 触发的饲料列表
unsigned long long bought[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++) {
        unsigned long long p, q;
        scanf("%llu%llu", &p, &q);
        feedOf[p].push_back(q);        // 题面保证 p < k
    }
    // 已买饲料：appear 中位触发的 q
    for (int b = 0; b < k; b++) {
        if (!((appear >> b) & 1ULL)) continue;
        for (unsigned long long q : feedOf[b])
            bought[boughtN++] = q;
    }
    sort(bought, bought + boughtN);
    boughtN = unique(bought, bought + boughtN) - bought;
    // 逐位判安全
    int safeCnt = 0;
    for (int b = 0; b < k; b++) {
        if ((appear >> b) & 1ULL) { safeCnt++; continue; }
        bool ok = true;
        for (unsigned long long q : feedOf[b])
            if (!binary_search(bought, bought + boughtN, q)) { ok = false; break; }
        if (ok) safeCnt++;
    }
    // 2^k 枚举计数（与公式 2^safeCnt 对照）
    long long total = 0;
    for (unsigned long long S = 0; S < (1ULL << k); S++) {
        bool ok = true;
        for (int b = 0; b < k && ok; b++)
            if ((S >> b) & 1ULL) {
                if (!((appear >> b) & 1ULL)) {
                    for (unsigned long long q : feedOf[b])
                        if (!binary_search(bought, bought + boughtN, q)) { ok = false; break; }
                }
            }
        if (ok) total++;
    }
    printf("%lld\n", total - (long long)n);
    return 0;
}
2020 动物园 · 方案一 子集枚举

正文

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

2020 动物园 · 方案一子集枚举
