题解：AT_arc203_a [ARC203A] All Winners

Binah_cyc · 2025-08-06 09:30:17 · 题解

一道小清新构造。

我们先钦定某一些人最终要拿奖，发现一共有 m\times {{n\times (n-1)}\over {2}} 场对局，根据贪心，我们肯定希望每一场对局都对答案有贡献，即每一场对局都要让钦定的人胜利。那么，因为每一个人都要赢 n-1 场，所以最多有 m\times n\over 2 个人能拿奖。

下给出一种构造方案满足这个要求。

如果 m 是偶数，则每一个队伍中钦定 m\over 2 个人最终要拿奖，另外一半作为牺牲者。在两个队比赛时，让 A 队的钦定要拿奖的人去和 B 队另外一半牺牲者比赛，反之亦然。这样每一队都能有 m\over2 个人拿奖，达到理论上界。

如果 m 是奇数，则每一个队伍中先钦定 \lfloor {m\over 2}\rfloor 个人最终要拿奖，随后操纵比赛让这些人拿奖。这个时候每一队都剩下了一个人没有被考虑，这时随机钦定一个人作为冠军，就能做到 \lfloor {m\over 2} \rfloor \times n + 1 的答案。可以发现，这也是理论最大值。

代码很好写，几行就写完了，就不放了。