两种做法+60部分分

部分分60（stack)

#include <bits/stdc++.h>
using namespace std;
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n,ans=0;
    cin>>n;
    string w;
    cin>>w;
    w=" "+w;
    if(n<=8000){
        for(int i=1;i<=n;i++){
            stack <char> s;
            for(int j=i;j<=n;j++){
                if(s.empty()||s.top()!=w[j]) s.push(w[j]);
                else{s.pop();}
                if(s.empty()) ans++;
            }
        }
    }
    else{
        for(int i=1;i<=n;i++){
            stack <char> s;
            for(int j=i;j<=min(n,i+20);j++){
                if(s.empty()||s.top()!=w[j]) s.push(w[j]);
                else{s.pop();}
                if(s.empty()) ans++;
            }
        }
    }
    cout<<ans;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

STRING HASH

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e5+10;
const ull f=131;
ull pw[maxn],has;
long long n,ans;
string str;
map <ull,int> mp;
int main(){
    cin>>n>>str;
    stack <char> s;
    pw[0]=1,mp[0]=1;
    for(int i=1;i<=200000;i++){
        pw[i]=pw[i-1]*f;
    }
    for(int i=0;i<n;i++){
        if(s.empty()||s.top()!=str[i]){
            has+=str[i]*pw[s.size()];
            ans+=mp[has];
            s.push(str[i]);
        }
        else{
            s.pop();
            has-=str[i]*pw[s.size()];
            ans+=mp[has];
        }
        mp[has]++;
    }
    cout<<ans;
    return 0;
}

DP

#include <bits/stdc++.h>
using namespace std;
const int maxn=2000010;
int l[maxn],dp[maxn],a[maxn][26];
long long n,ans=0;
string s;
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    cin>>n;
    cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++){
        l[i]=i;
        long long x=a[l[i-1]][s[i]-'a'];
        if(x!=0){
            l[i]=l[x-1];
            dp[i]=dp[x-1]+1;
        }
        a[l[i]][s[i]-'a']=i;
        ans+=dp[i];
    }
    cout<<ans;
    fclose(stdin);
    fclose(stdout);
    return 0;
}