36pts样例已过
查看原帖
36pts样例已过
1075989
BlauAnthony楼主2025/2/5 17:02

死亡回放:只有WA和AC

之前我使用了指针导致MLE,这次我学着开了个超大数组,但是还是没过 P8306指针方法

code:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int S=62;//A、a、0:26+26+10
const int N=3000005;
pair<int,int> trie[N][S];
int allpoint=0;
int getsize_t(char ch){
    if(ch>='0'&&ch<='9')return ch-'0'+52;
    else if(ch>='a'&&ch>='z')return ch-'a'+26;
    else return ch-'A';
}
void empty(int x){
    for(int i=0;i<S;i++){
        trie[x][i].first=0;
        trie[x][i].second=-1;
    }
}
void insert(string word){
    int pointer=0,tmpw;
    for(int i=0;i<word.size();i++){
        tmpw=getsize_t(word[i]);
        if(trie[pointer][tmpw].first==0){
            allpoint++;
            empty(allpoint);
            trie[pointer][tmpw].second=allpoint;
        }
        trie[pointer][tmpw].first++;
        pointer=trie[pointer][tmpw].second;
    }
}
int find(string word){
    int pointer=0,tmpw;
    int now;
    for(int i=0;i<word.size();i++){
        tmpw=getsize_t(word[i]);
        if(trie[pointer][tmpw].second==-1||trie[pointer][tmpw].first==0)return 0;
        now=trie[pointer][tmpw].first;
        pointer=trie[pointer][tmpw].second;
    }
    return now;
}
void start(){
    allpoint=0;empty(0);
    int n,q;cin>>n>>q;
	string s,t;
	for(int i=0;i<n;i++){cin>>s;insert(s);}
	for(int i=0;i<q;i++){cin>>t;cout<<find(t)<<endl;}
}
int main(){
	int tq;cin>>tq;
	for(int i=0;i<tq;i++)start();
	return 0;
} 
2025/2/5 17:02
加载中...