题目链接:https://codeforces.com/contest/1535/problem/C
——题目描述:给你一个0,1,?组成的串,在访问每一个子串时,?可以当作0或1。?并不是固定的0或固定的1,可以随子串不同而变化。问有多少个0101交替的子串。
——思路:0,01,010都算作0101交替的子串,如果一个01子串的最大长度为n,那么就会有n+n(n-1)/2个01串,那我们就可以从头开始遍历,找出一个最大的01串并算出他的长度,再往下找01串,重复这样的操作,但有这种情况存在:0101??1,我们从头开始找01串发现找到最长01串0101??,再算出结果后,再找下一个01串,我们发现下一个最长的01串不是1而是由??1组成的101,算出答案后再减去重复的由??组成的01串即可,即长度为6的答案减去长度为2的答案再加上长度为3的答案。由于01串只有两种状态,可以用这两种状态去判断当前是否在维持01的状态

code

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl "\n"
#define int long long
signed main() {
    ios;
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int num = 0, sum = 0, zt = 2, w = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') {
                num++;
                w++;
            } else if (s[i] == '1') {
                if ((zt == 1 || zt == 2) && i % 2 == 1)
                    num++;
                else if ((zt == 0 || zt == 2) && i % 2 == 0)
                    num++;
                else {
                    sum += (num + num * (num - 1) / 2),
                        num = w + 1, sum -= (w + w * (w - 1) / 2), w = 0;
                    if (zt == 1)
                        zt = 0;
                    else
                        zt = 1;
                }
                if (i % 2 == 1)
                    zt = 1;
                else
                    zt = 0;
                w = 0;
            } else {
                if ((zt == 1 || zt == 2) && i % 2 == 0)
                    num++;
                else if ((zt == 0 || zt == 2) && i % 2 == 1)
                    num++;
                else {
                    sum += (num + num * (num - 1) / 2),
                        num = w + 1, sum -= (w + w * (w - 1) / 2), w = 0;
                    if (zt == 1)
                        zt = 0;
                    else
                        zt = 1;
                }
                if (i % 2 == 1)
                    zt = 0;
                else
                    zt = 1;
                w = 0;
            }
        }
        sum += (num + num * (num - 1) / 2);
        cout << sum << endl;
    }
}