简答题
偏难
#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 <bits/stdc++.h>
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 <= 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 <= 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", &T);
while (T--) {
bool bk = false;
clear(0);
tot = 0;
int n;
scanf("%d", &n);
for (int i = 1; i <= 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>
这道题暂未补解析。