AcWing 4261. 孤独的照片
原题链接
简单
作者:
食蜂操析
,
2023-01-10 12:06:29
,
所有人可见
,
阅读 101
#include <iostream>
#define N 500010
typedef long long LL;
using namespace std;
char str[N];
int lH[N], lG[N];
int n;
int main()
{
scanf("%d", &n);
scanf("%s", str);
LL ans = 0;
for (int i = 0, cntH = 0, cntG = 0; i < n; i ++ )
if (str[i] == 'H') cntH++, lG[i] = cntG, cntG = 0;
else cntG++, lH[i] = cntH, cntH = 0;
for (int i = n - 1, cntH = 0, cntG = 0; i >= 0; i -- )
if (str[i] == 'H') cntH++, ans += (LL)lG[i] * cntG + max(cntG - 1, 0) + max(0, lG[i] - 1), cntG = 0;
else cntG++, ans += (LL)lH[i] * cntH + max(cntH - 1, 0) + max(0, lH[i] - 1), cntH = 0;
printf("%lld", ans);
}