CF1893D Colorful Constructive 题解

· · 题解

这场给我干傻了，1B 1C 写了一百年根本没时间看 1D，结果 1D 是纯 sbt（可以放 1B）。

考虑对于一个大小为 s 的架子，其限制为 k，什么情况下能满足要求。不难发现，必要条件是从左往右分成长为 k 的若干段和长为 s\bmod k 的余下一段（如果 s\bmod k\neq 0 的话）中段内部不能有相同颜色，这是非常显然的。但是仔细想想会发现这也是充分条件。

Proof：

不妨把余下那段移到最左边。这段随便放。然后从第 2 段开始的第 i 段，把其中出现过的数字按在第 i-1 段中的出现位置（没出现过就是看作 -1）从小到大排序，再放到第 i 段中。这样一来对于所有同时出现在第 i-1 段和第 i 段中的数字 x，其在第一段的出现位置一定比第二段更靠前，也就是他们的距离 \geq k。

那么就可以放心地拆架子了。将所有拆出来的段从长到短排序，对于长为 l 的段，若当前可选的不同的 a_i 少于 l 种，则答案不存在；否则取出当前出现次数最多的 l 种 a_i，扔到段里就行。这是经典的贪心策略。可以用 std::priority_queue 维护贪心过程。

时间复杂度线性对数。

for reference only.