[CSP-S 2020] 动物园

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

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

OJ: luogu

题目 ID: P7076

难度:普及+/提高

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

日期: 2026-06-20 10:42

题意

有 2^k 种动物，编号是 0 ~ 2^k - 1。

现在动物园里已经养了 n 种动物，编号分别是 a_i。
还有 m 条规则，每条规则是 (p, q)，表示：

如果动物编号的第 p 个二进制位是 1
就必须购买第 q 种饲料

当前动物园已经根据现有动物买好了一份饲料清单。

现在问：有多少种 当前还没养 的动物，可以直接加入动物园，而且加入后饲料清单不会发生变化。

思路

先看一个可以直接验证定义的小数据暴力：

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#include <bits/stdc++.h>
using namespace std;

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

// 小数据直接判断二进制位。
bool has_bit(unsigned long long x, int p) {
    return (x >> p) & 1ULL;
}

void build_current_feed() {
    current_feed.clear();

    // 朴素做法：枚举每只当前动物，再检查每一条规则是否触发。
    for (int i = 0; i < n; i++) {
        unsigned long long x = animals[i];
        for (int j = 0; j < m; j++) {
            if (has_bit(x, rule_p[j])) {
                current_feed.insert(rule_q[j]);
            }
        }
    }
}

bool can_add(unsigned long long x) {
    // 直接模拟：如果 x 会触发某条“当前还没买过”的饲料规则，
    // 那么加入它后清单就会变化，这种动物不能算。
    for (int i = 0; i < m; i++) {
        if (has_bit(x, rule_p[i]) && current_feed.find(rule_q[i]) == 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 (int i = 0; i < n; i++) {
        cin >> animals[i];
        exist_animal.insert(animals[i]);
    }

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

    build_current_feed();

    unsigned long long limit = 1ULL << k;
    unsigned long long ans = 0;
    for (unsigned long long x = 0; x < limit; x++) {
        if (exist_animal.find(x) != exist_animal.end()) {
            continue;
        }
        if (can_add(x)) {
            ans++;
        }
    }

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

brute.cpp 先朴素求出当前饲料清单，再枚举每一种还没养的动物，检查它会不会触发新的饲料。这个做法很直观，但只有在 k 很小时才能用。

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

先把所有当前动物做一个按位或：

zoo_mask = a_1 | a_2 | ... | a_n

它的含义是：

如果 zoo_mask 的第 p 位是 1
说明当前动物园里，至少已经有一种动物在第 p 位上是 1

于是对一条规则 (p, q) 来说，会分成两种情况：

情况	结论
`zoo_mask` 的第 `p` 位已经是 `1`	第 `q` 种饲料早就买过了
`zoo_mask` 的第 `p` 位是 `0`，且第 `q` 种饲料当前还没买	新动物不能把第 `p` 位设成 `1`

所以我们只需要关心那些 会引入新饲料 的位置，把它们记成一个集合 bad_mask：

如果某条规则 (p, q) 对应的第 q 种饲料现在还没买
那么第 p 位就是危险位，必须为 0

最后一个新动物 x 合法，当且仅当：

x 的所有危险位都是 0

也就是说：

危险位不能选
其它位都可以自由取 0/1

若危险位有 bad_cnt 个，那么自由位就有：

free_cnt = k - bad_cnt

所以满足条件的动物总数是：

2^{free_cnt}

但题目问的是“当前还没养”的动物种数，因此还要减去已经存在的 n 种动物：

ans = 2^{free_cnt} - n

实现时还有一个细节：

当 k = 64 且没有危险位时，总数是 2^64
这个值已经超出了 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
85
86
87
88
89#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1000005;

int n, m, c, k;
int rule_p[MAXM];
int rule_q[MAXM];
unsigned long long zoo_mask;   // 当前动物园里，哪些二进制位曾经出现过 1
unsigned long long bad_mask;   // 新动物这些位必须是 0，否则会引入新饲料
unordered_set<int> bought_feed;

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

void read_animals() {
    zoo_mask = 0;
    for (int i = 1; i <= n; i++) {
        unsigned long long 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 (int 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]);
        }
    }
}

void build_bad_mask() {
    bad_mask = 0;

    for (int i = 1; i <= m; i++) {
        // 如果第 q 种饲料现在还没买，那么新动物一旦在第 p 位取 1，
        // 就会触发一份新的饲料清单，于是这种位必须保持为 0。
        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 = k - bad_cnt;

    // free_cnt == 64 只会在 k == 64 且 bad_mask == 0 时出现。
    // 此时总方案数是 2^64，已经超出 unsigned long long 的正向表示范围。
    if (free_cnt == 64) {
        if (n == 0) {
            cout << "18446744073709551616\n";
        } else {
            unsigned long long ans = 0;
            ans -= (unsigned long long)n;  // 等价于 2^64 - n
            cout << ans << '\n';
        }
        return;
    }

    unsigned long long total = 1ULL << free_cnt;
    unsigned long long ans = total - (unsigned long long)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
其余位置全部自由

这样题目就从一个看起来很长的规则模拟题，变成了一个非常直接的位运算计数题。

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] 动物园

目录

题意

思路

代码

复杂度

总结