神秘RE求解答
查看原帖
神秘RE求解答
1417158
_zjzhe楼主2025/7/22 16:55

为什么第16行写成

memset(cnt,0,sizeof(cnt));

会RE

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=4e5+15,M=128;
int n,m,sa[N],rk[N<<1],ork[N<<1],cnt[M],id[N],h[N],f[N];
string s,t;
int solve(string s){
    n=s.size()-1,m=128;memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
    for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
    for(int w=1,p=0;;w<<=1,m=p){
        int cur=0;
        for(int i=n-w+1;i<=n;i++)id[++cur]=i;
        for(int i=1;i<=n;i++)if(sa[i]>w)id[++cur]=sa[i]-w;
/*16*/  memset(cnt,0,sizeof(int)*m+4); /*16*/
        for(int i=1;i<=n;i++)cnt[rk[i]]++;
        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[rk[id[i]]]--]=id[i];
        memcpy(ork,rk,sizeof(rk)),p=0;
        for(int i=1;i<=n;i++){
            if(ork[sa[i]]==ork[sa[i-1]]&&ork[sa[i]+w]==ork[sa[i-1]+w])rk[sa[i]]=p;
            else rk[sa[i]]=++p;
        }if(p==n)break;
    }
    for(int i=1,x=0;i<=n;i++){
        if(x>0)x--;
        if(rk[i]==1)continue;
        while(s[i+x]==s[sa[rk[i]-1]+x])x++;
        h[rk[i]]=x;
    }
    stack<int>st;int res=0;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&h[st.top()]>=h[i])st.pop();
        if(!st.empty())f[i]=f[st.top()]+(i-st.top())*h[i];
        else f[i]=i*h[i];res+=f[i];st.push(i);
    }
    return res;
}
#undef int 
int main(){
#define int long long 
    int ans=0;
    cin>>t;
    t='#'+t;
    ans-=solve(t);
    s+=t;
    cin>>t;
    t='#'+t;
    ans-=solve(t);
    s+=t;
    ans+=solve(s);
    cout<<ans;
    return 0;
}
2025/7/22 16:55
加载中...