AcWing 4261. 孤独的照片
原题链接
简单
作者:
无双飞怪
,
2024-04-19 16:35:53
,
所有人可见
,
阅读 1
枚举的子串其中有一个字母只出现一次
--可以枚举只出现一次的字母是哪个
枚举包含一个字母的且只包含一个G的且长度>=3的子串的数量
----G--
假设左边L个 右边R个H=>数量L*R
假设左边没有H:R-1(则右边至少包含2个H,3个H……R个H 共R-1种情况)
假设右边没有H:同理 L-1
l[i]:i左边有多少个字母与当前位置不一样
r[i]:i右边有多少个连续的位置与当前位置不一样
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
char str[N];
int l[N],r[N];
int g,h;
int main()
{
int n;
cin>>n;
cin>>str;
for(int i=0;i<n;i++)
{
if(str[i]=='G') l[i]=h,g++,h=0;
else l[i]=g,h++,g=0;
}
for(int i=n-1,h=0,g=0;i>=0;i--)
{
if(str[i]=='G') r[i]=h,h=0,g++;
else r[i]=g,g=0,h++;
}
long long res=0;
for(int i=0;i<n;i++)
{
res+=(long long)l[i]*r[i]+max(0,r[i]-1)+max(0,l[i]-1);//一定记得强制类型转换
}
cout<<res;
return 0;
}