「一本通 2.3 例 1」Phone List

题目描述

给定 $n$ 个长度不超过 $10$ 的数字串，判断是否存在两个串 $S,T$ 使 $S$ 是 $T$ 的前缀（两串相等也算）。多组数据：第一行组数 $T$ ，每组第一行 $n$ ，随后 $n$ 行是数字串；存在前缀对输出 NO，否则输出 YES（注意题面的反直觉对应）。数据范围 $1\le T\le 40$ ， $1\le n\le 10^4$ 。

样例：第一组 911, 97625999, 91125426 输出 NO（911 是 91125426 的前缀）；第二组 113, 12340, 123440, 12345, 98346 输出 YES。

思路

把所有串按字典序排序：若存在前缀对，则它们在排序中一定相邻，所以只需检查 $n-1$ 个相邻对。逐对判断前一串是否为后一串的前缀，命中即有前缀对，输出 NO，否则输出 YES。单组复杂度 $O(nL\log n)$ ， $L\le 10$ 为串长上限。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 12:43
# update_at: 2026-09-30 12:43

import sys
from itertools import pairwise


def has_prefix_pair(words: list[bytes]) -> bool:
    """判断是否存在两个串互为前缀：排序后只需看相邻两串（等串也算）。"""
    return any(b.startswith(a) for a, b in pairwise(sorted(words)))


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    T = int(next(data))

    for _ in range(T):
        n = int(next(data))
        words = [next(data) for _ in range(n)]
        # 有前缀对输出 NO，否则输出 YES（题面的反直觉对应关系）
        out.append("NO" if has_prefix_pair(words) else "YES")

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:19
 * update_at: 2026-10-06 00:19
 */

#include <algorithm>
#include <iostream>
#include <string>

typedef long long ll;

const int MAXN = 1e4 + 5; // 每组数据最多 1e4 个数字串

std::string word[MAXN]; // word[1..n] 保存当前这组的数字串

// 判断 a 是否为 b 的前缀（两串相等也算）
bool is_prefix(const std::string &a, const std::string &b) {
    if (a.size() > b.size()) return false;
    return b.compare(0, a.size(), a) == 0;
}

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

    int T;
    std::cin >> T;
    while (T--) {
        int n;
        std::cin >> n;
        for (int i = 1; i <= n; ++i) std::cin >> word[i];

        // 关键结论：若存在前缀对，排序后它们一定相邻，所以只需检查 n-1 个相邻对
        std::sort(word + 1, word + n + 1);

        bool found = false; // found = 是否存在一对前缀关系
        for (int i = 1; i < n; ++i) {
            if (is_prefix(word[i], word[i + 1])) {
                found = true;
                break;
            }
        }

        // 题面的反直觉对应：有前缀对输出 NO，否则输出 YES
        std::cout << (found ? "NO" : "YES") << "\n";
    }
    return 0;
}

「一本通 2.3 例 1」Phone List

目录

题目描述

思路

参考代码