专栏文章

题解：T561109 【MX-X7-T2】[LSOT-3] 姬誉蛙

2025/01/11 16:32题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论: 0 条
当前快照: 1 份
快照标识符: @miqjj25d
此快照首次捕获于: 2025/12/04 05:50
此快照最后确认于: 2025/12/04 05:50

二分答案竟然只有入门难度？！

做法

先审题

这 $k$ 个子串的最大权值最小可以是多少。

~~明显的二分答案~~

二分最大权值最小可以是多少（显然）。check 函数的写法应该有两种，如下：

每次 check $O(n)$ 枚举，当 $0$ 的个数乘上 $1$ 的个数大于二分的答案就新开一段（划分一次），最后判断划分次数是否可行即可
先跑一遍前缀和，但每次 check 仍有 $O(n)$ 的复杂度，并没有什么大用还增加写代码的难度……

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...