我感觉这道题还是挺妙的,所以就记录一下
题目的含义就是找有多少个类似于GHH GHHH HHG HHGH……的字符串
(某个字母仅出现一次)
可以在纸上写一下,方便理解
代码
#include<iostream> using namespace std; typedef long long LL; const int N = 500011; int n,l[N],r[N]; char s[N]; int main() { scanf("%d", &n); scanf("%s", s); for(int i=0,h=0,g=0;i<n;i++)//处理左边的 { if(s[i]=='G') //如果当前位置是G { //那么H的个数就要=0 l[i]=h; h=0; g++; //并且G的个数+1 } else { l[i]=g; g=0; h++; } } for(int i=n-1,h=0,g=0;i>=0;i--)//处理右边的 { if(s[i]=='G') { r[i]=h; h=0; g++; } else { r[i]=g; g=0; h++; } } LL res=0; for (int i = 0; i < n; i ++ ) { res+=(LL)l[i]*r[i]+max(l[i]-1,0)+max(r[i]-1,0);//防止结果小于0 } //case1:l[i]-1 cout<<res; //case2:r[i]-1 } //case3:l[i]*r[i] //看上去在for里面,又有了max(l[i]-1,0)max(r[i]-1,0) //但是实际上,l[0]l[1]......l[n-2]=0,只有l[n-1]!=0 //不信举个例子试试GHH //不信举个例子试试GHH //不信举个例子试试GHH
实在看不懂的话可以听听y总的视频讲解(文章开头有链接)
也不能一直扣一道题,休息一下再看说不定就会了