题意

https://vjudge.net/problem/CodeForces-1238D

如果一个字符串的每个字母，属于至少一个（长度大于1）的回文串，则称这个字符串为good。

一个长度为n的字符串s（只由字母A,B组成），问s的子串中有多少个good字符串

思路

发现只有XYX这种交错的串或者XX…X才可能是good串。

直接做比较难，我们考虑求不合法的串。

所以我们先正着遍历一遍字符串，找出XXXXY这种，即通过s[i]!=s[i-1]计算前面相同字符的个数，即为不合法串的个数（XY,XXY,XXXY,XXXXY都不合法）

再倒着遍历一遍，找出XYYYY这种，即通过s[i]!=s[i+1]计算后面相同字符的葛素，即为不合法串的个数（XY,XYY,XYYY,XYYYY）

但我们也可以发现，这样做会把XY这种减两遍，事实是正着算算成了XY，倒着算算成了YX，所以再遍历一遍，把XY这种交错的个数算出来。

长度为1的串肯定不合法，所以用总的串（n-1+1）*(n-1)/2 减去上面不合法的情况，再加上多减的XY。

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=200005;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

int main()

{

    std::ios::sync_with_stdio(false);

    ll n;

    cin>>n;

    string s;

    cin>>s;

    ll ans=n*(n-1)/2,cnt=1;

    for(int i=1;i<n;i++)//XXXXY

    {

        if(s[i]==s[i-1]) cnt++;

        else ans-=cnt,cnt=1;

    }

    cnt=1;

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

    {

        if(s[i]==s[i+1]) cnt++;

        else ans-=cnt,cnt=1;

    }

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

        if(s[i]!=s[i-1])

            ans++;

    cout<<ans<<endl;

    return 0;

}

巴特西

CodeForces - 1238D（思维）

题意

思路

代码

最新文章

热门文章