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

2周前 (06-21)比赛题解72

一、问题背景

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

二、核心算法解析

位运算基础
我们使用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;
}