链接：

https://codeforces.com/problemset/problem/1535/C

题意：

给一个只含有'0','1','?'的字符串s，如果一个s的子串，每一个相邻字符均不相同，则称该子串不稳定，如果是？可以用0或1代替，问最多有多少个不稳定的连续子串。

本题，当该位字符为0，则从前面到该位可以组成的不稳定子串数为ans[i][1] = ans[i - 1][0] + 1，若为1，则是ans[i][0] = ans[i - 1][1] + 1，如果是？，取两者最大值即可。

代码如下：

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<string.h>
#include<random>
using namespace std;
typedef long long ll;
int ans[200003][2];
int main() {
	int q;
	cin >> q;
	while (q--) {
		memset(ans, 0, sizeof(ans));
		string s;
		cin >> s;
		s = " " + s;
		ll mx=0;
		for (int i = 1; i < s.size(); i++) {
			if (s[i] == '1') {
				ans[i][0] = ans[i - 1][1] + 1;
			}
			else if (s[i] == '0') {
				ans[i][1] = ans[i - 1][0] + 1;
			}
			else {
				ans[i][0] = ans[i - 1][1] + 1;
				ans[i][1] = ans[i - 1][0] + 1;
			}
			mx += max(ans[i][1], ans[i][0]);
		}
		cout << mx;
		cout << endl;
	}
	return 0;
}

最后

以上就是洁净学姐为你收集整理的codeforces 1535C Unstable String链接：题意：的全部内容，希望文章能够帮你解决codeforces 1535C Unstable String链接：题意：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。