蒟蒻一直WA(trie)求条
查看原帖
蒟蒻一直WA(trie)求条
1373205
dg114514楼主2024/12/3 17:22
#include<bits/stdc++.h>
using namespace std;
int get(char x){
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
}
int ans=1;
class trie{
	#define u t[p][tmp] 
	vector<vector<int>>t;
	vector<int> cnt;
	vector<bool> vis;
	int tot,n;
	public:
	trie(int _n):t(_n+5,vector<int>(70,0)),tot(0),cnt(_n+5,0),vis(_n+5,0){}
	void insert(const string& s){
		int p=0,tmp;
		for(auto i:s){
			tmp=get(i);
			if(vis[p])ans=0;
			if(!u)u=++tot;p=u;
			cnt[p]++;
		}
		for(int i=52;i<=62;i++)if(t[p][i]){ans=0;break;}
		vis[p]=true;
	}
	void clear(){
		for(int i=0;i<=tot;i++)for(int j=0;j<63;j++)t[i][j]=0;
		for(int i=0;i<tot;i++)cnt[i]=0,vis[i]=false;
		tot=0;
	}
	int find(const string& s){
		int p=0,tmp;
		for(auto i:s){
			tmp=get(i);
			if(!u)return 0;p=u;
		}
		return cnt[p]<<1|vis[p];
	}
};
signed main(){
//	#ifdef _WIN32
//		freopen("trie.in","r",stdin);
//		freopen("tt.out","w",stdout);
//	#endif
//	cin.tie(0)->sync_with_stdio(false);
	trie t(150005);
	int T,n,q;
	cin>>T;
	string s;
	for(int i=1;i<=T;i++){
		cin>>n,ans=1;
		while(n--)cin>>s,t.insert(s);
		puts(ans?"YES":"NO");
		t.clear();
	}
}
2024/12/3 17:22
加载中...