题解

问题分析

题目要求计算动物园在不改变现有饲料清单的前提下，还能饲养多少种未被当前饲养的动物。核心在于分析新动物加入后是否会触发新的饲料需求，关键是确定哪些二进制位的取值会影响饲料清单。

核心思路

1. 饲料清单的决定因素：现有动物中，若某动物编号的第p位为1，则所有要求“第p位为1时需购买饲料q”的q都会被加入清单。
2. 新动物的限制：加入新动物x后，饲料清单不变意味着x的任何为1的二进制位p，必须已被现有动物触发（即现有动物中至少有一个的第p位为1），否则会新增饲料需求。
3. 自由位与受限制位：
   • 自由位：可以任意取0或1的位（不会触发新饲料需求）。
   • 受限制位：若现有动物中该位均为0，且存在相关饲料要求，则该位必须为0（否则触发新饲料）。
4. 计算逻辑：
   • 用mask记录现有动物所有位的“或”结果（某位置1表示现有动物中该位存在1）。
   • 统计受限制位的数量（去重后，满足“mask中该位为0且存在相关饲料要求”的位）。
   • 自由位数量 = 总位数k - 受限制位数量。
   • 可新增动物数量 = 2^自由位数量 - 现有动物数量n（减去已饲养的动物）。

代码解析

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;

int ans, n, m, c, k, a[1000005], answ;  // answ为现有动物的或运算结果（mask）
int vis[1000005], Ans = 1;  // vis标记受限制位是否已统计，Ans计算2^自由位
struct node {
    int p, q;
} r[1000005];

signed main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    cin >> n >> m >> c >> k;
    ans = k;  // 初始自由位为总位数k

    // 特殊情况：k=64且无动物和要求时，2^64无法用unsigned long long表示，直接输出
    if (k == 64 && !n && !m) {
        cout << "18446744073709551616";
        return 0;
    }

    // 计算现有动物的或运算结果mask
    for (int i = 1 ; i <= n ; i++)
        cin >> a[i], answ |= a[i];

    // 统计受限制位的数量（去重）
    for (int i = 1 ; i <= m ; i++) {
        cin >> r[i].p >> r[i].q;
        // 若mask中该位为0且未被标记，则该位是受限制位，自由位减1
        if (!((answ >> r[i].p) & 1) && !vis[r[i].p]) {
            ans--;
            vis[r[i].p] = 1;
        }
    }

    // 计算2^自由位数量
    for (int i = 1 ; i <= ans ; i++)
        Ans *= 2;

    // 结果为可新增动物数量（减去现有n种）
    cout << Ans - n;
    return 0;
}

复杂度分析

• 时间复杂度：O(n + m)，需遍历所有动物和饲料要求。
• 空间复杂度：O(m)，存储饲料要求和标记数组。

该算法通过位运算高效判断位的状态，结合去重统计受限制位，最终通过幂运算计算可能的新增动物数量，逻辑清晰且性能优异。