#P10388. [2021年联测]字符串

    ID: 9506 传统题 1000ms 256MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-逆向思考奇偶性分析势能分析贡献法

[2021年联测]字符串

题目背景

你有一个空的字符串 SS,你要对 SS 做一些操作,让它变成字符串 TT,并最大化分数。

每次操作你可以:

  • 在 SS 的任意一个位置插入一个 0 或 1。
  • 然后,得到奇数位上 1 的个数的分数(比如 01101 会加 22 分,因为第 33 位和第 55 位是 1)。

你需要进行 ∣T∣|T| 次操作,让 SS 变成 TT ,并输出最大可能的分数。

输入格式

一行一个只包含 0 或 1 的字符串 TT。

输出格式

一行一个整数表示最大可能的分数。

样例输入 1
1101
样例输出 1
5
样例解释 1
  • 第 1 轮后,S=1S=\texttt{1},分数+=11,分数=11。
  • 第 2 轮后,S=11S=\texttt{11},分数+=11,分数=22。
  • 第 3 轮后,S=111S=\texttt{111},分数+=22,分数=44。
  • 第 4 轮后,S=1101S=\texttt{1101},分数+=11,分数=55。

可以证明这是最大可能的分数。

样例输入 2
0111101101
样例输出 2
26

数据范围与约定

对于所有数据,满足 1≤∣T∣≤2×1051\le |T|\le 2\times 10^5。

Subtask1(3030 分):1≤∣T∣≤51\le |T|\le 5。

Subtask2(7070 分):无特殊限制。