两种做法

部分分60

#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;
}