首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#7355

电话号码(2022-12,六级) 给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如: Emergency 911 Alice…

电话号码(2022-12,六级)

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

Emergency 911

Alice 97 625 999

Bob 91 12 54 26

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

时间限制:1000

内存限制:65536

输入

第一行是一个整数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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5 + 10; struct Trie {   int c[10], s;   Trie() {     memset(c, 0, sizeof(c));     s = 0;   } } t[N]; int tot; void clear(int x) {   t[x].s = 0;   for (int i = 0; i &lt;= 9; i++)     if (t[x].c[i])       clear(t[x].c[i]), t[x].c[i] = 0; } char s[15]; bool bt(int x) {   int len = strlen(s + 1);   bool bk = false;   for (int i = 1; i &lt;= len; i++) {     int y = s[i] - '0';     if (!t[x].c[y])       t[x].c[y] = ++tot;     else if (i == len)       bk = true;     x = t[x].c[y];     if (t[x].s)       bk = true;   }   t[x].s++;   return bk; } int main() {   int T;   scanf("%d", &amp;T);   while (T--) {     bool bk = false;     clear(0);     tot = 0;     int n;     scanf("%d", &amp;n);     for (int i = 1; i &lt;= n; i++) {       scanf("%s", s + 1);       if (bk)         continue;       if (bt(0))         bk = true;     }     if (bk)       puts("NO");     else       puts("YES");   }   return 0; }</pre><p><span>  </span><br/></p>
这道题暂未补解析。