当前位置:首页 > 蓝桥杯 > 2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解

2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解

2个月前 (06-23)

2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解 蓝桥杯省赛  前缀总分 LCP算法 动态规划 字符串优化 第1张

一、题目解读

2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理动态规划能力,需高效计算LCP并优化得分策略。

二、解题思路

1. 核心算法:通过预处理计算任意两字符串的LCP,存储于二维矩阵中。

2. 总分计算:利用LCP矩阵,遍历所有字符串对求和。

3. 优化策略:对每个字符位置,迭代替换所有小写字母,动态计算替换后的LCP变化,更新最大得分。

4. 关键逻辑:移动字符仅影响其后的LCP值,通过前缀贡献数组记录原LCP,快速计算替换后的新LCP。

三、解题步骤解析

1. 预处理LCP矩阵:

    双循环遍历字符串对,逐字符比较直至不同,记录LCP值并对称填充矩阵。

2. 初始总分计算:

    利用LCP矩阵,累加所有非对角线元素得到原始总分。

3. 迭代优化得分:

    遍历每个字符串的每个字符位置,替换为其他小写字母。

    计算替换后的新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));  
    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; // 对称赋值  
        }  
    }  
    return lcp;  
}  

// 计算LCP总分  
long long compute_total(const vector<vector<int>>& lcp) {  
    long long total = 0;  
    int n = lcp.size();  
    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); // 预处理  
    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); // 记录原LCP贡献  
        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];  
            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; // 跳过自身  
                    int new_len = min(original_contrib[j], pos); // 替换后的前缀长度  
                    if (new_len == pos) {  
                        while (new_len < strs[i].size() && new_len < strs[j].size()) {  
                            if (strs[i][new_len]!= c || strs[j][new_len]!= c) break;  
                            new_len++; // 扩展新LCP  
                        }  
                    }  
                    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; 
}

注释说明:

    通过precompute_lcp高效计算LCP矩阵,减少重复计算。

    compute_total利用矩阵非对角线元素求和。

    主函数迭代每个字符位置替换,动态计算新LCP并累加差值,维持最大值。

五、总结

该解法通过预处理LCP矩阵降低时间复杂度,结合动态规划思想迭代字符替换,高效求解最大总分。核心在于理解LCP对总分的影响范围(仅后续字符),并通过前缀贡献数组优化替换后的LCP计算。算法复杂度主要集中于预处理(O(N^2 * M))和迭代替换(O(N * M * |Σ|)),适用于中小规模数据场景。


原创内容 转载请注明出处

分享给朋友:

相关文章

牛客DP41精讲:当背包必须装满时,你的状态转移方程该如何调整?

牛客DP41精讲:当背包必须装满时,你的状态转移方程该如何调整?

题目重解我们面对一个经典背包问题的变体:给定n个物品,每个物品有重量w和价值v,背包容量为V。需要回答两个问题:1) 普通情况下能获得的最大价值;2) 必须恰好装满背包时的最大价值(若无法装满则输出0...

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

一、题目解读    2024年GESP(青少年软件编程能力等级考试)五级中的“武器强化”(洛谷平台题目编号B4071)是一道典型的算法优化问题。题目要求通过合理...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

一、题目解读CSP-J 2019年的“公交换乘”题目(洛谷P5661)要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券,而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记...

LeetCode 2222题解析:高效统计"010"与"101"子序列数量的算法优化

LeetCode 2222题解析:高效统计"010"与"101"子序列数量的算法优化

一、题目解读题目要求计算给定字符串中包含"010"或"101"子序列的数量。关键难点在于高效遍历所有子序列,避免重复计算。传统暴力解法时间复杂度O(n^3)会超...

牛客网288555题解题指南:动态规划求解小红的暑假(附代码解析)

牛客网288555题解题指南:动态规划求解小红的暑假(附代码解析)

一、题目解读牛客网288555题要求解决一个组合数学问题:有三位朋友,每天需邀请其中一位参加聚会,但不能连续两天邀请同一位朋友。给定天数n,求满足条件的不同邀请方案总数。题目考察动态规划、状态转移及组...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。