注意力惊人 25寒假牛客4 BC题解

首先根据上题，我们需要发现两个结论：

1）首尾相同的字符串一定是平衡的。

2）首尾不相同的字符串一定是不平衡的。

——引用自官方题解

原题解对于做法讲的很清楚，这里仅作上述结论的证明

我们设字符串 $s$ 为

$s = s[0]s[1]...s[n-1]$

假设字符 '0' 是数字 $0$ ，字符 '1' 是数字 $1$ 。

令 $A$ 表示字符串 $s$ 中 "01" 子串出现的次数， $B$ 表示字符串 $s$ 中 "10" 子串出现的次数。

对于每个 $i\ (0 \leq i \leq n - 2)$ ，考虑差分

$d_i = s[i+1]-s[i]$

易知 ~~注意力惊人~~

对差分数组进行求和

又因为

$\sum_{i=0}^{n-2} d_i = \sum_{i=0}^{n-2} (s[i+1]-s[i]) = s[n-1]-s[0].$

整理，得

$A - B = s[n-1]-s[0]$

从而得出结论 当且仅当 $s[n-1]-s[0]=0$ 时，即 $s[0]==s[n-1]$ 时，字符串平衡。

因此字符串是否平衡只和首尾字符有关，接下来可以分情况继续讨论~