## 题目描述 满汉全席是中国最丰盛的宴客菜肴，有许多种不同的材料透过满族或是汉族的料理方式，呈现在数量繁多的菜色之中。由于菜色众多而繁杂，只有极少数博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成，而他们之间还细分为许多不同等级的厨师。 为了招收新进的厨师进入世界满汉全席协会，将于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在参赛的厨师之中，找到满汉界的明日之星。 大会的规则如下：每位参赛的选手可以得到 种材料，选手可以自由选择用满式或是汉式料理将材料当成菜肴。 大会的评审制度是：共有 位评审员分别把关。每一位评审员对于满汉全席有各自独特的见解，但基本见解是，要有两样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式的涮羊肉锅，就不能算是满汉全席。但避免过于有主见的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出来的状况下，才能淘汰一位选手，否则不能淘汰一位选手。 换句话说，只要参赛者能在这两种材料的做法中，其中一个符合评审的喜

以下是使用 Python 实现的解决方案： ```python # 并查集类，用于实现 2 - SAT 问题中的并查集操作 class UnionFind: def __init__(self, n): # 初始化每个元素的父节点为自身 self.parent = list(range(2 * n)) # 初始化每个集合的大小为 1 self.size = [1] * (2 * n) def find(self, x): # 查找元素 x 的根节点，并进行路径压缩 if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): # 合并元素 x 和 y 所在的集合 root_x = self.find(x) root_y = self.find(y) if root_x != root_y: if self.size[root_x] < self.size[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x self.size[root_x] += self.size[root_y] def is_same_set(self, x, y): # 判断元素 x 和 y 是否在同一个集合中 return self.find(x) == self.find(y) def solve(): t = int(input()) # 读取测试数据的组数 for _ in range(t): n, m = map(int, input().split()) # 读取材料的数量和评审员的数量 uf = UnionFind(n) for _ in range(m): # 读取每个评审员的喜好 a, b = input().split() # 解析第一个喜好的编号和类型 idx_a = int(a[1:]) - 1 type_a = 0 if a[0] == 'h' else 1 # 解析第二个喜好的编号和类型 idx_b = int(b[1:]) - 1 type_b = 0 if b[0] == 'h' else 1 # 根据 2 - SAT 问题的逻辑进行并查集的合并操作 uf.union(idx_a * 2 + (1 - type_a), idx_b * 2 + type_b) uf.union(idx_b * 2 + (1 - type_b), idx_a * 2 + type_a) can_pass = True for i in range(n): # 检查是否存在矛盾 if uf.is_same_set(i * 2, i * 2 + 1): can_pass = False break if can_pass: print("GOOD") else: print("BAD") # 调用 solve 函数解决问题 solve() ``` 代码解释： 1. 并查集类 `UnionFind`： - `__init__(self, n)`：初始化并查集，每个元素的父节点为自身，每个集合的大小为 1。 - `find(self, x)`：查找元素 `x` 的根节点，并进行路径压缩。 - `union(self, x, y)`：合并元素 `x` 和 `y` 所在的集合。 - `is_same_set(self, x, y)`：判断元素 `x` 和 `y` 是否在同一个集合中。 2. `solve` 函数： - 读取测试数据的组数 `t`。 - 对于每组测试数据，读取材料的数量 `n` 和评审员的数量 `m`。 - 对于每个评审员的喜好，根据 2 - SAT 问题的逻辑进行并查集的合并操作。 - 检查是否存在矛盾，如果存在矛盾则输出 `BAD`，否则输出 `GOOD`。 复杂度分析： - 时间复杂度：$O(t * m * \alpha(n))$，其中 $t$ 是测试数据的组数，$m$ 是评审员的数量，$n$ 是材料的数量，$\alpha(n)$ 是阿克曼函数的反函数，近似为常数。 - 空间复杂度：$O(n)$，主要用于并查集的存储。 [2025-12-13 10:47:33 | AI问答 | 954点数解答]