[eJOI2025] Collecting Diamonds 题解

FFTotoro · 2025-09-26 11:22:02 · 题解

有一个贪心策略：每一步都走当前能走的权值最大的边。根据题意这个策略是正确的，但是有些时候可能有多条这样的边。于是尝试维护第 i 步之后可能成为答案的结点集合（初始时为 \{0,1,\ldots,N-1\}，因为可以选择任意的起点）。

考察路径的形态，显然为一条链 + 一个环。感性理解：后面如果走过了一个环并且这个环是最优的，换一个环走必然不会更优。

考虑至少需要维护多少步的点集，才可以确定正确的路径。引理：如果两个无限数列 a,b 满足 a 的周期为 p，b 的周期为 q，若 a,b 的前 p+q 项相等，那么 a 与 b 相等。联想到这题，前面的链长最多为 n，环长最多为 n，所以需要维护 n+2n=3n 步。但事实上只需要维护 2n 步，因为链和环是不交的（相交必然不优）。

使用 bitset 维护每一步可能的点集，时间复杂度 O(NM)，空间复杂度 O\left(M+\frac{N^2}{w}\right)。

本题空间限制仅有 4\mathrm{MB}，代码因为卡空间，可读性比较差就不放了。实现时注意一下空间问题就行。