这道题的内存限制居然是1GB,太恐怖了,这居然也能MLE
我本以为这么多内存根本用不完,于是我的代码:
#include<iostream>
#include<cstring>
using namespace std;
const int S_size=26+26+10;
class Trie{
private:
int wordnum;
bool initboolean;
Trie* nexts[S_size]={};//Aa0
public:
Trie(): wordnum(0),initboolean(false){}
void init(){
initboolean=true;
for(int i=0;i<S_size;i++)this->nexts[i]=new Trie();
}
void insert(string word){
Trie* pointer;
if(word[0]>='0'&&word[0]<='9'){
pointer=nexts[word[0]-'0'+52];
}else if(word[0]>='a'&&word[0]<='z'){
pointer=nexts[word[0]-'a'+26];
}else{
pointer=nexts[word[0]-'A'];
}
pointer->wordnum++;
for(int i=1;i<word.size();i++){
if(pointer->initboolean==false)pointer->init();
if(word[i]>='0'&&word[i]<='9'){
pointer=pointer->nexts[word[i]-'0'+52];
}else if(word[i]>='a'&&word[i]<='z'){
pointer=pointer->nexts[word[i]-'a'+26];
}else{
pointer=pointer->nexts[word[i]-'A'];
}
pointer->wordnum++;
}
}
int find(string word){
Trie* pointer;
if(word[0]>='0'&&word[0]<='9'){
pointer=nexts[word[0]-'0'+52];
}else if(word[0]>='a'&&word[0]<='z'){
pointer=nexts[word[0]-'a'+26];
}else{
pointer=nexts[word[0]-'A'];
}
if(pointer->initboolean==false)return 0;
for(int i=1;i<word.size();i++){
if(pointer->initboolean==false)return 0;
if(word[i]>='0'&&word[i]<='9'){
pointer=pointer->nexts[word[i]-'0'+52];
}else if(word[i]>='a'&&word[i]<='z'){
pointer=pointer->nexts[word[i]-'a'+26];
}else{
pointer=pointer->nexts[word[i]-'A'];
}
}
return pointer->wordnum;
}
};
void start(){
int n,q;cin>>n>>q;
Trie man;man.init();//root
string s,t;
for(int i=0;i<n;i++){
cin>>s;
man.insert(s);
}
for(int i=0;i<q;i++){
cin>>t;
cout<<man.find(t)<<endl;
}
}
int main(){
int tq;cin>>tq;
for(int i=0;i<tq;i++)start();
return 0;
}
全部MLE,看来是我想简单了