CF Edu 25 / CF825

D Suitable Replacement

+1 二分 check 时候没有注意，炸 int 了。

二分一下会拿多少个 $T$ ，然后判断一下字母个数够不够用即可。复杂度 $O(n + 26\log n)$ 。

E Minimal Labels

1A

以前的 Edu round 总是可以做到做过的套路题欸。

字典序最小的拓扑序是在 菜肴制作 见过。做法是建反图，然后每次拿最大的点放当前能放的最大标记。

考虑证明，最大的标记肯定出现在出度为 $0$ 的点里面。考虑出度为 $0$ 的点中编号最大的点，记为 $u$ ，这个点必然拿 $n$ 是最优的。假设它没有拿 $n$ ，而拿了 $X$ ，那么我们可以可以把它变成 $n$ ，同时把 $X+1 \dots n$ 给变成 $X \dots n-1$ 。不难发现仍然满足拓扑序，并且字典序变小了。所以我们可以直接把最大点删掉，归纳证明了。

拿堆代替拓扑排序的 queue 即可。

F String Compression

+2 使用了库函数的 log10(x) ，这个东西非常慢，完全比不过手写。所以比较好的方式是预处理，如果太大了就除以 $10^5$ 再用预处理的值。

发现字符串长度才 $8000$ ，考虑直接整一个 $dp$ ，设 $dp[i]$ 表示将前 $i$ 个字符压缩好了，最小需要多少的长度。

转移就是枚举最后一次合并。考虑合并的过程，可以发现，一定拿最小循环节来合并最优秀。因为 $2x,x+1$ 都不可能带来 $c_i$ 上 $2$ 的差异。所以我们可以对每个后缀都预处理出 $\text{next}$ 数组，这样就可以方便地求一段区间的最小循环节了。

复杂度 $O(n^2)$ ，万万别用 cmath 里面的 log10(x) ，建议预处理。

G Tree Queries

+1 向上跳父亲的时候忘记判当前点如果已经染色就返回了。

对我来说感觉很不错的题，想一想还是可以想出来的小清新题。

看到这个题的第一想法是建点分树在点分树上搞。但是会发现 $n,q \le 10^6$ ，而且放在 Edu 比赛里面，不太可能是这种东西。

注意一下性质，可以发现一个点只会往黑色点变而不会变回白色点。我们考虑一个点从白色变成黑色会带来的影响是什么。

假设我们现在把图中的 $u$ 点给变成黑色了，此时 $v,w$ 是不同子树的两个点并且都已经成黑色了。会发现，这个时候 $u$ 的变色不会有任何影响。也就是对于其他任何一个点 $t$ ，它往 $u$ 的路径都一定被 $t \to v,t\to w$ 的至少一条包含。

这也就启发我们，当我们染色 $u$ 点的时候，它到任何一个黑点的路径上的点可以全部染黑。于是黑点会构成一个连通块！而一个点向一个连通块内的某个点的路径最小值就是这个点向任何一个连通块内的点的路径的最小值和连通块内所有点的权值取最小值。

注意到每个点只会被染黑一次，所以我们可以拿第一次染黑的点作为根，每次染色就是从 $u$ 开始向上跳，直到第一个黑点位置，同时把路径上所有点染黑，每次查询就是用这个点到根路径上的最小值与整个连通块取 $\min$ 。

复杂度 $O(n + q)$ 。

Edu 26 / CF837

D Round Subset

本质上是一个二维的背包。

我最开始的 $dp$ 方法比较复杂。考虑的是分别处理除掉 $10$ 后只有 $2$ 的情况和只有 $5$ 的情况。这两个集合分别算出 $dp[i][j]$ 表示选择了 $i$ 个数，其中 $2/5$ 的次幂拿了 $j$ ，最多可以拿多少个 $10$ ，然后再合并起来即可。

虽然过掉了但是写起来比较长，而且不优秀。后来学了一下别人的做法，可以直接设 $dp[i][j]$ 表示当前选择了 $i$ 个数，我们拿了 $j$ 个 $5$ 的情况下最多可以拿多少个 $2$ ，也就是不考虑 $10$ 的问题了。

转移就是看这个数是否拿上，倒序分别枚举这两维，最后答案是 $\min\{dp[k][i],i\}$ 。

这样就比较好写，而且代码很短。

两种实现都写了代码。

复杂度都是 $O(n^3 \log v)$ 。

E Vasya's Function

我们考虑如何去计算 $f(a,b)$ 。不妨设 $t = \gcd(a,b)$ 。不难发现，如果 $t \neq 1$ ，那么有

$f(a,b) = f(\frac a {\gcd(a,b)} , \frac b {\gcd(a,b)})$

所以我们考虑 $t = 1$ 的情况。相当于每次 $b$ 会减少 $1$ 直到 $\gcd(a,b) \neq 1$ 。我们考虑分解质因子 $a$ ，对于所有质因子，我们考虑 $b$ 想要有这个质因子需要减少多少。这个东西可以一次取模搞定，所以我们对这些质因子算这个取最小值，再用 $b$ 减掉即可。然后规模就至少缩小了一般。

最终复杂度 $O(\sqrt a \log b)$ 。

F Prefix Sums

我们考虑这个序列去掉开头的 $0$ 后长度。考虑这个东西的增长，不难发现即使开始是 $1,0,0,\dots ,0$ ，$k$ 次后的值也是 $O(k^{n-1})$ 级别的东西。

所以我们实际上需要进行的操作次数是 $O(\sqrt[n-1]{k} n)$ 。如果 $n > 3$ 可以暴力做。

如果 $n = 3$ ，那么我们可以二分一下要进行多少次操作才能得到大于 $k$ 的值，这里的判断可能会炸 long long ，过程中最好开个 __int128 来。

如果 $n = 2$ ，显然增长是一个一次函数，一次函数求第一次大于某个值的横坐标是很简单的。

这个题挺容易写 WA 的，因为有些乘法加法都可能爆出 long long 。

G Functions On The Segments

我们考虑分别考虑一个函数对 $(x_1,x_2]$ 以及对 $[1,x_1] , (x_2+1,n]$ 的贡献。不难发现对前面这种贡献是一个一次函数的系数的贡献和对这个值本身的贡献分开的，后面两个直接对值产生贡献。对一次函数的系数和值本身分别维护即可。

我们现在要询问只进行 $[l,r]$ 的操作后 $x$ 的值，因为强制在线，所以建两棵主席树后分别维护即可。

也算是很短的数据结构题了。

Edu 27 / CF845

E Fire in the City

个人感觉挺不错的题，因为实现上的细节问题吃了好几发罚时。

考虑我们先二分一下多少轮，然后看看能否通过添加一个矩形使得所有点都被覆盖。

这个东西看起来不太好维护，实际上我们可以离散化 $y$ 坐标，然后从左到右扫描线。记录下第一次扫到空位的地方，最后一次扫到空位的地方，最上方的空位，最下方的空位，然后看看这四个空位是否可以被同一个矩形所覆盖。

这个扫描线由于点的个数只有 $k = 500$ ，可以直接 $O(k)$ 扫描最靠左，最靠右的没有被覆盖的地方，并且 $O(k)$ 维护区间加减。

大概参考了一下别人的代码，做法都差不多。

复杂度 $O(k^2\log n)$ 。

F Guards In The Storehouse

也是不错的题！想了很久，开始一直在想按列来做 $dp$ ，一直感觉维护起来很困难，需要子集枚举之类的东西。很之后才发现插头 $dp$ 做这个东西就很好维护。感觉很多时候如果一条一条的加不好维护就可以考虑一个一个加，做插头 $dp$ 。

首先 $nm \le 250$ ，意味着较小的那一列只有 $15$ 级别。这个数据范围考虑状压 $dp$ 。

我们考虑让列成为 $n,m$ 中的较小值，如果不是则翻转一下。

然后设 $dp[i][j][sta][0/1][0/1]$ 表示当前在 $(i,j)$ 当前下方的轮廓线的被从上面的灯照射到的状态是 $sta$ ，类似一般的插头，长这样：

绿色部分是否被上方照射下来的灯光照射到的状态是 $sta$ ，红色点是当前考虑的 $(i,j)$ 。后面的第一个 $0/1$ 表示是否被左边的一个等照射过来照射到，第二个 $0/1$ 表示是否已经选择了一个格子不去被光照射。

转移分情况讨论，如果这个位置是墙，那么这个位置只能转移到这个位置没有被照射到的情况，转移就把 $sta$ 的这一位强制整成 $0$ 。否则：

• 假设这个位置没有放灯

  • 如果当前列不是这一行第一列，那么这个格子的左边格子如果被左边的灯所照射到，这个格子就也会被左边的灯所照到照射到。转移就保持之前的 $sta$ 不变。无论这个位置是否会被上面所照射到，都考虑进行这个转移。
  • 如果当前这一列被上面所照射到了，我们把左边没灯的情况转移过来，如果这是第一列，那么左边有灯也要转移（因为没在上面考虑到）
  • 如果这一列没被上面所照射到，如果也没被左边所照射到，可以在这里作为选择的一个格子不被光照射。选择的时候也要判断一下，如果当前位置是这一行开头，那么可以从左边有光转移过来。

• 假设这个位置有放灯

  那么转移到的状态 $sta$ 需要把这一位给安排上，同时一定转移到左边有灯照射的情况。

复杂度 $O(nm 2^{\sqrt{nm}})$ 。可以跑过去。

因为转移没讨论清楚吃了很多发罚时。

个人觉得写的比较好的是 Andrei1998 和 Benq 的代码。这两份代码在插头 $dp$ 讨论上一行到下一行的转移的时候都比我的代码清楚。

前者考虑转移把状态设成 $dp[0/1][i][sta][0/1][0/1]$ ，第一个状态表示滚动了行。然后枚举行的，在把这一行所有列处理结束后，考虑再进行一次转移表示从这一行转移到下一行，这一次转移就是在把 从左边是否被照到 这个状态给变成 $0$ ，其他状态不变。然后之后就照常转移即可。在这个题中这样写起来就会很方便。

后者类似于此，我们在转移完后把这一行转移结束后的状态丢到一个单独的数组 $s$ 中，同样是把上一层 从左边是否照到 这一维度给置空。

这两种做法都可以在动规中防止去讨论当前位置是否为这一行的开头。

最后修正了一下，代码好看了很多。

code

G Shortest Path Problem?

经典题。

找出所有环，然后把这些环都丢到线性基里面去，再随意拿一条 $1 \to n$ 的路径看看再线性基里面可以异或出的最大数。

因为在走一条 $1 \to n$ 路径的时候，唯一可以改变路径异或的方式就是走出去走到一个环上，跑一圈，再走回来，到环的路径被异或两次消没了。所以相当于是可以找一个环异或上。

Edu 28 / CF846

D Monitor

我们二分一下最早崩掉的时间，然后加入这些坐标后做一次二维前缀和，判断是否存在 $k \times k$ 的矩形即可。

复杂度 $O(n^2\log t)$ 。

E Chemistry in Berland

考虑做一个显然的 $dp$ 。设 $dp[u]$ 表示当前考虑到树上的 $u$ 这个节点和它的整个子树，还剩多少可以分出去（正值），或是有多少需要被送进来（负值）。向上转移过去的时候如果是负值需要乘上这条边的边权，正值就直接加上即可。复杂度是 $O(n)$ 。

但是注意到边权的乘积会非常大，所以需要考虑，如果一个 $dp$ 值爆过了 $-2 \times 10^{17}$ ，可以考虑直接认为这个位置是把所有物品都运送过来都无法解决的了，所以做的时候判断一下大小是否大过这个级别即可。

或者可以直接开 long double 。因为如果真的很大，那么对精度的要求就不会很高，只需要在意这个数量级。可以过掉这个题，但是能不能叉不太清楚。

开始读错题了，以为是儿子换父亲是 $1$ 换 $k$ WA 了一发，后来没有注意答案上界又 WA 了一发。

F Random Query

这题做 F 就很离谱。

考虑一个区间的答案，就是区间内中上一次出现位置小于左端点的个数。

考虑固定右端点，那么考虑每个数 $i$ 的贡献，相当于左端点处在 $[last_i + 1,i]$ 之间的时候存在贡献，贡献就是 $i - last_i$ ，所以对于一个右端点直接对 $\sum i - last_i$ 求和即可。

复杂度 $O(n)$ 。

Edu 29 / CF863

E Turn Off The TV

考虑一个区间 $[l,r]$ ，我们给这个区间加 $1$ 。

然后想要找一个区间删掉后覆盖的区域不变，就是内部最小值大于等于 $2$ 。

但是下标范围很大。所以可以离散化一下，考虑其实真正可能导致没覆盖的位置只可能是 $L-1,R+1$ 这种。所以加进去离散化即可。

数组没开够，RE 了一发。

F Almost Permutation

这都第二次做到很裸的费用流了

考虑把限制放到数组里面，区间大于等于 $t$ 相当于把区间的下界都与 $t$ 取 $\max$ ，区间小于等于 $t$ 就是上界取 $\min$ 。

所以我们可以整个序列处理好每个位置的上界和下界。

然后考虑每个位置我们都建一排 $1 \sim n$ 的点，在 $[L,R]$ 间给 $L \to L+1,L+1 \to L+2 \dots , R-1 \to R$ 都连上边，费用是 $0$ 容量是 $1$ 。然后考虑从每个值 $i_x$ 连向这个值真正代表的点 $i$ ，然后从每个值得点向汇点连 $n$ 条边，费用分别是 $1,2^2-1,3^2-2^2 \dots$ 这样的，容量均为 $1$ 。然后从原点向每个 $L_x$ 连费用 $0$ ，容量 $1$ 即可。

然后跑最小费用最大流，如果无法满流就无解，否则费用就是答案。

G Graphic Settings

分类讨论，而且不是很会做，感觉没啥意思，放掉了。