2024 暑假训练（2024-08-18~）

因为每次建一个文章太麻烦，所以整合到一起了。

2024-08-18

to

求一个表达式的期望值，每个数互不相同。

学到了一个东西：期望可加：\(E(X+Y)=E(X)+E(Y)\)。

也就是：\(E(abc+abd)=E(abc)+E(abd)\)。

很神奇，然后两个部分就互不影响了。

分数

求繁分式的一部分的值。

应该会有一个直观的感受，可以建出一个分治树，然后树上做：\(O(q dep)\)。

但是我们发现 \([l,r]\) 的答案就是 \(l-1\) 的点到 \(lca\) 的链上所有不在该链上的右儿子，与 \(r+1\) 的点到 \(lca\) 的链上所有不在该链上的左儿子。

      *
     / \
    *   *
   / \ / \
   * B C *
  / \   / \
l-1 A  r+1 *

字母的都是答案，那么就是 \(AB^{-1}C^{-1}\)。

然后 \(l-1\) 的答案是 \(AB^{-1}C^{-1}D^{-1}E^{-1}F^{-1}\cdots\) 的。

\(r+1\) 的答案是 \(A^{-1}BC^{-1}DE^{-1}F\cdots\) 的。

大力维护就好了，注意如果 \(l-1\) 不存在那么 \(r+1\) 的答案要取负数。

这是一种分治优化的套路，建出分治树然后用 \(l-1\) 和 \(r+1\) 与它们的 \(lca\) 计算答案。答案就是链上所有不在该链上的左/右儿子。

还有一个优化：这道题不需要再用 st 表求 lca，不然会爆空间。这里分治的 mid 是区间最大值，所以我们可以求 \(l-1\) 与 \(r+1\) 区间最大值找到 \(mid\) 是这个值的节点就可以了。

---

\(O(n)\) rmq：本质就是分块，见由乃救爷爷。

2024-08-20

树上选点

很妙的 dp。

我们朴素的想法是记录 \(f_{u,i,j}\) 表示第 \(u\) 个节点有 \(i\) 个点被染色，\(j\) 个点是好的。转移显然。

然后发现当 \(j\ge1\) 时，\(i\) 必定大于等于 \(k\)，所以记录 \(f_{u,i}\) 表示第 \(u\) 个节点有 \(i\) 个点被染色，\(0\) 个点是好的，记录 \(g_{u,i}\) 表示第 \(u\) 个节点有 \(\ge k\) 个点被染色，\(i\) 个点是好的。转移就很容易了。

这种题目需要注意的是发掘性质，发现无用的状态，将其优化掉。

排列

发现前两个都是确定性的，最后一个不确定，

所以就是三种方案：冒泡排序、倒序后冒泡排序，随机选择后冒泡排序。

设答案为 \(ans\)，我们随机选择时有两种情况：劣的与不劣的。

对于劣的，我们再随机一次，不劣的直接冒泡。

所以我们考虑什么时候叫做不劣的，枚举这个不劣的界限即可。

金鱼草（snapdragon）

签到题，用类似扫描线的思想维护。

思考：可以上树吗？

【TODO】

2024-08-21

阵

傻逼构造不给 spj 害的我忘记输出 Yes。

以后还是要细心细心再细心！

考虑蛇形构造即可。

1 4 5 8
2 3 6 7
9 12 13 16
10 11 14 15

堆

对 FWT 的理解又进了一步！

如果你做过 nim 游戏相关问题，容易发现这类 nim 游戏基本都是使用 fwt 的异或卷积来求解。最后答案就是除 \(0\) 以外所有卷积的结果（因为异或为 \(0\) 先手输）。所以我们考虑使用异或卷积。

---

这里有一个子问题：Nim Counting。

根据玩 Nim 游戏的经验，可以发现先手获胜当且仅当 \(\bigoplus_{i=0}^n A_i\neq 0\)。

所以我们定义 dp 式子 \(f_{i,j}\) 表示有 \(i\) 个石堆，且石堆异或和为 \(j\) 的获胜方案数，有： \[ f_{i-1,j}\to \sum_{k=1}^Kf_{i,j\oplus a_k} \]

答案就是 \(\sum_{i=1}^n\sum_{j\neq0} f_{i,j}\)。

直接转移是朴素的，发现上面的式子刚好是 FWT 异或操作，也就是： \[ f_{i,j}=\sum_{k\oplus x=j} f_{i-1,k}a_x \] 我们定义 \(a\) 是一个全是 \(1\) 的数组即可。

同时，我们发现其实不需要真的进行 \(n\) 次卷积，其实只需要利用 FWT 的线性性，将 FWT 变换过之后的结果 \(A\)，求出 \(A+A^2+A^3+\cdots+A^n\) 即可。

---

这题的 nim 游戏变种也不难可以推理出先手胜的要素。枚举所有石子的异或和，先手赢等价于没有一堆石子个数与所有石子的异或和相等。

那么不难发现我们可以枚举石子异或和，然后不取我们枚举的值的石子，那么就一定可以胜。

令 \(p\) 表示 \(a\) 对应的概率数组。设 \(f_{t,i,j}\) 表示钦定了异或和为 \(t\)，有 \(i\) 个石堆，且石堆异或和为 \(j\) 的获胜概率。

那么有： \[ f_{t,i-1,j}\to \sum_{k=1}^n[k\neq t]f_{t,i,j\oplus k} \] 答案就是 \(\sum_{i=0}^\infty f_{t,i,t}\)。

然后你发现你又会了。 枚举 \(t\)，对于每个 \(t\)，将 FWT 变换过之后的结果 \(A\)，求出 \(A_t^0+A_t^1+A_t^2+A_t^3+\cdots+A_t^\infty\) 即可。

不难发现上面的值是一种 \(\bf Sequence\) 构造。答案就是 \(\frac{1}{1-A_t}\)。

---

现在我们可以做到 \(O(n^2\log n)\)。

但是我们发现每次产生的变化无非就是 \(p_t=0\)，所以暴力做一位就好了。

同时逆变换后的答案也可以暴力求，因为只要 \(A_t\) 的值。

再使用线性求逆元就可以做到 \(O(n^2)\) 了。

思考：可以进阶到多维吗？

【TODO】

2024-08-24

基础题

傻了，以后要记得线段树维护不了区间翻转。

浪费了半个小时。

平衡树才可以。

深入了解了平衡树的维护过程。

吉滪金錀

本质是一个非常重要的转换：当 \(B_i=A_{i+1}-1,B_{i+1}=A_i+1\)，代价为 \(A_i+A_{i+1}\)，要使得序列单调不增，可设 \(C_i=A_i-i\)，直接交换代价为 \(C_i+C_{i+1}+2i+1\)，使得序列单调下降（感受一下）。

所以拿数据结构模拟一下即可。

矩阵

题解写得依托答辩。

---

先考虑怎么判定是否有解：对于一个点对，只有两种情况：在两个序列中的前后关系相同（简写为 \(W\) 点对）或者不同（简写为 \(Z\) 点对）。那么 \(W\) 点对要么对两种序列都产生 \(1\) 的贡献，要么都不产生贡献，\(Z\) 点对会对两种序列中的一种产生 \(1\) 的贡献。

		W			Z
		Z			W

如表，两个 W 组成一个 \(W\) 点对，两个 Z 组成一个 \(Z\) 点对。

我们计算 \(W\) 点对数量 \(Wmax\)，\(Z\) 点对数量 \(Zmax\)。梳理一下，\(Wmax\) 是可选的，会对 \(X,Y\) 都减 \(1\)，\(Zmax\) 是必选的，会对 \(X\) 或 \(Y\) 的一个减 \(1\)。

所以我们肯定是先使用 \(Zmax\) 把 \(X\) 和 \(Y\) 减成一样的，最后再使用 \(Wmax\) 把 \(X\) 和 \(Y\) 减成 \(0\)（因为 \(Wmax\) 是可选的，所以不一定要用完）。如果可以剪完，那么就合法，如果不能或减成小于 \(0\)，就不合法。

---

此时我们计算能对 \(X\) 产生贡献的 \(W\) 点对数量 \(Wcnt\)，能对 \(X\) 产生贡献的 \(Z\) 点对数量 \(Zcnt\)。

容易发现，如果 \(0\le Wcnt\le Wmax,0\le Zcnt\le Zmax\)，这种方案就是可实现的。

所以说，我们需要实时维护 \(Wcnt,Wmax,Zcnt,Zmax\)，如果进行一个操作后，它依旧满足上面的式子，这个操作就是合法的，否则就是不合法的。

我们从小到大向表格中填入数字，当填入 \(x\) 时，表格中已经填入的数一定都小于 \(x\)。

*	*	*						*
		*					*	*
	*					*	*	*
								*
				+
						*	*
	*						*
*		*					*	*
		*					*

如表，当我们向 + 填入数字，表格中标 * 都是在之前填入过数字的（换句话说，比 + 小的）。那么 + 左上角的非 * 与它组成一个 \(W\) 点对，而且因为这些位置还未填入，所以会比 + 大，会对 \(Wcnt\) 产生贡献，也会对 \(Wmax\) 产生贡献。

+ 右下角的非 * 与它组成一个 \(W\) 点对，而且因为这些位置还未填入，所以会比 + 大，不会产生逆序对，不会对 \(Wcnt\) 产生贡献，但会对 \(Wmax\) 产生贡献。

+ 左下角的非 * 与它组成一个 \(Z\) 点对，而且因为这些位置还未填入，所以会比 + 大，不会产生逆序对（对于 \(X\)），不会对 \(Zcnt\) 产生贡献（注意我们对 \(Zcnt\) 的定义是能对 \(X\) 产生贡献的 \(Z\) 点对数量），但会对 \(Zmax\) 产生贡献。

+ 右上角的非 * 与它组成一个 \(Z\) 点对，而且因为这些位置还未填入，所以会比 + 大，会产生逆序对（对于 \(X\)），会对 \(Zcnt\) 产生贡献，会对 \(Zmax\) 产生贡献。

也就是说，我们进行完这些操作后，\(Wcnt,Wmax,Zcnt,Zmax\) 会发生改变，如果 \(0\le Wcnt\le Wmax,0\le Zcnt\le Zmax\)，刚刚向 + 填入数字就是合法的。

我们有一个朴素的想法，枚举填入的数字与位置，可以做到 \(O(n^4\log^2 n)\)，后面的 \(\log\) 是求四角非 * 的数量用的树套树。

---

考虑优化，我们有一个非常强大的结论：对于当前满足条件的 \(Wcnt,Zcnt\)，在当前还未填入的点中，\((x,y)\) 最大/最小、\((y,x)\) 最大/最小的四个（可能更少）的点中（括号表示比较优先级），必然有一个可以归纳下去。

*	*	*	A
*
*
*
B
									D
									*
									*
					C	*	*	*	*
*	*	*	*	*	*	*	*	*	*

如表，* 都是在之前填入过数字的，那么目前 A,B,C,D 一定有一个是合法的。

考虑证明，我们将点两两分组，假设 A,B 为一组，C,D 为一组，那么 A,B 会让 \(Wmax\) 减去右下角还没被删的点数 \(x1\)，C,D 会让 \(Wcnt,Wmax\) 减去左上角还没被删的点数 \(x2\)，如果都不满足条件，那么有 \(Wcnt>Wmax-x1,Wcnt-x2<0\)，也就是 \(Wmax \le x1+x2-2\)，但 \(Wmax\) 是 \(W\) 点对数量 \(Wmax\)，显然会有 \(Wmax>x1+x2-2\)，所以不合法了。

\(Z\) 同理，我们就 AD,BC 分组即可。

所以说，四个点中必定存在一个点合法，我们就可以做到 \(O(n^2\log^2 n)\) 了，4 倍常数。

2024-08-24

math

阈值分治，hjy 出过题。当大小大于 \(\sqrt n\) 时，个数不会超过 \(\sqrt n\) 个，可以直接暴力，当大小小于 \(\sqrt n\) 时，直接暴力也不会超时。

然后就可以了。

kami

这里

使用了这个结论，类似数位 dp 地，当这一位限制为 \(1\)，我们取 \(0\) 时，后面就可以随便取，枚举 \(popcnt=i\)，如果 \({n\choose i} \bmod 2=1\)，那么就会对答案产生贡献，容易发现我们枚举 \(n\) 的子集暴力即可，复杂度不会证。

思考：这道题是一个类似于 \(\bigoplus_{n\and i=n} (i+x)\) 的模型，有其他更快的解法吗？

graph

整体二分好题。

我们考虑对时间轴分治，设 \(solve(l,r,E)\) 表示我们处理到 \(l,r\) 的时间，当前有用的边集为 \(E\)，我们要处理 \(mid\) 的答案，我们就对 \(e\le mid\) 加入 tarjan 跑一次（注意我们已经把 \(1\sim l-1\) 的缩点完了），找出 \(mid\) 的答案，然后对于一个 \(e\le mid\)，如果它对左边的强连通没有贡献，我们就算加入它也没用，所以我们就不把它加入左边的边集。如果它对左边的强连通有贡献，我们处理右边时已经把左边的缩点完了，加入也没用，所以我们就不把它加入右边的边集。

复杂度不会证明。