蓝桥杯 2023 省B 洛谷P9242题 解题思路和步骤

一、问题理解与建模分析

本题要求处理接龙数列的最长长度问题，核心在于识别数字序列的首位连接规律。根据题目描述，当某数字末位与后续数字首位相同时，可形成有效连接。我们需要建立数学模型：将每个数字抽象为具有首尾两个属性的节点，问题即转化为寻找最长符合条件的节点连接路径。

如何快速获取每个数字的首位数字？这涉及字符串处理技巧。对于输入数字n，可以通过转换为字符串后取首字符和末字符。数字123的首位分别是'1'和'3'。这个预处理步骤的时间复杂度直接影响整体算法效率，建议在O(1)时间内完成。

二、动态规划策略选择

采用动态规划算法是本问题的最优解，其关键在于状态定义。我们定义dp[i][j]表示前i个数字中以j结尾的最长接龙长度。但直接二维DP会超出内存限制，需要优化为滚动数组。改进方案是使用两个一维数组：prev数组记录上一轮状态，current数组更新当前轮次状态。

这种空间优化方法将空间复杂度从O(n10)降为O(10)，有效应对大规模数据。如何初始化状态数组？初始时所有数字结尾的长度都为0，遇到首个符合要求的数字时更新为1。这个初始化过程需要注意特殊测试用例，比如全0输入的情况。

三、代码注释

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

int main() {
    // 优化输入输出，提高处理速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;  // 输入数字的个数
    cin >> n;
    
    // dp数组：dp[i]表示以数字i(0-9)结尾的最长接龙序列长度
    vector<int> dp(10, 0);
    
    for (int i = 0; i < n; ++i) {
        string num;  // 当前数字的字符串表示
        cin >> num;
        
        // 获取数字的首位和末位数字
        int head = num[0] - '0';  // 首位数字
        int tail = num.back() - '0';  // 末位数字
        
        // 状态转移：当前数字可以接在相同head的数字后面
        // 更新以tail结尾的最长接龙序列长度
        dp[tail] = max(dp[tail], dp[head] + 1);
    }
    
    // 找出所有可能结尾中的最大值，即最长接龙序列长度
    int max_len = *max_element(dp.begin(), dp.end());
    
    // 输出需要删除的数字个数 = 总个数 - 最长接龙序列长度
    cout << n - max_len;
    
    return 0;
}

原文：蓝桥杯 2023 省B 洛谷P9242题 解题思路和步骤 C++实现带注释