[dp][思维]Paranoid String CF1694B

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

题意： 给出长度为n的01串，对于一段“01”的串可以转化为“1”，对于一段“10”的串可以转化为“0”，这种转化可以进行若干次，询问有多少个子串可以通过这种操作转化为1个字符。

分析： 先说下dp做法，可以设dp[i][0]为以第i个字符结尾且能转化为1个0的子串个数，dp[i][1]为以第i个字符结尾且能转化为1个1的子串个数，dp[i][2]为以第i个字符结尾且能转化为t个0的子串个数，其中t >= 2，dp[i][3]为以第i个字符结尾且能转化为t个1的子串个数，同样t >= 2，这样状态转移方程也比较显然了，如果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])，最后别忘了开long long！

不过这种做法其实有点麻烦了，实际上有一种非常简单的做法，不过比较难想到，可以发现对于以“01”或者“10”结尾的子串，不论其前面如何安排最后一定能转化为1个字符，例如 1010111001 01这样的形式，让其中的0先不断与它前面的1结合，这样就可以丢掉前面所有的1，最后剩下0000 01，这时候最后一个1再不断和前面的0结合就行了，对于10也是同理，所以只需要for循环遍历一下字符串，找到“01”或“10”出现的位置，然后答案加上i-1，最后答案别忘了再加上每位字符自己的贡献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; }

总结

以上是生活随笔为你收集整理的[dp][思维]Paranoid String CF1694B的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。