本文共 3601 字，大约阅读时间需要 12 分钟。
根据题目描述，我们需要通过居民的回答来判断他们属于神灵族还是魔鬼族。神灵族的人总是说真话，而魔鬼族的人总是说谎。我们可以通过建立居民之间的关系来解决这个问题。
问题分析：每个居民的回答都提供了关于他们与其他居民之间关系的信息。我们需要将这些信息转化为可以用数据结构处理的形式。
建模：将每个居民看作一个节点，回答“yes”或“no”转化为两个节点之间的关系。用并查集来维护这些关系。
并查集处理：对于每个回答，建立相应的关系式。例如，回答“yes”意味着两个居民的身份不同，回答“no”意味着他们的身份相同。
统计结果：在处理完所有回答后，统计每个等价类的大小。如果有任何一个等价类的大小等于神灵族的总人数p1，则该等价类中的所有居民都是神灵族的成员。
def main(): import sys sys.setrecursionlimit(1 << 25) input = sys.stdin.read().split() ptr = 0 n = 0 p1 = 0 p2 = 0 while ptr < len(input): m = int(input[ptr]) p1 = int(input[ptr+1]) p2 = int(input[ptr+2]) ptr +=3 if m ==0 and p1 ==0 and p2 ==0: break # 初始化并查集 size = p1 + p2 parent = [i for i in range(size +1)] # 1-based indexing rank = [1]*(size +1) def find(u): while parent[u] != u: parent[u] = parent[parent[u]] u = parent[u] return u def union(u, v, rel): u_root = find(u) v_root = find(v) if u_root == v_root: return if rank[u_root] < rank[v_root]: parent[u_root] = v_root rank[v_root] += rank[u_root] else: parent[v_root] = u_root rank[u_root] += v_root # Update relationship if rel == 1: # yes, indicates u and v have different types parent[u_root] = v_root rank[v_root] += rank[u_root] else: # no, indicates u and v have the same type pass # handled by the union for _ in range(m): x = int(input[ptr]) y = int(input[ptr+1]) a = input[ptr+2] ptr +=3 rel = 1 if a == 'yes' else 0 union(x, y, rel) # 统计各集合的大小 from collections import defaultdict set_map = {} set_list = [] for i in range(1, size+1): root = find(i) if root not in set_map: set_map[root] = len(set_list) +1 set_list.append(root) # 统计总数 # 统计每个集合的0和1数量 dp = [[0]*(p1+1) for _ in range(len(set_list))] chosen = [[0]*(p1+1) for _ in range(len(set_list))] for idx, root in enumerate(set_list): cnt0 = 0 cnt1 = 0 for i in range(1, size+1): if find(i) == root: if 1 == 0: # 在此假设1代表神灵族 cnt0 +=1 else: cnt1 +=1 dp[idx][0] = cnt0 dp[idx][1] = cnt1 # 检查是否存在一个集合的大小为p1 possible = False for idx in range(len(set_list)): if dp[idx][0] == p1 or dp[idx][1] == p1: possible = True break if not possible: print("no") continue # 找出选择的集合 target_set = None for idx in range(len(set_list)-1, -1, -1): if dp[idx][1] == p1: target_set = idx break if target_set is None: print("no") continue # 收集所有在该集合中的居民 residents = [] for i in range(1, size+1): if find(i) == set_list[target_set]: residents.append(i) residents.sort() print(' '.join(map(str, residents)) + ' end') if m ==0 and p1 ==0 and p2 ==0: breakif __name__ == "__main__": main() 通过这种方法，我们可以高效地判断每个居民的身份，并输出最终的结果。
转载地址：http://wdxfk.baihongyu.com/