大家好，又见面了，我是全栈君。
Trie树。
题意是问某个数字可不可能是其它数字的前缀。
就是裸的字典树。排序然后插进去就好了。
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
struct Trie
{
int word[100001][10];
int sz,cot;
int ex[1000010];
void intTrie()
{
sz=1;
cot=1;
memset(word[0],0,sizeof(word[0]));
ex[0]=0;
}
int insert(char *s)
{
int u=0,c,len=strlen(s);
int ans=0;
for(int i=0; i<len; i++)
{
c=s[i]-'0';
if(!word[u][c])
{
memset(word[sz],0,sizeof(word[sz]));
ex[sz]=0;
word[u][c]=sz++;
}
u=word[u][c];
ans+=ex[u];
}
if(ex[u]==0)ex[u]=1;
return ans;
}
}wo;
struct lx
{
char str[11];
}l[10001];
bool cmp(lx a,lx b)
{
return strcmp(a.str,b.str)<0;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
wo.intTrie();
scanf("%d",&n);
bool flag=0;
for(int i=0;i<n;i++)
scanf("%s",l[i].str);
sort(l,l+n,cmp);
for(int i=0;i<n;i++)
{
int ans=wo.insert(l[i].str);
if(ans>0)
{
flag=1;break;
}
}
if(flag)puts("NO");
else puts("YES");
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116617.html原文链接：https://javaforall.net
