题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5+10;
int n;
string s;
int l[N],r[N];
int main()
{
cin>>n;
cin>>s;
for(int i=0,h=0,g=0;i<n;i++)
{
if(s[i]=='H') l[i]=g,g=0,h++;
else l[i]=h,h=0,g++;
}
for(int i=n-1,h=0,g=0;i>=0;i--)
{
if(s[i]=='H') r[i]=g,g=0,h++;
else r[i]=h,h=0,g++;
}
long long sum=0;
for(int i=0;i<n;i++)
{
if(l[i]+r[i]>1)
sum+=(long long)l[i]*r[i]+max(0,l[i]-1)+max(0,r[i]-1);
}
cout<<sum<<endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla