题解：P17143 [NOI 2026] 中位数（暂无数据）

MPLN · 2026-07-24 18:55:39 · 题解

猜结论题，场上想了一百万年。

首先二分答案 x，\ge x 的设置为 1，其他设置成 -1。

问题变为划分为 k 段，其中 \ge \lceil\frac{m}{2}\rceil 段的和 \ge 0。

啥也看不出来，写个暴力 dp 找规律，我们用 g_i=0/1 表示 k=i 能否做到。

发现 i\le 5 的时候没什么规律，i\ge 6 时满足：找到最大的 j 使得 g_j=1，则 [6,j] 内所有偶数 i 均有 g_i=1，所有奇数 i 有 g_i 都为 0 或都为 1。

则问题分为两部分，求出最大可行段数，以及求出较小的若干 i\le B 的 g_i。

后者写暴力 dp 即可做到 O(nB^2)，设一维段数、一维和 \ge 0 的段数。

对于前者，显然每个 1 最多处于一段内，否则不优。则若开头为 (-1)1 可作为一段，结尾为 1(-1) 可作为一段，中间 1(-1)(-1)1 可作为左右两段，其余 1 单独成段，连续 (-1) 成段，判定是否合法即可（不合法则无可行方案）。

时间复杂度 O(n\operatorname{log}nB^2)，赛时取了 B=7，常数比较大。