自动搬运

查看原文

来自洛谷，原作者为

	lndjy 退役oier，偶尔参与比赛出题，tag是我另一个身份，有人认识吗（）

搬运于2025-08-24 22:36:26，当前版本为作者最后更新于2022-02-07 07:42:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Sub 1 是爆搜，Sub 2 是想到贪心策略但是没有预处理串之间，$O(n^2)$，Sub 3 是给可能有的奇怪的数据结构做法。

可以把题目中的取的方式抽象为 $n$ 个栈，每个栈里依次有所有后缀。

但是这样串长之和就是平方级别的了，所以考虑简化：对于每个串，中间的字符的贡献我们是已经确定的，先提前算好，现在只需要最大化串和串之间的贡献，也就是只有串的开头和结尾的信息有用。这样我们就把串长之和变成线性。且串只有 00 01 10 11 四种。

下面考虑贪心策略，重复执行以下策略直到所有栈为空：

如果当前最后一位是 0，先把 00 都用上，用不了了然后用 01。如果这也没有那么就用 11，如果同时有 10 11 那么先用 11 后面还能用上 10，比直接 10 合适。

如果当前最后一位是 1，先把 11 都用上，用不了了然后用 10。如果这也没有那么就用 00，如果同时有 00 01 那么先用 00 后面还能用上 01，比直接 01 合适。

枚举第一位是 0 还是 1 即可。复杂度 $O(n)$。