存在

jijidawang · 2023-07-29 10:11:07 · 题解

因为 Kaguya 先走一步了，所以题解是我写的。

结论：构造的序列形如 1 2 2 3 2 2 4 2 2 ...。

首先序列显然满足任意子区间存在主元素，关于元素种类数最大，考虑任意长为三的子区间至少有两个数相同，那么任意长为三的区间至多有两种颜色。假如三个数分成一组，那么考察相邻的两组，如果出现了四种不同元素，那么肯定形如 a,b,b,c,d,d，可以注意到整个区间是不存在主元素的，所以任意相邻两组必然存在一种元素相同。

那么，讨论 n\bmod 3 的值：

• 如果 n\bmod 3=0，那么有 \frac n3 组，从而此时至多有 \frac n3+1 种颜色，因为最多有 \frac n3 个不同的，1 个公共的。
• 如果 n\bmod 3=1，那么有 \frac{n-1}3 组，从而此时至多有 \frac{n-1}3+2 种颜色，因为最多有 \frac{n-1}3+1 个不同的，1 个公共的。
• 如果 n\bmod 3=2，那么有 \frac{n-2}3 组，从而此时至多有 \frac{n-2}3+2 种颜色，因为最多有 \frac{n-2}3+1 个不同的，1 个公共的。

综合，可以知道最多有 \lfloor\frac{n-1}3\rfloor+2 种颜色。注意到这个构造正好取到这个界，于是构造方案就是满足元素种类数最大的了。

那么这题就做完了，时间复杂度 O(n)，可以通过。