題目鏈接：點擊查看

題目大意：規定一個字符串將問號都替換成 $0$ 或 $1$ 后滿足 $01$ 交替的話，該字符串是合法的，現在給出一個長度為 $n$ 的字符串，求合法子串的個數

題目分析：兩種思路，第一種也是比賽里想到的，不太會實現細節，就是尺取每兩個合法 $01$ 段，然后對兩端連續的問號段容斥去重，個人感覺比較難寫

考慮子串就是每個前綴的所有后綴，所以枚舉點 $i$ 作為每個前綴 $s[1:i]$，找到其合法的最長的后綴所代表的左端點 $l$，使得 $[l,i]$ 這段區間是合法的，那么顯然 $[l,i]$ 這段區間內的任意點作為子串的左端點都是合法的，累加即可

不難發現上一段中提到的 $l$ 是遞增的，所以考慮如何簡單的維護

我們可以將每個位置的下標和 $01$ 串結合，不難發現，一段合法的子串，其 $i+s_i$ 的值奇偶性一定是相同的

所以我們按照其奇偶性維護一下兩種情況最后一次出現的位置就好了

代碼：

// Problem: C. Unstable String // Contest: Codeforces - Educational Codeforces Round 110 (Rated for Div. 2) // URL: https://codeforces.com/contest/1535/problem/C // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; char s[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {scanf("%s",s+1);int n=strlen(s+1);LL ans=0;int last[2]={0,0};for(int i=1;i<=n;i++) {if(s[i]!='?') {last[(i+s[i]-'0')%2]=i;}ans+=i-min(last[0],last[1]);}cout<<ans<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1535C Unstable String(思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。