題意
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/119220.html
標籤：其他
上一篇：記錄第一次發動態