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

题目大意

给定

n

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

思路

观察

修改一个字符串

s_k

的第

p

个字符时：

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

优化

对于字符串

s_i

和修改后的

s_k'

：

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

步骤

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

复杂度分析

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

代码

CPP

#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;
}

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

文章操作

题目大意

思路

观察

优化

步骤

复杂度分析

代码

相关推荐

评论

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