2020.08.19 2020杭电多校第一场

2020.08.21 2020杭电多校第二场

2020牛客暑期多校训练营（第一场）CJY G XX C

2020牛客暑期多校训练营（第二场）Finish

2020牛客暑期多校训练营（第三场）CJY J/K ZRX I

2020牛客暑期多校训练营（第四场）CJY E/J XX G ZRX I

2020牛客暑期多校训练营（第五场）CJY G/J ZRX A/H

2020牛客暑期多校训练营（第六场）CJY F XX I ZRX D

2020牛客暑期多校训练营（第七场）CJY E XX F ZRX A/C

2020牛客暑期多校训练营（第八场）CJY D XX J ZRX B/C

2020牛客暑期多校训练营（第九场）CJY H XX G ZRX L

2020牛客暑期多校训练营（第十场）CJY G/H XX B/D ZRX F

2020加赛1 CJY A/E XX B/C ZRX D

2020加赛2 CJY E

2015ICPC北京 CJY C XX D ZRX E (BFH)

2020杭电多校第一场 CJY E XX J ZRX C

无

2020.08.12 AtCoder Grand Contest 047

2020.08.13 Codeforces Round #664

2015ICPC Beijing C D

2020牛客多校训练营（第九场）D H

从二分图最大匹配到二分图最优匹配

2020.08.08 2020牛客暑期多校训练营（第九场）

2020.08.10 2020牛客暑期多校训练营（第十场）

2020.08.12 2015ICPC北京赛区

atcoder abc 171

atcoder abc 172

2020牛客暑期多校训练营（第四场）I

atcoder abc 171 F

atcoder abc 172 E

Lyndon分解

无

2020杭电多校第一场 J

Codeforces 1393 E

Codeforces 1398 F

题意

atcoder abc 171 F

长度为n(⇐1e6)的只有26个小写字母的串，往进再插入k个(⇐1e6)个小写字母，能组成多少种不同的串。

思路：

考虑最终的串，先把n个本身的串插进去，然后要求如果有重复的话，要求本身的串插进去的必须是最后一个出现的位置。

所以枚举第一个字符插到i，前面是随便填的，$26^{i-1}$,然后其他n-1个就通过一个组合数知道了方案数，至于剩下的没有被插入的位置，由于我们规定了原字符是出现的最后一个位置，所有它后面到下一个字符出现前只有25种选法，所以再乘上25的剩下位置次方即可。

评论：

找到一个好的去重姿势

2020牛客多校训练营（第九场）D

题意

有一棵树，n个点，每一条边只能是编号在$[L_i,R_i]$内的人通过，问每个人在通过不超过$K_i$($K_i\leq1$)条自己不能通过的边所能到达的点的数量。

思路：

容易想到用线段树维护加边，这样就转化成在线段树dfs，用可撤销并查集来维护连通块的一个问题。

当然K=0就已经完美解决了，我们发现K=1时要求的是这个连通块往外一步的点的个数，第一反应是去维护这个值，发现做不到，于是我们意识到

要利用树的性质。

考虑每个联通块维护除根节点向上以外的所有不属于这个连通块的一部点的数量，发现这个是可以维护的，只要维护每个连通块的最高节点就好

了。

再利用栈去维护修改操作就可了。

评论：

可撤销并查集是一个好东西，就看你会不会用。

来源：CF 1393 E2

算法：字符串排序、双指针、hash、二分

题意：n个串，每个串删一个字符或者不删，求n个串能排成按照字母序升序的方案的数量。

思路： 1. （串内）排序：求对于每一个串，求删除第i个字母后的串的排序。设$nxt_{i}$为第i个字母右侧第一个与之不同的字母的位置。从左到右扫一遍，如果$s_{i} > s_{nxt_{i}}$，放到sorted序列左边，否则放到右边。

2. DP：$f_{i,j}$表示第i个串，删除第$sorted_{j}$位置的方案数。利用双指针法进行转移。

3. 判断两个串的大小：hash+二分，二分第一个不同的位置，进行比较

题目

代码

评论：

根据字符串的特殊性质进行O(N)的排序。