刚学Trie,WA求助,求hack
查看原帖
刚学Trie,WA求助,求hack
105865
Jur_Cai楼主2021/8/6 23:50

RT

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct node {
	int tf,son[20];
	//tf标记是否有儿子  
}trie[100005];
int num;
inline bool insert(char* x) {
	int l=strlen(x),u=0,op=1;
	for(int i=0;i<l;i++) {
		int tmp=x[i]-'0';
		if(op==1&&trie[u].tf==0&&u) op=2;//表示前面经过的一段为前缀 
		if(!trie[u].son[tmp]) {
			if(op==1) op=0;//没有前缀 
			trie[u].son[tmp]=++num,trie[u].tf=1;
		}
		u=trie[u].son[tmp];
	}
	return op;
}
char s[50];
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		int n,flag=0;
		for(int i=1;i<=num;i++) {
			memset(trie[i].son,0,sizeof(trie[i].son));
			trie[i].tf=0;
		}
		num=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) {
			scanf("%s",s);
			if(flag) continue;//已经出现前缀就不用作了 
			flag=insert(s);
		}
		if(flag) puts("NO");
		else puts("YES");
	}
	return 0;
}
2021/8/6 23:50
加载中...