题解：CF2075B Array Recoloring

· · 题解

适合入门者看的，大佬请速通。

首先，我们知道拿了 k 个过后就是一个一个的拿，可以发现其实 1 和 n 并不相邻。

先考虑很容易想到的结论：答案是最大的 k+1 个。现在需要证明它的正确性。证明：我们先将这最大的 k+1 个在数组 a 中找出。只要我们取到最左边的和最右边的，中间的随便取 k-2 个，我们一定能通过一个个染色使得最后一个，即在第一轮取 k 个时没取到的是最后一个染色的。

还没懂？我们设这个没取到的为 i，显然它夹在第一轮取得的数的中间。设它夹在位置 x 和 y 间，显然我们可以通过染色挨个挨个从 x 向右染到位置 i-1，不染 i，接着从 y 向左染到位置 i+1，然后考虑这个连续子序列外的红色，显然可以都染成蓝色，最后在把位置 i 染成蓝色并计入它的贡献。

还是没懂？考虑用我们这种方法取点，一定能保证我们的可染色的点集始终大小 >1，所以就算我们需要的那个点在可染色的点集中，我们也一定可以选择其他点进行染色，保证我们需要的那个点是在最后染的。

你以为做完啦？我们又发现 k 的范围是 1 \leq k < n，不难发现这个证明只适合当 k \geq 2 的时候适用，所以我们还需分类讨论当 k=1 的情况。

结论：我们会计入两个点的贡献，其中一个要么是第 1 个要么就是第 n 个，另一个随便。证明：第一个可以随便乱取，第二个只能取边界，即第 1 个或者是第 n 个，不然的话，我们无法绕过取的第二个点到另一边，这是显而易见的。

最终这道题就可以愉快的切掉啦！

AC code。