复赛二：动物园(zoo)

洛谷：P7076
OJ：CSPS2020B

问题描述简要回顾：

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

算法思路：

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

代码实现：

 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
/**************************************************************** 
 * 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