题目 总觉得那个电话？？（大雾）有点滑稽。

题目大意

给定n个长度不超过10的数字串。

问其中是否存在两个数字串S，T。

使得S是T的前缀，多组数据。

对于100%的数据，1<=t<=40，1<=n<=10^4。

题目分析

一边建树一边做。

两种情况：

如果这个单词建树时没有插入任何新节点，那么这个单词是别的单词的前缀如果这个单词建树时经过的某个节点是某个单词的结尾，那么以这个单词结尾的单词是这个单词的前缀

我再说一遍我不是在绕口令。严肃脸。

以上。

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int len=0,kkk; struct node{int son[20],end;}tr[6000010]; void bt(char s[],int ss) { int now=1; bool q=false;//q用来判断是否符合情况1 for(int i=1;i<=ss;i++) { if(tr[now].son[s[i]-'0'])//第2种情况 { now=tr[now].son[s[i]-'0']; if(tr[now].end) kkk=false; } else { len++; tr[now].son[s[i]-'0']=len; now=len; tr[now].end=0; q=true; //如果插入了新节点，那么不符合情况1 } } tr[now].end++; if(!q) kkk=false;//符合情况1 } int main() { int t; scanf("%d",&t); while(t--) { memset(tr[1].son,0,sizeof(tr[1].son)); kkk=true; int n; scanf("%d",&n); for(int i=1;i<=n;i++) { char s[20]; scanf("%s",s+1); bt(s,strlen(s+1)); } if(kkk) printf("YES\n"); else printf("NO\n"); } return 0; }

双倍快乐！Immediate Decodability