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

LeNotFound · 2025-02-07 18:49:15 · 个人记录

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

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

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

——引用自 官方题解

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

我们设字符串 s 为

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

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

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

易知 注意力惊人

• s[i] = 0$ 且 $s[i+1] = 1$ 时，$d_i = 1
• s[i] = 1$ 且 $s[i+1] = 0$ 时，$d_i = -1

对差分数组进行求和

又因为

整理，得

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

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