P12877 [蓝桥杯 2025 国 Python A] 心意 题解

· · 题解

P12877 [蓝桥杯 2025 国 Python A] 心意 题解

这是一篇 Python 的偷鸡做法，看似绿题，实则绿的点只在于打出 KMP 板子。由于 Python 已经帮我们造好了轮子，我的评价是：建议降红。

0x01 分析

首先，题目中的旋转，可以注意到其实就是环形地向左平移，于是我们只需要破环成链——直接将 a 数组倍长，就可以拿着 b 数组从左往右一个个匹配，时间复杂度为 O(n^2)，即使是效率更高的 C++ 也只有 60pts。

考虑如何将匹配的复杂度降下来……等等，说到匹配，如果能使用 KMP 算法，复杂度就可以降到 O(n)。但显然不能直接这么搞，因为题目要求 a 数组加上一个数 x 后才能得到 b 数组，因此我们需要一些转化。

仔细再想想这句话，实际上能否匹配成功与 a、b 的具体取值无关，而在于元素之间的变化量是否一致。说到变化量，我们可以使用环形差分求出变化量，这样就可以直接通过 KMP 算法找出答案。

0x02 实现

Talk is cheap, show me the code!

Python 中的 KMP 算法实现为str类的find方法，通过调用内置的help(str.find)可以得到相关信息（已翻译）：

find(self, sub[, start[, end]], /) builtins.str 方法
    返回 S 中找到子串 sub 的最小索引，使得 sub 包含在 S[start:end] 之间。

    可选形参 start 和 end 与切片表示法一致。
    失败时返回 -1。

码量少，好写，去掉注释和空行仅有 22 行。

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 计算差分数组
differenceA, differenceB = [], []
# 特判第一个数字
differenceA.append(a[0] - a[n - 1])
differenceB.append(b[0] - b[n - 1])
for i in range(1, n):
    differenceA.append(a[i] - a[i - 1])
    differenceB.append(b[i] - b[i - 1])
# 破环成链
differenceA += differenceA
# 为了方便查找，将差分数组转换为字符串
stringA = ','.join(map(str, differenceA))
stringB = ','.join(map(str, differenceB))
# 核心算法：字符串匹配
result = stringA.find(stringB)
if result == -1:  # 若不存在则输出 -1
    print(result)
else:
    # 接下来我们需要找到下标 result 对应的是第几个数字
    currentPosition = 0  # 表示字符串中的位置
    for index, number in enumerate(differenceA):
        if currentPosition == result:
            print(index)
            break
        currentPosition += len(str(number)) + 1

0x03 总结

最慢时间 720ms，最大内存 145MB。另外，使用 PyPy 3 会负优化 T 掉（我也不知道为啥）。

这题其实不难想，只需要差分转化，正如开头所说，核心其实是 KMP 算法。玩 Python 想要偷鸡，同样需要对内置函数及标准库足够熟悉。如果考场上真忘了怎么用，就打开 Python 安装目录下的/Doc/html/index.html吧，尤其是 Library reference 板块，它会告诉你一切的。