题解 NOI2026 D2T1
Mr_罗
·
·
题解
这个题蛮简单的，只是我不知道为什么不去写后面暴力狂冲 T2 正解导致比 Ag 线低了 11 分。
首先二分答案是显然的，将比二分的值大的数改为 1，小的改为 -1，我们称 [l,r] 是好区间当且仅当它有至少 \lceil\frac{r-l+1}{2}\rceil 个 1。
- 贴边：希望选出来一个最小的 $[1,l]$ 好区间（另一侧同理），随便做。
- 贴贴：设俩区间为 $[l,t),[t,r]$，枚举 $t$ 直接在线段树上二分即可。
选出来包含最少的 $1$ 的方案之后看一下剩下几个 $1$，能凑出来 $k$ 个就行。
$k$ 是奇数的情况类似，不过现在需要考虑以下几种情况：
- $[1,l],[r,n]$，直接做。
- $[1,t),[t,l]$，直接做。另一侧同理。
- $[1,L],[l,t),[t,r]$，和上面类似。另一侧同理。
- $[l,t),[t,u),[u,r]$，易知中间区间贪心取最小是不劣的（先别急，继续看下去），比较容易。
- $[l,t),[t,r],[L,T),[T,R]$，求一下 $r<L$ 中 $[l,r]$ 包含最少 $1$ 的方案即可，也很容易。
直接写可能会在样例 4 遇到一些小问题，发现是上面的情况无法处理 $10\ [1]0\ 01$ 状物导致的（在 $1$ 那里会去贪心把 $0$ 留给后面让它倒闭），所以如果枚举的中间位置是 $1$ 且下一位是 $0$ 额外看一眼即可。
写完发现 selfEval 最大点 0.95s 偷过去了，那么就做完了，时间复杂度 $\mathcal O(n\log^2 n)$。
怎么 sys 比 pre 菜，才 0.870s。
拍了一下 $k$ 是奇数的 `chk` 函数。
