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是否是答案即可.

package readman;

import net.egork.io.InputReader;
import net.egork.io.OutputWriter;

public class TaskC {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        String s = in.readLine();
        StringBuffer sb = new StringBuffer(s);
        for (int i = 1; i < sb.length(); i+=2){
            if (sb.charAt(i) == '1')
                sb.setCharAt(i, '0');
            else if (sb.charAt(i) == '0')
                sb.setCharAt(i, '1');
        }
        long count=0;
        int[] cc = new int[255];
       int left = 0;
       int right = 0;
       while(right < sb.length()) {
           cc[sb.charAt(right++) - '0'] ++;
           if (cc[0]  != 0 && cc[1] != 0) { // if right pointer found first '1' or '0'
               while(cc[0] != 0 && cc[1] != 0){
                   cc[sb.charAt(left++) - '0']--;
               }
           }
           count += (right  - left);
       }
       out.printLine(count);
    }
}