P1601. Pizza Anyone? 题解

一、题目分析

本题要求判断是否存在一种披萨配料组合，使得对于每个朋友的所有配料请求，至少满足其中一个。每个请求可以是包含（+）或不包含（-）某个配料，需要找到一个配料集合，使得每个朋友的请求列表中至少有一个条件被满足。

关键条件

• 每个朋友的约束条件是一个逻辑“或”（至少满足一个请求）。
• 配料共有16种（A-P），每种配料有两种状态：包含（1）或不包含（0）。

二、解题思路

位运算优化

将每个朋友的请求转换为位掩码，利用位运算快速判断条件是否满足：

1. 正请求（+X）：表示配料X必须包含，对应位掩码中X的位置为1。
2. 负请求（-X）：表示配料X必须不包含，对应位掩码中X的位置为0（即全集掩码Max异或后该位为1）。

算法步骤

1. 输入解析：将每个朋友的请求拆分为正请求和负请求，分别存储为两个位掩码（person[num][1]和person[num][0]）。
   • person[num][1]：包含的配料位掩码（正请求的按位或）。
   • person[num][0]：不包含的配料位掩码（负请求的按位或，需通过全集掩码转换为“必须不包含”的条件）。
2. 枚举所有可能的配料组合：使用位掩码status枚举0到(1<<16)-1的所有可能（共65536种）。
3. 条件判断：对于每个status，检查是否满足所有朋友的约束条件：
   • 对于朋友num，若status包含其正请求的任意一位（status & person[num][1]），或不包含其负请求的任意一位（(status ^ Max) & person[num][0]），则该朋友的条件被满足。
4. 输出结果：找到第一个满足条件的status，按字母序输出配料；若无满足条件的组合，输出无解信息。

三、代码实现

#include <cstdio>
#include <cstring>

int main() {
    char str[50]; // 存储输入行
    while (scanf("%s", str) != EOF) { // 循环处理每组数据
        int n = 0; // 朋友数量
        int person[100][2] = {0}; // person[num][1]存储正请求掩码，person[num][0]存储负请求掩码
        int Max = (1 << 16) - 1; // 全集掩码（16位全为1）

        // 读取约束条件，直到遇到单独的`.`
        while (str[0] != '.') {
            for (int i = 0; i < strlen(str) - 1; i += 2) { // 遍历每个请求（每两个字符为一个请求）
                char sign = str[i];
                char topping = str[i + 1];
                int bit = 1 << (topping - 'A'); // 计算当前配料对应的位掩码
                if (sign == '+') {
                    person[n][1] |= bit; // 正请求：包含该配料，添加到正掩码
                } else {
                    person[n][0] |= bit; // 负请求：不包含该配料，添加到负掩码（后续通过异或处理）
                }
            }
            n++; // 朋友数量加1
            scanf("%s", str); // 读取下一行
        }

        int status;
        // 枚举所有可能的配料组合（0到2^16-1）
        for (status = 0; status <= Max; status++) {
            int num;
            for (num = 0; num < n; num++) {
                // 检查当前组合是否满足第num个朋友的条件：
                // 正请求至少满足一个（status & person[num][1]不为0）
                // 或负请求至少满足一个（(status ^ Max) & person[num][0]不为0，即status中对应位为0）
                if (!(status & person[num][1] || (status ^ Max) & person[num][0])) {
                    break; // 不满足，尝试下一个组合
                }
            }
            if (num == n) { // 所有朋友的条件都满足
                break;
            }
        }

        // 输出结果
        if (status <= Max) { // 找到有效组合
            printf("Toppings: ");
            for (int i = 0; i <= 15; i++) { // 按字母序输出配料（A-P对应0-15位）
                if (status & (1 << i)) {
                    printf("%c", 'A' + i);
                }
            }
            printf("\n");
        } else { // 无解
            printf("No pizza can satisfy these requests.\n");
        }
    }
    return 0;
}

四、代码解析

1. 输入处理：

   • 逐行读取输入，直到遇到.，解析每个朋友的正负请求，分别存储为位掩码。
   • 正请求（+X）直接按位或到person[num][1]。
   • 负请求（-X）按位或到person[num][0]，后续通过与status ^ Max（即取反）判断是否不包含该配料。

2. 枚举与判断：

   • 使用status枚举所有可能的配料组合（0到65535）。
   • 对每个status，检查是否满足所有朋友的条件：正请求或负请求至少有一个成立。

3. 结果输出：

   • 若找到有效组合，按字母序拼接配料代码并输出。
   • 若无解，输出特定提示信息。

五、优化说明

• 位运算高效性：通过位掩码将配料组合和约束条件转换为整数运算，显著提高枚举效率（65536次循环在C语言中可快速完成）。
• 提前终止：一旦发现某个朋友的条件不满足，立即跳出内层循环，减少不必要的计算。

该方法利用位运算的简洁性和高效性，巧妙地将逻辑判断转换为位操作，是解决此类二进制枚举问题的经典思路。