题解：CF2068A Condorcet Elections

InterRiver · 2025-04-02 18:59:02 · 题解

因为 a_i \ne b_i 且无序对 \set{a_i, b_i} 不重复，本题一定有解。

提供两种只需要 k = 2n 个选票列表的构造方案。

第一种构造方案

第一种是我练题的时候自己想的。对某个候选人 x，令 A 为他击败的候选人集合，令 B 为不在 A 中也不等于 x 的候选人的集合，可以尝试构造两个排列，满足以下条件：

• 在两个排列中，x 都胜过 A 的所有元素。
• 综合两个排列，A, B 势均力敌。
• 综合两个排列，x, B 势均力敌。
• 综合两个排列，A 和 B 各自内部任意两个候选人势均力敌。

令 A, B 为有序集合，\mathrm{rev}(S) 代表反向的有序集合 S，下面两个排列满足上述要求：

• x, A, B
• \mathrm{rev}(B), x, \mathrm{rev}(A)

对每一个候选人 1 \le x \le n 构造两个排列，总排列数 k = 2n。

第二种构造方案

在题解评论区，benq 提供了另一种方案，与官方题解思路比较相似。

对于一个限制 (a, b)，令 S 为不等于 a 也不等于 b 的候选人的有序集合，构造两个排列：

• a, b, S
• \mathrm{rev}(S), a, b

这样就可以做到 2m 个选票列表。但是，那么大那么长的一个 S 段落可能太浪费了，假设有另外一个限制 (c, d) 且 a, b, c, d 互不相同，完全可以在 S 段中再构造出 c 对 d 的胜利。令 R 为所有不属于 \set{a, b, c, d} 的候选人的有序集合：

• a, b, c, d, R
• \mathrm{rev}(R), c, d, a, b

依此类推，若有 \lfloor \frac{n}{2} \rfloor 对限制条件，它们的元素互不相同，可以只用两个排列，一次性构造出它们。

benq 给出的分类方案是，对每个限制条件 a, b，按照 (a + b) \mod n 进行分类。同类中任何两个限制条件的元素均不相同，可以只构造两个排列满足一类中所有的条件。显然种类数最多 n 种，总排列数 k \le 2n。