毒瘤模拟赛
Day 1
今天大概都是傻逼题，但是由于开题顺序、做题策略、心态爆炸等原因取得了极为不理想的成绩，后应多加注意。
A
场上把自己阴了，实为傻逼题。
想让 \(a=c\)，而每次操作会导致 \(a\) 变成 \(2a\) 或 \(2a-x\)（其中 \(x=a+b\)），然后发现 \(k\) 次操作后 \(2^ka-tx\) 的 \(t\) 可以为任意小于 \(2^k\) 的值，所以枚举 \(k\) 判断即可。
B
玄学题，取前 \(n-25\) 个划分使得差 \(\le W\)，然后从后面找能补全的子集，这个子集数量足够大以至于几乎一定可以有两个集合差满足要求。
C
性质题。首先发现一个能得到的点必然没有兄弟，而且子树大小只能是 \(1\) 或 \(\ge k+1\)。
而对于 \(1\) 的情况，还需要满足爷爷至少有 \(k\) 个孩子而且另外的孩子必须也满足上述条件。这样就可以直接 dp 了，非常简单易懂。
Day 2
傻逼出题人乱卡常。
B
由于与和或的性质，我们记录插过数的子集，然后贪心查询。
D
把询问离线，按血压排序
就练死劲呗？暴力启发式合并，拿一个集合维护答案。
Day 3
B
把式子反掉就是 \(\sum\limits_{d|x}\mu(d)\sum\limits_{i=l}^r[d|a_i]\)。
这样对于每个因数处理出它的倍数出现位置，对于查询的每个因数二分一下位置。
然而是过不掉的，可以加入一些优化，比如忽略 \(\mu=0\) 的因数、对于小因数的位置预处理前缀和或者离线等等，只加一个就足以通过。
D
可以抽象成每次有一个人随机干掉相邻的一条边，因为对答案有影响的一定是干掉了最短路树上的边，所以对于每个点求出干掉树上父亲后的最短路再 dp 转移即可，可以获得 40 分的好成绩。
暴力求太慢了，发现 \(x\) 的父亲边被干掉后最多只会回去走一条非树边 \((u,v,w)\) 走出 \(\text{dep}_v+\text{dep}_u-\text{dep}_x+w\)，这个回去的点一定是直着往下走而走到的点不能也在 \(x\) 子树内。根据这个，我们就能把每条非树边对应的树上路径整体取个 \(\min\)，暴力维护还是可能过不掉。
发现边权从小到大排序后就不需要考虑什么 \(\min\) 了，变成了覆盖没有盖过的边，我们把覆盖过的并查集一下就好了，比刚刚少一个 \(\log\)。
Day 4
刚 C 刚爆了掉大分/shq/cy
结果赛后发现自己一直刚的环形转移解方程是没必要的，今后要拓宽思路。
D
学到了神妙的科技之有向图 DAG 子图计数。
设 \(dp_S\) 表示 \(S\) 的导出子图构成 DAG 的方案数，然后由于是 DAG，所以我们钦定一个入度为 \(0\) 的点集 \(T\)，然后进行容斥。
设 \(f_T=2^{\text{path}(T,S-T)}dp_{S-T}\) 表示钦定 \(T\) 的方案数（其中 \(\text{path}(T,S-T)\) 表示 \(T\) 连到 \(S-T\) 的边数），\(g_T\) 为恰好 \(T\) 的方案数，那么有 \(f_T=\sum\limits_{T\subseteq S}g_S\)，反演一下就是 \(g_S=\sum\limits_{S\subseteq T}(-1)^{|T|-|S|}f_T\)。
那么我们需要的就是任意一个子集恰好为入度 \(0\) 集合的方案数之和，也就是 \(\sum\limits_{T\subseteq S,T\ne\varnothing}g_T=\sum\limits_{T\subseteq S,T\ne\varnothing}\sum\limits_{T\subseteq R}(-1)^{|R|-|T|}f_R=\sum\limits_{T\subseteq S,T\ne\varnothing}(-1)^{|T|-1}f_T\)。
上面这个东西手玩一下大概就显然了，接下来的任务是尝试预处理 \(\text{path}\)。
我们对每个 \(S\) 进行 dp，每次取出一个点转移，这样预处理点与点集之间的边数即可转移。
这样就做到了总复杂度 \(O(3^n)\)。
Day 5
A
其实是傻逼题但是全员读错题了/shq/cy
一定是一段一段地往下取直到取到 \(1\)，我们对于 \(q\) 的每个下降段可以计算答案，修改的话就拿 std::set 维护一下下降段的端点。
C
对不起我错了，根本没复习到线性基。
观察题目要求的部分，发现对于一个点可以先在搜到它时存下它前面的所有子树，再倒着搜一遍存下它后面的所有子树，这样两边子树的线性基合起来就是我们想要的。
这样带上了两个 \(\log\)，有可能卡不过。但是我们发现根据线性基的特性，加满了就不用再加了，这样两边各只需要维护 \(O(\log b_i)\) 种不同的线性基即可。
D
咕了（
Day 6
B
发现连续三个不全相同其实是等价于每两个内部不相同，这样对这些形式相同的限制二分图染色即可。
C
出题人又腿毛造数据？
\(l\) 的限制告诉我们不能直接求哈夫曼树，需要换个方向。
限制了深度，我们就从 Trie 上从下往上 dp，维护还剩几个能用的。
D
阴间题。
首先可以明确的是答案并不是所有正方形的面积并那么简单，因为有些相交的正方形会带来新的不可达区域。
为了简单下面先考虑左半边，也就是一堆等腰直角三角形。
发现从右往左扫到一条线段的时候，如果它高度的前驱后继与它相交，那么就可以合并成一整块三角形，我们求这些新的三角形的面积并即可。
那么加上右半边怎么做呢？显然就直接把三角形对称成正方形，求正方形的面积并即可。
Day 7
B
发现其实是诈骗题，因为一条路径从两边读得到的答案加起来恰好是 \(k\)。
所以这个题就变成了点分治板子。
虽然确实是这样的，但是这是 NOIP，我们还有一个更简单而且复杂度更正确不会被卡常的做法。
对于这种只跟深度有关的，我们可以通过按高度启发式合并减少一个 \(\log\)。
C
也是傻逼题，只需要求出环上每个点往下走的深度就可以拿单调队列优化式子，但是好像细节非常多。
Day 8
垃圾出题人放大超纲题。
B
求有多少个向量三元组不在同一平面，可以固定一个 \(\vec{i}\) 枚举一个 \(\vec{j}\)，要求第三个和它们组成的平面不等于前两个组成的平面。
对于每个平面求出有多少个 \(\vec{j}\) 落到上面。
C
屑套路见了不知道多少次了。
由于是套路，所以长驱直入生成函数，指数是 dp 式子中的连通块大小。可以一遍从下往上 dp 再一遍从上往下换根求出一个点值。
所以就是 \(O(n^2)\) 求点值再插值。
Day 9
D
我们反而计算不合法方案，这样就可以枚举某条路径的 LCA。
那么现在需要求以某个点为 LCA 的定长路径和经过某个点的定长路径。淀粉汁！
然后长剖 dp，差分后贡献变成子树内一个深度加。
Day 10
C
发现从一个点出发所需时间只跟在灯的哪个时刻有关，而遇到第一个红灯后就一定是从这个灯的时刻 \(0\) 出发，所以我们可以预处理出从每个点的 \(0\) 时刻出发走到终点的时间。
从后往前做，这个东西只跟遇到的第一个红灯有关，我们需要查询时刻在红灯区间内的最小值，把灯的时刻扔到权值线段树上即可。
D
这道题其实是一个 dp 套 dp 的模型，就是先写出判定的内层 dp，再以这个 dp 的值作为状态 dp。
把原问题转化成两个两个入栈，可以随时选择先加入一个数，做完操作后再加入这对数里的另一个。不难发现站内的情况怎么样是不重要的，我们只关心加入一个数后会消成什么。
我们把加入的数到消成的数这个映射作为状态进行 dp，就可以判定是不是好串。
然后我们把这四种映射的 dp 值作为状态压起来从前往后再进行 dp。
Day 11
D
咕了。
Day 12
B
二分图博弈板子，没听说过。
就是说如果有博弈能抽象成一个二分图，两人轮流操作到另一边，不能走重复点，容易证明先手必胜状态是最大匹配必须包含的点。
如何判断必须点呢？我们可以从一条未匹配边出发搜索，把所有匹配边对应的点标记一下表示这个点不一定在最大匹配里。
Day 13
B
考场上看范围以为是个 \(O(3^n)\) 的东西但发现 dp 不可行就弃了，其实已经很接近正解了。
涉及到森林之类的问题时其实只需要加上一个和所有点相连的虚点，然后显然这个东西的生成树个数就是题目要求的权值。
对于带环的情况，可以状压 dp 一个点集作为一个环的方案数。
C
由于有用的除法很少，可以直接 dp 选择的除法函数的集合，当 \(x\) 变化后有一段区间的取模函数就没用了。然后算一下发现状态是非常少的。
Day 14
B
朴素的 dp 不行，可以分治，枚举 \(t\) 断开的位置两边跑 dp。
然而复杂度还是不够，注意到数据随机，我们只考虑匹配的位置就可以除掉一个字符集大小。
C
min_25 筛？
Day 15
D
CDQ 分治，考虑计算上面对下面贡献时的形状，发现需要做一个前缀加和全局最大值查询。
Day 16
NOI Plus。
A
暴力 BFS 会 MLE，应该判断一下，如果队列里有超过 \(k\) 个就不搜最大的。
B
发现 \(a_i\) 一定是 \(b_{i-1},b_i,b_{i+1}\) 之一，所以可以 dp。（好像被暴力草过去了）
C
其实是板子，不过 LGV 的板子放 NOIP 就不太合适了。
写出答案行列式，发现可以通过一通消元变成 Vandermonde 行列式，然后就变成了一个差卷积的形式。
Day 17
D
容易发现固定左端点时前缀与最多变化 \(\log\) 次，所以就可以暴力二分出所有变化位置计算贡献。
Day 18
搬题怪差评！
B
首先可以暴力 \(O(n)\) dp，然后对于 \(y\) 比较小的情况，可以预处理出前几长的路。
但是 \(y\) 很大的时候不能全部预处理出来，我们就根号分治，预处理出前 \(B\) 长的路，询问的时候 \(y>B\) 暴力做，\(y\le B\) 直接查。
C
我们向两边搜索，可以先求出左边第一个开右门的钥匙和右边第一个开左门的钥匙，然后先推出右端点，再左右反复横跳。由于变化的位置是有限的，均摊下来大概是线性的样子。
D
这个题比较麻烦，我们一步步推进，首先可以看成一条链上的区间可以取反（这一段减一，剩下的加一），求最高点的最小高度。
这个东西显然是可二分的，因为每次多取反一个区间最多会导致最高点变化 \(1\)，所以初始值到答案中间的每个最高点都是可以取到的。
然后发现我们显然不会同时取反两个不交区间，也就是所有区间的交非空，设为 \(t\)。
容易发现 \(t\) 中一定存在原序列的最大值，所以找到一个最大值位置，二分它变成什么。
然后就可以贪心构造一下，相同的左端点一定先取反右端点靠右的。
凉心赠送赛
赠送赛 4 C
其实是一个见过的套路，对于左端点二分覆盖到的右端点即可。
赠送赛 5 B
发现先手可以领先后手的步数决定了胜负，而这个步数可以 dp 求出。
赠送赛 6 B
容易发现我们依然想尽快到达一个点，所以还是可以跑最短路，只不过边的长度是变化的。
赠送赛 7 C
点分后统计子树内深度的前缀，然后要容斥一下。