[六省联考2017]分手是祝愿
先考虑我们的最优策略是什么：每次先关掉编号最大的还亮着的开关，直到所有灯都熄灭。（因为最大的灯无论如何也都要熄灭的）。先判断一下初始局面还需要多少步，如果小于等于 (k) 则直接输出，否则一定是操作到某个恰好为 (k) 步的状态，然后再操作 (k) 步。
可以证明最优方案是唯一的，随机操作一步之后，只有两种可能，最少步数减一，或者最少步数加一，最少步数减一的概率就是操作了最优操作中的一步，所以只和当前最优步数为 (i) 时操作减一的概率是 (dfrac{i}{n})。
设 (f[i]) 表示从 (i) 到 (i-1) 期望要多少步，那么有 (dfrac{i}{n}) 的概率只要一步，有 (dfrac{n-i}{n}) 的概率要 (f[i+1]+f[i]+1) 步，那么我们有：(f[i] = 1+dfrac{n-i}{n}(f[i]+f[i+1]))，因此 (f[i] = dfrac{i}{n+(n-i) imes f[i+1]})。直接求和即可。
[六省联考2017]相逢是问候
每个节点的点权相当于 (c^{c^{c^{a_i}}})，根据拓展欧拉定理，指数可以先膜 (phi(p)) 再加 (phi(p))。根据 (phi) 函数的定义，所有奇数的欧拉函数为偶数，所有偶数的欧拉函数至少为 (x/2)（所有偶数都不互质），那么每个数至多修改 (log) 次之后就不会变了（膜数为 (1)），那么直接暴力修改就可以了。
[六省联考2017]寿司餐厅
首先可以让 (d_{i, i}) 减去 (a_i)，那么问题就代价就变成了 (mx^2)，这样就和取了多少个无关，只和取没取某种颜色有关。然后就是很明显的最大权闭合子图问题了，也就是选择了 (d_{l, r}) 则必须要选择 (d_{l+1, r}) 以及 (d_{l, r-1})，选择了 (d_{i, i}) 就必须要选择 (-mx^2)，直接跑最小割即可。
[八省联考2018]劈配
显然的是，只要解决了第一问，第二问就可以通过多一个二分的 (log) 来解决。
一个人去一个战队，这是一个典型的匹配问题，因此我们把人和战队均看成点，然后假设我们确定了某个人可以去的志愿为 (x)，那么就将这个人向 (x) 的所有战队连边，表示可以匹配。至于判断是否可以去志愿 (x) 的话，只要看加入这些边之后是否满流即可。复杂度不太会证，但看起来挺可以跑的。
[九省联考2018]IIIDX
首先有个贪心，就是每个点选择当前第 (size) 大的节点，然后递归下去。这样 (d_i) 互不相同时显然是对的。
对于 (d_i) 相同的情况，先将 (d_i) 从大到小排好序，然后给每个点设置一个权值 (f_i)，表示它往前还能选择多少个，每次就找到一个点，满足其 (f_i) 大于等于 (size_x)（这个可以通过线段树二分），然后假设对应的 (i) 的权值最靠右的那个数为 (y)，那么当前点就填入 (y)，对应的也就是需要在 (y) 前面再填入 (size_y) 个数，那么给前缀 (f) 数组减去 (size_y)，操作到某个点时，将它父亲对他的贡献减掉即可。
[九省联考2018]秘密袭击coat
首先有一个非常显然的 (O(N^2W)) 的做法，(1sim w) 枚举每种权值，考虑其被多少个方案当成答案，把大于等于它的数权值当作 (1)，比它小的数权值当作 (0)，问题就是有多少个连通块，权值至少为 (k)，统计可以直接 (N^2) 来统计，即 (f[i][j]) 表示考虑到 (i) 为根的节点，权值恰好为 (j) 的方案数，然后答案就是 (sum_{i, jge k}f[i][j])。（看了手题解发现卡卡常就能过了）
发现转移式中，第二维是一个卷积的形式，设 (F_i(x)=sum f[i][j]x^j)，然后转移就是 (prod (F_v(x)+1))。如果当前节点权值为 (1)，那么就再乘以 (x)。(Ans=sum_{i=1}^nsum_{j=k}^M[x^j]G_i(x)=sum_{j=k}^M[x^j]sum_{i=1}G_i(x))。
直接多项式乘法好像没有什么规律，考虑带入点值 (1sim m+1)，然后通过拉格朗日插值还原 (sum_{i=1}G_i(x))。
枚举求点值所需要的横坐标 (y=1sim m+1)。可以发现，对于相邻的两种权值 (x, x + 1) 所求得的 (dp) 数组实际上差别不大，具体的，也就是对于权值恰好为 (x+1) 的节点，需要乘以 (y)，如果一个字数内不存在这种点，那么 (x, x+1) 就可以看成是一类点了。这符合线段树合并的基本思路，我们只需要支持：区间乘 (y)，整体加一，对应位置相乘即可，复杂度 (O(n^2logn))。（实际上不用插值也能做到 (O(n^2log^2n))）
[十二省联考2019]字符串问题
先建立后缀树，找到每个字符串对应的节点。将 (a) 向其所支配的 (b) 连边，然后每个点向后缀树的儿子连边，那么 (t_x) 可以到 (t_{x+1}) 当且仅当 (t_x) 可以遍历到 (t_{x+1})，注意存在虚点，所以我们需要拆点表示权值，即 (a) 类点拆成两个，中间连长度权值的边，缩点之后跑拓扑排序 (dp) 求最长路即可。
[十二省联考2019]希望
有一个直观的想法就是枚举交集，然后在统计有多少种 (k) 个连通块交集为枚举的交集，且只能考虑离这些点距离不超过 (L) 的节点。
考虑到交集一定是一个连通块，直接枚举交集时不好的，考虑一个神奇的容斥：由于树的子图还是一棵树，树有一个优美的性质：点 (-) 边 (=1)。看上去没什么用，如果我们把每个点作为交集的答案减去每条边作为交集的答案，发现这就是我们要求的东西！！于是我们只要求出每个点作为根节点的答案以及每条边作为根（大概就是两个点一起做根）的答案，两种求法显然是类似的，这里只讨论点的情况。
也就是要选出 (k) 个越过根节点且深度不超过 (L) 的连通块，那么假设选择一个连通块的方案数是 (x)，那么选择 (k) 个的方案数就是 (x^k)。因此我们只需要求出一个连通块的方案数即可。
设 (f_{x, i}) 表示考虑到 (x) 子树内的点，距离他深度不超过 (i) 的连通块数量，设 (g_{x, i}) 表示考虑到 (x) 子树外的点，距离他深度不超过 (i) 的连通块数量，那么我们有转移：
然后答案显然为 (prod (f_{x, L-1}-1) imes(g_{x, L}-1))，于是我们就得到了一个 (O(NL)) 的做法。
没搞懂后面的长链剖分是在干嘛，鸽了。
[省选联考 2020 A 卷]魔法商店
首先要知道一个叫保序回归的东西。如果只知道结论的话实际上挺简单的。
保序回归问题是形如：给定一张 (DAG)，以及两个数组 (f, w)，你需要求出一个数组 (g)，使得 (g) 满足 (DAG) 上的偏序关系，且最小化 (sum w_i|g_i-f_i|^p)。
做法的话需要整体二分，考虑定义 (solve(U, l, r)) 表示点集 (U) 内的所有点的权值在区间 ([l, r]) 内，然后我们二分一个 (mid)，我们需要找到一组最优解，使得区间 ([l, r]) 内的所有数只用 (mid/mid+1)，并满足题意的偏序关系，然后找到两个集合，一个集合填入 (mid) 最优，设为 (U_1)，另一个填入 (mid+1) 最优，设为 (U_2)，这时候有个结论：我们递归 (solve(U_1,l,mid), solve(U_2, mid+1,r))，当 (l=r) 时，对应的点集的取值就是 (l)。我有一个绝妙的证明，可惜这里地方太小写不下（雾。
考虑这个题的做法，任意非空子集异或和不为 (0) 等价于线性基大小等于元素个数，也就是每次插入都成功的线性基。考虑替换一个元素是否合法，那么就是把原有的元素删除并新插入一个元素，插入成功则合法。
那么对于集合 (A) 来说，如果一个数 (x) 可以替换掉集合 (A) 中的元素 (y)，那么对应的就需要 (v_xge v_y)，对于集合 (B) 则需要 (v_xle v_y)。实际上用线性基记录求出每个元素可以被线性基的那些数表示，那么他就和这些数线性相关，也就可以直接替换掉这些数了。那么这就会生成一张 (DAG)，带入 (p=2)，(w_i=1)，就变成了保序回归问题。
至于二分之后怎么找两个点集继续递归，发现这是一个最大权闭合子图，每个点的权值设为 (f(mid)-f(mid+1))，如果某个点选择了 (mid+1)，那么他所到可以到达的点必须都选择 (mid+1)，跑最小割即可。
[省选联考 2020 B 卷]丁香之路
如果告诉你这是一个欧拉回路，这道题可能就比较平凡了。
问题等价于，寻找一条从(s o i)的路径，要求经过所有的关键边。我们先把关键边都连出来，再连出一条(s o i)的路径，那么问题转化成找到一条从(s o s)的欧拉回路，经过所有关键边恰好一次。
我们先把已经连好边的节点用并查集缩在一起，这些边一定是必须要被经过的，我们只需要求出剩余部分的最小代价即可。考虑欧拉回路的判定条件是所有点的度数都为偶数，那么所有的奇数点都是要连出一条边的。
贪心的连肯定是最小的连接次小的，以此类推，但是这样并不能满足图的连通性。
考虑到边权都是形如(|x-y|)的形式，所以我们如果需要连边(x o y)，不妨将(x o x + 1)， (x + 1 o x + 2)……(y - 1 o y)。这样消耗的代价是一样的，但是我们将中间的点都联通了，而且中间的点的度数奇偶性不变。
于是这样连边之后，原图会被我们划分成若干个连通块，每个连通块的节点都是连续的，而且每个点度数都是偶数，由于要让每个点度数仍然保持偶数，并且要让图联通，假设我们想要连接两个连通块(a, b)，那么肯定是寻找两个连通块中最小的(|a_i-b_j|)，然后连两次。注意这个地方我们的连通块不一定是一段连续区间，所以我们需要用最小生成树计算答案。