日记 2023.11.3：2023 syzx 秋季训练 5
A
在每个节点上决策，做两两匹配。
B
背包。\(dp(i, j, a-b)\) 表示前 \(i\) 张牌，有 \(j\) 张翻倍，Alice 点数是 \(a\)，Bob 点数是 \(b\)。\(O(26n^3)\)。
C
斐波那契拆分。当忽略 1,2 操作时，每一次操作完以后被操作的数 \(f_i=f_{i-1}+f_{i-2}\) 这样子的斐波那契数列。因为任意正整数可以拆分为若干斐波那契数的和，拆出 \(f_i\) 就在倒数第 \(i\) 次操作之前使得另一个数字 \(+1\)（相当于它的影响是后面的这些操作造就的，影响是斐波那契数）。有 \(87\) 个斐波那契数在值域内，但是我们不能选相邻的斐波那契数，否则可以合并成一个新的。
随机化。随机最终的 \(y\) 然后做辗转相除。
D
Kruskal 重构树。叶子是原来的点，中间的点是它们的边权。如果能到达 \(p\)，那么 \(p\) 的整棵子树都能到达，因为他是 Kruskal，下面边权更小。于是答案可以表示为重构树上的一个子树。倍增最终的子树是哪一棵。
启发式合并。离线询问，按照 Kruskal 的过程，合并两个点集，点集上挂着询问。每次合并时删掉止步于此的询问，剩下的询问就小的往大的合并。使用优先队列合并或者左偏树。
E
Bitset。\(O(n^2/w)\)。当知道 \(k-1\) 时每个右端点的答案后，尝试算 \(k\)。发现就是要找到一些区间和 \(=0\) 的区间（\(\forall x\in a,x:=1-2x\)）的所有右端点，考虑前缀和以后，搞几个基于值域的 Bitset。啊，真能转移吗？好像做一点左右移就行。啊？
F
Alice 是傀儡，因为 Bob 可以先在心中匹配好 \(n\) 对数，然后 Alice 选什么数，Bob 就选与之配对的数，所以博弈就能丢掉了。
分治。在某一位上时，如果这一位是 \(0\) 和 \(1\) 的大小都是偶数，那么两个子树内直接配对，分别递归下去。
否则答案就要跨过这颗子树了。枚举哪一对数跨过去，它们的异或最小值是多少？Trie。注意其他数字没有那一位，所以这样做就是对的。
\(O(n\log n)\)，因为每个数字只被插入一次。
注意这一对跨过去的数字，算的时候不可以忽略最高位排序然后选相邻两个来自不同子树的值。考虑 \(A\) 集合的数字 \(\leq 01111111_2\)，\(B\) 集合的数字 \(\geq 10000000_2\)，然后你选出 \(01111111_2\operatorname{xor}10000000_2\) 就寄了。当然如果是同一个集合，那么最小的两两异或值确实来自所有值域相邻的数字对。
G
容斥 \(x\) 条边断开，注意在一个置换环内不能断 \(0\) 条边。因为这个限制，我们刻画选 \(i\) 条边断开的方案数是：
\(-1\) 就是去掉了断 \(0\) 条边。最终容斥系数是 \((-1)^{n-i}\)。即答案是：
分治 FFT。
H
直接按行状压 DP。状态 \(O(n3^m)\) 表示上面封死，或者有一个车，或者需要一个车。决策就是枚举填成什么东西，需不需要放车。总共 \(O(n9^m)\) 或者 \(O(n6^m)\)。
轮廓线 DP，\(dp(i, j, msk)\) 表示在 \((i,j)\) 这个格子，左边的状态记录为 \(msk\) 的左边，上面的状态记录为 \(msk\) 的右边。然后决策只剩 \(O(1)\)。注意还需要记录来自左边的一个状态，\(O(nm3^{m+1})\)。
I
求 \(a_i\oplus a_j=0\)，其中 \(\oplus\) 就是那个计算门。枚举 \(a_i\)，现在 \(a_j\) 的某一些位必须是 \(1\)，或者必须是 \(0\)，或者没有关系。直接预处理它！！！FWT 或者直接暴力都行了。反正一万种做法，不知道为啥 7s。
J
倒着做，考虑最后一个 \(A_n\)，它可以是最后一个当且仅当 \(A_n\not\mid lcm(\{A_1, A_2, \cdots, A_{n-1}\})\)。考虑判定每个质因子的次数即可。
具体一点就是说我们要求 \(lcm(A_n, S)>lcm(S)\)，其中 \(S=\{A_1, A_2, \cdots, A_{n-1}\}\)，移项得 \(A_nlcm(S)>lcm(S)\gcd(A_n, lcm(S))\) 即 \(A_n>\gcd(A_n, lcm(S))\)，这个东西的处理是 \(=lcm_{x\in S}(\gcd(x, A_n))\)，你就考虑每一个指数确实如此。\(\min(x, \max_{y\in S}y)=\max_{y\in S}\min(x, y)\)。
然后也说明了我们可以随意选择 \(A_n\)，因为 \(A_n>gcd(A_n, lcm(S))\)，确定一个数字之后 \(lcm(S)\) 只会降低，\(\gcd\) 只会降低，它以后还是可以填到最后面，不破坏有解性。