跳转至

E - 新怀质问

基本信息

题目出处2023 广东省大学生程序设计竞赛
队伍通过率51/295 (17.3%)

题解

本题名称来自日文“新しい、でも懐かしい質問”(意为新的,但是令人怀念的问题),因为有人说命题人的题目都很有年代感...

考虑从左到右确定答案的每一位。我们举个例子来介绍这一过程。

假设我们已经确定了答案的前三位是 abc,接下来要确定第四位。为了让字典序尽量小,我们需要从 az 枚举第四位。

假设我们枚举到了 d,我们考虑已知答案为 abcd* 时,与已知答案为 abc* 时相比,能选择的字符串数量如何变化。

  • 所有 abc[a-d]* 都能选择,因为它们的最长公共前缀肯定小于等于 abcd*
  • 所有 abc[e-z]* 的字符串,原来答案是 abc* 的时候都能选择,现在每种字母只能选一个,否则比如 abce* 选了两个,那答案就至少是 abce > abcd* 了。
  • 剩下的字符串可选情况维持不变。

如果我们能选至少 \(k\) 个字符串,那么答案的第四位就是 d,否则我们要继续枚举 ef、...

确定了答案的第四位以后,我们还要确定答案是不是只有四位。考虑已知答案为 abcd 时,与已知答案为 abcd* 时相比,能选的字符串数量如何变化。

  • 所有 abcd[a-z]* 的字符串,原来答案是 abcd* 时都能选择,现在每种字母只能选一个,否则答案大于 abcd
  • 剩下的字符串可选情况维持不变。

如果我们能选至少 \(k\) 个字符串,那么答案就只有四位,否则继续枚举第五位。复杂度 \(\mathcal{O}(\sum |s|)\)

参考代码

 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define MAXLEN ((int) 1e6)
using namespace std;

int n, K;
char s[MAXLEN + 10];

// sz[i]:有几个字符串恰好被节点 i 代表
// tot[i]:以节点 i 为根的子树里一共有几个字符串
int nCnt, sz[MAXLEN + 10], tot[MAXLEN + 10], ch[MAXLEN + 10][26];

// 新建一个 trie 节点,返回节点编号
int newNode() {
    nCnt++;
    sz[nCnt] = tot[nCnt] = 0;
    memset(ch[nCnt], 0, sizeof(ch[nCnt]));
    return nCnt;
}

// 将 s 里保存的字符串加入 trie
void add() {
    int now = 1;
    tot[now]++;
    for (int i = 1; s[i]; i++) {
        int &c = ch[now][s[i] - 'a'];
        if (!c) c = newNode();
        tot[now = c]++;
    }
    sz[now]++;
}

void solve() {
    // 新建 trie 根节点,编号为 1
    nCnt = 0; newNode();

    scanf("%d%d", &n, &K);
    // 将每个字符串加入 trie
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        add();
    }

    // 逐位确定答案,now 表示目前已确定的答案前缀在 trie 上是哪个节点
    int now = 1;
    while (true) {
        // 判断答案是否就是 now 所在的节点
        // 首先,now 代表的字符串一定都可以选
        int t = sz[now];
        // 以 now 子节点为根的子树里,每棵子树最多选一个字符串
        for (int i = 0; i < 26; i++) if (tot[ch[now][i]]) t++;
        if (t >= K) {
            // 答案就是 now 所在的节点
            if (now == 1) printf("EMPTY");
            printf("\n");
            return;
        }

        // 枚举答案的下一个字母
        for (int i = 0; i < 26; i++) if (tot[ch[now][i]]) {
            // 现在以 now 子节点为根的子树里,每棵子树可以选任意个字符串
            t = t - 1 + tot[ch[now][i]];
            if (t >= K) {
                // 确定了下一个字母为 i
                K -= t - tot[ch[now][i]];
                now = ch[now][i];
                printf("%c", i + 'a');
                break;
            }
        }
    }
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}