Next Quiz

复赛二：动物园(zoo)

信息学奥赛历年真题 2020年NOIP提高组真题复赛二：动物园(zoo)

洛谷：P7076
OJ：CSPS2020B

问题描述简要回顾：

动物种类： 动物园中有 n 种动物，编号为 a_i。
饲养指南： 有 m 条要求，每条要求形如：
- 如果动物编号的第 p_j位为 1，则必须购买第 q_j种饲料。
饲料种类： 共有 c种饲料。
动物编号位数： 动物编号为 k 位的二进制数。
目标： 在不改变饲料清单的情况下，计算还能饲养多少种新的动物。

算法思路：

统计已有动物编号的位信息：
- 对所有已有动物的编号进行按位或（OR）运算，得到一个包含所有已有动物中为 1 的位的结果 existingBits。
- 这样，我们就知道了哪些位在已有动物中是为 1 的。
确定新动物编号中必须为 0 的位：
- 对于每条饲养指南的要求 (p_j, q_j)：
  - 如果已有动物在第 p_j位为 0，且该位尚未被标记为必须为 0，那么该位在新动物中必须为 0，以避免购买新的饲料。
  - 将该位标记为必须为 0，并将可自由变化的位数 freeBits 减 1。
计算可能的动物编号组合数：
- 可自由变化的位数为 freeBits，则可能的动物编号组合数为 2^freeBits。
- 这代表了新动物编号的所有可能组合数。
计算最终结果：
- 最终可添加的动物种类数为：totalCombinations - n。
- 即所有可能的组合数减去已有的动物数量。
特殊情况处理：
- 当没有已有动物和要求，且编号位数为 64 时，可能的组合数为 2⁶⁴，由于超出了 unsigned long long 的范围，需要特殊处理。

变量声明：

n：已有的动物数量。
m：饲养指南的要求数量。
c：饲料种类数量（在本程序中未直接使用）。
k：动物编号的二进制位数。
freeBits：可自由变化的位数，初始为 k。
bitMustBeZero[MAX_BITS]：用于标记哪些位必须为 0。
animalID：动物编号。
bitPosition：饲养指南中的位位置 pjp_jpj。
feedType：饲养指南中的饲料种类 qjq_jqj。
totalCombinations：可能的动物编号组合数，初始为 1。
existingBits：已有动物编号的按位或结果。

处理饲养指南：

循环读取每条饲养指南的位位置 bitPosition 和饲料种类 feedType。
判断条件解释：
- (existingBits >> bitPosition) & 1：检查 existingBits 的第 bitPosition 位是否为 1。
- !((existingBits >> bitPosition) & 1)：如果结果为真，表示该位为 0。
- !bitMustBeZero[bitPosition]：该位尚未被标记为必须为 0。
如果已有动物在该位为 0，且该位尚未被标记为必须为 0，则：
- 将 freeBits 减 1，表示可自由变化的位数减少。
- 将 bitMustBeZero[bitPosition] 标记为 true。

for (int i = 0; i < m; i++) {
        cin >> bitPosition >> feedType;
        if (!((existingBits >> bitPosition) & 1) && !bitMustBeZero[bitPosition]) {
            // 如果已有动物在第 bitPosition 位为 0，且该位尚未被标记为必须为 0
            freeBits--;  // 可自由变化的位数减 1
            bitMustBeZero[bitPosition] = true;  // 标记该位必须为 0
        }
    }

算法复杂度分析：

时间复杂度： O(n+m)
- 读取和处理已有动物编号的循环耗时 O(n)。
- 处理饲养指南的循环耗时 O(m)。
空间复杂度： O(k)
- 使用了大小为 k的数组 bitMustBeZero。

代码实现：

/**************************************************************** 
 * Description: 2020年提高组复赛第二题  动物园
 * Author: Alex Li
 * Date: 2024-09-30 00:54:57
 * LastEditTime: 2024-09-30 16:33:57
****************************************************************/
#include <cstdio>
#include <iostream>
                                                                                                                                                                                                                                                                                                                                                
#define LL long long 
#define ULL unsigned long long
const int MAX_BITS = 65;

using namespace std;

int n, m, c, k, freeBits;
bool bitMustBeZero[MAX_BITS];
LL animalID, bitPosition, feedType;
ULL totalCombinations = 1, existingBits;

int main() {
    // freopen("zoo.in","r","stdin");
    //freopen("zoo.in","w","stdout");
    // 读取已有的动物数量 n，要求数量 m，饲料种类数量 c，动物编号的位数 k
    cin >> n >> m >> c >> k;
    freeBits = k;  // 初始化可自由变化的位数为 k

    if (!n && !m && k == 64) {
        // 特殊情况处理：当没有已有动物和要求，且编号位数为 64 时
        cout << "18446744073709551616";
        return 0;
    }

    // 读取已有动物的编号，并计算所有编号的按位或结果
    for (int i = 1; i <= n; i++) {
        cin >> animalID;
        existingBits |= animalID;  // 将编号进行按位或，得到已有动物编号中为 1 的位
    }

    // 处理饲养指南的要求
    for (int i = 0; i < m; i++) {
        cin >> bitPosition >> feedType;
        if (!((existingBits >> bitPosition) & 1) && !bitMustBeZero[bitPosition]) {
            // 如果已有动物在第 bitPosition 位为 0，且该位尚未被标记为必须为 0
            freeBits--;  // 可自由变化的位数减 1
            bitMustBeZero[bitPosition] = true;  // 标记该位必须为 0
        }
    }

    // 计算可能的动物编号组合数
    for (int i = 1; i <= freeBits; i++) {
        totalCombinations *= 2;  // totalCombinations = 2^freeBits
    }

    // 输出结果，减去已有的动物数量
    cout << totalCombinations - n;
    return 0;
}

Previous Topic

Back to Lesson

Next Quiz