可以自己先读题,思考
以下内容由 AI 生成, 感觉很有教育意义, 于是拿出来分享
哈,算法萌新你好呀!这道 AtCoder 的密码题确实有点意思,就像一个需要耐心和智慧的小游戏。别担心,我们会一步一步拆解它,从最开始的懵懂想法,到找到巧妙的解法,再到把它打磨得更快,就像升级打怪一样!准备好了吗?我们开始探险吧!
第一站:理解游戏规则——“神奇密码锁”
想象一下,你面前有一个超酷的密码锁。它有一块屏幕和两个按钮:A按钮 和 B按钮。
- 屏幕(t):一开始,屏幕上是空的(我们叫它“空字符串”)。
- A按钮:按一下A,会在屏幕上当前显示的字符串末尾加上一个数字
0
。比如,如果屏幕是 1984
,按A就变成 19840
。
- B按钮:按一下B,屏幕上所有数字都会“集体升级”!
0
变1
,1
变2
,...,8
变9
。那9
呢?它会变回0
,像一个循环。比如,屏幕是 19840
,按B,1
变2
,9
变0
,8
变9
,4
变5
,0
变1
,所以屏幕变成 20951
。
你的任务:给定一个目标密码字符串 S
(比如 "21"),你需要从空屏幕开始,通过按这两个按钮,以最少的按键次数,让屏幕显示出 S
。
比如目标是 "21":
一种方法是:
- 按 A:屏幕
0
(用了1次)
- 按 B:屏幕
1
(用了2次)
- 按 A:屏幕
10
(用了3次)
- 按 B:屏幕
21
(用了4次) 我们找到了一个4次的方法!问题是,这是不是最少的呢?
第二站:最初的尝试——“摸着石头过河”
我们想找到最少的次数,最直接的想法就是“瞎试试”呗?但我们得有策略地试。
想法1:从空开始,一步步变出 S
这就像我们刚刚手动试 "21" 一样。
一开始是空 ""。
第一步,我们能干啥?只能按 A(因为按 B 对空字符串没用),得到 "0"。
第二步,从 "0" 出发,可以按 A 得到 "00",也可以按 B 得到 "1"。
第三步,从 "00" 出发,可以按 A 得到 "000",按 B 得到 "11"。从 "1" 出发,可以按 A 得到 "10",按 B 得到 "2"。
... 这样一直下去,直到某个时刻,屏幕上出现了 S!
这听起来像一棵“决策树”。每个节点是当前屏幕上的字符串和已用次数,它的孩子是按 A 或 B 之后的状态。
(想象一下这样的图,但节点是字符串)
遇到的麻烦:
选择困难症:每一步都有两个选择(按A还是按B),如果S很长,这棵树会变得超级巨大!我们怎么知道哪条路最短呢?
B按钮的“全局效应”:B按钮一下改变所有数字,这让预测变得困难。可能现在按B看起来不错,但它会不会让后面的步骤更麻烦?比如,我好不容易凑出个 ...0
,想按A变成 ...00
,结果手快按了B,0
变成 1
了,计划泡汤!
重复状态:我们可能会反复得到同一个字符串,但按键次数不同。比如 "0" -> A -> "00",也可能 "0" -> B -> "1" -> B*9次 -> "0" -> A -> "00"。我们需要记录到达每个字符串的“最少”次数。
这种“从前向后”的方法,虽然直观,但感觉有点“路漫漫其修远兮”,很容易迷失在无数的可能性中。
第三站:逆向思维的火花——“倒放电影”
当正向思考遇到困难时,聪明的侦探有时会从结果倒推。如果我们已经成功得到了目标密码 S
,那么,我们按下的 最后一下 按钮是什么呢?
第四站:系统地毯式搜索——“广度优先搜索 (BFS)”登场!
现在我们有了起点 S
,目标 ""
,以及两种“移动方式”(Un-A, Un-B)。怎么系统地找到最短路径呢?
这里就要请出我们的好朋友——广度优先搜索(Breadth-First Search, BFS)了。
BFS的直观理解:想象你在一个平静的湖面上丢下一颗石子,水波会一圈一圈地向外扩散。
- 第一圈(距离1):是石子直接能到达的地方。
- 第二圈(距离2):是从第一圈的点再走一步能到达的地方。
- ...以此类推。 BFS 就是这样,它会先找到所有“1步”能到达的状态,然后是所有“2步”能到达的状态,等等。所以,当它第一次找到目标状态时,一定是通过最少的步数找到的!
BFS 在我们问题中的应用(逆向操作版):
初始状态:字符串 S
,操作次数 0
。
队列(Queue):我们需要一个“待办事项”列表,按顺序处理。一开始,把 (S, 0)
放进队列。
记录员(Visited/Distance Map):为了避免重复计算同一个字符串(比如 S
-> Un-B -> S'
,我们不希望又从其他路径以更多步数到达 S'
),我们需要记录到达每个字符串所用的最少“撤销次数”。可以把它想象成一张地图,上面标着从 S
到各个中间字符串的最短距离。
搜索过程
:
从队列里拿出一个状态,比如 (current_string, current_cost)
。
如果 current_string
是 ""
(空字符串),太棒了!我们成功了!current_cost
就是答案。
否则,尝试对
current_string
进行两种“撤销操作”:
尝试 Un-A:如果 current_string
以 0
结尾,得到 next_string_A
。新的代价是 current_cost + 1
。如果这个代价比之前记录的到达 next_string_A
的代价要小(或者我们从未到过 next_string_A
),我们就更新记录,并把 (next_string_A, current_cost + 1)
加入队列。
尝试 Un-B:对 current_string
所有数字降级,得到 next_string_B
。新的代价是 current_cost + 1
。同样,如果代价更优或首次到达,更新记录并入队。
BFS 的一个大问题(又来了!):
字符串 S 最长可能有 500,000 位!如果我们把这些长长的字符串本身作为状态存到队列里,或者作为“记录员”地图的钥匙:
内存爆炸:可能会有很多很多不同的长字符串,内存根本存不下。
时间超限:每次复制字符串、比较字符串、计算字符串的哈希值(地图钥匙通常需要哈希)都会非常慢。 如果字符串长度是 N
,这种朴素BFS的复杂度可能是 N^3
甚至更高,对于 N=500,000
来说是天文数字。
看来,直接用字符串本身做状态还是不行。我们需要更聪明的“状态表示”。
第五站:“状态压缩”的魔法——BFS的华丽变身!
我们真的需要记住整个字符串的内容吗?仔细想想,在“撤销”的过程中:
- Un-A 操作:它只关心当前字符串的最后一个字符是不是
0
,并且它会把我们正在处理的 S
的有效前缀长度减 1。
- Un-B 操作:它会改变当前有效前缀的 所有 数字,但改变的方式是统一的——所有数字都减1(或者说,受到了一次全局的“降级”影响)。
这启发了我们!也许我们不需要存储完整的、变化后的字符串,只需要知道:
- 我们当前正在处理的是原始
S
的哪个部分(比如,是整个 S
,还是 S
去掉末尾几个字符后的前缀)。可以用一个数字 k
表示当前正在处理的 S
的前缀 S[0...k-1]
的长度。
- 这个部分(
S
的前缀)已经被全局“降级”(Un-B操作)了多少次。可以用一个数字 j
表示这个“降级次数”(或者叫“偏移量”)。这个 j
的范围其实只需要 0
到 9
,因为降级10次就等于没降级。
隆重推出我们的新状态:(k, j)
k
:当前我们认为屏幕上显示的字符串,对应于原始目标串 S
的前 k
个字符。例如,如果 k=N
(N
是S
的长度),我们就在处理整个S
。如果 k=0
,就表示空字符串。
j
:一个 0
到 9
之间的数字,表示 S
的这前 k
个字符,已经被整体执行了 j
次 Un-B(降级)操作了。所以 S
中的原始数字 d
,现在实际显示的是 (d - j + 10) % 10
。(+10
是为了确保即使 d-j
是负数,取模结果也是正的,比如 (0-1+10)%10 = 9
)。
新状态有多少种?
k
可以从 0
取到 N
,有 N+1
种可能。
j
可以从 0
取到 9
,有 10
种可能。 总的状态数大约是 (N+1) * 10
。如果 N=500,000
,状态数大约是 5 * 10^6
。这个数量级对于计算机来说是可以接受的!比之前存储整个字符串好太多了!
新状态下的“撤销操作”(转移规则):
假设我们当前处于状态 (k, j),已经花费了 cost 次操作。
尝试 Un-B
:
- 字符串的“概念长度”
k
不变。
- 全局降级次数
j
变为 (j + 1) % 10
(加1后对10取模,保持在0-9)。
- 花费
cost + 1
。
- 新状态是
(k, (j+1)%10)
。
尝试 Un-A
:
这个操作只有在 k > 0
(字符串非空)时才能进行。
我们需要看当前“概念字符串”的最后一个字符(即原始 S
的第 k-1
个字符,s_digits[k-1]
)在经过 j
次降级后是不是 0
。
这个字符的当前值是 (s_digits[k-1] - j + 10) % 10
。
如果这个值
等于 0
:太好了,可以执行 Un-A!
BFS 算法,使用新状态 (k,j)
:
“距离地图” dist[k][j]
:一个二维数组,dist[k][j]
记录从初始状态 (N,0)
到达状态 (k,j)
所需的最少操作次数。全部初始化为一个非常大的数(表示“无穷远”,还没到过)。
初始状态:我们从 S
开始,它对应状态 (N, 0)
(长度为 N
的 S
本身,降级了0次)。所以 dist[N][0] = 0
。
队列 q
:把初始状态 (N,0)
放进队列。
循环直到队列为空
:
最终答案:当 BFS 结束后(队列为空,所有能到达的状态都探索过了),我们需要找到到达“空字符串”状态的最小代价。空字符串对应的是 k=0
。此时,降级次数 j
是多少都可以(因为空字符串降级多少次还是空字符串)。所以,答案就是 min(dist[0][0], dist[0][1], ..., dist[0][9])
。
这个使用 (k,j)
状态的 BFS,因为每个操作代价都是1,所以它能正确找到最少操作次数。而且状态数量可控,计算转移也很快(不需要操作实际的长字符串),时间复杂度大约是 O(状态数 + 转移数)
,即 O(N*10 + N*10*2) = O(N)
。这对于 N=500,000
来说,是一个非常棒的进步!
第六站:Python代码实现——“将想法变为现实”
要把上面的思路变成计算机能懂的语言,我们需要用到 Python 的一些工具:
s_digits = [int(c) for c in S]
:把输入的字符串 S
变成一个整数列表,方便我们取用 s_digits[k-1]
。
dist = [[float('inf')] * 10 for _ in range(N + 1)]
:创建一个 (N+1) x 10
的二维列表作为我们的“距离地图”,用 float('inf')
初始化表示无穷大。
import collections; q = collections.deque()
:使用 collections
模块里的 deque
(双端队列),它在头部取出元素 (popleft()
) 和尾部加入元素 (append()
) 都非常快,非常适合做 BFS 的队列。
- 循环和条件判断就按照我们上面分析的转移规则来写。
<!-- end list -->
Python
import collections
# (这里是 solve 函数的框架)
# def solve():
# S_str = input() # 读入字符串 S
# N = len(S_str) # S 的长度
# s_digits = [int(c) for c in S_str] # 转成数字列表
# dist = [[float('inf')] * 10 for _ in range(N + 1)] # 初始化距离地图
# q = collections.deque() # 创建双端队列
# if N == 0: # 特殊情况:S 本身就是空串
# print(0)
# return
# dist[N][0] = 0 # 初始状态 (N, 0) 代价为0
# q.append((N, 0)) # 入队
# while q: # BFS 主循环
# k, j = q.popleft() # 取出队首状态
# current_cost = dist[k][j]
# # 尝试 Un-B 操作
# new_j_b = (j + 1) % 10
# if current_cost + 1 < dist[k][new_j_b]:
# dist[k][new_j_b] = current_cost + 1
# q.append((k, new_j_b))
# # 尝试 Un-A 操作
# if k > 0:
# char_val_original = s_digits[k-1]
# current_char_val = (char_val_original - j + 10) % 10
# if current_char_val == 0:
# if current_cost + 1 < dist[k-1][j]:
# dist[k-1][j] = current_cost + 1
# q.append((k-1, j))
# # 找结果
# min_ops = float('inf')
# for final_j_cost in dist[0]: # dist[0] 是一个包含10个cost的列表
# min_ops = min(min_ops, final_j_cost)
# print(min_ops)
(上面的代码是一个简化框架,实际提交的代码会更完整一些。)
第七站:追求极致——“榨干Python的最后一滴油”(针对仍然超时的优化)
你可能已经写出了上面 O(N) 的 BFS 代码,但发现对于最大的数据,它还是“差那么一点点”就超时了(比如题目限制2秒,你的程序跑了2.2秒)。这时候,我们就需要一些针对 Python 语言特性和执行效率的“微调手术”。这些操作不会改变算法的 O(N) 本质,但能让程序在 CPython (标准Python解释器)下跑得更快一点。
更快的输入输出:
input()
函数虽然方便,但速度不是最快的。在竞赛中,读取大量数据时,sys.stdin.readline()
通常更快。记得用 .strip()
去掉末尾的换行符。
print()
函数也有一些额外开销。sys.stdout.write(str(result) + "\n")
可以稍微快一点。
缓存方法:
在 while q: 循环里,我们反复调用 q.popleft() 和 q.append()。每次 Python 都要去 q 对象上查找这些方法。我们可以把它们“缓存”到局部变量:
Python
popleft = q.popleft
append = q.append
# ... 循环里用 popleft() 和 append(...)
这能减少一点点查找时间。
“整数状态”和“扁平化dist”:
map 函数的妙用:
s_digits = [int(c) for c in S_str] 已经不错了。但有时 s_digits = list(map(int, S_str)) 会因为 map 和 int 都是C语言实现的内建函数而有微弱的速度优势。
微调取模运算:
new_j = (j + 1) % 10 非常清晰。但因为 j 始终在 0 到 9,我们也可以写成:
Python
new_j = j + 1
if new_j == 10:
new_j = 0
这避免了 %
运算符(它内部可能涉及到除法),用一个加法、一个比较和一个赋值代替。在某些情况下,这可能快一点点,但也可能因为引入了分支而没有优势。这种属于“玄学优化”,需要实际测试。
把这些微调技巧应用到之前的BFS代码上,就能得到一个在CPython下尽可能快的版本。
第八站:以“21”为例,回顾 (k,j) BFS 之旅
让我们用 S="21"
(即 N=2
, s_digits=[2,1]
) 来完整走一遍优化后的 (k,j)
BFS,假设我们用整数状态 state_int = k*10+j
:
dist_flat
初始化为无穷大。 dist_flat[2*10+0 = 20] = 0
。
q
(双端队列) 中加入 20
。 popleft = q.popleft
, append = q.append
。
第一次循环
:
state_int = popleft()
得到 20
。 k=2, j=0
。 current_cost = dist_flat[20] = 0
。 next_op_cost = 1
。
Un-B: new_j_b = (0+1)%10 = 1
。目标索引 k*10+new_j_b = 2*10+1 = 21
。 dist_flat[21]
是无穷大,所以 1 < dist_flat[21]
。更新 dist_flat[21] = 1
。 append(21)
。
Un-A: k=2 > 0
。 s_digits[k-1] = s_digits[1] = 1
。 current_val = (1 - 0 + 10)%10 = 1
。不是0,不能Un-A。
q
中现在是 [21]
。
第二次循环
:
state_int = popleft()
得到 21
。 k=2, j=1
。 current_cost = dist_flat[21] = 1
。 next_op_cost = 2
。
Un-B: new_j_b = (1+1)%10 = 2
。目标索引 2*10+2 = 22
。 2 < dist_flat[22]
(无穷大)。更新 dist_flat[22] = 2
。 append(22)
。
Un-A: k=2 > 0
。 s_digits[1] = 1
。 current_val = (1 - 1 + 10)%10 = 0
。是0!可以Un-A。 new_k_a = 2-1 = 1
。目标索引 new_k_a*10+j = 1*10+1 = 11
。 2 < dist_flat[11]
(无穷大)。更新 dist_flat[11] = 2
。 append(11)
。
q
中现在是 [22, 11]
(注意BFS是先进先出,所以22先处理,或11先处理取决于实现细节,但最终都会处理)。
第三次循环 (假设处理22)
:
state_int = popleft()
得到 22
。 k=2, j=2
。 current_cost = dist_flat[22] = 2
。 next_op_cost = 3
。
Un-B: new_j_b = 3
。目标索引 23
。 dist_flat[23]=3
。 append(23)
。
Un-A: s_digits[1]=1
。 current_val = (1 - 2 + 10)%10 = 9
。不是0。
q
中是 [11, 23]
。
第四次循环 (处理11)
:
state_int = popleft()
得到 11
。 k=1, j=1
。 current_cost = dist_flat[11] = 2
。 next_op_cost = 3
。 (这个状态的含义是:原S的前1个字符 s_digits[0]='2'
,被降级了1次,所以现在代表数字'1'
。我们想把这个'1'
变为空。)
Un-B: new_j_b = 2
。目标索引 1*10+2 = 12
。 dist_flat[12]=3
。 append(12)
。 (状态12:原S的前1个字符 s_digits[0]='2'
,被降级了2次,所以代表数字'0'
。)
Un-A: k=1 > 0
。 s_digits[k-1] = s_digits[0] = 2
。 current_val = (2 - 1 + 10)%10 = 1
。不是0。
q
中是 [23, 12]
。
第五次循环 (假设处理23): ...略...
第六次循环 (处理12)
:
state_int = popleft()
得到 12
。 k=1, j=2
。 current_cost = dist_flat[12] = 3
。 next_op_cost = 4
。 (状态12:原S的前1个字符 s_digits[0]='2'
,被降级了2次,代表数字'0'
。)
Un-B: new_j_b = 3
。目标索引 1*10+3 = 13
。 dist_flat[13]=4
。 append(13)
。
Un-A: k=1 > 0
。 s_digits[0] = 2
。 current_val = (2 - 2 + 10)%10 = 0
。是0!可以Un-A。 new_k_a = 1-1 = 0
。目标索引 new_k_a*10+j = 0*10+2 = 2
。 4 < dist_flat[2]
(无穷大)。更新 dist_flat[2] = 4
。 append(2)
。
q
中是 [..., 13, 2]
。
... 若干循环后 ... 当处理到状态 2
(即 k=0, j=2
) 时,它代表空字符串。 此时 dist_flat[2]
的值是 4
。 最终,我们会发现 min(dist_flat[0], dist_flat[1], ..., dist_flat[9])
的最小值就是 4
(来自于 dist_flat[2]
)。
这就和我们之前手动推导的4步一致了!
第九站:旅程总结与展望
恭喜你,小英雄!我们一起经历了从理解问题、初步尝试、灵光一闪的逆向思维,到运用强大的BFS工具,再通过精巧的状态设计把复杂度降下来,最后还学习了如何给Python代码“提速”的秘籍。
这次探险告诉我们:
- 换个角度看问题:正向不行,试试反向!
- 抽象和建模是核心:找到正确的“状态”来描述问题,是解决复杂问题的金钥匙。
- 系统搜索有方法:BFS是寻找最短路径(在无权或单位权图中)的利器。
- 优化无止境:从算法复杂度的大优化,到代码实现的微调,都是提升程序效率的手段。
- 实践出真知:多写代码,多调试,才能真正理解这些思路的巧妙之处。
算法的世界就像一个充满宝藏的岛屿,每一次解题都是一次寻宝。希望这次“神奇密码锁”的旅程能让你对算法产生更浓厚的兴趣。继续探索,你一定会发现更多奇妙的算法和思想!加油!