【题解】2021年牛客寒假集训营第四场题解

邬澄瑶的gcd

如果用 表示第 个质数，那么任何一个整数 都对应唯一一个形如 的式子 。

而 。

即如果我们要求一堆数的最大公约数，我们只要对每一个质数求出在这些数的最大次数中的最小值，最后把这些幂次累乘起来，就是这些数的最大公约数。

吴楚月的表达式

一个非空表达式前缀可以表示成 的形式。

如果后面接了一个 ，则变成 ；

如果后面接了一个 ，则变成 ；

如果后面接了一个 ，则变成 ；

如果后面接了一个 ，则变成 。

最后还是可以表示成 的形式。

因此只需要遍历整棵树维护每个节点对应的 即可。

温澈滢的狗狗

一旦确定亲密值 以后就只需要 扫一遍即可。

考虑二分亲密值 ，问题转化为对于给定的 ，如何求解距离小于等于 的异色点对数呢？

异色点对数=总点对数-同色点对数。

其中总点对数可以推式子 求解，式子形如 个数。

同色点对数可以把同一种颜色的狗狗丢到一个 vector 中后利用双指针求解。

复杂度 。

武辰延的字符串

考虑枚举 和 的公共前缀，这部分其实就是在枚举 ，然后枚举 长度为 的后缀与 的公共前缀，这部分就是在枚举 。

每枚举到一对这样的 就可以让最终答案 。不过这样的复杂度是 的。

实际上我们不需要枚举 ，只需要让答案加上 长度为 的后缀与 的最长公共前缀即可。

也就是我们要知道 的每个后缀与 的最长公共前缀。

一个比较好想的思路是二分+哈希，二分公共前缀的长度，用哈希来判断两个公共前缀是否相等。复杂度 。

另一个思路是使用 exkmp 算法，这个算法可以计算出 串每个后缀与 串本身的最长公共前缀，我们把 接在 后面就可以求出想要的值了，复杂度 。

魏迟燕的自走棋

首先我们考虑把 件装备看作 条连接两个点的边（如果 则当成自环）。于是我们的问题转化为选出一张边权和最大的生成子图。

考虑什么样的生成子图是合法的。我们要求选中的边能够和点一一配对，显然每个联通块的边数不能超过点数。同时又因为每个联通块都至少有点数-1条边，因此每个联通快要么是树，要么是基环树。

一个结论是每次都选最大边一定不劣。

一旦我们选择一条最大边后，我们把两个点缩成一个点（选中非自环的情况），或者直接把这个点丢掉（选中自环的情况），就面临一个规模更小且完全一致的问题，可以继续执行选取最大边的策略。

也就是说我们只需要按照边权从大到小的顺序贪心地拿边，用一个并查集维护联通性和是否带环即可。

证明：

考虑一个不取最大边的方案。

如果把最大边加入后生成子图依旧满足条件，那么加入这条最大边会更优。

如果加入后发现这条边所在的连通块的边数超过了点数，说明原方案已经构成一棵基环树或两棵的基环树（被最大边连接），那么我们肯定可以断掉一条环边，把它变成一棵树或者一棵树+一棵基环树，再把最大边加入使其变成一棵基环树。

由于删掉的边的权值一定不大于最大边，因此新方案一定不劣于原方案。

复杂度

九峰与CFOP

观察发现2为转两次90°，‘为转三次90°，因此只需要写出转90°的操作，又发现所有操作都可以由RULBFDMES组合而成，那么需要模拟的操作就剩下这九种字母顺时针转90°，再加上四种还原状态的判断即可

九峰与签到题

签到题，按顺序计算通过率并打标记即可

九峰与子序列

两种方法：1.折半枚举，将前n/2个进行dfs并记录能匹配到k串的哪些位，后半部分同理，最后将答案合并

2.，转移方程为

九峰与蛇形填数

每一个点知道自己被覆盖的方阵的左上角和边长后可以计算出该点的值，所以考虑第i次操作将子矩阵的值赋为i，最后对于每个点重新计算答案，可以用线段树或优先队列维护行或列的修改，复杂度

tps:这题实际上解法多种多样，可以看看他人的代码学习新思想

九峰与分割序列

很容易发现数据小时可以dp，，数据范围较大后容易想到开3个线段树维护该dp，于是此题得解