C. Unstable String

大体上这题 思路可以陈述为 求给定这种字符串的数量
因此 拆分这个连续字符串到 每一个位置上 并进行Dp 因为每一个位置上的 字符的情况就几种 从前往后递推即可

• 首先$Dp[i][0]$表述为前i个字符中最后一个以字符是以0结尾的字符串 所能包含的 Beautiful串的数量
• 因此$Dp[i][0]=Dp[i-1][1]+1$ 注意当且仅当此时 $S[i]$位置上的字符是?或则和是0的时候才 说明这个字符串是存在的
• 同理 ：$Dp[i][1]=Dp[i-1][1]+1$

AC代码：

/*
当你觉得自己不行的时候 你就走到斑马线上 这样你就会成为一个行人
没关系 大不了我们大器晚成而已
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int dp[N][2];
char s[N];
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)
       {
           cin>>s+1;
           int n=strlen(s+1);
           memset(dp,0,sizeof dp);
           LL res=0;
           for(int i=1;i<=n;i++)
           {
                   if(s[i]=='0'||s[i]=='?')dp[i][0]=dp[i-1][1]+1;
                   if(s[i]=='1'||s[i]=='?')dp[i][1]=dp[i-1][0]+1;
                   res+=max(dp[i][0],dp[i][1]);
           }
           cout<<res<<endl;
       } 
        return 0;
}