2021 ICPC 沈阳站
题目链接
题解
B
枚举每一个位，枚举每个连通块对应选的是什么时最优，求个和即可。在枚举时可判断是否合法。
E
签到题。
F
暴力即可。
G
H
线图上的图匹配相当于原图中相邻两边的匹配。
性质一：一个有偶数条边的树可以匹配完。
证明：从最深叶子结点选择两条边，变成一个子问题。
性质二：一个有偶数条边的连通图可以完全匹配。
证明：相当于dfs树中加上若干条返祖边，在叶子结点选边匹配的时候优先选返祖边即可。
那么只剩下边为奇数的情况。显然如果删掉某条边后不改变图连通性，那么就可以删掉该边，否则该边为割边，删掉后需要满足两边边数均为偶数即可。这些均可在求割边时找出。
时间复杂度 $O(n+m)$。
I
将 $a,b,c,d$ 视为未知数。四个 $az_i+b=w_i(cz_i+d)$ 转换为线性齐次方程组。
由克拉默法则： $a,b,c,d$ 有非零解当且仅当：
$$\begin{vmatrix}
z_1 & 1 & w_1z_1 & w_1\
z_2 & 1 & w_2z_2 & w_2\
z_3 & 1 & w_3z_3 & w_3\
z_0 & 1 & f(z_0)z_0 & f(z_0)
\end{vmatrix}= 0$$
直接解出 $f(z_0)$ 即可。
J
将询问的两个数的每一位的差算出来，组成一个新的数 $x$。
然后预处理出 $0$ 到 $x$ 的距离即可。
L
设假设树上至少有 $i$ 对节点选择了的方案数为 $f(i)$，那么答案为 $\sum_{i=0}^n(-1)^if(i)\frac{(2(n-i))!}{(n-i)!2^{n-i}}$。
求 $f(i)$ 用树形背包即可。
时间复杂度 $O(n^2)$。
M
对反串建立SAM，对parent-tree中每个节点的边按字典序进行排序以后，相当于求一个前缀最大值。
时间复杂度 $O(n\sum)$。