注意到通过调整可以发现最优解所染色的区间要么不相交，要么先染的严格包含后染的。因此只需要第一层满足长度不超过 $k$，之后可以任意染色，也就是若目标的对应区间有 $d$ 段（每段颜色相同），那么除掉第一次染成全部相同后，还需要 $\lfloor d/2\rfloor$ 次就能达成目标状态。然后就可以 DP 了，用单调队列优化，时间复杂度 $O(n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #303 for Problem #3286. Black or White
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:00:04
Last updated: 2025-12-14 07:00:09
题解
Comments
No comments yet.