链接:
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,如果是?,取两者最大值即可。
代码如下:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#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内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复