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

深度学习
• 阅读 50

2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解 一、题目解读 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 * |Σ|)),适用于中小规模数据场景。

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

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
LeetCode:(14. 最长公共前缀!!!!!)
题目:14\.最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串“”。示例1:输入:\“flower”,“flow”,“flight”\输出:“fl”示例2:输入:\“dog”,“racecar”,“car”\输出:“”
贾蔷 贾蔷
1个月前
蓝桥杯2023接龙数列(洛谷P9242)题解:动态规划与数字首尾匹配的完美应用
一、题目解读这道蓝桥杯省赛真题要求找出数字序列中最长的接龙子序列(每个数字的首位等于前一个数字的末位),并计算需要删除的最少数字个数。题目考察动态规划的实际应用能力,是理解数字特征处理和状态转移的典型案例。二、解题步骤1.处理n1的特殊边界情况2.读取输入
贾蔷 贾蔷
1个月前
2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略
一、题目解读2025年GESP七级考试中的“等价消除(洛谷P11965)”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”,是指子串中所有字符出现的次数均相同。题目需要高效算法解决,考验对字符串处理和状态压缩的掌握。二、解题思路采用位运算
贾蔷 贾蔷
2星期前
CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解
一、题目解读CSPJ2019年的“公交换乘”题目(洛谷P5661)要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券,而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记录,优化总费用。该问题考察对时间窗口与动态资源管理的理解,需
深度学习 深度学习
2星期前
洛谷1111题解:基于Kruskal算法与并查集的最小生成树实现
一、题目解读洛谷1111题是一道经典的图论问题,要求构建一个无向图的最小生成树,并输出其最大边权值。题目核心在于通过给定的边集合,找到连接所有节点的最小权值子集,同时保证无环。这通常涉及最小生成树算法(如Kruskal)的应用,需要高效处理边权重与节点连通
贾蔷 贾蔷
2星期前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
深度学习 深度学习
2星期前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
2星期前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
贾蔷 贾蔷
4天前
2024蓝桥杯省赛B组“传送阵”题解
一、题目解读2024年省B组“传送阵”题目要求处理一个包含n个节点的,节点间存在单向传输关系。每个节点i可传送至a中的最长路径问题,需考虑环的存在及节点间的连通性。二、解题思路1.预处理阶段使用标记法找出所有环,记录每个环的大小(即节点数)。2.统计最大环
贾蔷 贾蔷
3天前
洛谷1220题解:动态规划与区间DP优化解法
一、题目解读1220题要求计算在n个位置放置灯的情况下,通过关闭连续区间灯并移动至区间端点,使得总耗电量最小。需考虑灯的功率与位置差异,设计高效的求解最优策略。二、解题思路1.:定义状态dp:使用sum存储灯功率前缀和,简化区间电量计算。3.核心:○向左