网站开发 项目的人员分配,单仁资讯做网站怎样,福州短视频seo获客,网络平台推广是干什么Farmer John 最近购入了 N 头新的奶牛#xff0c;每头奶牛的品种是更赛牛#xff08;Guernsey#xff09;或荷斯坦牛#xff08;Holstein#xff09;之一。 奶牛目前排成一排#xff0c;Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而#xff0c;他… 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可方案为GHHGHHH,GHHHH为3需要减一。 AC code #includebits/stdc.h
using namespace std;
unordered_mapchar, 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;
}
