原题链接：Problem - 1535C - Codeforces
题目大意：
有t 组询问，每次给定一个仅包含字符 1 或 0 或 ？的字符串 s ss。定义一个子串是不稳定的当且仅当子串中任意相邻两数均不相同，如 101010…101010… 或 010101…010101…。其中 ? 可以变为 1 或 0 其中一种。请求出给定的 s ss 中最多可以有的不稳定子串个数。
注意：
1.？？是一个符合的子串而不是两个，因为它有情况可以满足beautiful串（01/10），但是并不是算2个，只是算一个。
2.每轮不要忘记置0！！dp[][]要置0！！
#includeusing namespace std;#define INF 0x3f3f3f3ftypedef pair PII;const double pi = acos(-1.0);#define rep(i, n) for (int i = 1; i <= (n); ++i)#define rrep(i, n) for (int i = n; i >= (1); --i)typedef long long ll;#define sqar(x) ((x)*(x))const int N = 2e5 + 10;int dp[N][2]; //一维坐标为字符串中每个数的坐标，表示以s[i]为右端点子串数目int main(){ int t; string s; cin >> t; while(t--){ memset(dp, 0, sizeof dp); //记得置0 cin >> s; int n = s.length(); s = " " + s; ll res = 0; rep(i, n){ if(s[i] == '0') dp[i][0] = dp[i - 1][1] + 1; else if(s[i] == '1') dp[i][1] = dp[i - 1][0] + 1; else{ dp[i][0] = dp[i - 1][1] + 1; dp[i][1] = dp[i - 1][0] + 1; } res += max(dp[i][0], dp[i][1]); //其实如果？前面是0，那么其实它最后肯定是取[0]的那个大 } //？不是固定的，它在不同子串里可以代表不同的角色（0.1） //所以我们可以判定??是一个子串，而不是判定??为01/10两个子串 //这也就是我们取max而不是取sum的原因 printf("%lldn", res); } return 0;}