dp写法：f[i][j]表示第i位，当前位为j，能往前找的最大的合法长度。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 200010;int f[N][2];inline void solve()
{string s;cin >> s;int n = s.size();s = ' ' + s;memset(f, 0, (2 * n + 5) * sizeof (int));for(int i = 1; i <= n; i ++){if(s[i] == '0')f[i][0] = f[i - 1][1] + 1;else if(s[i] == '1')f[i][1] = f[i - 1][0] + 1;else{f[i][1] = f[i - 1][0] + 1;f[i][0] = f[i - 1][1] + 1;}}ll ans = 0;for(int i = 1; i <= n; i ++){if(s[i] == '0')ans += f[i][0];else if(s[i] == '1')ans += f[i][1];else ans += max(f[i][0], f[i][1]);}cout << ans << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}二分写法
w[i]记录第i个位置能往前找的最大合法长度，pos数组记录每个连续问号串中第一个问号的位置。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 200010;char s[N];
int w[N];
int l = 1;
char kep;bool check(int u)
{if(u % 2 == l % 2){if(kep == '?'){kep = s[u];return true;}if(kep == s[u] || s[u] == '?')return true;return false;}else{if(kep == '?'){if(s[u] == '1')kep = '0';else if(s[u] == '0')kep = '1';return true;}if(kep == '0' && s[u] == '1')return true;if(kep == '1' && s[u] == '0')return true;if(s[u] == '?')return true;return false;}
}void solve()
{cin >> s + 1;int n = strlen(s + 1);vector<int> pos;for(int i = 1; i <= n; i ++){if(s[i] == '?' && s[i - 1] != '?'){pos.push_back(i);}}pos.push_back(2e9);l = 1;kep = s[l];for(int i = 2; i <= n; i ++){if(!check(i)){int L = 0, R = pos.size() - 1;int f = 0;if(s[i - 1] == '?')f = 1;while(L < R){int mid = L + R + 1 >> 1;if(pos[mid] < i)L = mid;else R = mid - 1;}int tmp = i;if(f && pos[L] < i)tmp = pos[L];for(int j = l; j < tmp; j ++){w[j] = i - 1;}l = tmp;kep = s[l];i = tmp;}}for(int i = l; i <= n; i ++)w[i] = n;ll ans = 0;for(int i = 1; i <= n; i ++){ans += w[i] - i + 1;}cout << ans << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}Problem - 1535C - Codeforces
