专栏文章

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

LLeNotFound
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqbdsp9
此快照首次捕获于
2025/12/04 02:02
3 个月前
此快照最后确认于
2025/12/04 02:02
3 个月前
查看原文
首先根据上题，我们需要发现两个结论：
1） 首尾相同的字符串一定是平衡的。
2） 首尾不相同的字符串一定是不平衡的。
——引用自 官方题解
原题解对于做法讲的很清楚，这里仅作上述结论的证明
我们设字符串 ss 为
s=s[0]s[1]...s[n−1]s = s[0]s[1]...s[n-1]
假设字符 '0' 是数字 00，字符 '1' 是数字 11。
令 AA 表示字符串 ss 中 "01" 子串出现的次数，BB 表示字符串 ss 中 "10" 子串出现的次数。
对于每个 i (0≤i≤n−2)i\ (0 \leq i \leq n - 2)，考虑差分
di=s[i+1]−s[i]d_i = s[i+1]-s[i]
易知 注意力惊人
  • s[i]=0s[i] = 0 且 s[i+1]=1s[i+1] = 1 时，di=1d_i = 1
  • s[i]=1s[i] = 1 且 s[i+1]=0s[i+1] = 0 时，di=−1d_i = -1
对差分数组进行求和
又因为
∑i=0n−2di=∑i=0n−2(s[i+1]−s[i])=s[n−1]−s[0].\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]A - B = s[n-1]-s[0]
从而得出结论 当且仅当 s[n−1]−s[0]=0s[n-1]-s[0]=0 时，即 s[0]==s[n−1]s[0]==s[n-1] 时，字符串平衡。
因此字符串是否平衡只和首尾字符有关，接下来可以分情况继续讨论~

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...