题目内容

对于一个字符串，小美每次操作可以:添加或者删除一个 $0$ 字符或者 $1$ 。

她定义一个字符串 $t$ 的权值为:

满足任意次交换两个相邻字符的前提下使得任意相邻的两个字符都不相等的最少操作次数。

题解

给定一个长度为 $n$ 的二进制字符串 $s$ （仅包含字符 '0' 和 '1'），我们可以对任意子串执行以下操作：每次添加或删除一个字符 '0' 或者字符 '1'。现在要求我们求出所有非空子串的"权值"之和。

一个子串 $t$ 的权值定义为：通过任意次数交换相邻字符的前提下，确保任意相邻的字符都不相等的最少操作次数。换句话说，最小的操作次数就是将该子串变为一个 "交替字符串"（例如 '010101' 或 '101010'）所需的操作。