P16834 【MX-X29-T5】『FeOI-6』Nako 和众数最小（简单版） 题解

zrl123456 · 2026-06-09 17:50:42 · 题解

:::::info[闲话] 没有人类了。 ::::: :::::success[Hint 1] 考虑答案下界，通过打表等方式猜测不同 n 时的答案大小。 ::::: :::::success[Hint 2] 考虑 n 是偶数的情况，通过打表同样可以得到构造方案。 ::::: :::::success[Hint 3] 考虑 n 是奇数的情况，考虑倒序字典序最大的序列，当出现格格不入的情况时大胆忽略。 ::::: :::::success[Hint 4] 考虑 n\equiv 7\pmod 8，继续考虑倒序字典序最大的序列。 :::::

对应 Hint 1：

我们观察答案下界，由于一共有 \frac{n(n+1)}{2} 个区间，容易发现答案下界为 \lceil\frac{n(n+1)}{4}\rceil。

我们考虑通过使用 \Theta(2^n\text{poly}(n)) 的做法打表观察不同较小 n 的的具体答案，我们通过打表发现当 n\le 24 时只有 n=7 答案比 \lceil\frac{n(n+1)}{4}\rceil 大一，其它 n 答案都等于这个值，我们大胆猜测其余的 n 的答案都可以取到这个值，下文我们将通过构造证明这一点。

对应 Hint 2：

我们注意到部分分中对 n\bmod 8 进行了详尽的分讨，我们不妨对 n\bmod 8 分别考虑，同时我们注意到部分分中有一档全是偶数的部分分，我们考虑 n 是偶数的情况。

我们不妨再次打表观察，我们发现 n=2 时的唯二解是 [0,1] 和 [1,0]，n=4 时的唯一解是 [0,1,1,0]，n=6 时唯三解中存在两解分别为 [0,1,0,1,1,0] 和 [0,1,1,0,1,0]，我们猜测对于任意 n 是偶数存在形式为 \lfloor\frac n4\rfloor 个 [0,1] 和 \lceil\frac n4\rceil 个 [1,0] 拼接而形成的解，具体验证只需要暴力计算一下即可。

更加具体地，我们将 0 视为 -1，1 视为 +1，要求区间和非正，也就是问前缀和有多少非严格的逆序对。由于我们的前缀和形如 -1,0,-1,0,\cdots,-1,0,1,0,1,0,\cdots,1,0 那么逆序对数量我们是比较好算的。

更加具体地：

• 对于所有的 -1，我们发现和它配对的只能是后面的 -1，总配对数为 \frac{\lfloor\frac n4\rfloor(\lfloor\frac n4\rfloor+1)}{2}。
• 对于所有的 0，我们发现和它匹配的只能是后面的 0 或者 -1，总配对数为 \frac{\frac n2(\frac n2+1)}{2}+\frac{\lfloor\frac n4\rfloor(\lfloor\frac n4\rfloor-1)}{2}。
• 对于所有的 1，我们发现它能和后面任意一个字符配对，总配对数为 \frac{\lceil\frac n4\rceil(2\lceil\frac n4\rceil-1)}{2}。

加和后容易证明构造是正确的。

对应 Hint 3：

我们考虑继续打表观察，我们发现 n=3 时唯一解是 [1,0,1]，n=5 的两个解一个是 [0,1,0,1,1] 一个是 [1,1,0,1,0]，n=7 时的最优解就比较多了，但是我们暴力枚举出的最优解中倒序字典序最大（正序也一样，反正如果你的暴力是写得比较正常那么大概率就是第一个或者最后一个）的解为 [0,0,1,0,1,1,1]，n=9 的这个是 [0,0,0,1,0,0,1,1,1,1,1]，看上去非常有规律，我们可以总结一下递推规律：

根据上面的递推规律，我们可以得出更加一般的规律（令 p=\lfloor\frac n8\rfloor）：