|
试题描述
|
|
给定 n 个长度不超过 10 的数字串，问其中是否存在两个数字串 S,T，使得 S 是 T 的前缀，多组数据。1≤n≤10^4
|
|
输入
|
|
第一行一个整数 T，表示数据组数。
对于每组数据，第一行一个数 n，接下来 n 行输入 n 个数字串。 |
|
输出
|
|
对于每组数据，若存在两个数字串 S，T，使得 S 是 T 的前缀，则输出 NO ，否则输出 YES 。
请注意此处结果与输出的对应关系！ |
|
输入示例
|
|
2
3 911 97625999 91125426 5 113 12340 123440 12345 98346 |
|
输出示例
|
|
NO
YES |
|
其他说明
|
|
对于 100% 的数据，1≤T≤40,1≤n≤10^4。
|
是一道板子，几分钟就切了，不会trie树的，我也没办法
在加边的同时判断是否为前缀
有两种情况
（1）这个串是别的串的前缀
（2）别的串是这个串的前缀
然后就是YES和NO是反的
还好有提示（要不然以我的情况要写一天）
下面给出代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int total=0; int trie[100006][12]; int vis[100006]; char x[10006]; int len; int n,f=0; void solve(){ int c=1; for(int i=1;i<=len;i++){ int s=x[i]-'0'; if(!trie[c][s]) trie[c][s]=++total;//trie树上加点 else if(i==len||vis[trie[c][s]]) f=1;//分类判断 c=trie[c][s]; } vis[c]=1;//表示以第c个点结尾的是一个整个的字符串 return ; } int main(){ int T; T=rd(); while(T--){ total=1; f=0;//赋初值 n=rd(); memset(trie,0,sizeof(trie)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ scanf("%s",x+1); len=strlen(x+1); solve(); } if(f==1) printf("NO "); else printf("YES "); } return 0; }