Codeforces Round 920 (Div. 3)

BrotherCall · 2024-01-25 15:53:23 · 个人记录

赛时过了 A~E ，表现分 1738 。

感觉 D~G 都挺有意义拿出来说的。

[D] Very Different Array

首先一个贪心的猜想是：如果 A 和 B 长度相同，那一个顺序一个逆序应该是最优的情况。

思考下如何证明这个猜想。

假如 A 和 B 的长度均为 2 ，易证 A_1 < A_2 ，B_1 > B_2 时最优。

把这个结论推广到长度为 n ，那么对于每一个 A 和 B 均顺序的数对，都可通过使 B 逆序的方式得到更大的答案。这样就证完了。

本题就是一个 B 的长度为 m ，比 A 长的情型。

那么还是考虑把 B 倒着放，然后 B 的前 k 个和 A 的前 k 个配对，后 (n - k) 个和 A 的后 (n - k) 个配对即可得到答案。枚举 k 即可。

[E] Eat the Chip

首先发现 A 和 B 谁有机会赢只与 x_A - x_B 的奇偶性有关。

然后 x_A - x_B 不超过 10^6 ，那么一步步模拟没机会赢的人往离另一个人更远的地方跑，有机会赢的人追赶即可。

[F] Sum of Progression

赛场上一眼看出了根号分治但由于滥用 map 而导致卡不过去。

做法就是 d 大于 \sqrt{n} 时暴力跳，每次跳复杂度 \sqrt{n}。