孤独的照片-创新互联

题目链接：4261. 孤独的照片 - AcWing题库

ps：一开始以为是字符串问题，然后就是一阵WA...

题解：读完题，你会发现。一张照片里面至少存在3头牛。

错误思想：直接每三头牛为一组照片，判断是否合理。 

解释：

1：一张照片里面说的是至少三头牛。GHHH也是符合条件的

2：三个一组，会TLE的

正解：那么如何才能进行思维转化呢？

我们发现，只要照片里面存在一只孤独的牛，那么就会对答案产生贡献。

我们列组样例进行解释：GGHHHGGG

先说思路：我们把每一个相同字符连续的段看为一个贡献者。这个贡献者可能会贡献，也可能不会贡献。

因为只有孤独的牛才会对答案产生贡献。

所以，我们每次只需要在连续的段里面选择一个字符，看他能否在他的左边/右边组成符合条件的照片。

图解：

这里还存在一种情况：夹心（GHG）--->（GGG...H...GGG）

然而这种情况的贡献值：H左边牛的个数*H右边牛的个数（举个夹心情况算一下就会明白哦）

最后再处理一下两端贡献者的贡献就行啦 

具体看代码：

#include#define int long long
using namespace std;
const int N=2e6+10;

inline void solve(){
	int n;string s;cin>>n>>s;
	vectorve;//这里用vector存每段贡献者的长度
	for(int i=0,j;i1) ans+=(ve[1]-1)+(ve[(int)ve.size()-2]-1);//最后处理一下两端
	cout<

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧