12.1-12.15
P11364 [NOIP2024] 树上查询
简单题，不知道场上在干嘛，拿出 \([l,r]\) 只有 \(O(n)\) 个区间的结论，然后找出来直接扫描线就好了。
实际上更好的做法是
\[LCA(l,r)=\text{mindep}_{i=l}^{r-1}lca(i,i+1) \]找出来建笛卡尔树，然后扫描线应该会更好写。
这个结论怎么能忘了的？
P7737 [NOI2021] 庆典
首先把可达性缩一下，然后对于每个点，只有一个点指向它，即我们缩点后再拓扑排序是一颗叶向树。
然后我们可以直接在上面跑虚树，记录每条虚树上的边和点的可达性，然后统计答案就很简单了。
P9120 [春季测试 2023] 密码锁
首先 \(k=1,2\) 的情况都是简单的。
然后考虑 \(k=3\) 的情况，枚举全局最大值和最小值之间的距离差值，然后二分，考虑剩下一个数可以是哪些，不难发现，对于此时剩下一行的最小值，每一列的限制是存在于若干个区间的并集之内，然后把并集拆成若干不交的，此时就询问是否存在一个点被覆盖了 n 次，这个可以直接线段树区间加，全局最大值。
\(k=4\)，不难知道变成了矩阵并加，询问全局最大值，由于每列矩阵个数只有 \(O(k)\)，所以可以暴力处理，然后扫描线处理即可，复杂度似乎是 \(O(nk^2\log n)\)。
P3352 [ZJOI2016] 线段树
大概是考察 01 序列怎么做，然后拆成若干值域段，整体 dp 即可。
P7907 [Ynoi2005] rmscne
不是很难的扫描线题。
由于存在单调性，可以简单解决。
P6185 [NOI Online #1 提高组] 序列
简单分析一下即可。
P7782 「MCOI-Zero / AC6-M03」 Sipli Field
简单树分治题目。
P4886 快递员
神秘树分治题目，大概是考察最大值的路径所在位置，然后点分治下去找哪个子树。
P9669 [ICPC2022 Jinan R] DFS Order 2
不是很困难的 dp，需要回退背包。
P4437 [HNOI/AHOI2018] 排列
那个什么 Exchange Argument 板子。
P3749 [六省联考 2017] 寿司餐厅
最小割板子。
P8367 [LNOI2022] 盒
设 \(s_i\) 是 \(a_i\) 前缀和，首先我们可以写出暴力式子。
\[\begin{aligned} ans=\sum_{i=1}^{n-1}w_i\sum_{j=0}^S|j-s_i|Val(j,i)Val(S-j,n-i) \end{aligned} \]其中 \(Val(n,m)\) 表示把 \(n\) 个球放到 \(m\) 个盒子，且每个盒子可以为空的方案数，不难知道是 \(\binom {n+m-1}{n-1}\)。
此时我们复杂度为 \(O(nS)\)，可以通过 \(40pts\)。
考虑把绝对值拆开，然后设：
\[\begin{aligned} f(n,m,i,k)&=\sum_{j=0}^k\binom {i+j-1}{j}\binom {m-j+n-i-1}{m-j}\\ g(n,m,i,k)&=\sum_{j=0}^kj\binom {i+j-1}{j}\binom {m-j+n-i-1}{m-j}\\ &=\sum_{j=0}^ki\binom {i+j-1}{j-1}\binom {m-j+n-i-1}{m-j}\\ &=i\sum_{j=0}^{k-1}\binom {i+j}{j}\binom {m-j+n-i-2}{m-j-1}\\ &=i\times f(n+1,m-1,i+1,k-1) \end{aligned} \]所以我们只需要求解 \(f(n,m,i,k)\) 即可。
我们考虑莫队的思想，每次增加 \(i\) 或者 \(k\) 即可。
增加 \(k\) 可以直接计算，现在的问题变成了如何计算增加 \(i\) 的时候的答案。
换一个角度考虑 f。
\(f(n,m,i,k)\) 的组合意义是前 \(i\) 个数和 \(\le k\) 且所有 \(n\) 个数和为 \(m\) 的方案数。
其实就是把 \(m\) 个无序的小球放进 \(n\) 个有序的盒子里，要求前 \(i\) 个盒子里的小球总数不超过 \(k\)。
而这相当于从左往右第 \(k+1\) 个小球不在前 \(i\) 个盒子里！
枚举第 \(k+1\)个小球放在哪个盒子里，可以得到：
然后此时 \(i\) 增加 \(1\) 就容易计算了，时间复杂度 \(O(n+S)\)。
P10982 Connected Graph
简单题。
P6596 How Many of Them
钦定有 \(k\) 条割边，然后二项式反演。
然后考虑钦定 \(k\) 条割边如何计算，不难发现把 \(k\) 条割边拿走后是若干连通块，所以我们先做一个连通块计数。
然后我们考虑连通块如何通过 \(k\) 条割边拼起来，不难发现这是 prufer 序列经典问题，然后我们把这个贡献系数融进去即可。
AT_agc017_f [AGC017F] Zigzag
考虑一条链一条链转移，每条链用其差分后的数组状压成二进制数描述形态。
然后考虑一个点一个点转移，很难发现的一点是我们每次实际上不用记录之前有多少个 \(1\)，而是可以直接消去前一条链的第一个 \(1\)，这样我们就可以方便的描述其是否合法。
AT_agc024_e [AGC024E] Sequence Growing Hard
我们考察如果知道 \(A_n\)，如何求出有多少 \(A_0,A_1\ldots A_{n-1}\)。
我们发现，从 \(A_n\) 到 \(A_0\) 的过程相当于每次删掉一个数，并要求字典序递减。
然后我们考虑删去第 \(i\) 个元素后，如何比较，首先我们知道 \(s'_j=s_{j+1}(j\ge i)\)，且前 \(i-1\) 个元素相同。
那么如果 \(s_{i}=s'_i=s_{i+1}\)，那么比较 \(s_{i+1}\) 和 \(s'_{i+1}\)。
如果 \(s_{i+1}=s'_{i+1}=s_{i+2}\)，那么比较 \(s_{i+2}\) 和 \(s'_{i+2}\)
所以我们一定是比较到两者不同或者比较到串的末尾。
故 \(s\) 删去第 \(i\) 个元素后字典序变小 的条件实际上等价于： \(s_i\) 大于 \(i\) 之后第一个不等于 \(s_i\) 的元素。
然后如果 \(s\) 存在多个相邻的相同元素，删去会存在相同的 \(A_{n-1}\)，我们不妨钦定一个顺序，这样可以避免重复计算，由于我们还有删到串结尾的情况，所以我们可以钦定每次我们删除的就是每一段的结尾，此时的条件变成了 \(s_{i}>s_{i+1}\) 或者 \(s_i\) 是串的结尾。
我们考虑如何计数，考虑设 \(f_i\) 表示长度为 \(i\) 的方案数。
为了避免重复，我们考虑枚举第一个 \(1\) 出现的位置 \(k\) 和删除时间 \(p\)，则前后两段分别构成一个子问题，但是前面一段不能再次出现 \(1\)，所以我们给状态加上一维，表示值域为 \([1,j]\) 的方案数，则此时转移就是：
\[f_{i,j}=\sum_{k=1}^i\sum_{p=0}^if_{k-1,j-1}f_{i-k,j}\binom {p-1}{i-k} \]注意由于值域可以不满，所以我们需要做一个前缀和。
然后 dp 优化发现后面是一个上指标求和，直接做即可。
P9021 [USACO23JAN] Subtree Activation P
我们考察这个东西等价于什么。
发现是一个找若干条边，使得边权和最小，且形成一条经过所有点的欧拉回路。
我们可以建立一个虚点和所有点连边，这样变成了经过 \(0\) 的欧拉回路，简单 dp 即可。
CF303E Random Ranking
我们先离散化出 \(O(n)\) 个段，然后对于每个人，计算他在哪个段，然后计算这个段有 \(A\) 人，小于这个段的有 \(B\) 人的概率，则这人在 \(B+1,B+2\ldots B+A\) 的概率分别是这个的 \(\frac 1A\)，暴力计算是 \(O(n^5)\) 的，然后观察 dp 过程是一个类似背包的过程，可以直接分治优化，\(O(n^4\log n)\)，可以通过。
CF455E Function
首先我们可以把题目转化成，初始在 \(j\)，需要经过 \(i\) 时间，每个时刻可以选择往左走一步或者留在原地，每个时刻开始时需要累加上当前位置的 \(a\)，求最小代价。
不难发现我们一定是走到某个地方，然后停下来，设我们在 \(r\)，需要经过 \(l\) 时间，最后走到了 \(i\)，则代价为：
\[(l-(r-i))a_i+s_r-s_i \]式子拆开之后是一个一次函数形式，可以直接二区间合并+李超线段树做到 \(O(n\log^2 n+q\log n)\)，套用 [CTSC2016] 时空旅行 的离线按斜率排序后建凸包可以做到 \(O((n+q)\log n)\)，但是不想写维护凸包。
CF1499G Graph Coloring
感觉比较牛的一个题。
首先考虑静态如何处理，我们考虑建立一个虚点，对奇数度数的点连边，然后跑欧拉回路，在这上面黑白染色，不难知道此时答案达到了下界。
然后考虑动态如何处理，如果你想着对于虚点删边连边就寄了。
实际上是你考虑删除虚点之后，原图变成若干环和若干链，环的部分不用再管，所以你只需要考虑链的部分，考虑连接这条边时，两边是否为一条链的一端，都是的话可能需要反转其中一条链的颜色，否则需要简单规划一下这条链的颜色。
然后翻转链的颜色部分，我们发现我们只有链的合并，则我们可以使用带权并查集维护即可。
CF164D Minimum Diameter
神秘的题目，求最小点覆盖+剪枝。
每次找到 deg 最大的点，考虑是否需要。
CF1909F2 Small Permutation Problem (Hard Version)
简单题，画出二维平面，然后计数比较简单。
标签：考虑,12,记录,sum,然后,做题,可以,binom,我们 From： https://www.cnblogs.com/Nityacke/p/18613466