蒟蒻求调 WA1-4

P8306 【模板】字典树

YQWQ @ 2023-07-13 16:33:43

#include <bits/stdc++.h>
using namespace std;

const int Kmax=3e6,MAXN=75;

int T,n,m,t,now;

string s;

struct  trieN{
    int is_l;
    int next[MAXN];
}trie[Kmax];

void fil(){
    for(int i=0;i<=t;i++){
        trie[i].is_l=0;
        for(int j=0;j<MAXN;j++){
            trie[i].next[j]=0;
        }
    } 
}

void build(int p,int i){
    trie[p].is_l++;
    now=trie[p].next[s[i]-'0'];
    if(!now) now=trie[p].next[s[i]-'0']=++t;
    if(i<s.size()-1){
        build(now,i+1);
    }
}

void find(int p,int i){
//  cout<<"   "<<p<<" "<<i<<endl;
    if(i==s.size()-1){
        cout<<trie[p].is_l<<endl;
    }else{
        now=trie[p].next[s[i]-'0'];
        if(!now) cout<<0<<endl;
        else{
            find(now,i+1);
        }
    }
}

int main(){
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    cin>>T;
    while(T--){
        t=0;
        cin>>n>>m;
        for(int i=1;i<=n+m;i++){
            cin>>s;
            if(i<=n) build(0,0);
            else find(0,0);
        }
        fil();
    }
}

by henryyin @ 2023-07-28 22:21:45

我也是在这里被卡了...

trie[p].is_l++;
now=trie[p].next[s[i]-'0'];

两行调换位置,并且将

if(i==s.size()-1){
cout<<trie[p].is_l<<endl;
}

改为

if(i==s.size()){
cout<<trie[p].is_l<<endl;
}

就对了

相当于update时每次存的节点的size都是父节点的,所以query时变为

if(i==s.size())

问题在于当s.size()=1的时候的答案和s.size()=0是一样的,都返回的是 trie[0].is_l


|