专栏文章

题解：CF2068A Condorcet Elections

IInterRiver
CF2068A题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipqh8hu
此快照首次捕获于
2025/12/03 16:17
3 个月前
此快照最后确认于
2025/12/03 16:17
3 个月前
查看原文
因为 ai≠bia_i \ne b_i 且无序对 { ai,bi }\set{a_i, b_i} 不重复，本题一定有解。
提供两种只需要 k=2nk = 2n 个选票列表的构造方案。

第一种构造方案

第一种是我练题的时候自己想的。对某个候选人 xx，令 AA 为他击败的候选人集合，令 BB 为不在 AA 中也不等于 xx 的候选人的集合，可以尝试构造两个排列，满足以下条件：
  • 在两个排列中，xx 都胜过 AA 的所有元素。
  • 综合两个排列，A,BA, B 势均力敌。
  • 综合两个排列，x,Bx, B 势均力敌。
  • 综合两个排列，AA 和 BB 各自内部任意两个候选人势均力敌。
令 A,BA, B 为有序集合，rev(S)\mathrm{rev}(S) 代表反向的有序集合 SS，下面两个排列满足上述要求：
  • x,A,Bx, A, B
  • rev(B),x,rev(A)\mathrm{rev}(B), x, \mathrm{rev}(A)
对每一个候选人 1≤x≤n1 \le x \le n 构造两个排列，总排列数 k=2nk = 2n。

第二种构造方案

在题解评论区，benq 提供了另一种方案，与官方题解思路比较相似。
对于一个限制 (a,b)(a, b)，令 SS 为不等于 aa 也不等于 bb 的候选人的有序集合，构造两个排列：
  • a,b,Sa, b, S
  • rev(S),a,b\mathrm{rev}(S), a, b
这样就可以做到 2m2m 个选票列表。但是，那么大那么长的一个 SS 段落可能太浪费了，假设有另外一个限制 (c,d)(c, d) 且 a,b,c,da, b, c, d 互不相同，完全可以在 SS 段中再构造出 cc 对 dd 的胜利。令 RR 为所有不属于 { a,b,c,d }\set{a, b, c, d} 的候选人的有序集合：
  • a,b,c,d,Ra, b, c, d, R
  • rev(R),c,d,a,b\mathrm{rev}(R), c, d, a, b
依此类推，若有 ⌊n2⌋\lfloor \frac{n}{2} \rfloor 对限制条件，它们的元素互不相同，可以只用两个排列，一次性构造出它们。
benq 给出的分类方案是，对每个限制条件 a,ba, b，按照 (a+b)mod  n(a + b) \mod n 进行分类。同类中任何两个限制条件的元素均不相同，可以只构造两个排列满足一类中所有的条件。显然种类数最多 nn 种，总排列数 k≤2nk \le 2n。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...