11.16（C0389）
100+10+50=160，rk3。
本来 BC 都应该写出来的。
A：dp 或 贪心 都可以，贪心直接从下往上覆盖即可。
B：
注意：这里的 \(\oplus\) 指的是按位或。
合法条件可以化简为：\(\oplus_{i=1}^{p}a_i = \oplus_{i = p+1}^{n}a_i\)。
继续挖掘。看到位运算肯定想到拆位，考虑每一位第一次和最后一次出现的位置。枚举或和相等的位置 \(p\)，令第 \(i\) 位为 \(1\) 的最左边的数为 \(l_i\)，最右边为 \(r_i\)。则 \(\forall l_i,r_i\) 满足 \(\bigcap\limits_{i=0}^{k-1}[l_i, r_i]\neq \varnothing\) 时为合法条件。此时的方案数为 \(((2^p-1)(2^{n-p}-1)+1)^k\)，但是最后的 \([l,r]\) 可能会有多个 \(p\) 产生贡献，所以要减去 \(((2^p-2)(2^{n-p}-1)+1)^k\)，即强制 \(l_i = p\)。
最后还要加上一个 \(1\)，因为全 \(0\) 也是可以的。
C：
D：
11.17（C0390）
A：直接贪心即可。
B：
只会 \(\mathcal{O}(m^3\log m)\) 做法。
看到 \(n=10^9,m=200\) 是容易想到矩阵的。
考虑 dp。
令 \(f_{i, j}\) 表示填了 \(i\) 个数，前面有 \(j\) 个互不相同的数（包含 \(j\)）。转移是容易的：\(f_{i, j} = (m - j + 1)\times f_{i - 1, j - 1} + \sum\limits_{k = j + 1}^{m - 1}f_{i - 1, k}\)
然后发现后面的东西可以直接矩阵优化，快速幂即可。
反正我是不会 \(\mathcal{O}(m\log m)\) 的做法的。
C：
大模拟什么东西，没调出来。
D：
DS，原题 P4690？
校内模拟赛大常数 \(\mathcal{O}(n^\frac{5}{3})\) \(3s\) 过 \(2\times10^5\) 也是离谱。
11.22（C0392）
考的很烂，T2 没写出来，只有 154pts。
A：
先写一下赛时做法。
首先肯定要拆掉绝对值的符号，先把 \(x\) 离散化，然后发现按 \(w_i\) 从大到小的选择一定最优。但是发现如果这样会有点被多次选择，于是就会退化到 \(\mathcal{O}(n^2)\)。
优化的话直接上势能线段树即可。
题解是直接拆掉绝对值解不等式，即变为两个恒等式：
\( \left\{ \begin{aligned} x_i-x_j\le w_i-w_j \\ x_j-x_i\le w_i-w_j \end{aligned} \right. \)
然后再变一下：
\( \left\{ \begin{aligned} x_i-w_i\le x_j-w_j\\ x_i+w_i\ge x_j+w_j \end{aligned} \right. \)
现在将 \((-x_i+w_i, x_i+w_i)\) 看作一个点，则变为删一个点就删去它左下角的所有点，排序后做一下就行了。
B：
赛时为什么没有做出来呢？赛时为什么没有做出来呢？赛时为什么没有做出来呢？
你发现这个 \([S,T]\) 是很烦的，做一个容斥，分别统计 \(1\sim S-1\) 和 \(1\sim T\)。
然后把每个 \([A_i,B_i]\) 变成 \(2X_i+P_i\)，这样就可以求出 \(X_i\) 的范围，也不需要考虑奇偶数了，然后还能求出 \(\sum X_i\) 的范围。
然后发现这玩意儿还是不好做，继续容斥。
因为很不爽的是这个 \(X_i\) 有上界，如果把上界去掉，就可以变为 \(X_1+X_2+\dots+X_n\in[L,R]\)，同时减去所有下界，就变为 \(n\) 个非负整数在 \([L,R]\) 内，对 \([L,R]\) 再做容斥变成 \(1\sim L-1\) 和 \(1\sim R\)。变为 \(\sum X_i\le V\)，\(X_i\) 为非负整数。你这时候再加上一个数把小于变成等于，插板法即可。
C：做一个树形 dp。
具体地，你发现点性质，然后就能知道就是把树的直径的中间的那条边给提出来，对两边分别作。
就分为路径经过和不经过直径讨论一下，经过直径的路径在套一个桶上去就行了，然后要预处理一下 \(rt_{1/2}\to u\) 的高度。
D：咕咕咕。
11.24（C0394）
没打，但是感觉挺简单。后面看一下 B。
11.24-26
烦烦烦，发烧了，头很晕。
11.27（C0398）
头很晕，直接垫底。
A：很简单其实，但是我写的很麻烦。
当时在想两个点满足所有 \(1\sim i\) 时，路径上有 \(i+1\) 就很麻烦，当时是解决了，但是是否能形成路径这上面有点问题，不想调了，于是就换了一种写法。
直接统计 \(ans\) 的后缀和的数组就十分简单了，就可以最后进行一个查分，然后判断是否是一条路径可以判断每个点的度数，然后因为最多加入 \(n\) 个点，所以这里可以暴力向上跳，对 \(u\) 周围所有的 \(d\) 都进行更新即可。
B：简单题，考场上因为头晕直接摆烂了，就只口胡了一下。
去掉所有平方因子是显而易见的。
先看 \(k=0\) 的情况。肯定想 dp，\(f_i=\min f_j+1\)，条件是 \([j+1,i]\) 之间的数没有重复。但你这样是 \(\mathcal{O}(n^2)\) 的。然后优化挺显然，就是这个 \(f\) 单调递增，所以处理一个 \(pre\) 数组表示第 \(i\) 个数最前面的满足 \([pre_i+1,i]\) 无重复即可，这个 \(pre\) 显然可以预处理。
然后带修也差不多，处理 \(pre_{i,j}\) 表示第 \(i\) 个数经过 \(j\) 次修改后最前面能到哪，这个东西也比较好处理，dp 方程加一维带一个权就行了，复杂度变成 \(\mathcal{O}(nk^2)\)。
C：
如果胜负不确定，有最优策略这个东西就很难做。
但是你发现后手必胜，具体地待会儿证明，然后就只需要知道有多少最终态。
肯定如果有空格的话，一定是 A_B 或 B_A 的形式，因为 A_A 中间能填一个 B，两个空格怎么都能继续填。然后是个环，所以先拆成链，然后去掉空格肯定是 ABABABABAB，最后肯定不是 A，因为是一个环，然后枚举空格数组合统计一下即可。
D：先咕一下。