目录
比赛名称
A.
upsolved by JJLeo
题意
给出一个$n$个点$m$条边的图，从$1$号点出发，依次经过$2k$个点，途中经过一点时可以在这点放传送门，任意时刻只能存在最多两个传送门，两个传送门可以瞬间互达，求途径的最短距离。$(n, k \le 300, m \le 40000)$
题解
设$f_{i,j}$为目前已经到第$i$个目标点，传送门位于$j$点所经历的最短路程。转移有以下几种：直接走到下一个目标点；直接传送到传$j$的位置，然后走到一个位置放传送门，再走到下一个目标点；直接走到一个位置放传送门，走到这个位置然后传送到$j$的位置，再走到下一个目标点。两点间最短距离跑一遍floyd即可，注意有重边，总复杂度$O(n^2k)$。
B.
solved by JJLeo
题意
给出一棵$n$个点的树，每条边有权值，可以删边或加边任意次，要求任意时刻满足图联通且所有环的边权异或值为$0$，求最终所有边权之和的最小值。$(n \le 100000)$。
题解
XOR-MST。
C.
upsolved by JJLeo
题意
设两个长度为$k$的正整数序列$a$和$b$，他们的和分别为$N$和$M$，求所有可能的$a$和$b$的$\prod_{i=1}^k\min(a_i,b_i)$之和。$(1 \le N,M \le 10^6,1\ \le k \le \min(N,M))$
题解
构造二元生成函数$f(x,y)=\sum{\min(n,m)x^ny^m}$，$f^k(x,y)$中$x^Ny^M$的系数即为答案。差分后可以凑出$f(x,y)$的和函数为$\dfrac{xy}{(1-x)(1-y)(1-xy)}$，因此只需求$\dfrac{1}{{(1-x)}^k{(1-y)}^k{(1-xy)}^k}$展开式中$x^{(N-k)}y^{(M-k)}$的系数即可。枚举$\dfrac{1}{{(1-xy)}^k}$的次数，即可得到$\dfrac{1}{{(1-x)}^k}$和$\dfrac{1}{{(1-y)}^k}$对应的次数，最后答案为数个三组合数乘积的和，时间复杂度$O(\min(N-k,M-k))$。
D.
solved by 2sozx JJLeo
题意
给定一个$1$到$n$的排列，有两种操作，第一种操作为将倒数第二个操作移动到第一个；第二种操作为将第一个元素移动到最后一个。设连续的第一种操作为一个大操作，问将排列变为有序最少需要几次大操作。$(n \le 500)$
题解
可以发现第二种操作相当于进行循环同构，因此连续的第一种操作等价于将某个元素放到任意一个位置。因此只需要找所有循环同构中找一个最长上升子序列，调整其它数字位置即可。
E.
upsolved by
题意
题解
F.
solved by
题意
题解
G.
upsolved by JJLeo
题意
给定一棵有根树，每个点有一个颜色$c_i$，每个点可以取一个权值$d_i$，设以其为根的子树中颜色为$d_i$的点的数量为$x$，则该点权值为$xd_i$。现在问所有点权值组成集合的$\operatorname{mex}$最大为多少。$(n \le 20000)$ 本题时限8s。
题解
因此
H.
upsolved by JJLeo
题意
题解
I.
solved by 2sozx
题意
定义三种颜色 $G,H,E$ ，与 $H$ 相邻的四个格子中至少有 $G,E$ 各一个，现在考虑无限大的平面，问 $H$ 所占的比例最大是多少。
题解
按对角线排，两行H，一行GE交错为最优，答案即为$\frac{2}{3}$
J.
upsolved by
题意
题解
K.
upsolved by JJLeo
题意
题解
记录
0min：开局分题
10min：CSK秒F，MJX ZYF看I，WA
35min：MJX AC I
63min：MJX Python 写E，写崩了
73min：MJX 和 ZYF看D，CSK接手E
138min：ZYF AC D，看B
144min：CSK AC E
204min：ZYF AC B
till end：集体看K没调出来
总结
- MJX：熟悉熟悉Python，别犯低级错误
