CF757G Can Bash Save the Day? 时间复杂度分析好题（大雾）。 将询问拆成几部分，也就是 $dis(u, v) = dep(u) + dep(v) - 2 * dep(Lca(u, v))$。 显然对于 $Lca$ 我们直接进行树链剖分即可。 我们对于每一个 $v$ 维护 $\le l$ 的 $dep(Lca)$ 的贡献，为了节省空间我们直接使用可持久化线段树，进行插入的时候使用标记永久化。 具体来说就是将 $[l, r]$ 这个 $dfs$ 序的区间进行 $+ 1$ 意味着，整个区间加上了 $sumdep_r - sumdep_{l - 1}$ 的贡献，之后为了保证线段树的复杂度是 $\log n$ 我们直接在这里记录标记了几次。然后在进行查询的时候直接下传还有多少次标记没有传完即可。直接像普通线段树下传标记会出现下传了不是属于当前线段树节点的情况。 对于修改的话，发现前缀和只有一个位置变了，也就是只需要修改一个位置。 然后因为本题是卡空间的，我们考虑一次加入点是 $\log n$ 的，一次插入也是 $\log n$ 的，本质就是一次插入需要 $ ...

CF827F Dirty Arkady’s Kitchen 说实话这个拆点和拆边都是可以过的。 发现边是可以重复经过的，那么对于两条边只要考虑奇偶性就好了。 我们考虑对于一条边拆成两部分，一个是起点为奇的，另外一个是偶的。 什么时候一条路径是合法的，也就是说对于一条边 $E$，起点到他的路径上肯定存在一条边的上界是 $\ge E_l$ 的。 注意这里边是会消失的。 然后考虑加边的顺序，比较显然直接是从小到大进行加边。这样对于我们路径的上界肯定是从拓扑序比起小的边得到的，也就是意味着这条边出现的时候肯定是可以走的。 设 $f(i, 0/1)$ 表示到当前点的奇偶性为 $0/1$ 的最晚时间。 如果说当前时刻这条边是不能走的，我们可以考虑将其加入到当前 $u$ 的边集中，之后更新。 因为现在不能走并不意味着不能被其他的边更新。 然后之后更新就是像最短路一样，如果说一条边的终止点在之前被更新过了，那么我们就直接跳过更新。 12345678910111213141516171819202122232425262728293031323334353637383940 ...

CF1523H首先这个东西很像一个 $dp$。我们不妨将删点记录成一个状态，然后发现状态数量太多了，我们可以倍增优化一下状态数量。 设 $f(i, j, k)$ 表示从点 $k$ 开始删除了 $j$ 个点，走 $2^i$ 个点能到达的最优的点。 我们考虑最简单的情况，就是从 $i$ 开始走 $j$ 步能走到的最优的点。答案是 $x +a_x$ 最大的点，因为对于一个 $y > x, a_y + y < a_x + x$ 这样就可以走更多的点。 我们通过 $st$ 表的方式直接进行维护即可。 对于一个询问，我们对于二进制进行拆位分析即可，对于一个不能直接到达的加上 $2^i$ 的贡献。注意特判直接能到达的情况和走一步能到达的情况。 $2^0, 0$。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 ...

CF1446D2 Frequency Problem (Hard Version)讲一种 $O(n)$ 的神仙做法，代码转载于 $gmh77$ 神仙。 说实话这个我也不懂算不算转载，如果有问题可以直接私聊我。 考虑对于最终答案来说，我们重复计算不符合条件的比较小的区间是不影响的。 所以我们可以考虑对于每一个非众数进行计算。 计算只有一个众数的情况 虽然说可能出现了两个非众数，但是肯定存在比其更大的区间。 计算多个众数的情况，我们不妨记录一下众数的位置每次来跳众数，每一次更新一下当前值为 $s$ 的非众数的出现次数。也就是从左到右进行枚举。 考虑对于非众数进行圈定一个区间，同时记录当前值 $s$ 出现的最靠右的位置和其经过的众数，为了防止数组冲突可能需要额外处理一下。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818 ...

平面图转对偶图[BeiJing2006]狼抓兔子这个是经典题，显然就是求一个最小割。然后网络流建立无向图即可。 但是如果数据范围没有那么小呢？ 众所周知网络流的复杂度其实挺玄学的，而且这又是一张平面图，不妨将其转化为对偶图。 定义： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146> ```面的次数```：边界的长度，用 $deg(R_i)$ 表示。>> ```阶` ...

CF756F 原本以为校内有神仙要讲评这题，就赶快去做了。结果啊，是我题号记错的 $\dots$ 题目大意： 给出一个字符串请解析这个字符串构成的数。 $l - r$ 表示 $l \sim r$ 中的所有数， $8 -10$ 表示 $8910$。 $+ x$ 表示单纯增加一个 $x$，如 $8-10+5$ 表示 $89105$。 我们称上面的这样的形式为表达式。 对于 $a(\text{表达式})$ 这样的形式，表示写 $a$ 遍表达式表示的数。 运算优先级是 $(), +, -$ 从高到低。 考虑建立一个表达式树，进行分治处理。 感觉这里最妙的一点就是节点的合并。 因为我们节点的合并可能是重复写很多次，我们不妨记录节点的数值和长度作为一点类。设其为 $(x, y)$。 我们分类讨论一下合并的情况： $a + b$。$(a_x \times 10^{b_y} + b_x, a_y + b_y)$。 $a(b)$。$(b_x \times ({(10^{b_y})}^{a_x} - 1) \div (10^{b_y} - 1), b_y \times a_x)$。这里代码 ...

CF1548C The Three Little Pigs 算基础的生成函数题了吧。 反正当时隔壁老哥在打 VP 的时候，推了半天 $C$ 没有推出来。被我一眼秒了 $\dots$ 就是答案肯定是 $\sum_{i = 0} ^ {n} \binom{3i}{x}$。 发现这个东西就是个二项式定理。 那么如果写成生成函数就是 $[z^x] (1 + x) ^ {3i}$ 设 $F(x) = \sum_{i = 0} ^{n} (1 + x) ^ {3i}$ 求通项可以得到。$$F(x) = \frac{(1 + x) ^{3n + 3} - (1 + x) ^ 3}{(1 + x)^3 - 1}$$上面那个二项式定理展开可以 $O(1)$ 计算每一项。 之后下面那个直接暴力除法就好了。 大神可以跳过这一段 下面那个柿子展开是 $x^3 + 3x^2 + 3x$。 我们考虑对于一个最高次是 $y$ 的多项式，我们除法第一遍做的商肯定是 $y - 3$。 那么得到 $x^y + 3x^{y - 1} + 3x^{y - 2}$。之后这个是要减 ...

CF1528F 其实不难，但是又有懂得都懂的感觉。 某谷的翻译真的鬼畜。 题目大意： 一个合法的序列 $A$ 是 $\forall j \le n, \sum_{i = 1} ^ n [a_i \ge j] \le n - j + 1$。 给了一个限制 $B$ 序列，要求 $a_{b_1} = a_{b_2} = \dots = a_{b_k}$ 求这样 $(A, B)$ 的数量和。 首先考虑 $A, B$ 看起来很独立，我们考虑分开计算。 对于 $A$ 的限制我们不妨改变一下。 看成有 $n$ 个人，每个人都选择了一个位置 $a_i$。每个人依次坐其选定的位置，如果这个位置有人了那么就向右坐一个位置。如果 $n + 1$ 这个位置没有人，就是合法的。 我们考虑总方案是 $(n + 1) ^ n$ 然后对于一个合法位置其经过变换可以得到 $n$ 个不合法的位置。 那么合法的方案就是 $(n + 1) ^ {n - 1}$。 然后考虑 $B$ 的计数，因为只要满足 $a_{b_1} = a_{b_2} = \dots ...