AcWing 4261. 孤独的照片
原题链接
简单
作者:
只怪我平庸至极
,
2023-05-27 14:18:15
,
所有人可见
,
阅读 149
#include<iostream>
using namespace std;
const int N=5*100005;
char w[N];
//表示左右有多少连续的与当前字符不一样的数量
int l[N],r[N];
int main()
{
int n;
cin>>n;
char e;
scanf("%c",&e);
for(int i=1;i<=n;++i)
{
scanf("%c",&w[i]);
}
//先处理L数组
for(int i=1,h=0,g=0;i<=n;++i)
{
if(w[i]=='G') l[i]=h,h=0,g++;
else l[i]=g,g=0,h++;
}
for(int i=n,h=0,g=0;i>=1;--i)
{
if(w[i]=='G') r[i]=h,h=0,g++;
else r[i]=g,g=0,h++;
}
long long int ans=0;
for(int i=1;i<=n;++i)
{
ans+=(long long)l[i]*r[i]+max(0,l[i]-1)+max(0,r[i]-1);
}
cout<<ans<<endl;
return 0;
}