[CSP-S 2020] 动物园

GitHub跳转原题关系图返回列表

先用现有动物的按位或找出已出现过的二进制位，再把仍会引入新饲料的位置并成危险位，最后按自由位数量直接计数。

OJ: luogu

题目 ID: P7076

难度:普及+/提高-

标签:位运算二进制计数思维

创建: 2026-06-20 10:42

更新: 2026-10-07 10:45

后置题目

luogu P5522[yLOI2019] 棠梨煎雪B 复用 A 的自由位计数步骤：约束压成掩码后统计自由位，答案为 2 的自由位数次幂

形式化题目

有 $2^k$ 种动物，编号为 $0 \sim 2^k - 1$ 。动物园已饲养 $n$ 种（编号 $a_i$ ），另有 $m$ 条规则 $(p_j, q_j)$ ：若某种动物编号的第 $p_j$ 个二进制位为 $1$ ，则必须购买第 $q_j$ 种饲料。

当前动物园已根据现有动物购买了一份饲料清单。问：有多少种当前未饲养的动物，加入后饲料清单不发生变化。

解法路线

题面给出了四个真实的分数档位：

档位	真实约束	做法	瓶颈
$20\%$	$k \leqslant 5,\ n \leqslant 5$	枚举所有 $2^k$ 只动物逐只判断	$2^k$ 枚举
$40\%$	$k \leqslant 20,\ n \leqslant 15$	同上	$2^{20} \approx 10^6$ ，尚可
$60\%$	$k \leqslant 30$	统计禁止位，公式 $2^{free} - n$	无
$100\%$	$k \leqslant 64$	同上 + 处理 $2^{64}$ 溢出边界	无

$20\%$ 和 $40\%$ 共用暴力枚举， $60\%$ 和 $100\%$ 共用公式，区别仅在 $2^{64}$ 的溢出处理。每层代码都能独立提交、逐层拿分。

暴力解法： $k \leqslant 20$

适用范围

$20\%$ 和 $40\%$ 的数据满足 $k \leqslant 20$ ，此时 $2^k \leqslant 10^6$ ，可以枚举所有动物逐只判断。

思路

先根据当前 $n$ 只动物算出已购买的饲料集合，再枚举每一种未饲养的编号 $x$ ，检查 $x$ 是否会触发某条"当前还没买"的饲料规则。如果不触发， $x$ 就可以加入。

代码

cpp

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:31
 * update_at: 2026-10-01 22:31
 */
// subtask_40.cpp：40% 数据 k ≤ 20，枚举所有 2^k 只动物逐只判断。
// 时间 O(2^k · m)，空间 O(n + m)。覆盖 20% 和 40% 两档。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

ll n, m, c, k;
vector<ull> animals;
vector<int> rule_p;
vector<int> rule_q;
unordered_set<ull> exist_animal;
unordered_set<int> current_feed;

bool has_bit(ull x, int p) {
    return (x >> p) & 1ULL;
}

// 枚举所有动物和规则，算出当前已购买的饲料。
void build_current_feed() {
    current_feed.clear();
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < m; j++) {
            if (has_bit(animals[i], rule_p[j])) {
                current_feed.insert(rule_q[j]);
            }
        }
    }
}

// 判断新动物 x 能否加入：不触发任何"当前还没买"的饲料规则。
bool can_add(ull x) {
    for (ll j = 0; j < m; j++) {
        if (has_bit(x, rule_p[j]) && current_feed.find(rule_q[j]) == current_feed.end()) {
            return false;
        }
    }
    return true;
}

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

    cin >> n >> m >> c >> k;

    animals.resize(n);
    for (ll i = 0; i < n; i++) {
        cin >> animals[i];
        exist_animal.insert(animals[i]);
    }

    rule_p.resize(m);
    rule_q.resize(m);
    for (ll i = 0; i < m; i++) {
        cin >> rule_p[i] >> rule_q[i];
    }

    build_current_feed();

    // 枚举所有编号，跳过已饲养的，统计能加入的。
    ull limit = 1ULL << k;
    ull ans = 0;
    for (ull x = 0; x < limit; x++) {
        if (exist_animal.find(x) != exist_animal.end()) {
            continue;
        }
        if (can_add(x)) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度与瓶颈

时间 $O(2^k \cdot m)$ 。 $k = 20$ 时 $2^{20} \approx 10^6$ ， $m \leqslant 20$ ，尚可；但 $k = 30$ 时 $2^{30} \approx 10^9$ 就超时了。

子任务解法： $k \leqslant 30$

适用范围

$60\%$ 的数据满足 $k \leqslant 30$ 。 $2^{30}$ 太大不能枚举，但可以用公式一步算出答案。

思路

真正的关键是把"会不会引入新饲料"翻译成对二进制位的限制。

先把所有当前动物做一个按位或： $zoo\_mask = a_1 | a_2 | \cdots | a_n$ 。它的第 $p$ 位为 $1$ 表示至少已有一种动物在第 $p$ 位上是 $1$ 。

对规则 $(p, q)$ 分两种情况：

情况	结论
$zoo\_mask$ 第 $p$ 位已是 $1$	第 $q$ 种饲料早已买过
$zoo\_mask$ 第 $p$ 位是 $0$ ，且第 $q$ 种饲料还没买	新动物不能把第 $p$ 位设成 $1$

把所有"会引入新饲料"的位置并成禁止位掩码 $bad\_mask$ 。新动物合法当且仅当它的所有禁止位都是 $0$ 。若禁止位有 $bad\_cnt$ 个，自由位就有 $free\_cnt = k - bad\_cnt$ 个，合法动物总数为 $2^{free\_cnt}$ ，减去已饲养的 $n$ 种即得答案。

因为 $k \leqslant 30$ ， $free\_cnt \leqslant 30$ ， $2^{30}$ 远小于 unsigned long long 上限，无需溢出处理。

代码

cpp

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:31
 * update_at: 2026-10-01 22:31
 */
// subtask_60.cpp：60% 数据 k ≤ 30，用公式 2^free_cnt - n 直接算答案。
// 核心思路：统计"禁止位"（未买饲料对应的位），自由位数 = k - 禁止位数。
// 因为 k ≤ 30，free_cnt ≤ 30，2^30 远小于 ull 上限，无需溢出处理。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXM = 1000005;

ll m, c, k;
ll n;
int rule_p[MAXM];
int rule_q[MAXM];
ull zoo_mask;
ull bad_mask;
unordered_set<int> bought_feed;

bool has_bit(ull x, int p) {
    return (x >> p) & 1ULL;
}

// 读入动物编号，合并为位掩码。
void read_animals() {
    zoo_mask = 0;
    for (ll i = 0; i < n; i++) {
        ull x;
        cin >> x;
        zoo_mask |= x;
    }
}

// 读入规则，标记已购买的饲料。
void read_rules() {
    bought_feed.clear();
    for (ll i = 1; i <= m; i++) {
        cin >> rule_p[i] >> rule_q[i];
        if (has_bit(zoo_mask, rule_p[i])) {
            bought_feed.insert(rule_q[i]);
        }
    }
}

// 构建禁止位掩码。
void build_bad_mask() {
    bad_mask = 0;
    for (ll i = 1; i <= m; i++) {
        if (bought_feed.find(rule_q[i]) == bought_feed.end()) {
            bad_mask |= (1ULL << rule_p[i]);
        }
    }
}

void solve() {
    read_animals();
    read_rules();
    build_bad_mask();

    int bad_cnt = __builtin_popcountll(bad_mask);
    int free_cnt = (int)k - bad_cnt;

    // k ≤ 30 保证 free_cnt ≤ 30，1ULL << 30 不会溢出。
    ull total = 1ULL << free_cnt;
    ull ans = total - n;
    cout << ans << '\n';
}

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

    cin >> n >> m >> c >> k;
    solve();

    return 0;
}

复杂度与瓶颈

时间 $O(n + m)$ ，空间 $O(m)$ 。公式本身没问题，唯一需要注意的是 $k = 64$ 时 $2^{64}$ 的溢出。

正解

关键观察

公式 $ans = 2^{free\_cnt} - n$ 对全部合法数据都成立。 $100\%$ 数据和 $60\%$ 数据的算法完全相同，唯一区别是 $k = 64$ 时 $free\_cnt$ 可能等于 $64$ ，此时 $2^{64}$ 超出 unsigned long long 的正向表示范围。

思路

读入动物编号，合并为 $zoo\_mask$ ；
读入规则，标记已购买的饲料，构建禁止位掩码 $bad\_mask$ ；
$free\_cnt = k - \operatorname{popcount}(bad\_mask)$ ；
若 $free\_cnt = 64$ ，用无符号回绕计算 $2^{64} - n$ ；否则直接 $2^{free\_cnt} - n$ 。

代码

cpp

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:31
 * update_at: 2026-10-01 22:31
 */
// main.cpp：满分做法，统计"禁止位"后用公式 2^free_cnt - n 得到答案。
// 核心思路：当前动物园已有动物的位掩码决定哪些规则的饲料已买，
// 未买饲料对应的位就是"禁止位"，新动物这些位必须为 0。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXM = 1000005;

ll m, c, k;          // 要求数、饲料种数、二进制位数
ull n;               // 动物数量（需要无符号做减法，见下方 2^64 边界处理）
int rule_p[MAXM];    // rule_p[j] = 第 j 条规则的二进制位编号（0 ~ k-1）
int rule_q[MAXM];    // rule_q[j] = 第 j 条规则对应的饲料编号（1 ~ c）
ull zoo_mask;        // 当前动物园里，哪些二进制位曾经出现过 1
ull bad_mask;        // 新动物这些位必须是 0，否则会引入新饲料
unordered_set<int> bought_feed; // 当前已购买的饲料集合

// 判断 x 的第 p 位是否为 1。
bool has_bit(ull x, int p) {
    return (x >> p) & 1ULL;
}

// 读入所有动物编号，合并为一个位掩码。
void read_animals() {
    zoo_mask = 0;
    for (ull i = 0; i < n; i++) {
        ull x;
        cin >> x;
        zoo_mask |= x;
    }
}

// 读入规则，同时标记哪些饲料已经被购买。
void read_rules() {
    bought_feed.clear();
    bought_feed.reserve((size_t)m * 2 + 5);
    bought_feed.max_load_factor(0.7f);

    for (ll i = 1; i <= m; i++) {
        cin >> rule_p[i] >> rule_q[i];

        // 如果当前动物园里已有动物在第 p 位上是 1，这条规则的饲料一定买过了。
        if (has_bit(zoo_mask, rule_p[i])) {
            bought_feed.insert(rule_q[i]);
        }
    }
}

// 构建禁止位掩码：未买饲料对应的位，新动物不能取 1。
void build_bad_mask() {
    bad_mask = 0;
    for (ll i = 1; i <= m; i++) {
        // 如果第 q 种饲料还没买，新动物一旦在第 p 位取 1 就会触发新饲料。
        if (bought_feed.find(rule_q[i]) == bought_feed.end()) {
            bad_mask |= (1ULL << rule_p[i]);
        }
    }
}

void solve() {
    read_animals();
    read_rules();
    build_bad_mask();

    int bad_cnt = __builtin_popcountll(bad_mask);
    int free_cnt = (int)k - bad_cnt; // 自由位数（不在禁止掩码中的位）

    // free_cnt == 64 只在 k == 64 且 bad_mask == 0 时出现。
    // 此时总方案数是 2^64，超出 ull 的正向表示范围，需要特殊处理。
    if (free_cnt == 64) {
        if (n == 0) {
            cout << "18446744073709551616\n"; // 2^64
        } else {
            ull ans = 0;
            ans -= n; // 等价于 2^64 - n（ull 回绕）
            cout << ans << '\n';
        }
        return;
    }

    ull total = 1ULL << free_cnt;
    ull ans = total - n;
    cout << ans << '\n';
}

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

    cin >> n >> m >> c >> k;
    solve();

    return 0;
}

复杂度

时间复杂度： $O(n + m)$ 。
空间复杂度： $O(m)$ 。

总结

这题的核心不是去模拟"买了哪些饲料"，而是先看出：当前动物园真正提供的信息只有"哪些二进制位曾经出现过 $1$ "。再进一步推出：所有会导致新饲料出现的位置必须固定为 $0$ ，其余位置全部自由。这样题目就从一个规则模拟题变成了一个直接的位运算计数题。

四个分数档位串起来是一条"从枚举到公式、从有符号到无符号"的路线：暴力枚举 $2^k$ → 统计禁止位用公式 → 处理 $2^{64}$ 溢出边界。真正需要记住的只有 $ans = 2^{free\_cnt} - n$ 和 $k = 64$ 时的溢出处理。

本文的 main.cpp 已用逐只枚举版 brute.cpp 进行 300 组随机对拍，覆盖 $k \leqslant 10$ 的随机数据。

P7076 [CSP-S 2020] 动物园

题目描述

动物园里饲养了很多动物，饲养员小 A 会根据饲养动物的情况，按照《饲养指南》购买不同种类的饲料，并将购买清单发给采购员小 B。

具体而言，动物世界里存在 $2^k$ 种不同的动物，它们被编号为 $0 \sim 2^k - 1$ 。动物园里饲养了其中的 $n$ 种，其中第 $i$ 种动物的编号为 $a_i$ 。

《饲养指南》中共有 $m$ 条要求，第 $j$ 条要求形如“如果动物园中饲养着某种动物，满足其编号的二进制表示的第 $p_j$ 位为 $1$ ，则必须购买第 $q_j$ 种饲料”。其中饲料共有 $c$ 种，它们从 $1 \sim c$ 编号。本题中我们将动物编号的二进制表示视为一个 $k$ 位 01 串，第 $0$ 位是最低位，第 $k - 1$ 位是最高位。

根据《饲养指南》，小 A 将会制定饲料清单交给小 B，由小 B 购买饲料。清单形如一个 $c$ 位 $01$ 串，第 $i$ 位为 $1$ 时，表示需要购买第 $i$ 种饲料；第 $i$ 位为 $0$ 时，表示不需要购买第 $i$ 种饲料。实际上根据购买到的饲料，动物园可能可以饲养更多的动物。更具体地，如果将当前未被饲养的编号为 $x$ 的动物加入动物园饲养后，饲料清单没有变化，那么我们认为动物园当前还能饲养编号为 $x$ 的动物。

现在小 B 想请你帮忙算算，动物园目前还能饲养多少种动物。

输入格式

第一行包含四个以空格分隔的整数 $n, m, c, k$ 。

分别表示动物园中动物数量、《饲养指南》要求数、饲料种数与动物编号的二进制表示位数。

第二行 $n$ 个以空格分隔的整数，其中第 $i$ 个整数表示 $a_i$ 。

接下来 $m$ 行，每行两个整数 $p_i, q_i$ 表示一条要求。

数据保证所有 $a_i$ 互不相同，所有的 $q_i$ 互不相同。

输出格式

仅一行一个整数表示答案。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

1见附件中的 zoo/zoo3.in

输出 #3

text

1见附件中的 zoo/zoo3.ans

说明/提示

【样例 #1 解释】

动物园里饲养了编号为 $1, 4, 6$ 的三种动物，《饲养指南》上的三条要求为：

若饲养的某种动物的编号的第 $0$ 个二进制位为 $1$ ，则需购买第 $3$ 种饲料。
若饲养的某种动物的编号的第 $2$ 个二进制位为 $1$ ，则需购买第 $4$ 种饲料。
若饲养的某种动物的编号的第 $2$ 个二进制位为 $1$ ，则需购买第 $5$ 种饲料。

饲料购买情况为：

编号为 $1$ 的动物的第 $0$ 个二进制位为 $1$ ，因此需要购买第 $3$ 种饲料；
编号为 $4, 6$ 的动物的第 $2$ 个二进制位为 $1$ ，因此需要购买第 $4, 5$ 种饲料。

由于在当前动物园中加入一种编号为 $0, 2, 3, 5, 7, 8, \ldots , 15$ 之一的动物，购物清单都不会改变，因此答案为 $13$ 。

【数据范围】

对于 $20 \%$ 的数据， $k \le n \le 5$ ， $m \le 10$ ， $c \le 10$ ，所有的 $p_i$ 互不相同。

对于 $40 \%$ 的数据， $n \le 15$ ， $k \le 20$ ， $m \le 20$ ， $c \le 20$ 。

对于 $60 \%$ 的数据， $n \le 30$ ， $k \le 30$ ， $m \le 1000$ 。

对于 $100 \%$ 的数据， $0 \le n, m \le 10^6$ ， $0 \le k \le 64$ ， $1 \le c \le 10^8$ 。

[CSP-S 2020] 动物园

目录

形式化题目

解法路线

暴力解法：k⩽20k \leqslant 20k⩽20

适用范围

思路

代码

复杂度与瓶颈

子任务解法：k⩽30k \leqslant 30k⩽30

适用范围

思路

代码

复杂度与瓶颈

正解

关键观察

思路

代码

复杂度

总结

暴力解法： $k \leqslant 20$

子任务解法： $k \leqslant 30$