codeforces #334 div 2 C. Alternative Thinking

2015年12月2日 0 作者 CrazyKK

题意:给定一个01串。要进行一次变换:选一段连续的非空的字串,将这段串的0和1反转(0变成1,1变成0)
然后问能得到的最长的0,1交替的序列的长度是多少(不一定连续)

比赛的时候想出来两种会将答案增加的可能情况。一种是10000001 中间有大于等于3个的连续字符,这样可以把中间反转一下,答案会+2 另外一种是 1001001 这样。。有至少两段的连续两个以上的相同字符被另一个字符隔开的情况。只要将1001001变成1010101。答案还是会+2。。。然后发现这两种情况实际上可以统一起来。即:有至少两段的连续相同字符。
注意000 也算有两段。 如果有两段或者以上,那么答案+2.