孤独的照片
Problem
Farmer John 最近购入了 $N$ 头新的奶牛,每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。
奶牛目前排成一排,Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。
然而,他不想拍摄这样的照片,其中只有一头牛的品种是更赛牛,或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。
在为每个连续不少于三头奶牛的序列拍摄了一张照片后,他把所有「孤独的」照片,即其中只有一头更赛牛或荷斯坦奶牛的照片,都扔掉了。
给定奶牛的排列方式,请帮助 Farmer John 求出他会扔掉多少张孤独的照片。
如果两张照片以不同位置的奶牛开始或结束,则认为它们是不同的。
输入格式
输入的第一行包含 $N$。
输入的第二行包含一个长为 $N$ 的字符串。如果队伍中的第 $i$ 头奶牛是更赛牛,则字符串的第 $i$ 个字符为 G
。否则,第 $i$ 头奶牛是荷斯坦牛,该字符为 H
。
输出格式
输出 Farmer John 会扔掉的孤独的照片数量。
数据范围
$3≤N≤5×10^5$
输入样例:
5
GHGHG
输出样例:
3
样例解释
这个例子中的每一个长为 $3$ 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片,并会被 Farmer John 扔掉。
所有更长的子串(GHGH
、HGHG
和 GHGHG
)都可以被接受。
Solutions
法一
枚举所有的区间,判断区间里面是否只有一头孤独的牛。枚举所有的区间时间复杂度$O(n^2)$,判断是否只有一头孤独的牛时间复杂度$O(1)$(用前缀和优化),总时间复杂度$O(n^2)$
法二
枚举所有的孤独的牛,每一个孤独的牛贡献的孤独区间即为这头牛的贡献值。
比如字符串HHHGHH
,对于孤独的牛G
,贡献的孤独的区间有分为$3$种:
+ 左边:HG
(不符合长度$\geq3$)HHG
HHHG
+ 右边:GH
(不符合长度$\geq3$)GHH
+ 左右:HHHGH
HHGH
HGH
HHHGHH
HHGHH
HGHH
可以发现规律($l$=左边连续H
$r$=右边连续H
)
+ 左边:$l-1$
+ 右边:$r-1$
+ 左右:$l\times r$
$Q:$对于不同的牛G
和H
贡献的孤独区间是否会重复?
$A:$不会重复,因为题目要求孤独区间的长度$\geq3$,所以每一个孤独区间,G
(H
)一定是唯一的,并且H
(G
)一定是不唯一的,所以贡献的孤独区间一定不会重复
代码实现
以G
为例,可以记录每一个G
出现的位置,那么$l$=当前G
的位置距离上一次G
的距离,同理,$r$=当前位置距离下一次G
的位置的距离。
为了方便代码编写,可以将第一次G
出现的位置记为$-1$,最后一次G
出现的位置记为$n$,具体看代码实现。
对于H
,同理。
AC Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> h,g;
signed main()
{
int n,res=0;
cin>>n;
string str;
cin>>str;
g.push_back(-1);
h.push_back(-1);
for(int i=0;i<str.size();++i)
{
if(str[i]=='G') g.push_back(i);
else h.push_back(i);
}
g.push_back(n);
h.push_back(n);
for(int i=1;i<g.size()-1;++i)
{
int l=g[i]-g[i-1]-1;
int r=g[i+1]-g[i]-1;
res+=l*r;//第一种情况
res+=max(0ll,r-1);
res+=max(0ll,l-1);
}
for(int i=1;i<h.size()-1;++i)
{
int l=h[i]-h[i-1]-1;
int r=h[i+1]-h[i]-1;
res+=l*r;//第一种情况
res+=max(0ll,r-1);
res+=max(0ll,l-1);
}
cout<<res<<endl;
return 0;
}
写得好棒QAQ