比赛链接

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)$。

solved by JJLeo

给出一棵$n$个点的树，每条边有权值，可以删边或加边任意次，要求任意时刻满足图联通且所有环的边权异或值为$0$，求最终所有边权之和的最小值。$(n \le 100000)$。

XOR-MST。

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))$。

solved by 2sozx JJLeo

给定一个$1$到$n$的排列，有两种操作，第一种操作为将倒数第二个操作移动到第一个；第二种操作为将第一个元素移动到最后一个。设连续的第一种操作为一个大操作，问将排列变为有序最少需要几次大操作。$(n \le 500)$

可以发现第二种操作相当于进行循环同构，因此连续的第一种操作等价于将某个元素放到任意一个位置。因此只需要找所有循环同构中找一个最长上升子序列，调整其它数字位置即可。

solved by Bazoka13

给定一个排序，每次将第$i$位数字移动到$b[i]$位，问有几种数列按照该方法进行足够多次可以完成排序。

求所有循环节结点数的$lcm$即可，注意高精，python除法用$//$

solved by Bazoka13

按照题意模拟的水题，不过题面描述貌似不太通顺导致卡到10min才过

upsolved by JJLeo

给定一棵有根树，每个点有一个颜色$c_i$，每个点可以取一个权值$d_i$，设以其为根的子树中颜色为$d_i$的点的数量为$x$，则该点权值为$xd_i$。现在问所有点权值组成集合的$\operatorname{mex}$最大为多少。$(n \le 20000)$

本题时限8s，空间64MB。

时限很大，因此直接$O(n^2)$找每个点可能的权值（直接dfs一次记录dfn序常数更小），然后二分图跑最大匹配。但是本题卡空间，所以拿bitset存边，然后用增广路算法跑，虽然复杂度是$O(n^3)$的但是跑不满可以卡过。

upsolved by JJLeo

给出一个长度为$n$的序列，$q$次询问一个区间所有子区间$AND$值所组成集合的大小，强制在线。$(n,q \le 10^5)$

固定右端点，有可能的取值为$O(\log n)$种，因此我们可以从左到右，固定右端点，将$a_i$与右端点为$i-1$的所有值进行$AND$操作，得到所有可能的取值及其左端点的范围，这一部分总复杂度为$O(n \log n)$。接下来以每个点为右端点为根，建立主席树，对于$[l,r],[l+1,r],\cdots , [L,r]$均为某一个值$x$，直接在$r$为根对应的线段树上给$l$位置加一即可。考虑去重：如果相同的数上一次加一的位置若$< l$，则在老的位置减一即可，否则不做加一操作，直接用上次的值即可。

solved by 2sozx

定义三种颜色 $G,H,E$ ，与 $H$ 相邻的四个格子中至少有 $G,E$ 各一个，现在考虑无限大的平面，问 $H$ 所占的比例最大是多少。

按对角线排，两行H，一行GE交错为最优，答案即为$\frac{2}{3}$

upsolved by

upsolved by JJLeo

合并一个代码的两个分支使得总代码行数最短，代码中有的部分是分支1，有的部分是分支2，还有公用的部分。要求两个分支合并后代码执行顺序要和合并前相同，且只有完全相同的行才可以放在公共部分，否则必须出现在#ifdef branch1 和 #ifdef branch的代码块内，当然也可以用#else 和 #endif。

设$f_{i,j,k}$表示此时到分支1的第$i$行，分支2的第$j$行，此时处于分支1/分支2/公用的代码块内。限定分支1可以到分支2，分支2不能切到分支1，且只有两行完全一致才能在共用代码块，具体行数变化分类讨论一下即可。另外要给每个转移标个号最后逆序记录方案输出。

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，别犯低级错误
• ZYF：前期梦游，昏昏欲睡。最后一个多小时K题完全理解错题意，被之前某括号匹配误导，难受。
• CSK：熟悉熟悉python+1，白给一发才发现除号错误，甚至跑去用java白给了一发