LOV3 -> OV3

无限进步

首页 已发布 标签 友链 关于

[AtCoder] ABC_147_C 来自 Gemini 的教学

2025-05-25 22 min read

ABC_147_C

哈，算法萌新你好呀！这道 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"

一种方法是

  1. 按 A屏幕 0 （用了1次）
  2. 按 B屏幕 1 （用了2次）
  3. 按 A屏幕 10 （用了3次）
  4. 按 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 之后的状态。

    (想象一下这样的图，但节点是字符串)

    遇到的麻烦

    1. 选择困难症每一步都有两个选择（按A还是按B），如果S很长，这棵树会变得超级巨大！我们怎么知道哪条路最短呢？
    2. **B按钮的“全局效应”**B按钮一下改变所有数字，这让预测变得困难。可能现在按B看起来不错，但它会不会让后面的步骤更麻烦？比如，我好不容易凑出个 ...0，想按A变成 ...00，结果手快按了B，0 变成 1 了，计划泡汤！
    3. 重复状态我们可能会反复得到同一个字符串，但按键次数不同。比如 "0" -> A -> "00"，也可能 "0" -> B -> "1" -> B*9次 -> "0" -> A -> "00"。我们需要记录到达每个字符串的“最少”次数。

    这种“从前向后”的方法，虽然直观，但感觉有点“路漫漫其修远兮”，很容易迷失在无数的可能性中。

第三站逆向思维的火花——“倒放电影”

当正向思考遇到困难时，聪明的侦探有时会从结果倒推。如果我们已经成功得到了目标密码 S，那么，我们按下的 最后一下 按钮是什么呢？

  • 如果最后一下是 A按钮这意味着，在按 A 之前，屏幕上的字符串 t 加上一个 0 就变成了 S。那么，S 必须是以 0 结尾的！并且，按 A 之前的字符串 t 就是 S 去掉最后一个 0。

    • 例如如果 S 是 120，那么按 A 前的 t 就是 12。

  • 如果最后一下是 B按钮这意味着，在按 B 之前，屏幕上的字符串 t 经过“集体升级”后变成了 S。那么，t 的每一个数字，都应该是 S 对应位置数字的“降一级”版本。

    • 例如如果 S 是 21，2降一级是1，1降一级是0，所以按 B 前的 t 就是 10。
    • 如果 S 是 0，0降一级是9，所以按 B 前的 t 就是 9。

    太棒了！这给了我们一种“撤销”操作或者说“逆操作”的想法

    1. **“撤销A”（Un-A）**如果当前字符串是以 0 结尾的，那么我们可以认为最后一步是按了A。撤销它，就是把末尾的 0 去掉。这“撤销”也算一次操作。
    2. **“撤销B”（Un-B）**我们可以认为最后一步是按了B。撤销它，就是把当前字符串的所有数字都“集体降级”（0变9，1变0，...，9变8）。这也算一次操作。

    新的游戏目标从目标字符串 S 开始，通过不断进行 “Un-A” 和 “Un-B” 操作，最终把 S 变回 “空字符串” ""。我们想找到使用最少“撤销操作”次数的方法。这个次数，其实就等于正向操作得到 S 的最少次数！

    为什么“倒放电影”可能更好？

    • “Un-A” 操作使字符串变短了，这感觉像是在朝着“空字符串”的目标前进。
    • 目标明确变成空字符串。

第四站系统地毯式搜索——“广度优先搜索 (BFS)”登场！

现在我们有了起点 S，目标 ""，以及两种“移动方式”（Un-A, Un-B）。怎么系统地找到最短路径呢？

这里就要请出我们的好朋友——**广度优先搜索（Breadth-First Search, BFS）**了。

  • BFS的直观理解想象你在一个平静的湖面上丢下一颗石子，水波会一圈一圈地向外扩散。

    • 第一圈（距离1）是石子直接能到达的地方。
    • 第二圈（距离2）是从第一圈的点再走一步能到达的地方。
    • ...以此类推。 BFS 就是这样，它会先找到所有“1步”能到达的状态，然后是所有“2步”能到达的状态，等等。所以，当它第一次找到目标状态时，一定是通过最少的步数找到的！

  • BFS 在我们问题中的应用（逆向操作版）

    1. 初始状态字符串 S，操作次数 0。

    2. **队列（Queue）**我们需要一个“待办事项”列表，按顺序处理。一开始，把 (S, 0) 放进队列。

    3. **记录员（Visited/Distance Map）**为了避免重复计算同一个字符串（比如 S -> Un-B -> S'，我们不希望又从其他路径以更多步数到达 S'），我们需要记录到达每个字符串所用的最少“撤销次数”。可以把它想象成一张地图，上面标着从 S 到各个中间字符串的最短距离。

    4. 搜索过程

      • 从队列里拿出一个状态，比如 (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（或者说，受到了一次全局的“降级”影响）。

这启发了我们！也许我们不需要存储完整的、变化后的字符串，只需要知道

  1. 我们当前正在处理的是原始 S 的哪个部分（比如，是整个 S，还是 S 去掉末尾几个字符后的前缀）。可以用一个数字 k 表示当前正在处理的 S 的前缀 S[0...k-1] 的长度。
  2. 这个部分（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 次操作。

  1. 尝试 Un-B

    • 字符串的“概念长度” k 不变。
    • 全局降级次数 j 变为 (j + 1) % 10 （加1后对10取模，保持在0-9）。
    • 花费 cost + 1。
    • 新状态是 (k, (j+1)%10)。

  2. 尝试 Un-A

    • 这个操作只有在 k > 0 （字符串非空）时才能进行。

    • 我们需要看当前“概念字符串”的最后一个字符（即原始 S 的第 k-1 个字符，s_digits[k-1]）在经过 j 次降级后是不是 0。

    • 这个字符的当前值是 (s_digits[k-1] - j + 10) % 10。

    • 如果这个值

      等于 0

      太好了，可以执行 Un-A！

      • 字符串的“概念长度” k 变为 k-1。
      • 全局降级次数 j 不变（因为 Un-A 不影响其他数字的相对降级状态）。
      • 花费 cost + 1。
      • 新状态是 (k-1, j)。

BFS 算法，使用新状态 (k,j)

  1. **“距离地图” dist[k][j]**一个二维数组，dist[k][j] 记录从初始状态 (N,0) 到达状态 (k,j) 所需的最少操作次数。全部初始化为一个非常大的数（表示“无穷远”，还没到过）。

  2. 初始状态我们从 S 开始，它对应状态 (N, 0)（长度为 N 的 S 本身，降级了0次）。所以 dist[N][0] = 0。

  3. **队列 q**把初始状态 (N,0) 放进队列。

  4. 循环直到队列为空

    • 从队列头部取出一个状态 (current_k, current_j)。

    • 获取到达此状态的已知最小代价 current_cost = dist[current_k][current_j]。

    • 尝试 Un-B 转移

      • 计算出新状态 (target_k_B, target_j_B) = (current_k, (current_j + 1) % 10)。
      • 新代价 new_cost_B = current_cost + 1。
      • 如果 new_cost_B < dist[target_k_B][target_j_B] （找到了更短的路），那么更新 dist[target_k_B][target_j_B] = new_cost_B，并把 (target_k_B, target_j_B) 加入队列尾部。

    • 尝试 Un-A 转移

      （前提是

      current_k > 0

      且

      S[current_k-1]

      降级

      current_j

      次后为

      0

      ）

      • 计算出新状态 (target_k_A, target_j_A) = (current_k - 1, current_j)。
      • 新代价 new_cost_A = current_cost + 1。
      • 如果 new_cost_A < dist[target_k_A][target_j_A]，那么更新 dist 并入队。

  5. 最终答案当 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 的队列。
  • 循环和条件判断就按照我们上面分析的转移规则来写。
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解释器)下跑得更快一点。

  1. 更快的输入输出

    • input() 函数虽然方便，但速度不是最快的。在竞赛中，读取大量数据时，sys.stdin.readline() 通常更快。记得用 .strip() 去掉末尾的换行符。
    • print() 函数也有一些额外开销。sys.stdout.write(str(result) + "\n") 可以稍微快一点。

  2. 缓存方法

    在 while q: 循环里，我们反复调用 q.popleft() 和 q.append()。每次 Python 都要去 q 对象上查找这些方法。我们可以把它们“缓存”到局部变量

    popleft = q.popleft
append = q.append
# ... 循环里用 popleft() 和 append(...)

    这能减少一点点查找时间。

  3. “整数状态”和“扁平化dist”

    • 之前我们队列里存的是元组 (k, j)。创建和解包元组有微小开_cost_。我们可以把 (k,j) 状态编码成一个整数，比如 state_int = k * 10 + j (因为 j 只有0-9)。入队和出队时都用这个整数。取出时再用 k = state_int // 10 和 j = state_int % 10 还原。

    • 相应地，

      dist

      数组也可以从二维

      dist[k][j]

      变成一维的

      dist_flat

      ，大小是

      (N+1)*10

      。通过

      dist_flat[k*10+j]

      来访问。这样做的好处是

      • 可能提高内存访问的“局部性”（数据在内存中更连续）。
      • 避免了 Python 中“列表的列表”的额外间接层。

  4. map 函数的妙用

    s_digits = [int(c) for c in S_str] 已经不错了。但有时 s_digits = list(map(int, S_str)) 会因为 map 和 int 都是C语言实现的内建函数而有微弱的速度优势。

  5. 微调取模运算

    new_j = (j + 1) % 10 非常清晰。但因为 j 始终在 0 到 9，我们也可以写成

    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

  1. dist_flat 初始化为无穷大。 dist_flat[2*10+0 = 20] = 0。

  2. q (双端队列) 中加入 20。 popleft = q.popleft, append = q.append。

  3. 第一次循环

    • 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]。

  4. 第二次循环

    • 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先处理取决于实现细节，但最终都会处理)。

  5. 第三次循环 (假设处理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]。

  6. 第四次循环 (处理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]。

  7. 第五次循环 (假设处理23) ...略...

  8. 第六次循环 (处理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]。

  9. ... 若干循环后 ... 当处理到状态 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是寻找最短路径（在无权或单位权图中）的利器。
  • 优化无止境从算法复杂度的大优化，到代码实现的微调，都是提升程序效率的手段。
  • 实践出真知多写代码，多调试，才能真正理解这些思路的巧妙之处。

算法的世界就像一个充满宝藏的岛屿，每一次解题都是一次寻宝。希望这次“神奇密码锁”的旅程能让你对算法产生更浓厚的兴趣。继续探索，你一定会发现更多奇妙的算法和思想！加油！

RSS   DK盾 - 高防服务器赞助商