题解：AT_arc219_a [ARC219A] Similarity

Jason20090916 · 2026-05-11 16:53:18 · 题解

题意

给定 N 个长为 M 的 01 字符串，记为 S_1, S_2, \dots, S_n。要求你构建一个 01 字符串 T，使其和每个 S_i 都至少有一位相同，并问 T 能否构建出来。

思路

考虑构建一个字典树，在 u 点选择 0/1 即将 u 的 0/1 子树剪掉（子树内的 S_i 因为我们选了 0/1 而满足了至少有一位相同的条件），贪心地选择子树中包括更多字符串的那个，然后继续递归另一子树即可。
如果已经递归了 M 层，且我们所在节点非空，那么 T 不可能存在。
否则输出递归的路径并随意填写缺少的部分。
如此贪心，在每一层我们至少可以消除一半的字符串，则最多 \log{n} 次递归就能找到答案。