Acwing2024蓝桥杯贡献法

题目:

AcWing 4261. 孤独的照片

依次遍历后,再双向遍历

#include<iostream>
using namespace std;
long long ans;
int main(){
    ios::sync_with_stdio(false);
    //输入
    int n;string s="";cin>>n;cin>>s;
    //依次遍历每一个字母
    for(int i=0;i<n;i++){
        //两种情况
        if(s[i]=='G'){
            int l=0,r=0;
            //向右寻找
            for(int j=i+1;;j++){
                if(s[j]=='G'||j>=n){
                    r=j;
                    break;
                }
            }
            //向左寻找
            for(int k=i-1;;k--){
                if(s[k]=='G'||k<0){
                    l=k;
                    break;
                }
            }
            //累加
            l=i-l-1,r=r-i-1;
            ans+=(long long)l*r+max(0,l-1)+max(0,r-1);
        }
        else{
            int l=0,r=0;
            //向右寻找
            for(int j=i+1;;j++){
                if(s[j]=='H'||j>=n){
                    r=j;
                    break;
                }
            }
            //向左寻找
            for(int k=i-1;;k--){
                if(s[k]=='H'||k<0){
                    l=k;
                    break;
                }
            }
            //累加
            l=i-l-1,r=r-i-1;
            ans+=(long long)l*r+max(0,l-1)+max(0,r-1);
        }
    }
    //输出
    cout<<ans<<endl;
    return 0;
}

优化:双向遍历后直接存入左右数组

#include<iostream>
using namespace std;
const int N=5e5+5;
int l[N],r[N];
long long ans;
int main(){
    ios::sync_with_stdio(false);
    int n;string s="";cin>>n;cin>>s;
    int Hcnt=0,Gcnt=0;
    for(int i=0;i<n;i++){
        if(s[i]=='H'){
            r[i]=Gcnt;
            Gcnt=0;
            Hcnt++;
        }
        else{
            r[i]=Hcnt;
            Hcnt=0;
            Gcnt++;
        }
    }
    Hcnt=0,Gcnt=0;
    for(int i=n-1;i>=0;i--){
        if(s[i]=='H'){
            l[i]=Gcnt;
            Gcnt=0;
            Hcnt++;
        }
        else{
            l[i]=Hcnt;
            Hcnt=0;
            Gcnt++;
        }
    }
    for(int i=0;i<n;i++){
        ans+=(long long)l[i]*r[i]+max(l[i]-1,0)+max(r[i]-1,0);
    }
    cout<<ans<<endl;
    return 0;
}

AcWing 2868. 子串分值(第十一届省赛)

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5;
string s;
long long ans;
int main(){
    cin>>s;
    int n=s.size();
    for(int i=0;i<n;i++){
        char ch=s[i];
        int l=0,r=0;
        for(int j=i+1;;j++){
            if(s[j]==ch||j>=n) break;
            else r++;
        }
        for(int k=i-1;;k--){
            if(s[k]==ch||k<0) break;
            else l++;
        }
        ans+=(long long)l*r+1+l+r;
    }
    cout<<ans<<endl;
    return 0;
}