本文主要是介绍AcWing 4261. 孤独的照片（每日一题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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）都可以被接受。
解题思路：
这个题看着不难，其实做起来还是很棘手的，看了y总讲解才知道用的是贡献法，这个思想是第一次听说，具体意思就是横看成岭侧成峰，换一种角度看问题，比如许多人做慈善，让贫穷的人脱贫致富，换种思想就是一个做慈善的人对脱贫做了多少贡献。大体是这个思想。这个题其实我没有感觉到有贡献法地思想，具体做法就是，这一排牛任意一个，先确定他是H品种还是G品种，这里以H品种为例子，要想满足孤独照片，至少要三头牛在这一张照片上，具体方案为：GGH、GHG、HGG。那一张照片四头牛呢，GGGH、GGHG、GHGG、HGGG，那五头、六头……这样看来，我们先找一下此头牛（H）前面有几头连续地G头牛，在看看后面有几头连续地G头牛。我既可以让H这头牛站在中央两边补G，我也可以让H站在两边，其余的补G。这样不就出来了嘛，ans+=l[i]*r[i]+max(0,l[i]-1)+max(0,r[i]-1)，l[i]-1和r[i]-1是为了留一个位置让H进去。
例： HHHGGHGG
这里以第4个H为例
ans+=l[i]*r[i]+max(0,l[i]-1)+max(0,r[i]-1)
首先遍历到第四个H是r[i]=2,l[i]=2
l[i]*r[i]为第一种方案2*2=4
第一种方案前面2个跟后面两个可一个退出一个进来，同时进，同时退
分别为：GGHG、GHGG、GGHGG、GHG
第二种方案就是让H站在最右侧max(0,l[i]-1)=1
分别为：GGH
第三种方案就是让H站在最左侧max(0,r[i]-1)=1
分别为：HGG
同理其他的也可以按照这样处理代码：
#include<iostream>
using namespace std;
const int N=5e5+5;
typedef long long ll;
ll n,ans;
char ch[N];
int r[N],l[N];//r数组表示由左向右遍历，第i个点前面有几个不同的连续的牛，//l数组为由右向左遍历，第i个点后面有几个不同的牛
int main(){cin>>n;getchar();//吃掉回车,防止ch输入不进去scanf("%s",ch);int sh=0,sg=0;//sh表示此头牛为前面有几头H牛，sg表示此头牛为前面有几头G牛for(int i=0;i<n;i++){if(ch[i]=='H'){//如果此头牛为H,数组赋值前面不同品种牛(G)的数l[i]=sg;sh++;//此头牛自身也是H品种，所以加一sg=0;//因为照片拍的是连续的，此头为H,G品种的牛就被隔断了，需要重新计数}else{l[i]=sh;sg++;sh=0;}}sh=0,sg=0;//清零，逆序遍历for(int i=n-1;i>=0;i--){if(ch[i]=='H'){//与上面同理r[i]=sg;sh++;sg=0;}else{r[i]=sh;sg++;sh=0;}}for(int i=0;i<n;i++){//遍历每一头牛,查找孤独的照片ans+=(ll)l[i]*r[i]+max(0,l[i]-1)+max(0,r[i]-1);//注意l[i]*r[i]会爆int//当l[i]为0时,会出现-1,不符合题意,还能倒贴一张照片？最低也就一张孤独照片也没有}cout<<ans<<endl;return 0;
}博主写的不是很详细，还是从刷题者地角度去以解题目的去写的，若有不足地地方，恳请大家指出，共同进步。但愿各位能从我的文章中get到一点启发，对给位有所帮助。
这篇关于AcWing 4261. 孤独的照片（每日一题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
