✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🤖 内容包含AI辅助生成，题解和代码均经过多轮验证，有问题欢迎评论

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

淘天-2026.04.11-算法岗

题目总览

这套算法岗的三题方向差得比较开。第一题是纯转化，第二题看构造能力和收尾是否稳，第三题则回到状态可达问题。写的时候如果能尽早认出模型，推进会顺很多。

1. 小哀的轮转

问题描述

小哀拿到一个只包含小写字母的字符串 s。
随后她会执行 q 次全局替换操作，每次给出两个字符 x, y，表示把当前字符串中所有的 x 同时改成 y。

请你输出所有操作做完之后的最终字符串。

输入格式

第一行输入整数 T，表示测试组数。
每组数据先输入 n, q，再输入字符串 s，之后给出 q 行替换规则。

输出格式

对每组数据输出一行最终字符串。

样例输入

1
5 3
abaca
a b
b c
c a

样例输出

aaaaa

样例说明

第一次操作后字符串变成 bbbcb，第二次变成 ccccc，第三次再统一改成 aaaaa。

数据范围

• 1 <= T <= 10
• 1 <= n, q <= 4 * 10^5
• 所有测试数据的 n 之和、q 之和都不超过 4 * 10^5

题解

如果正着模拟，每次都去扫描整条字符串，复杂度会偏大。
但字母只有 26 种，所以真正该维护的是“某个字母最后会变成什么”。

把所有操作倒着看。
假设当前处理到一条 x -> y，在它后面的所有操作已经折叠进数组 to 里了，那么正着执行这条操作之后，x 最终会去到 to[y]。
所以倒着更新时，只需要做：

to[x] = to[y]

最后再扫一遍原串，把每个字符替换成它最终对应的字母即可。

参考代码（Python）

import sys


def solve() -> None:
    # Read input in ACM mode and build the answer directly.
    input = sys.stdin.readline
    t = int(input())
    out = []

    for _ in range(t):
        # Process each test case independently.
        n, q = map(int, input().split())
        s = input().strip()
        ops = [tuple(input().split()) for _ in range(q)]

        to = list(range(26))
        for x, y in reversed(ops):
            ix = ord(x) - 97
            iy = ord(y) - 97
            to[ix] = to[iy]

        out.append("".join(chr(to[ord(ch) - 97] + 97) for ch in s))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    # Standard ACM entry.
    solve()

2. 阿笠博士的凑对

问题描述

阿笠博士想把 1 到 n 这 n 个整数排成一个排列，其中 n 一定是偶数。
然后按相邻两个数一组切开，得到若干对 (x, y)。

每一对都必须同时满足：

• x + y 不是质数；
• |x - y| 也不是质数。

如果存在合法排列，输出任意一个；否则输出 -1。

输入格式

第一行输入整数 T。
接下来每组数据输入一个偶数 n。

输出格式

若无解，输出 -1。
否则输出一行排列。

样例输入

2
6
8

样例输出

-1
1 5 2 6 3 7 4 8

样例说明

对于 n = 6，无法把所有数两两配完并满足限制。
而当 n = 8 时，可以按 (1,5),(2,6),(3,7),(4,8) 这样分组。每一对的差都是 4，和都是大于 2 的偶数，所以两个条件都满足。

数据范围

• 1 <= T <= 10^4
• 2 <= n <= 2 * 10^5
• n 为偶数
• 所有测试数据的 n 之和不超过 2 * 10^5

题解

这一题要先找出稳定结构。

如果手里有连续的 8 个数：

s, s+1, ..., s+7

可以固定配成：

(s, s+4), (s+1, s+5), (s+2, s+6), (s+3, s+7)

这样差值永远是 4，不是质数；每一对的和又都是大于 2 的偶数，也不是质数。
所以凡是能整块切成若干个长度为 8 的区间，前面部分都能直接构造出来。

真正的问题只剩尾巴。
把 n mod 8 分类以后，只会留下 0 / 10 / 12 / 14 这几种尾长。
这些规模都很小，可以把最后这一小段数拿出来，先预处理任意两数能不能配对，再做一次状态压缩搜索，看看能否凑成完美匹配。

n = 2, 4, 6 时答案不存在；n >= 8 时，用“大块构造 + 小尾巴搜索”就能完成。

参考代码（Python）

import sys
from functools import lru_cache


def sieve(limit: int):
    prime = [True] * (limit + 1)
    if limit >= 0:
        prime[0] = Fals