• 作者: 作者
  • 时间:
  • 分类: 文章

最近参加了传智杯算法竞赛，运气不错，在B组拿了国一。趁着还热乎，赶紧来复盘一下这次比赛中比较有意思的一道题——T2“神奇的数字”。

传智杯算法竞赛B组国一榜单

2025传智杯决赛B组国一榜单截图

说实话，做这道题的时候我看了一眼后面的官方题解，感觉稍微有点绕。既然拿了奖，我就分享下我自己当时想出来的、比官方更简单直接的思路，希望能帮到以后参赛的同学。

01 题目到底在说什么？

题目核心就几个关键动作，我们把它拆解开来，其实没那么吓人：

  1. 输入：给你一个整数 $N$（虽然题目里可能有 $N$ 个询问，但核心逻辑是针对每个数字的判断）。
  2. 操作过程：
    • 把这个数字的每一位都拆开。
    • 做一轮操作：相邻两位数字相加，然后对 $10$ 取模。比如 $18$，$1+8=9$，结果就是 $9$；比如 $57$，$5+7=12$，对 $10$ 取模就是 $2$。这样就会生成一个新的数字序列。
    • 去零：如果这一轮操作完，新数字的前面有 $0$，全部删掉。
    • 特殊情况：如果这一轮算完全是 $0$，那就直接把它当作 $0$。
    • 循环：重复上述操作，直到这个数字变成只剩一位数为止。
  3. 判断标准（神奇的数字）：
    • 第一步：算出初始那个数字的数位和（比如 $123$，和就是 $1+2+3=6$）。
    • 第二步：看这个数位和是不是一个完全平方数（比如 $1, 4, 9, 16, 25...$）。
    • 第三步：如果是完全平方数，算出它的算术平方根（比如和是 $9$，根就是 $3$）。看这个根，是否等于我们通过无数次操作最后留下的那一位数。
    • 如果都满足，那它就是“神奇的数字”。

02 官方思路 vs 我的思路

官方题解通常会比较严谨，可能会用数学归纳法或者寻找模 $9$ 的规律去优化。对于初学者或者比赛时间紧张的人来说，推导规律容易出错。

我的思路非常朴实无华：暴力模拟。

你可能会问，暴力模拟会不会超时？

这就涉及到题目中的数据范围了。题目中 $N$（也就是数据组数）和每个数字的位数其实是非常小的。这意味着我们完全可以直接写一个循环，硬算出最终的那一位数，根本不需要复杂的数学证明。

03 具体实现步骤

我们可以把问题拆成两个函数来解决，逻辑会非常清晰。

第一步：获取最终的一位数

我们需要写一个函数 get_final_digit(num_str)，输入是数字字符串（方便处理每一位），输出是最后剩下的那个一位数。

  • 循环条件：只要当前字符串长度大于 $1$，就继续操作。
  • 内部操作：
    • 创建一个新的空字符串 temp。
    • 遍历当前字符串，从索引 $0$ 到 $len-2$，取出 s[i] 和 s[i+1]。
    • 转成整数相加，对 $10$ 取模，再加回 temp。
    • 处理前导零：这是最容易忘的！新字符串生成后，要把前面的 $0$ 全部删掉。可以用 while 循环或者正则替换。
    • 全零处理：如果删完前导零后字符串空了，说明之前的数全是 $0$，直接返回 "0" 并结束。
    • 把 temp 赋值给当前字符串，进入下一轮循环。

第二步：判断是否神奇

主函数逻辑就简单了：

  1. 读取输入的数字字符串。
  2. 调用第一步的函数，算出 final_digit（最终结果）。
  3. 计算初始数字的数位和 sum_digits。
  4. 判断 sum_digits 是否是完全平方数：
    • 方法是算 int(sqrt(sum_digits)) 的平方，看是否等于 sum_digits。
  5. 如果是完全平方数，取出根 root。
  6. 比较 root 和 final_digit。注意数据类型转换，字符串转整数比一比就行了。

04 代码片段参考（伪代码/思路）

为了方便大家理解，我写一段类 Python 的伪代码逻辑：

import math

def get_final_digit(s):
    while len(s) > 1:
        temp = ""
        for i in range(len(s) - 1):
            val = (int(s[i]) + int(s[i+1])) % 10
            temp += str(val)
        # 去除前导零
        s = temp.lstrip('0')
        # 如果处理完变成空字符串，说明全0
        if s == "":
            return "0"
    return s

def is_magic(s):
    # 1. 算最终一位数
    res = get_final_digit(s)

# 2. 算数位和
    digit_sum = sum(int(c) for c in s)

# 3. 判断完全平方数
    root = int(math.sqrt(digit_sum))
    if root * root != digit_sum:
        return False

# 4. 比较根和最终值
    return root == int(res)
``

### 05 复杂度分析

*   **时间复杂度**：虽然看起来有嵌套循环，但因为数字的长度在除以 $2$ 之后是急剧缩短的（每两个相邻位变成一个新位），实际的操作次数非常少，大概在 $O(L * \log L)$ 级别，其中 $L$ 是数字长度。对于题目给的数据范围，这简直就是秒过.

*   **空间复杂度**：我们只需要存储几个中间字符串变量，$O(L)$ 即可。

### 写在最后

这道题其实就是考大家的**模拟能力**和**细心程度**。很多时候，我们容易被题目里的“完全平方数”、“算术平方根”吓住，觉得这一定是个数学题。但实际上，只要数据范围允许，**“无脑”模拟**往往是最稳妥、编码速度最快、也是最不容易出错的方法。

官方解法虽然高级，适合大规模数据，但在这种竞赛的特定场景下，简单粗暴才是王道。下次遇到类似的题，先别急着找数学公式，先看看能不能直接算出来，说不定会有惊喜！

希望这个思路对大家刷题或者比赛有帮助，祝大家都能拿到心仪的 Offer！

标签: none

评论已关闭