夺宝网站制作/优化器

怎么说呢,这题是树的简单应用,基本只要写完运行无错误是可以一遍AC的.再加上
今晚发烧,身体很不舒服,就迷迷糊糊的把这题给写了.

4089:电话号码

总时间限制: 1000ms 内存限制: 65536kB

描述
给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：

Emergency 911
Alice 97 625 999
Bob 91 12 54 26

在这个例子中，我们不可能拨通Bob的电话，因为Emergency的电话是它的前缀，当拨打Bob的电话时会先接通Emergency，所以这些电话号码不是一致的。

输入
第一行是一个整数t，1 ≤ t ≤ 40，表示测试数据的数目。
每个测试样例的第一行是一个整数n，1 ≤ n ≤ 10000，其后n行每行是一个不超过10位的电话号码。
输出
对于每个测试数据，如果是一致的输出“YES”，如果不是输出“NO”。

样例输入
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

样例输出
NO
YES

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;int t, n, flag;struct data
{char str[11];
}d[10010];struct tree
{char val;bool tail;tree *son[10];tree(){tail = false;for(int i=0;i<10;i++)son[i] = NULL;}
};void insert(tree *&root,char *a)
{int len = strlen(a);tree *t = new tree;t = root;if(root == NULL){root = new tree;//新建头结点}for(int i=0;i<len;i++){if(t->son[a[i]-'0'])//有重合{if(t->son[a[i]-'0']->tail)flag = 1;}else{tree *temp = new tree;temp->val = a[i];t->son[a[i]-'0'] = temp;}t = t->son[a[i]-'0'];if(i == len-1)//这是某个电话号码的最后一位t->tail = true;}
}bool cmp(data a,data b)
{return strcmp(a.str,b.str)<0;
}int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);tree *root = new tree;flag = 0;//判断是否有重合的for(int i=0;i<n;i++)scanf("%s",&d[i].str);sort(d,d+n,cmp);for(int i=0;i<n;i++){insert(root,d[i].str);}if(flag)printf("NO\n");elseprintf("YES\n");}return 0;
}