数字消除与连锁进位

题目描述

给定一个只包含数字 0 到 9 的字符串，以及一个整数 k。从左到右依次处理每个数字：

1. 将当前数字放入一个结果序列（用栈模拟）。
2. 如果栈顶出现连续 k 个相同数字，则消除这 k 个数字，并生成一个新数字：(被消除数字 + 1) % 10。
3. 新数字插入到消除位置，可能与前面的数字相同，形成新的连续段。若新连续段长度又达到 k，则继续消除和进位，直到稳定。
4. 处理完整个字符串后，输出最终剩下的数字序列。若全部消除，输出空行。

数据范围：t ≤ 10^5，所有测试用例的 n 之和 ≤ 2 × 10^5，2 ≤ k ≤ n。

示例

输入：

2
5 2
11111
4 3
3331

输出：

31
41

解释：

• 样例 1：11111，k=2
  • 读入两个 1 → 消除得 2；
  • 继续读 1、1 → 消除得 2，与前面的 2 合并成 22，又消除得 3；
  • 最后剩一个 1，输出 31。
• 样例 2：3331，k=3
  • 前三个 3 消除得 4；
  • 剩下 1，输出 41。

核心思路

用栈模拟消除过程。栈中每个元素存储 [数字, 连续个数]。

遍历字符串的每个字符 ch：

1. 将 ch 转为数字 d；
2. 若栈非空且栈顶数字等于 d，则栈顶计数加一；否则压入 [d, 1]；
3. 检查栈顶计数是否达到 k：
   • 若达到，弹出栈顶，计算新数字 new_d = (d + 1) % 10；
   • 将 new_d 与新的栈顶合并（若相同则计数加一，否则压入 [new_d, 1]）；
   • 重复检查，直到栈顶计数不再达到 k 或栈为空。

由于每个字符最多进栈一次、出栈一次，且每次消除只操作栈顶，整体时间复杂度为 $O(n)$。

代码实现

t = int(input())
for _ in range(t):
	n, k = map(int, input().split())
	s = input().strip()

	stack = []  # 每个元素为 [digit, count]
	for ch in s:
		d = int(ch)
		if stack and stack[-1][0] == d:
			stack[-1][1] += 1
		else:
			stack.append([d, 1])

		# 连锁消除
		while stack and stack[-1][1] >= k:
			d, cnt = stack.pop()
			# 根据规则，cnt 恰好等于 k（因为每次只加 1，达到 k 立即消除）
			new_d = (d + 1) % 10
			if stack and stack[-1][0] == new_d:
				stack[-1][1] += 1
			else:
				stack.append([new_d, 1])

        # 构建结果字符串
        res = []
        for d, cnt in stack:
            res.append(str(d) * cnt)
        print(''.join(res))

复杂度分析

• 时间复杂度：$O(n)$，每个数字最多进栈、出栈一次，连锁消除的总操作次数与栈的弹出次数成正比，总体线性。
• 空间复杂度：$O(n)$，栈中最多存储 $n$ 个元素（每个元素包含数字和计数）。

关键细节

1. 栈元素设计：用 [数字, 连续个数] 而不是逐个字符存储，能有效压缩连续相同数字，减少操作次数。
2. 连锁消除：用 while 循环持续检查栈顶，直到不再满足消除条件。
3. 新数字合并：消除后生成的新数字可能与前面的数字相同，需要立即合并，并再次检查是否达到 k。
4. 计数不会超过 k：因为每次只增加 1，达到 k 就立即消除，所以 cnt 恰好为 k。若 k=1 则不同，但题目保证 k ≥ 2。
5. 输出空行：若最终栈为空，out_lines 中加入空字符串，输出时自然形成空行。

总结

本题是典型的栈模拟 + 连锁反应问题。核心在于用栈维护当前序列，遇到连续 k 个相同数字就消除并进位，同时不断检查新生成的数字是否引发新的消除。由于每个元素只处理常数次，整体效率很高，适合处理 $2 \times 10^5$ 规模的数据。

相关题目

• LC 1047. 删除字符串中的所有相邻重复项（类似栈消除）
• LC 1209. 删除字符串中的所有相邻重复项 II（连续 k 个消除）
• 数字进位与模运算模拟