目录
比赛名称
A.
solved by 2sozx
题意
给定一个无向图，每个点有个权值 $b_i$ ，每次操作可以选择一个连通块并且将这个连通块所有点的 $b_i-1$，问最少要操作几次使得$b_i=0(i=1,2\cdots n)$。$(n\le10^5,m\le2\cdot10^5)$
题解
暴力的思路很好想，每次选择一个不包含 $b_i=0$ 的最大连通块，然后将这个连通块所有 $b_i-1$即可，显然会超时。
我们考虑将 $b_i$ 从大到小排序，对于扫到的点我们只考虑比当前枚举的 $b_i$ 大的点。先将 $b_i$ 加入答案，如果此时不在一个联通块中将其合并，并且可以从答案中减去 $b_i$，因为在考虑过这个点之后比他大的点就可以少操作 $b_i$ 次，用并查集维护联通即可。
B.
solved by
题意
题解
C.
upsolved by
题意
题解
D.
upsolved by JJLeo
题意
给定一个$n \times n$的方格图，每次只能向右向下走，要从左上角走到右下角。每个方格有一个权值$a_{i,j}$，路径上每经过一个点就会获得${(n^2)}^{a_{i,j}}$的权值。现在有$q$次询问，询问若一个矩形区域不可通过，所有合法路径中的最大权值对$10^9+7$取模。$(n \le 400, q \le 2 \times 10^5)$
题解
如图所示，设灰色区域为被禁止通过的区域，那么所有合法路径一定至少经过了一个红色格子或绿色格子，同时至少经过了一个红色格子或绿色格子的路径也是合法的。因此可以求出每个点分别到起点和终点的最大权值，求一下每一行的前缀后缀最大值即可。
然而cls并没有让这题就这样结束，可以发现权值太大没有办法直接维护。观察权值的底数可以发现我们可以将权值和写成$n^2$进制，这样权值相加可以保证不会发生进位，从而将比较大小改为比较两个字符串的字典序。每次转移中相当于在某一位加了个$1$，因此我们可以用主席树维护每个权值，比较大小时维护区间哈希值，在线段树上二分最长公共前缀，最终比较第一位不同的而得出大小关系。另外因为我们要维护每个点分别到起点和终点的最大值，最终求每一行的最大值前后缀需要进行加法，因为两者相加的哈希值等于两者的哈希值相加，所以直接将两棵树放一起进行比较即可。
E.
solved by JJLeo
题意
$n$个人，$m$个机器，第$i$个人找第$j$个机器权值为$a_ij^2+b_ij+c_i$，现在问匹配$1,2,\cdots ,n$个人的最小收益都是多少。$(n \le 50, m \le 10^9,a_i > 0, {b_i}^2-4a_ic_i \le 0)$
题解
找二次函数顶点，周围扩一定量的点，肯定是最优的，但是不能一个扩$n$个不然$O(n^5)$会炸的。然后乱搞一波套EK就过了。
F.
solved by
题意
题解
G.
upsolved by JJLeo
题意
给出一个$n$个节点的树，每条边有两个权值$a_i$和$b_i$，现在可以让恰好$k$条边为$a_i$，其它边为$b_i$，问最小直径是多少。$(n \le 2 \times 10^4, k\le 20)$
题解
先二分直径长度，然后设$f_{i,j}$为以$i$为根的子树中有$j$条边选择$a_i$时所有链长度都不超过二分的长度，满足上述条件的所有方案中以$i$为端点的最长链的最小值。合并时只要两者之和不超过二分的长度即可合并，初始值$f_{i,0}$设为$0$，其它全部设为正无穷即可。可以发现这就是个树形背包，因此上下界优化后复杂度为$O(nk)$，再加上二分的总复杂度为$O(nk\log n)$。（但是还是被卡常卡吐了，比标程慢了一倍多，cls，卡常的神！）
H.
upsolved by JJLeo
题意
给定数个
题解
I.
upsolved by
题意
题解
J.
solved by JJLeo
题意
题解
K.
upsolved by
题意
题解
L.
upsolved by
题意
题解
记录
0min：分题，又没找到签到题
38min：ZYF冲J暴搜，T2后AC，CSK冲F
78min：CSK T2,WA3后AC，MJX冲A
104min：MJX WA1后AC
144min：ZYF WA1后AC，MJX ZYF 冲E
227min：N WA后AC，CSK冲I
287min：N RE后AC
till end：G被卡常了，cls为啥能跑那么快
总结
- MJX：并查集合并出问题，太离谱了。
- ZYF：感觉低级错误太多，码力不够，WA了无数次，浪费了大好时光。最后G写对了可惜被卡常了。
