恐怖如斯的MLE
查看原帖
恐怖如斯的MLE
1075989
BlauAnthony楼主2025/1/19 17:12

这道题的内存限制居然是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,看来是我想简单了

2025/1/19 17:12
加载中...