題目鏈接：Problem - B - Codeforces

樣例輸入：

5 1 1 2 01 3 100 4 1001 5 11111

?樣例輸出：

1 3 4 8 5

題意：多組測試，每次給定一個n，代表字符串的長度，然后給定一個長度為n的字符串，字符串中的每個字符為0或者1，我們可以對一個字符串進行操作，每次可以把01變成1或者把10變成0，然后問我們在這個字符串中有多少個子串可以經(jīng)過若干次操作變?yōu)橐粋€數(shù)。

舉個例子比如100，首先1，0，0三個單獨可以作為一個子串，其次100整體可以作為一個子串，因為100->10->0,所以對于100共有4個子串可以經(jīng)過若干次操作變?yōu)橐粋€數(shù)，而對于1001的話就有

1，0，0，1，10，01，001，1001這8個子串滿足題意

這個題有兩種做法，先來說一下比較簡單的做法：

假如第i個數(shù)字與第i-1個數(shù)字不同，那么我們直接把答案+i就行，因為以第i個數(shù)字結(jié)尾向前擴展任意長度的子串都是滿足題意的，為什么會這樣呢？給大家舉個例子大家應該就明白了：

比如序列是xxxxxxxxxxxx01,我們可以通過若干次操作把前面的x全部變成0，因為假如前面是0那就不用操作，如果前面是1，那我們可以用倒數(shù)第二個數(shù)0和前面的數(shù)組成10然后合成0重復這樣的操作就可以使得所有的x變?yōu)?，那么就成為了00……01的這種形式,然后就可以直接合并成1

同理假如序列是xxxxxxxxxxxx10,我們可以通過若干次操作把前面的x全部變成1，因為假如前面是1那就不用操作，如果前面是0，那我們可以用倒數(shù)第二個數(shù)1和前面的數(shù)組成01然后合成1重復這樣的操作就可以使得所有的x變?yōu)?，那么就成為了11……10的這種形式,然后就可以直接合并成0

如果要是當前位和上一位是相同的，因為01->1,10->0所以我們無論怎樣操作最后都無法消成一個數(shù)，所以只需要把答案+1即可，因為只有把當前這一個字符作為子串才是滿足題意的。

代碼實現(xiàn)很簡單，注意ans開long long：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<cmath> using namespace std; const int N=2e5+10; char s[N]; int main() {int T;scanf("%d",&T);while(T--){int n;scanf("%d%s",&n,s+1);long long ans=1;for(int i=2;i<=n;i++){if((s[i]-'0')^(s[i-1]-'0')) ans+=i;else ans+=1;}printf("%lld\n",ans);}return 0; }

下面來說一種動態(tài)規(guī)劃的解決方法，因為一開始沒有想到上面的解法，就用動態(tài)規(guī)劃求解的。

設:

f[i][0]代表以第i個數(shù)結(jié)尾形成一個0的子串數(shù)目

f[i][1]代表以第i個數(shù)結(jié)尾形成一個1的子串數(shù)目

f[i][2]代表以第i個數(shù)結(jié)尾形成連續(xù)兩個及以上0的子串數(shù)目

f[i][3]代表以第i個數(shù)結(jié)尾形成連續(xù)兩個及以上1的子串數(shù)目

知道了狀態(tài)表示，狀態(tài)轉(zhuǎn)移方程就比較容易推導了，下面是分析思路：

假如當前位是0，那么一定有f[i][1]=f[i][3]=0,當前位為0就代表著以當前位作為結(jié)尾形成的子串的末尾一定不可能是1，那么f[i][0]=1+f[i-1][1]+f[i-1][3]就是前面的1個1或者若干個1加上當前位的0組成一個0，f[i][2]=f[i-1][2]+f[i-1][0]，當前的若干個0是由前i-1位中的若干個0或者1個0來組成。

同理，假如當前位是1，那么一定有f[i][0]=f[i][2]=0,當前位為1就代表著以當前位作為結(jié)尾形成的子串的末尾一定不可能是0，那么f[i][1]=1+f[i-1][0]+f[i-1][2]就是前面的1個0或者若干個0加上當前位的1組成一個1，f[i][3]=f[i-1][3]+f[i-1][1]，當前的若干個1是由前i-1位中的若干個1或者1個1來組成。

分析到這，狀態(tài)轉(zhuǎn)移方程就推導出來了，結(jié)果就是每一位字符作為結(jié)尾的子串經(jīng)過操作后能夠形成一個數(shù)的數(shù)目和。

下面是代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<cmath> using namespace std; const int N=3e5+10; char s[N]; int f[N][4];//f[i][0/1/2/3]代表以第i個數(shù)結(jié)尾形成一個0/1/0……0/1……1的方案數(shù) int main() {int T;cin>>T;while(T--){int n;scanf("%d%s",&n,s+1);long long ans=0;for(int i=1;i<=n;i++){f[i][0]=f[i][1]=f[i][2]=f[i][3]=0;if(s[i]=='0'){f[i][0]=1+f[i-1][1]+f[i-1][3];f[i][2]=f[i-1][2]+f[i-1][0];}else{f[i][1]=1+f[i-1][0]+f[i-1][2];f[i][3]=f[i-1][3]+f[i-1][1];}ans+=f[i][0]+f[i][1];}printf("%lld\n",ans);} return 0; }

總結(jié)

以上是生活随笔為你收集整理的（Codeforces800Div2）B. Paranoid String（思维/动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。