A

题目A: 回文!

核心问题：判断一个字符串是否可以在最多删除一个字符的条件下成为回文串。

算法：双指针。

思路：

 使用左右指针从两端向中间扫描，比较字符。

 若遇到第一对不相等的字符，则分别尝试删除左边字符（检查子区间 `[l+1, r]`）或删除右边字符（检查子区间 `[l, r-1]`）。

 若任一子区间是回文，则整个字符串可通过删除一个字符变为回文，输出“Yes”；否则输出“No”。

时间复杂度：O(n)。

B

核心问题：给定两个数，通过给一个或两个数分别加1（总操作次数不超过2次），使它们变为不互质（即最大公约数大于1），求所需的最小操作次数。

算法：基于最大公约数 (gcd) 的数学判断。

思路：

 答案只能是0、1或2。

 **0**：若两数初始就不互质（`gcd(x, y) > 1`），无需操作。

 **1**：若给其中一个数加1后，新数与另一个数不互质，则操作1次。

 **2**：否则，给两数各加1。因为两个奇数加1后都变为偶数，必定拥有公约数2，总操作数为2。

时间复杂度：O(T log(1e12))，其中T应为测试用例数量。

C

题目大意

有一个未知长度为 n 的字符串 t，每个字符都是 0,1,...,m-1 中的一个。

GTNewHorizons 会从左到右念出我们构造的字符串 s。

困难版本中，不再是一段一段停留匹配，而是消音器每次只检查最近连续念出的若干个字符。

当某一时刻最近连续的 n 个字符正好等于 t 时，就视为成功。

要求构造一个长度不超过：

的字符串 s，使得对于任意可能的长度为 n 的字符串 t，它都一定会作为 s 的某个连续子串出现。

核心思路

只看最近连续的 n 个音节。

所以问题等价于：

构造一个字符串 s，使得所有长度为 n、字符集为 [0,m-1] 的字符串都作为 s 的子串出现。

考虑建图。

每个点表示一个长度为 n - 1 的字符串。

每条边表示一个长度为 n 的字符串。

对于长度为 n 的串：

它对应一条边：

边上的字符为 cn。

每条边唯一对应一个长度为 n 的咒印。

因此，只要找到一条经过所有边恰好一次的欧拉回路，就能得到一个包含所有长度为 n 字符串的序列。

把长度为 n - 1 的状态看成一个 m 进制数。

设：

当前点为 u，枚举下一个字符 c，转移到：

这个转移的含义是：

1. 在当前长度为 n - 1 的字符串后面加上字符 c；
2. 如果长度超过 n - 1，就删掉最前面的字符；
3. 得到新的长度为 n - 1 的状态。

然后使用 Hierholzer 算法求欧拉回路。

最后在得到的边字符序列前面补上 n - 1 个 0。

最终长度为：

符合题目限制。

D

题目大意

有一个未知长度为 n 的字符串 t，每个字符都是 0,1,...,m-1 中的一个。

从第 1 段开始，依次匹配：

t1, t2, ..., tn

每次念出一个字符：

• 如果等于当前需要的字符 ti，就进入下一段；
• 如果不等于当前需要的字符 ti，就停留在当前段。

要求构造一个长度不超过 n × m 的字符串 s，使得无论真正的 t 是什么，按照 s 从左到右念完后都一定能匹配完整个 t。

核心思路

当前在第 i 段时，只要接下来念出的音节中包含 ti，就一定能前进到第 i + 1 段。

因此我们每一轮都把 0,1,...,m-1 全部念一遍，那么无论当前需要哪个音节，都一定能前进一步。

构造字符串：

也就是把 0,1,...,m-1 重复 n 次。

长度为：

符合题目限制。

E

题目大意

一共有若干个符号，每个符号是 A ~ E 中的一个大写字母。

每个符号都代表一个 0 ~ 9 之间的数字，不同符号可以代表相同数字。

给定 m 条称重记录，最后给定一个密码串 p，需要求出 p 中每个符号对应的数字，并按顺序输出。

如果有多种合法方案，需要输出字典序最小的密码数字串。

如果不存在合法方案，输出：Impossible

核心思路

因为题目中只会出现 A ~ E 这 5 种符号，所以每个符号最多有 10 种取值。

最多需要枚举： 种方案

这个数量很小，可以直接DFS暴力枚举每个符号代表的数字，然后检查所有称重记录是否满足。

F

#　韩洪文刷物品

#构造 #贪心 #枚举 #数学

容易发现给出 后，最少我们能提升 的属性，最高我们能提升 的属性，所以 高于这个值的话，直接免谈。任何不超过这个值的都可以直接贪心构造。 考虑以下构造方式：维护左右指针 l=1,r=N，以及当前属性距离 的差值 d=K-M，每次比较当前能提升的最大差值 ，如果 ，则向答案加入 ，然后 。否则直接向答案加入 即可，此时一定有 ，所以不会发生重复。

G

韩洪文立体几何

#计算几何 #数学

你说得对，但是正方体是一个有 个顶点、 条棱、 个面，所有棱长相等，所有面都是全等的正方形，每个顶点处有 条棱两两垂直的凸多面体。判断给出的 个点是否构成正方形的方法有很多，此处给出一种参考方式，其他方法欢迎在讨论区分享。

设标准正方体 （底面 , 顶面 , 侧楞 ） 顶点依次编号为，对应，根据正方体的结构，有以下邻接关系：

顶点	邻接顶点（共棱）

如果输入的 个点能构成一个正方体，那么存在一种双射（即排列）将标准正方体的顶点映射到输入点，使得每个标准顶点的三个邻接顶点在输入中对应的点，从该顶点出发的三个向量满足长度相等且两两垂直。此时，将标准正方体中任意一条体对角线的两个端点（如顶点 和顶点 ）通过该双射映射回输入点，输出这两个端点的坐标即可。

我们可以枚举所有排列，找到满足以上条件的那一个排列，如果没有满足条件的排列，那就不是正方体。

时间复杂度

H

#　韩洪文论文查重

#暴力 #KMP #字符串哈希

注意到 我们可以枚举 的字符，每次暴力查询是否出现 了即可。时间复杂度

I

题目大意

一共有若干个符号，每个符号是 A ~ E 中的一个大写字母。

每个符号都代表一个 0 ~ 9 之间的数字，不同符号可以代表相同数字。

给定 m 条称重记录，最后给定一个密码串 p，需要求出 p 中每个符号对应的数字，并按顺序输出。

如果有多种合法方案，需要输出字典序最小的密码数字串。

如果不存在合法方案，输出：Impossible

核心思路

因为题目中只会出现 A ~ E 这 5 种符号，所以每个符号最多有 10 种取值。

最多需要枚举： 种方案

这个数量很小，可以直接DFS暴力枚举每个符号代表的数字，然后检查所有称重记录是否满足。

J

韩洪文航天基地

#离散化 #树状数组 #扫描线 #优先队列 #双指针 #贪心 #排序 #二分

这种统计区间相交对数问题的做法很多：

1. 双指针 & 优先队列 先将所有区间 seg[n] 按左端点 seg[i].first 升序排序。同时将右端点 seg[i].second 取出，单独对所有的右端点排序得到有序数组 r，枚举 seg ,同时维护指针 idx , 不断 ++idx 直到 r[idx] >= seg[i].first，此时前面共有 个区间（下标 ），其中右端点小于左端点 seg[i].first 的有 个，因此与当前区间相交的区间数为 ，累加到答案中即可。这个过程也可以用优先队列(小根堆)维护，具体实现请读者自行探究 时间复杂度 空间复杂度

2. 树状数组 首先要离散化坐标。然后我们按照区间右端点排序，依次处理右端点，每次使用树状数组询问在区间 中的已经处理过的右端点数量即可，向答案累加，然后让树状数组中的 加 。 时间复杂度 空间复杂度

3. 扫描线 我们将区间 拆成 两件事并排序，表示在 有一个玩家上线，在 有一个玩家下线，然后我们维护一个计时器 表示同时在线的玩家数量，遍历排序后的事件，如果是事件 ，则当前这个玩家与所有其他在线玩家同时在线，所以答案累加 。然后 ++count 表示该玩家上线。否则执行 count-=1，表示某个玩家离线。最后输出答案即可。 时间复杂度 空间复杂度

K

韩洪文南征北战

#暴力 #并查集 #搜索

注意到 ，暴力枚举所有情况即可。可以使用并查集或者搜索计算每个情况的贡献。别忘了开 。

时间复杂度 ，极限操作下大概需要 次操作，实际运行较快 空间复杂度

L

题解：海獭机与环形纸带

核心转化

对于一个格子 ，设它被访问了 次。

我们需要判断：

可以使用恒等式：

因此，对于一条路径，它最终发光的格子数量为：

化简得：

所以问题从“统计访问奇数次的格子数量”，转化为计算：

起点对称性

对于一个固定操作序列，如果起点从 改成 ，整条路径只是整体在环上平移了 。

因此发光格子数量不会改变。

所以：

其中表示操作序列， 表示从起点 执行操作序列 后发光格子的数量。

设定符号

令：

其中 表示从 出发，执行操作序列后，格子 被访问的次数。

那么答案为：

接下来只需要计算 $R_n$。

带符号游走

考虑固定一个格子0。

定义：

如果一条路径每次访问格子 0 时，权值乘上 -1，访问其他格子时权值乘上 1，那么整条路径的权值就是：

于是可以设计带符号 DP。

定义：

表示从格子出发，走 步的所有路径的符号权值之和。

初始状态

当 时，路径只访问起点本身。

因此：

也就是：

状态转移

从格子 (i) 出发，第一步可以走到：

或者：

下标均对 取模。

由于当前访问了格子，需要先乘上 。

所以：

为什么这个 DP 能得到

原来：

这里枚举的是“从 (0) 出发，标记点为 (x)”的带符号路径贡献。

由于环具有平移对称性：

• 从 (0) 出发，标记点为 (x)；
• 等价于从 (-x) 出发，标记点为 (0)。

所以：

记：

则：

最终答案为：

注意 DP 转移是线性的。

可以写成：

其中 是一个 的矩阵。

因此：

所以可以：

1. 用普通 DP 生成前若干项 ；
2. 用 Berlekamp-Massey 求出最短线性递推；
3. 用线性递推快速幂求出；
4. 代入公式：

本质上，简单来说，这个本质上就是通过代数运算，提出影响的变量。然后将变量求和，先思考这个如何求，发现这个dp式子，有明显的后向前递推且因为是m维的线性系统，所以我们能够用BM去暴力推出递推式，然后就是可以用快速幂去计算，时间复杂度