Lonely Photo

题目描述

农夫约翰最近获得了 $N$ 头新奶牛 $(3 \le N \le 5 \times 10^5)$，每头奶牛的品种要么是更赛牛（Guernsey），要么是荷斯坦牛（Holstein）。 奶牛目前排成一列，农夫约翰想为每一段长度至少为 3 的连续奶牛序列拍一张照片。然而，他不想拍一张照片中恰好只有一头更赛牛，或恰好只有一头荷斯坦牛——他认为这头“独苗”会感到孤立和不自在。 在为所有长度至少为 3 的序列都拍完照之后，他会把所有这类所谓“孤独”的照片丢掉，即其中恰好只有一头更赛牛或恰好只有一头荷斯坦牛的照片。 给定奶牛的队列，请帮助农夫约翰确定他会丢掉多少张孤独照片。如果两张照片在队列中的起点或终点奶牛不同，则认为这两张照片不同。

输入格式

第一行输入包含 $N$。 第二行包含一个长度为 $N$ 的字符串。第 $i$ 个字符为 G 表示队列中的第 $i$ 头奶牛是更赛牛；否则该字符为 H，表示第 $i$ 头奶牛是荷斯坦牛。

输出格式

请输出农夫约翰将因为“孤独”而丢掉的照片数量。

5
GHGHG

3

提示

在本例中，所有长度为 3 的子串都恰好包含一头更赛牛或恰好包含一头荷斯坦牛——因此这些子串对应的照片都是孤独照片，会被农夫约翰丢掉。 所有更长的子串（GHGH、HGHG 和 GHGHG）对他来说都是可以接受的。

评分： 测试点 2 到 4 满足 $N \le 50$。 测试点 5 到 10 满足 $N \le 5000$。 为了更具挑战性，测试点 11 没有其他限制。注意该测试点的答案可能大到无法放入标准的 32 位整数中，可能需要使用更大的整数类型（例如 C++ 中的 64 位 “long long int”。）。 题目致谢：Nick Wu

标签: USACO|2021|Bronze

来源

USACO|2021|Bronze