题解：P12124 [蓝桥杯 2024 省 B 第二场] 前缀总分

bilibili_daogu · 2025-10-30 22:28:52 · 题解

题目大意

给定 n 个小写字母字符串，定义前缀总分为所有字符串对的最长公共前缀长度之和。可以选择其中一个字符串修改其中一个字符，求修改后可能的最大前缀总分。

思路

观察

修改一个字符串 s_k 的第 p 个字符时：

• 只有与 s_k 配对的字符串对的 LCP 会发生变化。
• 其他字符串对之间的 LCP 保持不变。

优化

对于字符串 s_i 和修改后的 s_k'：

• 如果原 LCP < p：修改不影响，LCP 不变。
• 如果原 LCP \geq p：
  • 如果 s_i[p] = s_k'[p]：新 LCP = p + 1 + \text{后续匹配长度}。
  • 否则：新 LCP = p。

步骤

1. 预处理：计算所有字符串对的原始 LCP。
2. 计算原总分：V_0 = \sum_{i<j} \text{LCP}(s_i, s_j)。
3. 枚举修改：对每个字符串、每个位置、每个可能的字符进行尝试。
4. 快速计算：利用预处理信息快速计算新总分。
5. 取最大值：记录所有情况中的最大得分。

复杂度分析

• 预处理 LCP：O(n^2L)。
• 枚举修改：O(nL \cdot 26 \cdot n)。
• 总复杂度：O(n^2L \cdot 26)，在 n=200, L=200 时可接受。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    // 预处理所有字符串对的 LCP。
    vector<vector<int>> lcp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int len = min(s[i].size(), s[j].size());
            int k = 0;
            while (k < len && s[i][k] == s[j][k]) k++;
            lcp[i][j] = lcp[j][i] = k;
        }
    }
    // 计算原始总分。
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            total += lcp[i][j];
        }
    }
    // 计算每个字符串与其他字符串的 LCP 和。
    vector<int> sum_k(n, 0);
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (i != k) sum_k[k] += lcp[k][i];
        }
    }
    int ans = total;  // 不修改的情况。
    // 枚举修改的字符串、位置和新字符。
    for (int k = 0; k < n; k++) {
        int len = s[k].size();
        for (int p = 0; p < len; p++) {
            char old = s[k][p];
            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (ch == old) continue;
                int new_sum = 0;
                for (int i = 0; i < n; i++) {
                    if (i == k) continue;
                    if (lcp[k][i] < p) {
                        // 原 LCP 小于 p，修改不影响。
                        new_sum += lcp[k][i];
                    } else {
                        if (s[i][p] == ch) {
                            // 在 p 位置匹配成功，继续向后匹配。
                            int match = p + 1;
                            while (match < s[i].size() && match < len && s[i][match] == s[k][match]) {
                                match++;
                            }
                            new_sum += match;
                        } else {
                            // 在 p 位置不匹配。
                            new_sum += p;
                        }
                    }
                }
                // 更新答案。
                ans = max(ans, total - sum_k[k] + new_sum);
            }
        }
    }
    cout << ans;
    return 0;
}