自动搬运

查看原文

来自洛谷，原作者为

	徐晨轩✅ https://discord.gg/bNTY6ThGZD

搬运于2025-08-24 22:35:00，当前版本为作者最后更新于2021-12-27 18:10:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题窝想了 2h 才出正解

大致思路是这样的：扫描每一头牛，计算出这头牛是“孤独的”的照片有多少张，加到 ans 里头去。最后输出 ans。有人担心这种方法会重复计算，实际上是不会的。因为每张照片都只会有唯一的一只牛是“孤独的”，也就是说这张照片只会被这只“孤独的”牛计算一遍。

那么重点来了，怎么算呢？？

我们可以再计算前先处理四个数组：LG[],RG[],LH[],RH[]。这四个数组的第 $i$ 位分别表示：第 $i$ 头牛左边有几头连续的更赛牛，第 $i$ 头牛右边有几头连续的更赛牛，第 $i$ 头牛左边有几头连续的荷斯坦牛，第 $i$ 头牛右边有几头连续的荷斯坦牛。在计算答案时，对于每头牛（假设这头牛是更赛牛，荷斯坦牛类似），考虑以下两种情况：

1. 这头牛是在照片里的最左边或最右边。这种情况可以加上 LH[i]?LH[i-1]:0+RH[i]?RH[i+1]:0（-1 或 +1 是为了避免 len==2 的情况），画图如下：

2. 这头牛实在照片里的中间。这种情况可以加上 LH[i]*RH[i]，画图如下：

将这两个加起来就行了。

AC Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=500001;
int n,l=1,r=1,ans,LG[N],RG[N],LH[N],RH[N];
string s;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> s;s=" "+s;
	for(int i=2;i<=n;i++)
		LG[i]=s[i-1]=='G'?LG[i-1]+1:0;
	for(int i=n-1;i>=1;i--)
		RG[i]=s[i+1]=='G'?RG[i+1]+1:0;
	for(int i=2;i<=n;i++)
		LH[i]=s[i-1]=='H'?LH[i-1]+1:0;
	for(int i=n-1;i>=1;i--)
		RH[i]=s[i+1]=='H'?RH[i+1]+1:0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='H')
		{
			if(LG[i])ans+=LG[i-1];
			if(RG[i])ans+=RG[i+1];
			ans+=LG[i]*RG[i];
		}
		else
		{
			if(LH[i])ans+=LH[i-1];
			if(RH[i])ans+=RH[i+1];
			ans+=LH[i]*RH[i];
		}
//		cout << ans << endl;
	}
	cout << ans << endl;
	return 0;
}