CSP-S2020 洛谷P7076 从零理解位运算：动物园问题深度解析

15303105423 · 发表于 2025-6-24 20:47:38

一、问题背景
动物园问题要求我们计算在特定规则下可以饲养的新动物数量。题目涉及位运算、集合论等计算机科学基础知识，是理解二进制运算的绝佳案例。
二、核心算法解析

位运算基础
我们使用unsigned long long存储动物属性，每个二进制位代表一种特征。例如：
动物A：1010（二进制）表示具有第1和第3种特征
动物B：1100表示具有第2和第3种特征

关键步骤分解
(1) 合并已有动物属性：
通过按位或运算合并所有动物的特征，得到总特征集合
(2) 处理饲养员要求：
对每个要求的二进制位进行标记，并检查现有动物是否满足
(3) 计算自由位数：
未被限制的二进制位可以自由组合，决定新动物的可能数量

三、代码实现要点输入优化：使用ios::sync_with_stdio加速输入输出
位运算技巧：

使用1ULL << p获取第p位的掩码
按位或(|)合并属性
按位与(&)检查属性

边界处理：

特别注意n=0和free_bits=64的情况
使用unsigned long long防止溢出

四、完整代码#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

/*

* 解题思路：

* 1. 使用位运算处理动物属性

* 2. 统计每个二进制位上的需求情况

* 3. 计算满足所有饲养员要求的最小动物数量

*/

int main() {

// 输入优化

ios::sync_with_stdio(false);

cin.tie(nullptr);

int n, m, c, k;

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

// 读取已有动物属性

unsigned long long animals = 0;

for (int i = 0; i < n; ++i) {

      unsigned long long a;

      cin >> a;

      animals |= a; // 合并所有动物的属性

}

// 处理每个二进制位

vector<bool> required(k, false);

vector<bool> forbidden(k, false);

// 处理饲养员要求

for (int i = 0; i < m; ++i) {

      int p, q;

      cin >> p >> q;

      required[p] = true; // 标记该位有要求



      // 如果已有动物不满足该位要求，则禁止该位为1

      if (!(animals & (1ULL << p))) {

         forbidden[p] = true;

      }

}

// 计算可选位数

int free_bits = 0;

for (int i = 0; i < k; ++i) {

      if (!required[i] || (required[i] && !forbidden[i])) {

         free_bits++;

      }

}

// 计算结果（注意处理n=0的特殊情况）

if (free_bits == 64 && n == 0) {

      cout << "18446744073709551616" << endl;

} else {

      cout << (1ULL << free_bits) - n << endl;

}

return 0;

}
复制代码

五、复杂度分析时间复杂度：O(n + m + k)
空间复杂度：O(k)
高效处理了题目最大数据范围
六、总结通过这个问题，我们可以深入理解位运算在实际问题中的应用，培养抽象建模能力。建议读者在理解本解法后，尝试用其他方法（如集合运算）重新实现，比较不同解法的优劣。
CSP-S2020 洛谷P7076 从零理解位运算：动物园问题深度解析