D. AB-string （思维）

传送门

题意：给你一个长度为n的字符串，字符串只由 A B 组成。

　　　问你这个字符串存在多少个 good string；（连续的一段子串）

　　　good string 的定义就是：字符串中所有的元素都属于这个字符串中的某个回文串。

　　　例如： AAABBB 就是一个good string，因为 AAA 都属于AAA这个回文。BBB也属于BBB这个回文。

　　 ABAA 也是一个 good string，因为第一个A 属于 ABA 这个回文，最后一个A属于AA这个回文。

解：思维题。发现只有 ABB或者 BBA 这种是不行的，其他怎么选都是行的。

　　若全都是合法的，那对于每个位置 i，以它作为子串的右端点，能选的左端点有 i - 1个。

　　那对于以 i 为右端点的，不能选的左端点分类。

　　 1、若是像 ABBBA, 这种的，那你以第二个A为右端点，不能选的就是两个A之间连续的B那一段的长度。

　　 2、对于 ABBABBBB 那你以最右边的B为右端点，不能选的就是以第二个A为左端点的这一段，其他都可以选。

#include <bits/stdc++.h>

#define LL long long

#define ULL unsigned long long

#define rep(i,j,k) for(int i=j;i<=k;i++)

#define dep(i,j,k) for(int i=k;i>=j;i--)

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define make(i,j) make_pair(i,j)

#define pb push_back

#define Pi acos(-1.0)

using namespace std;

const int N = 3e5 + ;

char a[N];

int main() {

    int n;

    scanf("%d %s",&n, a + );

    LL ans = ; int like = ;

    rep(i, , n) {

        if (i ==  || a[i] == a[i - ]) like++, ans += i -  - (like < i);

        else ans += i -  - like, like = ;

    }

    printf("%lld\n",ans);

    return ;

}

巴特西

D. AB-string （思维）

最新文章

热门文章

巴特西

D. AB-string （ 思维 ）

最新文章

热门文章

D. AB-string （思维）