贡献法:USACO 2021 December Contest Bronze:孤独的照片

Farmer John 最近购入了 N 头新的奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。

然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。

在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。

给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。

如果两张照片以不同位置的奶牛开始或结束，则认为它们是不同的。

输入格式

输入的第一行包含 N。

输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛，则字符串的第 i 个字符为 G。否则，第 i 头奶牛是荷斯坦牛，该字符为 H。

输出格式

输出 Farmer John 会扔掉的孤独的照片数量。

数据范围

3≤N≤5×105

输入样例：

5
GHGHG

输出样例：

3

样例解释

这个例子中的每一个长为 3 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片，并会被 Farmer John 扔掉。

所有更长的子串（GHGH、HGHG 和 GHGHG）都可以被接受。

可以通过 l 和 r 数组记录 每头牛左右两边有多少连续的不同种类的牛数量

然后孤独照片数量就是通过 l[i] 和 r[i] 分三类相加得出

找出当前这个牛的左边相邻的连续不同的牛 *  右边的相邻连续不同的牛 + 左边的不同牛的长度 - 1 + 右边不同的牛的长度 - 1

为什么左右两边的长度要减1，因为照片长度至少3，假如是 GHHHH，右边不同长度的牛为4，可方案为，GHH，GHHH,GHHHH，为3，需要减一。

AC code：

#include<bits/stdc++.h>
using namespace std;
unordered_map<char, int> mp;
int n;
int l[500010], r[500010];
string s;
int main() {
	cin >> n;
	cin >> s;
	int hh = 0, gg = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'H') {
			hh++;
			l[i] = gg;
			gg = 0;
		} else {
			gg++;
			l[i] = hh;
			hh = 0;
		}
	}
	hh = 0, gg = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == 'H') {
			hh++;
			r[i] = gg;
			gg = 0;
		} else {
			gg++;
			r[i] = hh;
			hh = 0;
		}
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		ans += (long long)l[i] * r[i] + max(0, l[i] - 1) + max(0, r[i] - 1);
//		cout << l[i] << " " << r[i] << endl;
	}
	cout << ans;
}