02-08 18:21 北京印刷学院 C++ 发布于北京

关注

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

Tokitsukaze and Balance String (hard)

https://ac.nowcoder.com/acm/contest/95336/C

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

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]$

易知 ~~注意力惊人~~

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

对差分数组进行求和

又因为

$\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]$ 时，字符串平衡。

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

全部评论

推荐最新楼层

MoonLe

河北工程大学 Java

很好的证明👍

点赞回复分享

发布于 02-10 15:09 河北

07-24 19:44

苏州大学集成电路IC设计

强行上台

不知道大家是否还记得性教育这么通识课程，一个大教室里面几百个人，我当时是听说这门课很水，绩点比较高，报的这门课，谁知道最后有个男女混合上台做活动，几百上千个人里面，竟然抽中了我，直接让微内的我裂开，玩的活动还非常尴尬，前人搭着后人跳兔子舞，能想象吗，在几百人面前的台子上，就老师在那指挥，下面全是沉默，给点反应互动也不至于这么尴尬，大学反正都管自己玩游戏，谁还真上课啊。

校园里的破防时刻

点赞评论收藏

07-24 16:16

西安电子科技大学 Java

面试造火箭：MySQL自增ID用完了怎么办？

大家好，我是大都督周瑜，最近一位同学遇到了这样一道面试题：MySQL自增ID用完了怎么办？这道面试题其实也是一道面试造火箭的面试题，如果ID字段是INT类型，那么最大值约为21亿，如果ID字段是BIGINT类型，最大值则可以达到约为9亿亿，因此只有在数据量特别大的情况下才需要考虑自增ID用完之后怎么办，不过为了大家能拿到心仪的offer，我这里提供以下几种方案。切换到BIGINT如果当前字段类型是INT类型，通过修改字段类型，将INT类型升级为BIGINT类型，从而可以大幅提高自增ID的上限。不过要注意，在已有大量数据的表上进行字段类型修改的操作可能会影响性能，建议使用在线修改工具如pt-on...

牛客创作赏金赛

点赞评论收藏

06-20 18:18

中国农业大学前端工程师

逆天岗位😓

allin秋招的单身...：我投过这家上来就发个设计图给我，让我做好发到他邮箱

点赞评论收藏

07-13 18:34

来offer来oc：快进到offer打牌

点赞评论收藏

不愿透露姓名的神秘牛友

07-22 17:34

百度提前批

百度提前批二面已完，HR面已约，我会不会是第一个拿下熊厂offer的人呢？

百度HR面16人在聊

点赞评论收藏

全站热榜

创作者周榜

正在热议

# 机械人，你被简历秒挂的企业有哪些？ #

# 机械人，秋招第一次笔试的企业是哪家？ #