Menu Sidebar
Menu

Archive: June 6, 2021

Educational Codeforces Round 110 (Rated for Div. 2)C. Unstable String

给一个字符串, 里面有0,1和?, ?可以是1或者0, 求这个字符串的子字符串中可以变成1和0 交替出现的字符串的个数. 这题就是counting问题, 做的时候用的dp, 想了半天都有错, 后来想想, ?基本没啥用的地方, 因为0和1交替出现的字符串就两种, 一种是0101或者1010…所以如果我们强制替换奇数位上的1变成0, 0变成1, 那么如果是以上两种, 就会变成0000或者1111, 所以我们只需要用两个指针count一下每个substring是否是答案即可.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.