Codechef Dynamic GCD Codechef Dynamic GCD 就是考虑维护链上 $\gcd$ 和链加。我们先考虑这个东西放到序列上怎么做，首先进行差分，之后因为 $\gcd$ 是不变的，但是区间加可以直接变成了单点修改用线段树进行维护即可。 对于树上的情况，我们直接使用树链剖分进行分成若干条链进行计算。 具体来说我们考虑对于一条链 $u, v, fa_u = v$，我们让节点 $u$ 的值变成 $a_v - a_u$ 即可。对于链头的情况我们直接作为原来的值即可。 但是会有一个问题，如果我们一条链没有被使用完成我们就需要知道最上面的那个值。 对于这个我们只需要维护一下被加的值即可，为了方便使用了标记永久化。 一些细节： 根据我们差分的定义，对于一个节点 $u$ 增加了 $c$ 的时候，其单点维护的 $\gcd$ 是要 $- c$ 的，其儿子是要 $+ c$ 的。当然对于 $u = \tt{top}_u$ 的情况例外。 我们进行最终计算答案的时候不要忘记计算最上面一个点的贡献，也不要多计算。 123456789101112131415161718 ...

CF1043F Make It One CF1043F Make It One 首先看一下质因子个数最多只有 $6$ 个，考虑答案上界是多少。 122 3 5 7 11 133 5 7 11 13 17 不要忘记 $17$。 你们答案的上界就是 $7$。 我们考虑对于 $\gcd$ 进行卷积，那么我们需要使用容斥。 考虑反演：$$g = f \times I \f = g \times \mu$$ 原理就是 $I \times \mu = e$。 但是反演其实还有一种形式。$$g(n) = \sum_{i = 1, i \times n \le m} f(i \times n) \f(n) = \sum_{i = 1, i \times n \le m} g(i \times m) \times \mu(i)$$我们直接使用后面一种即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 ...

CF383E Vowels CF383E Vowels。 emmm 可以自己想出来的简单题。 就是考虑容斥，也就是 $A \cup B = A + B - A \cap B$。三个数的情况也是同理。发现每个字符串的长度 $= 3$ 所以我们可以直接对于集合大小是 $3$ 的进行暴力容斥计算。 之后我们考虑集合的合并，直接进行状压 $\tt Dp$，我们考虑删除最前面和最后面的那一位的贡献之和减去同时删除的贡献即可。 或者说我们可以考虑更好写的情况。我们发现合法的集合肯定是至少包含其中一个位置的。 对于至少可以通过取补集转换成全部不包含。 对于一个不合法的集合肯定是所有位置都在这里的，那么后者完全可以使用高位前缀和进行维护，我们对于每一个补集进行计算即可。 显然所有的集合都被计算过了。因为两个交集为空，并集为全集的集合会互相计算。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include < ...

$$\textbf{Funtion}\ \text{的使用}$$ 关于 function属实是一种有趣的语法。 我们常常会碰到的问题，就是我们在一个函数内部想使用其局部变量来进行一些操作。 我们常用的写法是直接定义一个函数： 123auto F = [&, i] () -> void{ ..... }; 但是如果说我们需要使用一些递归的调用，auto不能判断出其类型，我们就必须使用 function函数。 换言之 function本质上是一种类型，表示一个递归函数的指针。 1function<A(B)> dfs; 其中 A表示返回值的类型，B表示要填的参数。 举一个列子，我们需要遍历以当前节点 $x$ 为根的树。 123456for(int i = 1; i <= n; ++ i) { function<void(const int& p,int pre)> dfs; dfs = [&] (const int &p,int pre) { for(au ...

CF1562E Rescue Niwen! CF1562E Rescue Niwen! 应该是经典 $\tt Dp$ 题目的变种。 字符串 $\tt Lis$ 直接做复杂度是 $O(n^3)$ 的。我们来找寻一下这个的性质。也就是考虑对于一个字符串如果选择了他，肯定可以选择其之后的所有后缀，答案肯定会更优的。 那么我们的 $\tt Lis$ 可以枚举每个位置的起点，如果能加就肯定是直接加了。 $s_i > s_j$ 肯定是直接加入了，别忘记加上 $j$ 后缀的贡献。 $s_i = s_j, s_{i + lcp(i, j)} > s_{j + lcp(i, j)}$ 同样加入贡献，但是为了保证合法我们的 $i$ 肯定需要选之后的 $lcp(i, j)$ 个字符来保证可以接到 $j$ 上。 但是我们第二种方法不一定更优，我们钦定一下转移的顺序从小到大进行转移，可以发现后缀是变少的，那么选了 $j$ 的后缀肯定不会比选了 $i$ 的后缀更劣。 12345678910111213141516171819202122232425262728293031323 ...

CF1550F Jumping Around CF1550F Jumping Around 经典的转化，可能有点正难则反的意味。 $\textbf{我的思路：}$可以看出因为 $d$ 是不变的，所以对于一个逐渐增大的 $k$ 可以到达的点是逐渐变多的，换言之就是具有单调性。 有一个比较显然的想法，就是离线一下 $k$ 考虑从小到大进行计算。考虑暴力，就是对于每一个 $k$ 建图跑一遍 $\textbf{Dijstra}$。 复杂度是 $O(n^2 + q\ n\log n)$ 的，用一下线段树优化建图复杂度就是 $O(q\ n \log n)$ 了。 尝试考虑能否继承，但是没有结果。那么我们对于一个 $k$ 进行判断，不妨我们判断对于一条路径其合法需要的最小的 $k$。 $\textbf{题解：}$我们思考对于一条路径其最小的 $k$ 就是其路径上的最大值，也就是说我们对于任意一条路径我们要让其最大值最小。这就可以使用最小生成树维护了 $(\text{也就是最小生成树的定义})$。 但是发现边数是 $O(n^2)$ 级别的，直接会想到那个奇妙的 $\textb ...

HDU6580 Milk HDU 6580 Milk 校内考试题目，感觉考试的时候没看这题，之后还被恶心了一下 $\dots$。 考试的经过： 搞 $\tt T3$ 嗯，很好简单二项式反演。好最后转换错了，没了。 之后 $\tt 30 \ minutes$ 诶呀这个不是网络流题吗？高分暴力呀！！ 之后没写出来，显然网络流不能处理这个东西，及时说每次修改终点那一段的权值。仅仅是样例就能说明费用流显然是直接流最好。这个真的要搞清楚定义，哎呀。 感觉建图的时候还要稍微改一下不能很随便就直接距离连边之类的。 题解：我们考虑只有中间的一条线可以走，我们不妨对于每一个终止行进行计算。那么其他的位置肯定是 进入行的内部再回到中间 。 不妨对于每一行进行 $\tt Dp$ 保存向左终止和向右终止，向左返回和向右返回的情况。 之后合并的时候使用背包。 每次 $\tt Dp$ 的时候对于每个位置都计算一次贡献，从距离起始点从近到远进行计算即可。 之后每次枚举行，然后记录一下之前的 $\tt Dp$ 。 不要忘了离散化。 123456789101112131415161718192 ...

切比雪夫距离和曼哈顿距离 众所周知两个点 $(x_1, y_1), (x_2, y_2)$ 的曼哈顿距离是 $|x_1 - x_2| + |y_1 - y_2|$。 显然我们可以通过不等式去掉绝对值 $\max(|x_1 + y_1 + x_2 + y_2|, |x_1 + y_1 - (x_2 + y_2)|)$。 切比雪夫距离就是 $\max(|x_1 - x_2|, |y_1 - y_2|)$。 然后我们发现这两个格式很像，事实上确实是可以转换的： 曼哈顿距离 到 切比雪夫距离 ： $(x, y) \to (x + y, x -y )$。 切比雪夫距离 到 曼哈顿距离 ： $(x, y) \to (\frac{x + y}{2}, \frac{x - y}{2})$。 注意： 可能 $\frac{x + y}{2}$ 不一定是整数，那么我们不妨考虑在四周枚举一下。 P3964 [TJOI2013]松鼠聚会 P3439 [POI2006]MAG-Warehouse 这题就是经典的不一定是整数，我们要在周围的点分类讨论一下。 123456789101112131 ...