Codeforces 1238D. AB-string

传送门

求合法的串看一眼很不可做

考虑一下总方案减去不合法方案

考虑如何求不合法的串，首先串中连续的相同字符一定是回文串的一部分

然后考虑 $AB$ 交错的情况，发现对于某个 $A$ 它如果左右都有 $B$ 那么一定也是回文串的一部分

对于 $B$ 也是同理

那么只要考虑一段 $A$ 和一段 $B$ 连在一起的情况，发现当 $ABBBBB...$ 的时候，串是不合法的

当然 $BAAAAA...$ ，$AAAA...B$，$BBBB...A$ 也都是不合法的，其他情况显然都是合法的

然后所有情况都考虑完了，计算不合法情况很简单，直接看代码吧

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=3e5+;

int n;

ll Ans;

char s[N];

int main()

{

    n=read(); scanf("%s",s+);

    int pre=; Ans=1ll*n*(n-)/;

    for(int i=;i<=n;i++)

    {

        if(s[i]==s[i-]) continue;

        Ans++;//注意这里 Ans++ 是因为 'AB'或'BA' 之后会再次被减去

        Ans-=(i-pre);

        pre=i;

    }

    pre=n;

    for(int i=n-;i>=;i--)

    {

        if(s[i]==s[i+]) continue;

        Ans-=(pre-i); pre=i;

    }

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

    return ;

}

巴特西

Codeforces 1238D. AB-string

最新文章

热门文章