F1. Representative Sampling - 题解
比赛与标签
比赛: ABBYY Cup 2.0 - Hard 标签: Trie, Tree DP, Knapsack DP 难度: *1800
题目大意喵~
主人，这道题是这样子的呐：我们有 n 个蛋白质字符串，需要从里面挑选出 k 个，组成一个最具“代表性”的子集。
那“代表性”是什么呢？它被定义为，我们选出的这 k 个字符串中，所有可能的字符串对 (a_i, a_j) 的最长公共前缀 (LCP) 的长度之和。
我们的任务就是找到一个大小为 k 的子集，让这个代表性的总和达到最大值！然后把这个最大值告诉大家就好啦，喵~
举个例子：如果我们选了 {"abc", "abd", "abe"}，那么：
- LCP("abc", "abd") = 2 (前缀是 "ab")
- LCP("abc", "abe") = 2 (前缀是 "ab")
- LCP("abd", "abe") = 2 (前缀是 "ab") 总的代表性就是 2 + 2 + 2 = 6 啦！
解题思路，一起动动脑筋吧！
看到“最长公共前缀”，本猫娘的DNA就动了！这种问题，十有八九都和我们的好朋友——**Trie树（前缀树）**有关哦！
1. 为什么是Trie树呢？
Trie树有一个非常棒的性质：所有经过同一个节点的字符串，都共享这个节点所代表的前缀。比如说，所有经过代表 "ab" 的节点的字符串，都必然以 "ab" 开头。这个性质简直是为我们量身定做的呀！
2. 换个角度看问题
我们要求的代表性是 ∑ LCP(s_i, s_j)。直接枚举 k 个字符串的组合太慢了，肯定会超时的说。
所以，我们不妨换个思路来计算贡献。对于一个长度为 L 的公共前缀，它会为一对字符串贡献 L。这等价于，这个公共前缀的每一个字符（从第1个到第L个），都为这对字符串贡献了 1。
这启发我们，可以把贡献拆分到Trie树的每个节点上！
- Trie树中的每个节点
u都代表一个前缀。 - 假设我们从所有字符串中挑选了
k个，其中有c个字符串的路径经过了节点u。 - 这
c个字符串两两之间都拥有u所代表的那个公共前缀。它们能组成C(c, 2) = c * (c - 1) / 2个字符串对。 - 对于节点
u本身（也就是前缀的最后一个字符），它为这C(c, 2)对字符串的LCP长度都贡献了1。
所以，总的代表性就可以表示为： Total Representativity = ∑ (对于Trie中所有节点 u) C(c_u, 2) 这里的 c_u 是指我们选出的 k 个字符串中，有多少个经过了节点 u。
3. 树上动态规划 (Tree DP)！
现在问题就转化成：我们要在Trie树上为每个节点 u 分配选择名额 c_u，总共选择 k 个字符串（叶子节点），使得 ∑ C(c_u, 2) 最大。
这不就是经典的树上背包问题嘛！喵~
我们可以定义一个DP状态： dp[u][i] 表示：在以节点 u 为根的子树中，选择 i 个字符串（这些字符串的路径都经过u的子树），能够获得的最大代表性贡献（仅计算 u 的子树内部）。
4. DP的转移过程
我们用深度优先搜索（DFS）的方式来计算DP。对于一个节点 u：
初始化: 我们先只考虑那些恰好在节点
u结束的字符串。假设有ends_here[u]个这样的字符串。我们可以从中选择j个 (0 <= j <= ends_here[u])。此时，dp[u][j]初始化为 0，因为还没有合并子树的贡献。合并子节点 (背包合并): 遍历
u的每一个子节点v。我们已经通过递归计算出了dp[v]表。现在要把子节点v的信息合并到父节点u上。- 这就像合并两个背包。我们创建一个临时的
new_dp表。 - 如果我们从
u当前已合并的部分选择了j个字符串（值为dp[u][j]），并从子节点v的子树中选择了l个字符串（值为dp[v][l]），那么我们就可以凑成一个j + l个字符串的选择方案。 - 新的贡献是
dp[u][j] + dp[v][l]。我们用这个值去更新new_dp[u][j+l]，取最大值。 new_dp[j + l] = max(new_dp[j + l], dp[u][j] + dp[v][l])- 遍历完所有
j和l后，用new_dp更新dp[u]。
- 这就像合并两个背包。我们创建一个临时的
计算当前节点的贡献: 当所有子节点都合并完毕后，
dp[u][i]就表示从u的整个子树里选i个字符串，来自子树内部的最大贡献。现在，我们要加上节点u自己的贡献了！这i个字符串都经过了节点u，所以它们之间会产生C(i, 2)对共享u所代表前缀的组合。- 所以，我们更新
dp[u][i] = dp[u][i] + C(i, 2)。
- 所以，我们更新
这样，从叶子节点一路向上计算，最终我们就能得到根节点（代表空前缀）的DP表 dp[root]。
5. 最终答案
dp[root][k] 就是我们想要的答案吗？等一下，猫娘的胡须感觉到了一个陷阱！
我们的计算方法把根节点（深度为0，代表空前缀）的贡献也算进去了。根节点会被所有 k 个选中的字符串经过，所以会加上 C(k, 2)。但题目要求的是最长公共前缀的长度之和，长度为0的前缀不应该有贡献。
所以，最终的答案应该是 dp[root][k] - C(k, 2)。这样就完美啦！
代码实现喵！
下面就是把我们的思路变成代码啦！本猫娘已经加上了详细的注释，主人可以轻松看懂哦！
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
// 用 -1 表示一个无效或不可达的DP状态，喵~
const long long UNREACHABLE = -1;
// Trie树节点的结构体
struct TrieNode {
int children[26];
int count; // 有多少个原始字符串的路径经过此节点
int ends_here; // 有多少个原始字符串在此节点结束
TrieNode() : count(0), ends_here(0) {
std::fill(children, children + 26, 0);
}
};
std::vector<TrieNode> trie;
int next_node_idx = 1; // 根节点在索引1的位置，喵
// 初始化Trie树，预分配足够的空间
void init_trie(int n, int max_len) {
// 最大可能的节点数：根节点 + n * max_len。再加一点点缓冲~
trie.resize(2 + (long long)n * max_len);
}
// 向Trie树中插入一个字符串
void insert(const std::string& s) {
int curr = 1; // 从根节点开始
trie[curr].count++;
for (char ch : s) {
int c = ch - 'a';
if (trie[curr].children[c] == 0) {
trie[curr].children[c] = ++next_node_idx;
}
curr = trie[curr].children[c];
trie[curr].count++;
}
trie[curr].ends_here++;
}
// 计算组合数 C(n, 2)，也就是 n*(n-1)/2
long long combinations2(int n) {
if (n < 2) return 0;
return (long long)n * (n - 1) / 2;
}
// Trie上的动态规划函数！
// 返回一个DP表: dp[i] = 从该子树选择i个字符串能获得的最大代表性
std::vector<long long> solve(int u, int k_max) {
// dp_u[i] 存储的是，从u的子树中选择i个字符串（包括在u结束的），
// 它们在u的子树内部产生的最大贡献。
std::vector<long long> dp_u;
dp_u.assign(trie[u].ends_here + 1, 0); // 1. 初始化：只考虑在u结束的字符串
int current_total_strings = trie[u].ends_here;
// 2. 遍历所有子节点，进行背包合并
for (int i = 0; i < 26; ++i) {
int v = trie[u].children[i];
if (v == 0) continue; // 如果没有这个子节点，就跳过
// 递归地解决子问题
std::vector<long long> child_dp = solve(v, k_max);
int child_string_count = trie[v].count;
// 创建一个新的DP表来存储合并结果
int new_total_strings = current_total_strings + child_string_count;
std::vector<long long> next_dp_u(new_total_strings + 1, UNREACHABLE);
// 背包合并的核心逻辑
for (int j = 0; j <= current_total_strings; ++j) {
if (dp_u[j] == UNREACHABLE) continue;
for (int l = 0; l <= child_string_count; ++l) {
if (l >= child_dp.size() || child_dp[l] == UNREACHABLE) continue;
int total_chosen = j + l;
if (total_chosen > k_max) continue; // 剪枝：选择的总数不能超过k
long long new_val = dp_u[j] + child_dp[l];
if (next_dp_u[total_chosen] == UNREACHABLE || new_val > next_dp_u[total_chosen]) {
next_dp_u[total_chosen] = new_val;
}
}
}
// 用合并后的结果更新当前节点的DP表
dp_u = std::move(next_dp_u);
current_total_strings = new_total_strings;
}
// 3. 加上当前节点u自身的贡献
for (int i = 0; i <= current_total_strings; ++i) {
if (i >= dp_u.size()) break;
if (dp_u[i] != UNREACHABLE) {
// 从u的子树中选了i个字符串，它们都经过u，所以贡献C(i,2)
dp_u[i] += combinations2(i);
}
}
return dp_u;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, k;
std::cin >> n >> k;
int max_len = 0;
std::vector<std::string> proteins(n);
for (int i = 0; i < n; ++i) {
std::cin >> proteins[i];
if ((int)proteins[i].length() > max_len) {
max_len = proteins[i].length();
}
}
// 构建Trie树
init_trie(n, max_len);
for (const auto& s : proteins) {
insert(s);
}
// 从根节点开始进行DP
std::vector<long long> dp_root = solve(1, k);
long long result = 0;
if (k < dp_root.size() && dp_root[k] != UNREACHABLE) {
// solve函数计算的结果包含了根节点（空前缀）的贡献
// 题目定义的是非空前缀的长度和，所以要减去根节点的贡献
result = dp_root[k] - combinations2(k);
}
std::cout << result << std::endl;
return 0;
}复杂度分析
时间复杂度: O(N * L + N²) 的说。
- 构建Trie树需要 O(N * L) 时间，其中 N 是字符串数量，L 是最大字符串长度。
- 树上DP的部分是核心。这是一个树上背包问题，其经典复杂度是 O(N²)，因为在合并子树时，最坏情况下会将两个大小为
s1和s2的DP表合并，复杂度为O(s1 * s2)。在整棵树上，总的计算量是 O(N²)。 - 所以总时间复杂度是 O(N * L + N²)，对于 N=2000 来说是可以通过的！
空间复杂度: O(N * L) 的说。
- Trie树本身最多有 O(N * L) 个节点，这是空间占用的主要部分。
- DP表在递归过程中会创建，但由于我们是一层层返回的，所以同时存在的DP表所占空间不会超过 O(N * L)。
知识点与总结
这次的冒险让我们学会了好多东西呀，喵~
- Trie (前缀树): 解决字符串前缀问题的超级利器！一定要牢牢记住它的结构和性质哦。
- 问题转化: 这是解题的灵魂！把
∑ LCP转化为在Trie树上∑ C(c_u, 2)是最关键的一步。这种贡献法思想在很多计数题和最优解问题中都很有用。 - 树上背包 (Tree DP with Knapsack Merge): 在树形结构上选择有限个物品以达到最优解的经典模型。核心就是递归解决子问题，然后通过背包合并的方式将子问题的解合并到父节点。
- 注意边界和定义: 一定要仔细读题！这次我们就发现了“空前缀”这个小陷阱。差之毫厘，谬以千里，喵~
希望本猫娘的讲解对主人有帮助！如果还有其他问题，随时可以再来找我玩哦！一起加油，变得更强吧！Nya~