2024年蓝桥杯省赛B组前缀总分（洛谷P12124）：前缀总分详解

1天前比赛题解48

一、问题描述

给定N个字符串，定义字符串i和j的前缀相似度为它们的最长公共前缀长度LCP(i,j)。要求计算所有字符串对(i<j)的LCP之和，并允许修改任意一个字符串的任意一个字符（改为小写字母），求可能获得的最大总分值。

二、完整代码解析（含详细注释）

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 预处理所有字符串对的LCP（最长公共前缀）
vector<vector<int>> precompute_lcp(const vector<string>& strs) {
    int n = strs.size();
    vector<vector<int>> lcp(n, vector<int>(n, 0)); // n×n的LCP矩阵
    
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            int len = 0;
            // 逐字符比较直到不匹配或到达任一字符串末尾
            while (len < strs[i].size() && len < strs[j].size() 
                   && strs[i][len] == strs[j][len]) {
                len++;
            }
            lcp[i][j] = lcp[j][i] = len; // LCP是对称的
        }
    }
    return lcp;
}

// 计算当前LCP矩阵的总分
long long compute_total(const vector<vector<int>>& lcp) {
    long long total = 0;
    int n = lcp.size();
    // 只计算i<j的对，避免重复计算
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            total += lcp[i][j];
        }
    }
    return total;
}

// 主求解函数
long long solve(vector<string>& strs) {
    int n = strs.size();
    auto lcp = precompute_lcp(strs); // 预处理LCP
    long long original = compute_total(lcp); // 原始总分
    long long max_score = original; // 初始化最大分数
    
    // 尝试修改每个字符串的每个位置
    for (int i = 0; i < n; ++i) {
        string original_str = strs[i];
        vector<int> original_contrib(n, 0); // 记录原始贡献值
        
        // 预先计算当前字符串对其他所有字符串的原始贡献
        for (int j = 0; j < n; ++j) {
            if (j != i) original_contrib[j] = lcp[i][j];
        }
        
        // 遍历字符串的每个位置
        for (int pos = 0; pos < original_str.size(); ++pos) {
            char original_char = original_str[pos];
            
            // 尝试修改为其他25个小写字母
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == original_char) continue; // 跳过不修改的情况
                
                long long delta = 0; // 记录分数变化量
                // 计算对每个其他字符串的影响
                for (int j = 0; j < n; ++j) {
                    if (j == i) continue; // 不计算自己与自己的LCP
                    
                    // 新LCP长度不超过原始值和当前位置
                    int new_len = min(original_contrib[j], pos);
                    // 只有当原始LCP>=pos时才需要重新计算
                    if (new_len == pos) {
                        // 重新计算从pos开始的新LCP
                        while (new_len < strs[i].size() && new_len < strs[j].size()) {
                            char ci = (new_len == pos) ? c : strs[i][new_len];
                            if (ci != strs[j][new_len]) break;
                            new_len++;
                        }
                    }
                    delta += (new_len - original_contrib[j]); // 累计变化量
                }
                
                // 更新最大分数
                max_score = max(max_score, original + delta);
            }
        }
    }
    
    return max_score;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    vector<string> strs(n);
    for (int i = 0; i < n; ++i) cin >> strs[i];
    cout << solve(strs) << endl;
    return 0;
}