Lei

A题意简述给你一个长度为 $nk$ 的字符串，再给你 $n$ 个长度为 $k$ 的字符串片段，需要你重新排列这些字符串片段，定义一个排列的值为每个片段匹配原串的最长前缀之和，求所有可能的排列中的最大值。 题目分析可以先把原来的字符串分成 $n$ 份再插入 trie 树中，再将每个字符串片段在 trie 树上遍历一遍，记录可以到达的最后位置。 剩下即是思考求解最大值。 考虑贪心，可以发现先将片段匹配

Encrypted.

A题目简介给你一个 $n$ 个点，$m$ 条边的 DAG，每条边有一个权值，经过一条路径就可以形成一个字符串，$q$ 个询问，询问从 $u$ 出发第 $k$ 大字符串的终点在哪。 题目分析首先考虑暴力做法，即是处理 $dp$ 数组，代表每个点向后走能形成多少个字符串，递推公式显然为 dp[u] += dp[v] + 1。然后询问即是试探每个儿子走，如果不走当前儿子，就减去当前儿子贡献，试探下一个儿

A题意简述给你一幅图，求割点，割边，极大点双连通分量数以及其边数 题目分析模板题。割点数注意特判根结点以及去重。 注意图可能不连通 普通割点判断条件：low[v] >= dfn[u] 桥判断条件：low[v] > dfn[u] 极大点双连通分量在求割点时统计即可 而其边数可以将极大点双连通分量分组，然后暴力统计组内点之间的连边有多少即可 B题意简述求树上两点之间的最短距离 题目分析df

A题意简述给定 $n$ 个数字，$q$ 个询问，每次询问一个区间 $(l, r)$，问多少个数对 $(p, q)$ 满足 $p < l, r < q, a_p = a_q$。 题目分析考虑到问题区间可以通过单点移动求出来，即使用莫队算法，维护所给区间两边的数字个数，如果区间向一边收缩了一位，即有一边增加了一个数，答案就增加另一边相同数的数目，减少同理 B题意简述给定 $n$

B 首先一定是提最小的字母，其次发现，如果有多个最小的，则最后的那一个才是最优的（因为前面的提走了，就会在更早的地方没有最小的） C 数学公式化简，set 维护邻值即可 D 首先不可能每个都算，因为边的变化与最远能到达有关，所以想到考虑每个点最远能到达的点，也即是求每个点的最远距离。对于最远距离大于等于 $k$ 的点，发现一定能组成一个集合，而剩下的各自为一个集合 所以问题变为求每个点的最远距

B 如果直接想答案，显然不好想。但如果逆向思考，如果固定了最终腿的长度，一定是尽可能用最长，再在中途走一步来补足余数。即对于长度 m，则答案为 $\lceil\frac{a}{m}\rceil + \lceil\frac{b}{m}\rceil + m - 1$ 去掉 ceil，发现即是一个简单的不等式在 $m = \sqrt{a + b}$ 时取等，因为有 ceil，所以是在附近取最小

B 翻译题意，即是求两个点所在的正方形的距离 可以用 min({x, y, n - x + 1, m - y + 1}) 来表示 C 首先第一个位置和最后一个位置的取法可以无脑取第一个和最后一个，正确性显然 而对于中间的位置猜测是 $a_i = \min(b_i, b_{i + 1})$ 证明可以看官方题解，其实就是代换回去得到 $b_i$ 的定义 我的解法是根据 b 序

A 判断中间是否有格点，显然就是最大公因数为 1，注意考虑 0 的情况 既然能走两步且不用最优，则默认两步，第一步横坐标走到 x - 1 位置（注意 x 等于 1 的情况要特判 2），纵坐标的要求即是与 x - 1 互质，第二步因为横坐标相差 1，显然怎么走都没有格点。 即考虑一个与 x - 1（x + 1 当目标坐标为 1 时）互质的数，考虑两个在 1e5 范围左右的质数，显然对于 $x \le

B 手模一下发现奇数都可以表示，而且从一个奇数变成另一个奇数的变换方案只有一种 C 两种操作的效果是没有交集的，即变成一个合法答案，所需要的操作是可以贪心出来的 剩下就是最终形成什么序列，然后双指针模拟一下需要增加多少个数，移除多少个数即可 D 数学转换即可，注意第一天即可上去的特殊情况 注意向上取整可以在原来基础上加上 除数 - 1 E 并查集维护关系 可以对每个 0 点开始都搜一下最后能