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

15303105423

一、问题理解与建模分析

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

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

二、动态规划策略选择

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

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

三、关键代码实现步骤

代码实现分为三个主要模块：输入处理、DP状态转移、结果输出。使用快速IO优化输入输出，避免超时问题。对于每个输入数字，同步记录其首位数字和末位数字。核心代码如下：

string s = to_string(num);
char head = s[0], tail = s.back();

动态规划转移方程的实现需要特别注意状态继承关系。每次处理新数字时，其可能贡献的链长是之前同首位的最大链长+1，同时需要维护当前末位数字对应的最大值。这种双重维护机制确保了时间复杂度控制在O(n)级别。

四、代码注释

C++

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

五、时间复杂度优化验证

通过大样例测试验证算法效率，在n=1e5量级的数据下仍能保持线性时间复杂度。使用预处理缓存数字的首尾值，避免了重复计算。对比暴力解法O(n²)的时间复杂度，本方案的优化效果显著。

实际测试中发现，字符串转换操作的时间消耗占比较大。是否可以考虑数值运算代替字符串操作？通过数学方法提取首尾数字。但实验证明当n≤1e5时，字符串处理方式在C++中仍然高效，且代码更易维护。

来源：竞赛学习