题解：P9694 [GDCPC2023] New but Nostalgic Problem

· · 题解

Solution

Trie。

假设此时已经确定答案前三位为 \texttt{abc}，接下来确定第四位。

要求字典序最小，从 \texttt{a} \sim \texttt{z} 枚举第四位。

假设当前枚举到字母 \texttt{e}：

  1. 对于 \forall \texttt{abc}_{\texttt{a} \sim \texttt{e} } \dots 可选。因为他们 LCP 一定小于等于 \texttt{abce} \dots。
  2. 对于 \texttt{abc}_{\texttt{f} \sim \texttt{z}} \dots，如果存在那么每个顶多选一个。

举个例子：

如果我们选择大于等于两个 \texttt{abcf} \dots，那么此时最大 LCP 成为 \texttt{abcf} \dots，不再是 \texttt{abce} \dots。

  1. 剩下字符串可选情况维持原状。

以上，在合法情况下我们一定尽量多选。

如果此时我们已经可以选至少 k 个字符串，那么第四位确定为 \texttt{e}，否则继续向下枚举。

在确定第四位时，我们需要确定答案是否就为四位。

考虑我们现在已经确定答案为 \texttt{abce}，那么：

  1. 所有 \texttt{abce}_{\texttt{a} \sim \texttt{z}} \dots 字符串，我们每种只能最多选择一个。否则答案大于当前确定的答案。
  2. 剩下字符串可选情况维持原状。

如果此时我们能够选至少 k 个字符串，那么答案确定只有四位，否则向下枚举第五位。

重复直到可判定答案合法。

以上策略保证答案最优，即 LCP 最小。若存在比当前枚举的答案更优的合法方案，一定会在之前被枚举到。

在 Trie 上进行这一过程，时间复杂度为 O(c \times \sum len(s))，其中 c 为字符集大小。

Code

#include <bits/stdc++.h>

using namespace std;

int t;

#define maxn 1000005

int ed[maxn], cnt[maxn];

int tr[maxn][27], tot = 1;

void add(char *s, int len) {
    int p = 1;
    ++cnt[p];
    for (int i = 1; i <= len; ++i) {
        int u = s[i] - 'a' + 1;
        if (!tr[p][u]) {
            tr[p][u] = ++tot;
            memset(tr[tot], 0, sizeof tr[tot]); // 插入时顺便清空 trie
        }
        p = tr[p][u];
        ++cnt[p]; // 记录经过当前位置的字符串个数
    }
    ++ed[p]; // 记录从当前位置结束的字符串个数
    return;
}

char s[maxn];

void sol() {
    // 多测记得清空
    tot = 1;
    for (int i = 1; i <= 26; ++i)
        tr[1][i] = 0; // 清空首层
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        add(s, len); 
    }
    int p = 1;
    // 题解大部分写的是 dfs，这里用简单循环实现
    while (1) {
        int sum = ed[p];
        for (int i = 1; i <= 26; ++i)
            if (cnt[tr[p][i]])
                ++sum; // 下一位每个字符串最多选一个
        if (sum >= k) {
            // 判定答案合法
            for (int i = 1; i <= tot; ++i) {
                ed[i] = 0;
                cnt[i] = 0;
            }
            if (p == 1) // 在首层，即答案为空字符串
                printf("EMPTY");
            putchar('\n');
            // 已经找到最优合法答案，结束程序即可
            return;
        }
        for (int i = 1; i <= 26; ++i) {
            if (!cnt[tr[p][i]])
                continue;
            sum += cnt[tr[p][i]] - 1;
            // 之所以减一，因为上面已经每个算了一个
            if (sum >= k) {
                // 确定下一位字母
                k -= (sum - cnt[tr[p][i]]);
                // 把当前可选所有字符串数从 k 中减掉
                putchar((char)('a' + i - 1));
                // 已确定，直接输出即可
                p = tr[p][i];
                break; // 进入下一位的枚举
            }
        }
    }
    return;
}

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