1020 周总结

之前一天联考一篇查找一个题太史了，按月 merge 了一下。

现在在这里：https://www.cnblogs.com/Nityacke/p/18475669

CF1474F

首先仿照划艇的做法，把值域离散化，然后考虑 dp，我们表示在第 \(i\) 个段，填值域 \(j\)，的情况 \(f_{i,j}\)，然后转移可以组合数计算，时间复杂度 \(O(n^5)\)。

CF1804E

问题等价于我们找一个环，使得所有点和环相邻，状压 dp 即可，时间复杂度 \(\mathcal O(n2^n)\)。

CF1225G

我们不难发现，因为 \(k\nmid a_i\)，所以最后每个数的贡献可以写成 \(a_ik^{-b_i}\) 的形式，然后我们状压然后 bitset 优化即可。

CF1188D

先排序，然后不妨假设最后所有数都是 \(x+a_n-a_1\)，那么我们就需要 \(\sum popcount(x+a_n-a_1)\) 最小，仔细一看，这不是我们 ARC153D 吗，然后直接做就好了。

复杂度 \(O(n\log V\log n)\)。

CF1408H

线段树模拟最小割。

首先我们考虑怎么建图，首先我们设 \(0\) 的个数是 \(n0\)。

则我们按第 \(\frac {n0}2\) 个 \(0\) 的位置分组，则我们右边的点向右边第一个 \(0\) 连边，左边的点向左边第一个 \(0\) 连边。

然后考虑颜色的限制，我们发现我们只需要对于每种颜色左边最右边的一个和右边最左边的一个连边即可。

然后我们建出来的图是这样的：

由于最大流等于最小割，不难发现，我们只会割 $S\to $ 或者 \(\to T\) 的边，且是一个前缀一个后缀的形式，我们枚举割了多少条前缀，线段树维护每条后缀时的答案即可。

CF1648E

按边权排序，枚举补图边权最大值，然后启发式合并维护有哪些连通块合并，最后在建出来的树上查询最大值即可，复杂度甚至是 \(\mathcal O((n+m)\log n)\)。

CF1085G

设 \(f_{i,j}\) 表示长度为 \(i\) 的排列 \(a\)，有 \(j\) 个位置满足 \(a_x\not= x\) 的方案数，不难发现 \(f_{i,i}\) 就是错排数量。

考虑如何转移，枚举最后一个不受限制的数放在哪里：

\[f_{i,j}=jf_{i-1,j-1}+(i-j)f_{i-1,j} \]

先枚举前缀相同的长度，对于第一行，康托展开一下，后面的系数是 \(f_{n,n}^{n-1}\)。

然后对于后面的，我们相当于计算后面还有多少个数小于当前位置，以及多少个是不能满足限制的，树状数组维护这些数的个数即可。

CF1712F

奇妙的题目，首先对于问题变成询问 \(\min(X+f_u+f_v,dis(u,v))\) 的最大值。

然后如何计算，我们设 \(dp_{x,i}\) 表示 \(x\) 子树内，\(f_u=i\) 的最大的 \(dep_u\)，不难发现这个是单调的，假设现在答案是 \(ans\)，枚举 dp 数组大小更小的 \(f_v\)，则我们需要满足 \(f_u \ge ans+1-X-f_v\)，然后判断这个 dis 是否满足即可。

复杂度 \(O(nq)\)。

CF1477D

人类智慧，根本想不到。

呜呼，无法可想！

首先对于度数为 \(n-1\) 的点，不难发现我们定向之后他的位置就确定了，不妨把这些都扔到最后面。

所以现在就没有度数为 \(n-1\) 的点了。

然后人类智慧出现了：我们从补图考虑。

首先对于一个菊花，那么我们就可以在 P,Q 中分别把根定为 \(1,n\)，然后剩下的点分别变成 \(2,3,\ldots n\) 和 \(1,2,\ldots n-1\) 即可，此时我们可以做到所有的 P，Q 不等。

然后我们考虑，如果能把这个补图剖成若干菊花即可。

考虑依次加点，如果新加的这个点连接的所有点中所有点都没有被划分过，那么就可以把这个点和它连接的点划分成一个菊花。

如果有一至少一个点被划分过，我们可以随便找出一个点，设为 \(x\)。

首先，\(x\) 一定不是它所属菊花的根，否则当前点也会被划分到这个菊花。

那么如果这个菊花内有大于 \(2\) 个点，那么就把 \(x\) 从原本的菊花中删了，并和当前点构成一个新的菊花。

如果恰好有 \(2\) 个点，那么可以把那个菊花的根变成 \(x\) ,并把当前点划分到这个菊花内。

AT_arc184_d

转化我们计数的条件，变成计数有多少个集合 \(S\)，满足 \(S\) 加上任何一个不属于 \(S\) 的点就会删除一个点，这个可以直接 dp 即可。

AT_arc125_f

首先我们把每个点度数 \(-1\)，则我们可以证明此时每种度数和选出的数的个数是连续的，证明略去，然后就可以 \(O(n\sqrt n)\) 背包即可。

AT_agc039_e

很神秘的题，首先枚举 \(1\) 和哪个点相连，设其为 \(k\)，然后我们考虑设计 dp 状态，设 \(f_{l,r,k}\) 表示区间 \([l,r]\) 其中 \(k\) 往外面的点 \(K\)，有一条边的方案数。

我们枚举和 \((K,k)\) 有交的最大的一条线 \((x,y)\)，则我们存在两个点 \(p,q\) 满足 \([l,p]\),\([q,r]\) 是跨过 \((x,y)\) 的，所以就变成了 \(f_{l,p,x},f_{p+1,q-1,k},f_{q,r,y}\)，转移即可。

AT_arc068_d

我们首先考虑这个双端队列什么样子，不难发现就是形如这个样子：

然后我们忽略最后 \(n-k\) 个数，有 \(2^{n-k-1}\) 种方法。

所以我们取出来的数列一定可以被划分成不超过 \(2\) 个下降子序列，且第 \(k\) 个数是 \(1\)。

由于 Dilworth 定理，所以我们知道最长上升子序列长度不超过 \(2\)，且第 \(k\) 个数是 \(1\)。

我们考虑逆排列，则我们满足相同的规则，我们设 \(f_{i,j}\) 表示长度为 \(i\) 的且第一个数是 \(j\) 的序列个数，则我们考虑转移：

\[\begin{aligned} f_{i,j}=f_{i-1,j}+\sum_{k<j}f_{i-1,k}(j<i)\\ f_{i,i}=\sum_{j<i}f_{i-1,j}\\ \end{aligned} \]

此时我们就可以做到 \(O(n^2)\)。

考虑我们重新写一下转移：

\[f_{i,j}=f_{i,j-1}+f_{i-1,j}(j<i)\\ f_{i,i}=f_{i,i-1} \]

然后我们不难发现这个东西形如从 \((1,1)\) 走到 \((n,k)\)，但是不能经过 \(y=x+1\)。

容斥一下得到方案数是：\(\binom {n+k-2}{n-1}-\binom {n+k-2}n\)。

然后就做完了。