CSP-S 2023消消乐 字符串哈希做法and链表优化dp做法

做完这题感觉整个人都升华了...

打算说一下两种做法，字符串哈希和dp均可。

dp则需要维护一个前向星去检索出第一个符合要求的位置。

题解明天补，先写高数了。

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
#define pii pair<int,int>
const int N=3e6+5;

char t[N];
int n;
int f[N];
int lst[N];

int32_t main(){
    cin>>n;
    rep(i,1,n) cin>>t[i];
    int ans=0;
    rep(i,1,n){
        for(int j=i-1;j>0;j=lst[j]-1){
            if(t[j]==t[i]){
                lst[i]=j;
                break;
            }
        }
        if(lst[i]) f[i]=f[lst[i]-1]+1;ans+=f[i];
    }
    //rep(i,1,n) cout<<f[i]<<" ";cout<<'\n';
    cout<<ans;
}

　//字符串哈希

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
#define pii pair<int,int>
const int N=3e6+5;

char t[N];
int n;
ull p[N];
char st[N];
unordered_map<ull,int> cnt;

int32_t main(){
    //prework
    cin>>n;
    p[0]=1;
    rep(i,1,n){p[i]=p[i-1]*13331;}

    rep(i,1,n) cin>>t[i];
    cnt[0]=1;
    int tp=0;
    ull res=0;
    int ans=0;
    rep(i,1,n){
        if(tp!=0&&st[tp]==t[i]){
            res-=p[tp]*t[i];tp--;
        }else{
            res+=p[++tp]*t[i];st[tp]=t[i];
        }
        ans+=cnt[res];cnt[res]++;
    }
    cout<<ans;
}