2023年蓝桥杯c++国赛拼数字

<think>我们被要求回答关于2023年蓝桥杯C++国赛题目“拼数字”的解析。根据引用[1]和[3]提供的代码片段，我们可以推断题目的大致内容。 引用[1]中提到了一个动态规划解法，用于计算一个由1到2023的数字拼接而成的字符串中，子序列"2023"出现的次数（或者类似的计数）。但题目名称是“拼数字”，而引用[3]中则有一个名为“拼数字”的题目，但代码中处理的是删除数字使得相邻数字首尾相连的问题。 然而，用户特别询问“拼数字”题目，我们需要从引用[3]中提取信息。引用[3]的代码注释提到：“这种解法是假定一定含有首元素才是最优解，但其实可能首元素也会被删除”，并且代码中处理了一个序列，每个元素是一个数字（可能是多位数），然后检查相邻两个数字，前一个数字的末位和后一个数字的首位是否相等，如果不相等则删除（计数加一），否则保留并更新前一个数字的末位。 因此，我们可以推断“拼数字”题目的描述大致如下： 题目描述：给定一个由n个正整数组成的序列，要求删除一些数字，使得剩下的序列满足：对于任意相邻的两个数字，前一个数字的末位等于后一个数字的首位。求最少删除的数字个数。 引用[3]中的代码思路： 1. 读取整数n，然后读取n个整数存入数组dele。 2. 初始化prev_tail为第一个数字的末位（dele[0]%10）。 3. 从第二个数字开始遍历： 当前数字的末位：now_tail = dele[i] % 10 当前数字的首位：通过一个函数func（即不断除以10直到只剩一位）得到now_head 如果当前数字的首位now_head不等于前一个数字的末位prev_tail，那么表示这两个数字不能相邻，需要删除当前数字（ret++），并且不更新prev_tail（因为当前数字被删除了，下一个数字的前一个数字还是原来的那个）。 否则，不删除，更新prev_tail为当前数字的末位（now_tail），然后继续。 但是，这个解法有一个问题：它假定第一个数字一定保留，并且从第一个数字开始向后匹配。然而，题目要求的是最少删除数，可能第一个数字也需要被删除。因此，这个解法可能不是最优的。 实际上，这个问题可以转化为：求最长的满足条件的子序列长度，然后用总数减去这个长度就是最少删除数。满足条件的子序列需要满足：对于子序列中相邻的两个数，前一个数的末位等于后一个数的首位。 因此，我们可以使用动态规划： 设dp[i]表示以第i个数字为结尾的最长满足条件的子序列长度。 转移方程：dp[i] = max{ dp[j] + 1 }，其中j从0到i-1，并且要求第j个数字的末位等于第i个数字的首位。 同时，我们也可以单独以第i个数字作为一个子序列，此时长度为1。 那么，最终的最长子序列长度就是max(dp[i])，i从0到n-1。 最少删除数字个数 = n - 最长子序列长度。 但是，引用[3]中的代码采用了一种贪心策略，即从第一个开始，能保留就保留，不能保留就删除。这种贪心策略不一定得到最优解。 例如，考虑序列：12, 23, 34, 45, 25。按照贪心策略： 第一个数字12，末位为2。 第二个数字23，首位为2（等于2），保留，更新末位为3。 第三个数字34，首位为3（等于3），保留，更新末位为4。 第四个数字45，首位为4（等于4），保留，更新末位为5。 第五个数字25，首位为2，不等于5，删除。 所以保留4个，删除1个。 但最优解可能是：12, 25（12的末位2等于25的首位2，25的末位5，后面没有了）-> 长度为2；或者23,34,45（长度3）？实际上，23,34,45是连续的，长度为3；而12,25也是连续的，长度为2。所以最长子序列长度是3，删除2个。 因此，我们需要用动态规划来求解。下面我们给出动态规划的解法。 步骤： 1. 预处理每个数字的首位和末位。 2. 初始化dp数组，dp[i] = 1（每个数字自身构成一个序列）。 3. 遍历每个数字i，对于每个i，遍历j从0到i-1： 如果第j个数字的末位等于第i个数字的首位，那么可以更新dp[i] = max(dp[i], dp[j]+1) 4. 找到dp数组中的最大值max_len。 5. 答案 = n - max_len。 注意：题目中数字可能很大，但n不会太大（蓝桥杯一般n<=10^5？但本题中n是数字个数，题目没有给出，但根据引用[3]的代码，n是输入的第一个整数，所以需要根据题目数据范围设计）。 但是，引用[3]的代码中n的范围是多少？代码中只是简单读取n，然后循环n次。所以我们可以假设n在10^5以内。 然而，动态规划的双重循环会导致O(n^2)的时间复杂度，对于10^5的数据会超时。因此，我们需要优化。 优化思路： 我们注意到，状态转移时，我们只关心以某个末位数字结尾的子序列的最大长度。因此，我们可以设f[k]表示以末位数字为k的子序列的最大长度（k是0到9的数字）。 步骤： 初始化：f[0..9] = 0 遍历每个数字i： 设当前数字的首位为a，末位为b。 那么，以当前数字结尾的最长子序列长度可以是：1（单独自己）或者f[a]+1（即前面末位为a的子序列后面接上这个数字，因为当前数字的首位a等于前面子序列最后一个数字的末位a，而前面子序列的末位a我们恰好用f[a]记录了）。 然后，我们用这个值去更新f[b]：f[b] = max(f[b], 上面计算的值) 同时，我们也可以用一个变量记录全局最大值。 注意：这里我们并没有考虑同一个数字只能使用一次，但题目中每个数字是独立的，我们按顺序使用，所以不会重复使用同一个数字。 但是，这里有一个问题：同一个数字可能被多次更新，而且我们要求的是以当前数字为结尾，所以每次更新f[b]时，我们只关心当前数字之前的状态。 因此，算法如下： max_len = 0 f[0..9] = 0 遍历每个数字（按顺序）： a = 当前数字的首位 b = 当前数字的末位 // 当前数字可以接在末位为a的子序列后面，形成末位为b的子序列 current = max(1, f[a] + 1) // 因为至少可以单独作为一个序列 // 更新f[b]：我们希望f[b]记录的是末位为b的子序列的最大长度，所以用current更新 if current > f[b]: f[b] = current // 更新全局最大值 if current > max_len: max_len = current 答案 = n - max_len 这个算法的时间复杂度是O(n)，因为每个数字只处理一次。 举例验证：序列[12, 23, 34, 45, 25] 数字1: 12 -> a=1, b=2 current = max(1, f[1]+1) = max(1,0+1)=1 更新f[2]=1, max_len=1 数字2: 23 -> a=2, b=3 current = max(1, f[2]+1)=max(1,1+1)=2 更新f[3]=2, max_len=2 数字3: 34 -> a=3, b=4 current = max(1, f[3]+1)=max(1,2+1)=3 更新f[4]=3, max_len=3 数字4: 45 -> a=4, b=5 current = max(1, f[4]+1)=max(1,3+1)=4 更新f[5]=4, max_len=4 数字5: 25 -> a=2, b=5 current = max(1, f[2]+1)=max(1,1+1)=2 因为f[5]=4>2，所以不更新f[5]（注意：我们要求最大值，所以如果current比f[b]大才更新，否则保留大的） 所以f[5]还是4，max_len=4 这样得到的最长子序列长度是4？但实际序列是12,23,34,45（长度为4）吗？但是12的末位是2，23的首位是2（匹配），23的末位3和34的首位3匹配，34的末位4和45的首位4匹配。所以确实有长度为4的子序列。 但是，我们再看另一个子序列：25可以接在12后面（12的末位2和25的首位2匹配），形成12,25（长度为2）。但是按照我们的算法，25来的时候，f[2]是1（因为12的末位是2，所以f[2]=1），所以25的current=1+1=2，然后更新f[5]=max(4,2) -> 因为之前45已经更新f[5]=4，所以25不会更新f[5]。所以全局最大值max_len=4。 因此，我们得到最少删除数=5-4=1。但是，实际上我们有一个长度为4的子序列（12,23,34,45）和一个长度为2的子序列（12,25），但最长的是4，所以删除1个（25）即可。所以答案正确。 但是，这个算法得到的子序列并不一定是连续的？注意，题目要求子序列（不要求连续）？题目要求删除一些数字后剩下的序列满足相邻条件，所以剩下的数字在原序列中不一定连续？但是，题目没有明确是否连续，但根据题意，删除后剩下的序列按原顺序排列，所以是子序列（不一定连续）。 然而，我们的动态规划算法允许跳过中间的数字，因为我们在遍历每个数字时，可以接在任意一个末位为a的子序列后面，不管这个子序列的最后一个数字在原序列中是否在当前数字之前（但必须按顺序，所以我们按顺序遍历，前面的数字已经处理过了）。 因此，这个算法是可行的。 但是，我们再看一个例子：序列[12, 25, 23, 34, 45] 数字1:12 -> a=1,b=2 -> f[2]=1, max_len=1 数字2:25 -> a=2,b=5 -> current=f[2]+1=2 -> f[5]=2, max_len=2 数字3:23 -> a=2,b=3 -> current=f[2]+1=2 -> 更新f[3]=2, max_len=2 数字4:34 -> a=3,b=4 -> current=f[3]+1=3 -> 更新f[4]=3, max_len=3 数字5:45 -> a=4,b=5 -> current=f[4]+1=4 -> 更新f[5]=4（因为4>2，所以覆盖掉25得到的2），max_len=4 所以最长子序列长度=4，删除1个（25或23？）。但实际上，我们可以得到子序列12,23,34,45（长度为4），而25被跳过。所以正确。 因此，我们给出“拼数字”题目的解析： 题目：给定n个正整数，求最少删除多少个数字，使得剩下的序列满足：对于任意相邻的两个数，前一个数的末位等于后一个数的首位。 解析：使用动态规划，用f[k]表示当前以末位数字k结尾的子序列的最大长度。遍历每个数字，计算其首位a和末位b，然后更新f[b] = max(f[b], f[a]+1)，同时更新全局最大长度。最后，最少删除个数为n减去全局最大长度。 代码实现（C++）： 注意：需要预处理每个数字的首位和末位。 求首位：可以不断除以10直到小于10（或者用字符串取第一位，但用数学方法也可以）。 例如： int first_digit(long long x) { while (x >= 10) x /= 10; return x; } 末位：x % 10。 代码框架： #include <iostream> #include <vector> #include <algorithm> using namespace std; int first_digit(long long x) { while (x >= 10) x /= 10; return x; } int main() { int n; cin >> n; vector<long long> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } // f[k]表示以末位数字k结尾的子序列的最大长度，k从0到9 vector<int> f(10, 0); int max_len = 0; for (int i = 0; i < n; i++) { long long num = nums[i]; int a = first_digit(num); int b = num % 10; int current = max(1, f[a] + 1); // 至少可以单独作为一个序列 if (current > f[b]) { f[b] = current; } if (current > max_len) { max_len = current; } } cout << n - max_len << endl; return 0; } 但是，注意：这个动态规划中，我们更新f[b]时，并没有考虑同一个数字可能被多次使用的情况？不会，因为我们按顺序处理每个数字，每个数字只用来更新一次。 然而，有一个细节：当我们更新f[b]时，这个更新会立即影响后面的数字。例如，如果后面有多个数字的首位等于b，那么它们都可以利用这个更新后的f[b]来更新。这是正确的，因为子序列允许不连续（只要顺序不变）。 因此，我们按照上述方法即可。 但是，引用[3]中的代码为什么没有用动态规划呢？可能是因为题目数据范围较小，或者题目描述有差异？或者他们采用贪心策略是因为题目要求连续子序列？引用[3]的代码中，它只检查相邻的两个数字，并且是连续的（没有跳过），所以它实际上求的是连续满足条件的子序列？但题目要求的是删除后剩下的序列满足相邻条件，所以剩下的数字在原序列中不一定连续相邻（可以跳过中间删除的），所以应该是不连续的子序列。因此，引用[3]的代码是错误的（它只考虑了连续的情况，而且贪心策略也不对）。 所以，我们这里提供的动态规划解法应该是正确的。 另外，引用[1]中提到的动态规划是另一个题目（关于字符串中找子序列"2023"的计数），与本题无关。 总结：用户询问的“拼数字”题目，我们根据引用[3]的代码推测出题目，并给出了正确的动态规划解法。 相关问题： 1. 为什么贪心策略在“拼数字”题目中不一定得到最优解？ 2. 如何证明上述动态规划解法的正确性？ 3. 如果题目要求输出删除后满足条件的序列（而不仅仅是删除的个数），该如何做？</think>### 2023 蓝桥杯 C++ 国赛“拼数字”题目解析 #### 题目描述（根据引用[3]推断） 给定一个由 $n$ 个正整数组成的序列，要求删除最少的数字，使得剩余序列满足：**任意相邻两个数字中，前一个数字的末位等于后一个数字的首位**。求最少删除的数字个数。 **输入格式**： - 第一行：整数 $n$（序列长度） - 第二行：$n$ 个正整数 **输出格式**： - 最少删除的数字个数 --- #### 解析与正确解法 ##### 1. **问题分析** - **核心要求**：在序列中找出最长的子序列，满足相邻数字首尾相连（前一个末位 = 后一个首位）。 - **关键点**：子序列不要求连续，因此需全局优化，而非局部贪心。 - **贪心策略的缺陷**（引用[3]代码问题）： - 原解法（贪心）总保留第一个数字，但最优解可能需删除首元素。 - 例如序列 $[12, 25, 53]$： - 贪心：保留 $12$（末位$2$），$25$ 首位 $2$ 匹配，保留；$53$ 首位 $5 \neq 25$ 末位 $5$，删除。删除 $1$ 个。 - 最优解：删除 $12$，保留 $25, 53$（$25$ 末位 $5 = 53$ 首位 $5$），删除 $1$ 个。但若序列为 $[12, 23, 34, 45, 25]$，贪心可能无法得到最优解。 ##### 2. **动态规划解法** 用 $f[k]$ 表示 **以末位数字 $k$ 结尾的子序列的最大长度**（$k$ 为 $0 \sim 9$）： 1. **预处理**：计算每个数字 $x$ 的首位 $a$ 和末位 $b$。 - 首位 $a$：通过 $a = \text{first\_digit}(x)$（不断除以 $10$ 直到 $x < 10$）。 - 末位 $b = x \% 10$。 2. **状态转移**： - 遍历每个数字，若其首位为 $a$，末位为 $b$： - 可单独成序列：长度 $=1$。 - 或接在末位为 $a$ 的子序列后：长度 $= f[a] + 1$。 - 更新：$f[b] = \max(f[b], \ 1, \ f[a] + 1)$。 3. **结果**：$\text{最少删除数} = n - \max_{k \in [0,9]} f[k]$。 **时间复杂度**：$O(n \cdot C)$（$C=10$），高效。 ##### 3. **C++ 代码实现** ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 求数字首位 int first_digit(long long x) { while (x >= 10) x /= 10; return x; } int main() { int n; cin >> n; vector<long long> nums(n); for (int i = 0; i < n; i++) cin >> nums[i]; // f[k]: 以末位数字k结尾的子序列最大长度 vector<int> f(10, 0); int max_len = 0; for (int i = 0; i < n; i++) { int a = first_digit(nums[i]); int b = nums[i] % 10; int current = max(1, f[a] + 1); // 单独或接续 if (current > f[b]) f[b] = current; max_len = max(max_len, current); } cout << n - max_len << endl; return 0; } ``` ##### 4. **示例验证** **输入**： ``` 5 12 23 34 45 25 ``` **处理**： 1. $12$：$a=1,\ b=2 \to f[2]=1$ 2. $23$：$a=2,\ b=3 \to f[3]=f[2]+1=2$ 3. $34$：$a=3,\ b=4 \to f[4]=f[3]+1=3$ 4. $45$：$a=4,\ b=5 \to f[5]=f[4]+1=4$ 5. $25$：$a=2,\ b=5 \to \text{current}=f[2]+1=2$（小于 $f[5]=4$，不更新） - 最长子序列长度 $=4$（如 $12,23,34,45$），删除 $1$ 个数字（$25$）。 **输出**：$1$。 --- #### 对比引用[3]的解法 - **原代码问题**： - 贪心策略强制保留首元素，可能错过最优解。 - 仅检查相邻数字，未考虑非连续子序列。 - **改进**：动态规划全局优化，覆盖所有子序列组合。 --- ### 相关问题 1. **贪心策略在哪些情况下会失效？** - 当最优解需删除序列前段的数字时（如首元素与后续不匹配）。 2. **如何输出删除后的序列（而不仅删除个数）？** - 需记录状态转移路径：维护 $prev[i]$ 表示第 $i$ 个数字的前驱数字下标，回溯最长路径。 3. **若数字极大（$10^{18}$），如何优化求首位？** - 用字符串转换：`string s = to_string(x); int a = s[0] - '0';`。 4. **若允许循环连接（末位与首位可任意匹配），如何修改？** - 转化为图问题：数字首末位为节点，求最长路径（需拓扑排序或 DP 迭代）[^1]。 [^1]: 2023第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 B 组(真题&题解) [^2]: 2023蓝桥杯大学A组C++国赛游记+个人题解 [^3]: 2023蓝桥杯c++ b组真题(附题目与逐步解析)