社区讨论

求助,莫名其妙数组越界

P14363[CSP-S 2025] 谐音替换参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mhixqmez
此快照首次捕获于
2025/11/03 17:26
4 个月前
此快照最后确认于
2025/11/08 07:50
3 个月前
查看原帖
RT。我将 MAXN 设为 2e5 就会越界 WA95,设成 4e5 就 AC 了。球球大佬们帮忙看一眼哪里能越界啊 qwq。
CPP
/*

       2025.11.1

 * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int>P;
typedef pair<ull,ull>PP;
const int MAXN=200005,MAXN2=5000005,inf=0x3f3f3f3f;
const ull mul=233;
int n,q,ans[MAXN];
ull ta[MAXN2],tb[MAXN2],mu[MAXN2];
bool vis[MAXN];
map<ull,int>ts,mp2;int cnt2;
map<int,int>_rev;
map<PP,int>mp;int cnt;
vector<int>ask[MAXN],g[MAXN];
vector<ull>gg[MAXN],pre[MAXN],suf[MAXN];
struct node{
    ull l,mid,r;
}aa[MAXN];
ull gt(int l,int r){return ta[r]-ta[l-1]*mu[r-l+1];}
ull gtb(int l,int r){return tb[r]-tb[l-1]*mu[r-l+1];}
int rev(ull x,ull y){
    if(mp.find({x,y})==mp.end())mp[{x,y}]=++cnt;
    return mp[{x,y}];
}
int rev2(ull x){
    if(mp2.find(x)==mp2.end())mp2[x]=++cnt2;
    return mp2[x];
}
void dfs(int x,const vector<int> &f){
    if(f.size()==0)return ;
    if(pre[f[0]][x]<MAXN)for(ull i:gg[pre[f[0]][x]])ts[i]++;
    for(int i:f){
        if(pre[i].size()==x+1){
            vis[i]=1;
            for(ull j:suf[i])if(ts.find(j)!=ts.end())ans[i]+=ts[j];
        }
    }
    _rev.clear();int tot=0;vector<vector<int> >ggg;
    for(int i:f){
        if(vis[i])continue;
        if(_rev.find(pre[i][x+1])==_rev.end()){
            _rev[pre[i][x+1]]=tot++;
            ggg.pb(vector<int>() );
        }
        ggg[_rev[pre[i][x+1]]].pb(i);
    }
    for(int i=0;i<tot;i++)dfs(x+1,ggg[i]);
    if(pre[f[0]][x]<MAXN)for(ull i:gg[pre[f[0]][x]])ts[i]--;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
//    freopen("replace.in","r",stdin);freopen("replace.out","w",stdout);
    cin>>n>>q;
    mu[0]=1;
    for(int i=1;i<MAXN2;i++)mu[i]=mu[i-1]*mul;
    for(int i=1;i<=n;i++){
        string a,b;cin>>a>>b;
        if(a==b)continue;
        int mx=0,mn=inf;
        for(int j=0;j<a.size();j++)ta[j+1]=ta[j]*mul+(ull)(a[j]-'a'+1),tb[j+1]=tb[j]*mul+(ull)(b[j]-'a'+1);
        for(int j=0;j<a.size();j++)if(a[j]!=b[j])mx=max(mx,j+1),mn=min(mn,j+1);
        aa[i]=node{gt(1,mn-1),gt(mn,mx),gt(mx+1,a.size())};
        g[rev(gt(mn,mx),gtb(mn,mx))].pb(i);
    }
    for(int i=1;i<=q;i++){
        string a,b;cin>>a>>b;
        if(a.size()!=b.size())continue;
        int mx=0,mn=inf;
        for(int j=0;j<a.size();j++)ta[j+1]=ta[j]*mul+(a[j]-'a'+1),tb[j+1]=tb[j]*mul+(b[j]-'a'+1);
        for(int j=0;j<a.size();j++)if(a[j]!=b[j])mx=max(mx,j+1),mn=min(mn,j+1);
        if(mp.find({gt(mn,mx),gtb(mn,mx)})==mp.end())continue;
        suf[i].pb(0);
        for(int j=mx+1;j<=a.size();j++)suf[i].pb(gt(mx+1,j));
        pre[i].pb(0);
        for(int j=mn-1;j>=1;j--)pre[i].pb(gt(j,mn-1));
        ask[mp[{gt(mn,mx),gtb(mn,mx)}]].pb(i);
    }
    for(int i=1;i<=cnt;i++){
        if(g[i].size()==0||ask[i].size()==0)continue;
        for(int j=1;j<=cnt2;j++)gg[j].clear();
        cnt2=0;mp2.clear();ts.clear();
        for(int j:g[i]){
            gg[rev2(aa[j].l)].pb(aa[j].r);
        }
        for(int j:ask[i]){
            for(int k=0;k<pre[j].size();k++)pre[j][k]=rev2(pre[j][k]);
        }
        dfs(0,ask[i]);
    }int ccnt=0;
    for(int i=1;i<=q;i++){
        if(ans[i]<0)ccnt++;
        cout<<ans[i]<<'\n';
    }
    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...