CF1463F Max Correct Set

Max Correct Set

考虑 \(n\) 的范围那么大， 肯定要找到神秘结论。 所以瞎考虑 \(x = y\) 的情况， 不难想到放 \(x\) 个连续的数， 再空 \(x\) 个不
放， 再放 \(x\) 个连续的。

再考虑 \(x \not= y\) 的情况， 我们猜测依旧是按循环节长度 \(x + y\) 一直放。
结论：求出 \([1, x + y]\) 范围内最大长度， 那么后面的直接复制。
证明：

必要性： 假设存在 \(i, j\) 使 \(j - i = x\)， 且 \(i, j\) 在不同的块里， 那么就有 \(i, j -x - y\) 在同一块里， 但是根据条件， 同一块不存在 \(i, j - x - y\)， 因为 \(j - x - y - i = y\)， 所以是必要条件。

充分性：如果复制第一个循环节不是最优的， 即存在某个循环节可以选出更多的数， 那我们可以直接选取那个循环节作为第一个循环节， 所以得证。