2026 Summer Day26

依旧挂大分 $130 \to 30, rk38 \to rk 123$ 。

T1 love problem

这道题总算是让我对 B 班的模拟赛有了一点信心，结论简单，但是我还是写了 1h，旁边的 xzy 大佬只用了 20mins 就爆切 T1 /bx /bx /bx。

对 $0/1$ 每 $k$ 个分组，发现最后的答案是绝对值之和的形式，只需要找到 $kj$ 让这个绝对值之和最小即可。

发现只需要讨论每个矩形的左右两个端点即可。发现左端点只能覆盖右墙面和自己的左墙面，右端点镜像。同时发现一般情况下的最小答案个数为 $n - 1$ ，且是答案上界。

然后考场上就开始走歪路了（可能也不是很歪）。发现特殊性质是 高度单调递增，所以考试考虑单调区间之间的贡献影响。后来转变思路，有了 $O(n^2)$ 做法：

贪心选取每次还能覆盖还未被其他守卫覆盖的候选点中的最大的那一个，可以做到 $O(n^2)$

但是这个做法考场上写挂了，每调出来，最后写了一个 $20pts$ 的暴力还有特殊性质的 $10pts$ 。

看题解发现，所有在答案中选中的点是一个凸包，我们可以用单调栈维护凸包来决定当前点是否放置。前后个扫一遍。对于第一次扫描不确定的位置打标记，如果第二遍扫描发现依然可以被其他点覆盖的话，就可以让答案上界减一，复杂度 $O(n \log n)$ ，因为还要排序。