Let's call a binary string?TT?of length?mm?indexed from?11?to?mm?paranoid?if we can obtain a string of length?11?by performing the following two kinds of operations?m?1m?1?times in any order :

• Select any substring of?TT?that is equal to?01, and then replace it with?1.
• Select any substring of?TT?that is equal to?10, and then replace it with?0.

  For example, if?T=T=?001, we can select the substring?[T2T3][T2T3]?and perform the first operation. So we obtain?T=T=?01.

You are given a binary string?SS?of length?nn?indexed from?11?to?nn. Find the number of pairs of integers?(l,r)(l,r)?1≤l≤r≤n1≤l≤r≤n?such that?S[l…r]S[l…r]?(the substring of?SS?from?ll?to?rr) is a?paranoid?string.

Input

The first line contains an integer?tt?(1≤t≤10001≤t≤1000)?— the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer?nn?(1≤n≤2?1051≤n≤2?105)?— the size of?SS.

The second line of each test case contains a binary string?SS?of?nn?characters?S1S2…SnS1S2…Sn. (Si=Si=?0?or?Si=Si=?1?for each?1≤i≤n1≤i≤n)

It is guaranteed that the sum of?nn?over all test cases doesn't exceed?2?1052?105.

Output

For each test case, output the number of pairs of integers?(l,r)(l,r)?1≤l≤r≤n1≤l≤r≤n?such that?S[l…r]S[l…r]?(the substring of?SS?from?ll?to?rr) is a?paranoid?string.

Example

input

Copy

5 1 1 2 01 3 100 4 1001 5 11111

output

Copy

1 3 4 8 5

題意：?給出長(zhǎng)度為n的01串，對(duì)于一段“01”的串可以轉(zhuǎn)化為“1”，對(duì)于一段“10”的串可以轉(zhuǎn)化為“0”，這種轉(zhuǎn)化可以進(jìn)行若干次，詢(xún)問(wèn)有多少個(gè)子串可以通過(guò)這種操作轉(zhuǎn)化為1個(gè)字符。

分析：?先說(shuō)下dp做法，可以設(shè)dp[i][0]為以第i個(gè)字符結(jié)尾且能轉(zhuǎn)化為1個(gè)0的子串個(gè)數(shù)，dp[i][1]為以第i個(gè)字符結(jié)尾且能轉(zhuǎn)化為1個(gè)1的子串個(gè)數(shù)，dp[i][2]為以第i個(gè)字符結(jié)尾且能轉(zhuǎn)化為t個(gè)0的子串個(gè)數(shù)，其中t >= 2，dp[i][3]為以第i個(gè)字符結(jié)尾且能轉(zhuǎn)化為t個(gè)1的子串個(gè)數(shù)，同樣t >= 2，這樣狀態(tài)轉(zhuǎn)移方程也比較顯然了，如果s[i] == '0'，那dp[i][0]就是1+dp[i-1][1]+dp[i-1][3]，dp[i][2]就是dp[i-1][2]+dp[i-1][0]，如果s[i] == '1'，那dp[i][1]就是1+dp[i-1][0]+dp[i-1][2]，dp[i][3]就是dp[i-1][3]+dp[i-1][1]，最終答案就是遍歷一遍求sum(dp[i][0]+dp[i][1])，最后別忘了開(kāi)long long！

不過(guò)這種做法其實(shí)有點(diǎn)麻煩了，實(shí)際上有一種非常簡(jiǎn)單的做法，不過(guò)比較難想到，可以發(fā)現(xiàn)對(duì)于以“01”或者“10”結(jié)尾的子串，不論其前面如何安排最后一定能轉(zhuǎn)化為1個(gè)字符，例如 1010111001 01這樣的形式，讓其中的0先不斷與它前面的1結(jié)合，這樣就可以丟掉前面所有的1，最后剩下0000 01，這時(shí)候最后一個(gè)1再不斷和前面的0結(jié)合就行了，對(duì)于10也是同理，所以只需要for循環(huán)遍歷一下字符串，找到“01”或“10”出現(xiàn)的位置，然后答案加上i-1，最后答案別忘了再加上每位字符自己的貢獻(xiàn)n。

具體代碼如下：

dp做法：

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> using namespace std;char a[200005]; int dp[200005][4];signed main() {int T;cin >> T;while(T--){int n;scanf("%d", &n);scanf("%s", a+1);for(int i = 1; i <= n; i++)for(int j = 0; j <= 3; j++)dp[i][j] = 0;dp[1][0] = (a[1] == '0');dp[1][1] = (a[1] == '1');long long ans = 0;for(int i = 2; i <= n; i++){if(a[i] == '0'){dp[i][0] = 1+dp[i-1][1]+dp[i-1][3];dp[i][2] = dp[i-1][0]+dp[i-1][2];}else{dp[i][1] = 1+dp[i-1][0]+dp[i-1][2];dp[i][3] = dp[i-1][1]+dp[i-1][3];}ans += dp[i][0]+dp[i][1];}ans += dp[1][0]+dp[1][1]; // for(int i = 1; i <= n; i++, putchar('\n')) // for(int j = 0; j < 2; j++) // cout << dp[i][j] << " ";printf("%lld\n", ans);} return 0; }

?官方正解：

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> using namespace std;char a[200005];signed main() {int T;cin >> T;while(T--){int n;scanf("%d%s", &n, a+1);long long ans = n; //答案至少為n for(int i = 2; i <= n; i++)if(a[i] == '0' && a[i-1] == '1' || a[i] == '1' && a[i-1] == '0')ans += i-1;printf("%lld\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[dp][思维]Paranoid String CF1694B的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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