2024.12.21 校内模拟赛 题解 最后更新于 2025-05-01 20:03:05

# T1 背包DP，加一个bitset优化，时间复杂度 $O$ ( $n^2/w$ )。 [**T1 AC code**](https://www.luogu.com.cn/paste/qct90eqt) # T2 发现随便确定一个点的权值，就可以确定全图的所有点的权值。于是用未知数 $x$ 表示联通块中每一个结点。遇到奇环就解方程，偶环判是否无解。如果没有奇环，零点分段（七上数学）。时间复杂度 $O$ ( $nlogn$ )，带 $log$ 的原因是有一个排序 。 [**T2 AC code**](https://www.luogu.com.cn/paste/bkxpyp3s) # T3 启发式合并即可，合并的同时更新最小值。用set写会比较方便，时间复杂度 $O$ ( $nlog^2n$ ) 。 [**T3 AC code**](https://www.luogu.com.cn/paste/6ymrbsnt) # T4