省流
欢声笑语中打出 gg。感受很正常，解压了。
11.7
内含剧透，请vp后再来。
不是题解！！！！！！！
赛时
直接说题目。暴力不谈。
B 题是要求构造一个长度为 \(n \leq 1e5\) 的序列，其中有 \(m\) 个限制，第 \(k\) 个限制是要求 \(a_i \oplus a_j = w_k\)。问能否构造出满足所有限制的序列，如果可以构造一个和最小的。
先考虑可达性。利用异或可逆，可以把一个点上所有条件转化成除它之外的点之间的条件，然后往后一直找到结尾，如果没有冲突就可以实现。然而这样的复杂度达到了 \(O(n^3)\)。利用异或只与某一位相关，把所有数拆成二进制，跑一个 dfs 可以把一些相关的点分成两组，选其中较小的一组在这一位上填 \(1\) 即可。
J 题给了一个四位的锁，有一个初始状态和目标状态，每次可以把相连的一些数增大或减小一。问至少多少次变成目标状态。首先可以把所有状态都转换成从 \(0000\) 开始，然后 dp。由于几种操作的先后顺序不影响最后结果，所以之间跑一个暴力，用每种操作方式对于每个状态遍历能到的所有情况并尽量减小，状态数为 \(1e5\)，每次遍历的大小为 \(10\)，操作方式也就十几二十种，故可以通过。
赛后
L 题给定一个 \(2 \times n, n \leq 2000\) 的完全图，在其中删掉一颗大小为 \(2n - 1\) 的树，问剩下的图中完全匹配方式数。考虑容斥原理，就是整张图减去用一个边加用两个边……对于用 \(k\) 条边的，可以拆成在删除的树种找 \(k\) 条可以同时选的边乘剩下的图中选择 \(n-k\) 条边的方式。后面显然比较好求，选择任意第一个点后，剩余可选点数就减二，递推容易得到所有情况的值。前者可以通过简单的树形 dp 解决。
2025年9月24日