题目描述
http://codeforces.com/contest/1535/problem/C
简要题意：给定一个含有 $0,1,?$ 的字符串，$?$ 可以变成 $0$ 或者 $1$，求有多少子串满足存在一种将 $?$ 替换成 $0$ 或者 $1$ 的方案，使得这个子串不存在有任何两个相邻位置的字符相同
$n\le 2\times 10^5$
Solution
首先是一个非常弱智的想法，我们令 $f[0/1]$ 表示以 $0$ 或者以 $1$ 结尾的合法区间的个数，但是这样 $?$ 是不能转移的，然后就自闭了
那么我们换一个方向来考虑，首先对于任意一个合法子串 $[l,r]$，它的子区间都是合法的，那么我们可以对于每个点记录以它结尾的最长合法区间
我们同样以 $f[0/1]$ 来表示以 $0$ 或者以 $1$ 结尾的最长合法区间的长度，然后这样 $?$ 就能转移了，而在计算答案时我们只需要加上 $max\lbrace f[0],f[1]\rbrace$ 即可
这道题让我觉得自己像一个弱智
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 200010
#define ll long long
using namespace std;
int n;
ll f[2];
char s[maxn];
void work() {
cin >> s + 1; n = strlen(s + 1); f[0] = f[1] = 0; ll ans = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == '0') f[0] = f[1] + 1, f[1] = 0;
if (s[i] == '1') f[1] = f[0] + 1, f[0] = 0;
if (s[i] == '?') {
int x = f[0], y = f[1];
f[0] = y + 1; f[1] = x + 1;
}
ans += max(f[0], f[1]);
} cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|