4261. 孤独的照片 - AcWing题库

这题看数据范围 n ≤  不可能暴力做 会tle

1、双指针暴力模拟 tle

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,res=0;
    string s;
    cin>>n>>s;
    for(int i=0;i<n-2;i++)
    {
        int g=0,h=0;
        for(int l=3;i+l<=n;l++)
        {
            string str=s.substr(i,l);
            for(char x:str) 
                if(x=='G') g++;
                else h++;
            if(g==1||h==1) res++;
        }
    }
    cout<<res;
}

2、乘法原理

枚举每一头牛 计算包含该牛子串的要删除的照片数

   i这头牛左边相邻最长连续不同牛数

  i这头牛右边相邻最长连续不同牛数

像GGHGGG这种情况   

H左边有2种G可以选择 H右边有3种G可以选择

• H在中间时 一共有2×3=6种情况

        比如选左边G1和右边G2  这种要删掉照片的情况就是GGHGG

        再比如选左边G2和右边G3 这种要删掉照片的情况就是GHGGG

• H在边界时 像左边GGH 1种情况  右边HGG HGGG 2种情况

        也就是 l[i]-1种+r[i]-1种

则以该H为中心的该删除的照片数为 

max(0,l[i]-1) max(0,r[i]-1) 是防止为负数

#include <bits/stdc++.h>
using namespace std;

const int N=6e5+10;
int l[N],r[N];

int main()
{
    int n;
    string s;
    cin>>n>>s;
    for(int i=0,g=0,h=0;i<n;i++)
    {
        if(s[i]=='G') l[i]=h,h=0,g++;
        else l[i]=g,g=0,h++;
    }
    for(int i=n-1,g=0,h=0;i>=0;i--)
    {
        if(s[i]=='G') r[i]=h,h=0,g++;
        else r[i]=g,g=0,h++;
    }
    long long res=0;
    for(int i=0;i<n;i++)
        res+=(long long)l[i]*r[i]+max(0,l[i]-1)+max(0,r[i]-1);
    
    cout<<res;
}