2021 年 12 月青少年软编等考 C 语言六级真题解析

T1. 电话号码

题目链接：SOJ D1137

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

Emergency 911
Alice 97 625 999
Bob 91 12 54 26

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

时间限制：1 s
内存限制：64 MB

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

  2
  3
  911
  97625999
  91125426
  5
  113
  12340
  123440
  12345
  98346
  

• 样例输出

  NO
  YES
  

思路分析

此题考查哈希算法，属于基础题。

可以使用 $\mathtt{STL}$ 中的 $\mathtt{map}$ 来实现哈希。先将所有电话号码加入哈希表，并记录出现次数。然后依次检测输入的每个电话号码 $x$，如果它自身出现次数超过 $1$ 次，则说明电话号码不一致。否则就枚举它的所有前缀子串，在 $\mathtt{map}$ 中检测是否已经出现过，如果出现过，则说明存在一个电话号码是该号码的前缀，即电话号码不一致。

/*
 * Name: T1.cpp
 * Problem: 电话号码
 * Author: Teacher Gao.
 * Date&Time: 2025/03/12 17:18
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t, n;
    cin >> t;

    while (t--) {
   
        LL a[10005];
        map<LL, int> mp;
        string ans = "YES\n";

        cin >> n;
        for (int i = 1; i <= n; i++) {
   
            cin >> a[i];
            mp[a[i]]++;
        }

        for (int i = 1; ans == "YES\n" && i <= n; i++) {
   
            if (mp[a[i]] > 1) {
   
                ans = "NO\n";
                break;
            }
            while (a[i]) {
   
                a[i] /= 10;