NOIP 后讲题 Part 1
题太多了，也不知道啥时候能补完，先写着吧。
CF1842F Tenzing and Tree
把边权变成 |k−2sizx|，sizx 表示 x 子树内黑点数量。
绝对值很难搞。
考虑钦定黑点重心做根，由重心性质有 k≥2sizx。
把绝对值拆掉，染一个点会产生 −2depx 的贡献。
于是贪心取深度最小的 k 个点即可。
如果这个根不是重心怎么办？显然这样只会少算，不会影响最优化。
P9021 [USACO23JAN] Subtree Activation P
显然题目是问启发式合并状物的最小操作数。
建超级源点 0，在 u,fau 之间连权值为 sizfau−sizu 的无向边 ，在 u,0 之间连权值为 sizu 的无向边。
现在我们要选出一个代价最小的可重边集 E′，使得 (V,E) 存在欧拉回路。
回顾无向图欧拉回路的判定条件：
1∼n 联通。
每个点度数为偶数。
直接树形 dp，设 fu,0/1,0/1 表示当前在 u，u 是否与 S 联通，u 的度数。
P4886 快递员
另一类点分治的题目。
假设选取了一个点 u，并且可以确定最终答案在 u 的某颗子树里。
我们可以用点分治把这个过程加速到 logn。
记当前的最长距离为 (x,y)。
x→y 过 u，那么无论怎么移动最大值一定不会变小，直接返回。
x→y 在某颗子树内，显然 u 向这颗子树移动一定不劣。
P6185 [NOI Online #1 提高组] 序列
发现 t=2 的性质更好。
于是先按 t=2 建图，同一个连通块内权值可以随意“运输”。
于是缩点，现在只有 t=1 了。
接下来是传统套路，先拉一颗 dfs 树，调整使得只有根节点不对，然后用非树边调整。
CF1696F Tree Recovery
如果我们知道了一条边 (x,y)，那么我们可以通过 disx,y,disy,z 的关系找出所有边 (x,z)。
所以说，可以通过一条已知边 dfs 出整棵树。
怎么找到已知边呢？枚举所有 (1,i) 总有一条存在。
经典问题
链接自己找的。
考虑最小值和次小值，这两条一定存在。
考虑第三小 (x,y)，分类讨论：
如果加入这条边会影响连通性。那么这条边必定存在，否则 disx,y>ax,y。
否则一定不存在，因为我们假定前面加入的边必须存在。
归纳法。跑一边 kruskal 即可。
P8367 盒
对于一个确定的 (b1,b2,…,bn) 如何计算代价呢？
val(b1,b2,…,bn)=∑i=1n−1wi|ci−di|，c,d 分别为 a,b 的前缀和。
经典拆贡献，枚举 di，计算可能的方案数。
ans=∑i=1n−1wi∑j=0S|ci−j|(i+j−1i−1)(n−i+S−j−1n−i−1)f(n,S,k,i)=∑j=0k(i+j−1i−1)(n−i+S−j−1n−i−1)g(n,S,k,i)=∑j=0kj(i+j−1i−1)(n−i+S−j−1n−i−1)val(i)=ci(2f(n,S,ci,i)−f(n,S,S,i))+g(n,S,S,i)−2g(n,S,ci,i)g(n,S,k,i)=∑j=0ki(i+j−1i)(n−i+S−j−1n−i−1)=i∑j=1k(i+j−1i)(n−i+S−j−1n−i−1)=i∑j=0k−1(i+ji)(n−i+S−j−2n−i−1)=if(n+1,S−1,k−1,i+1)val(i)=(2ci−S+1)cif(n,S,S,i)+if(n+1,S−1,S−1,i+1)−2if(n+1,S−1,ci−1,i+1)
好长的 LaTeX。
显然重点在计算柿子的最后一项。
现在我们要维护 f(n,S,k,i)→f(n,S,k,i+1),f(n,S,k+1,i)。
对于后者，直接使用原定义维护。
对于前者，我们还需要变换一下柿子。
考虑其组合意义：在前 i 个盒子里放不超过 k 个球的方案数。
枚举第 k+1 个球的位置。
f(n,S,k,i)=∑j=i+1n(k+j−1j−1)(S−k−1+n−j+1−1n−j+1−1)。
好耶，现在两者都可以维护了，复杂度 O(n+S)。
NOIP2024 树上查询
注意到 depLCA∗(l,r)=minl≤i<rdepLCA(i,i+1)。
证明：注意到 LCA∗(l,r)=u 当且仅当 [l,r] 中有两个点来自 u 的不同子树。
且必定存在编号相邻的两个点在 u 的不同子树。
于是令 ai←depLCA(i,i+1),r←r−1,k←k−1。
题目实际上在问 maxl≤l′≤r,r′−l′+1≥kminl′≤i≤r′ai。
这个简单，用单调栈求出最小值能取到 ai 的极长区间 [xi,yi]。
求所有满足 |[l,r]∩[xi,yi]|≥k 的 ai 的最大值。
讨论一下三种情况：
y≥r,x≤r−k+1。
x≤l,y≥l+k−1。
x≥l,y≤r,y−x+1≥k。
前两种是二维偏序，第三种是三维偏序。
把第三种并到第二种上：
y≥r,x≤r−k+1。
l+k−1≤y≤r,y−x+1≥k。
做两次二维偏序即可。
NOIP2024 树的遍历
考虑对于一颗形态确定的新树，哪些点可以作为起始点。
观察原树中点 u 的所有连边，这些边在新树中一定构成一条链。
这条链的首尾为 x,y，那么起始点只可能在 x,y 的子树内。
所以可能的起始点在原树上一定构成一条从叶子到叶子的链。
如果现在已经确定了根链，怎么统计新树的方案数呢？
对于根链上的点，邻边的起始和终止都确定了，方案数为 (du−2)!。
对于不在根链上的点，邻边的起始已经确定，方案数为 (du−1)!。
整合一下，总方案数为 ∏u(du−1)!∏u∈chaindu−1。分子可以提出来。
回到题目，考虑到每棵新树唯一对应一条根链，我们只需要对所有合法的根链统计对应的新树个数之和即可。
一条根链合法，当且仅当其经过了一条关键边。
这个很好办，树形 dp 记 fu,0/1 表示 u 的子树内有根链的其中一端，且路径上没有/有关键边的带权方案数。
选取非叶子节点作为树根，同时特判 n=2。
PKUSC 2021 D1T1 矩阵
观察矩阵中只有一个 1 时操作的过程。发现过程中只会出现三种不同的值 A,B,C。
A,B,C 可以递推求出，矩阵快速幂优化。
线性变换，位置之间对答案矩阵的贡献是独立的。
PKUWC2020 排列
考虑求本质不同子序列怎么求。
设 fi,j 表示当前考虑到第 i 位，且最后一位为 j 的本质不同子序列数。
如何避免算重？转移时钦定若 si=j，则必须要选第 i 位。
fi,j={fi−1,jsi≠j(∑kfi−1,k)+1si=j
显然转移可以写成矩阵的形式。把 si=j 的转移矩阵记为 Mj。
tip：下文中的“序列”均为“矩阵序列”，“拼接序列”均为“进行矩阵乘法”。
回到题目，如果 {p}=3,2,1,4，生成出来的序列是什么样子的？
显然，开头会有一段第一位为 1 的所有排列拼接而成的序列，记为 F1。
接下来，会有一段第一位为 2 的所有排列拼接而成的序列。
这个和 F1 其实是同质的，可以通过把 F1 的第 1,2 行，第 1,2 列分别交换得到，下文称为”置换了 (1,2)“。
好的，现在 F1 怎么求呢？
记前 i 位分别为 1∼i 的所有排列 {a} 拼接成的序列为 Fi。
Fi 可以由 Fi+1 转移过来。转移形如改变 ai+1 上的 i+1，依次置换 (i+1,i+1),(i+1,i+2),…,(n−1,n)。Fn=[n]。
现在我们已经会了不限制字典序时的答案了，就是 F0。
限制字典序也很好做，在置换到 (pi−1,pi) 时停止即可。
EC Final 2021 String-dle Count
考虑猜测的评级传递了什么信息。
位置 i 一定是字符 c。
位置 i 一定不是字符 c。
字符 c 恰好有 Fc 个。（出现了 x）
字符 c 至少有 Fc 个。（没有出现 x）
首先 ∑Fc 应该小于等于 k，否则不可能放得下。
k 很小，这启示我们把当前用 ∑Fc 的长度把当前状态状压下来。其中，字符 c 占 Fc 位，前 x 位为 1 代表已经填了 x 个 c。显然 ≥Fc 的部分不需要管。
然后设 fi,state 表示当前考虑到第 i 位，当前状态为 state。
转移枚举当前这一位填的字符 c，而且要满足上面 3 个限制。
ABC242Ex Random Painting
考虑 min-max 容斥，设位置 i 涂黑的时刻位 ti，S=[1,2,…,n]。
E[maxi∈Sti]=∑T⊂S(−1)T+1E[mini∈Tti]
对于任意 T∈S，E[mini∈Tti]=mF(T)，F(T) 表示与 T 有交的区间个数。
显然可以 dp 计算容斥方案，fi,j 表示 T∈[1,2,…,i],i∈T,F(T)=j 的容斥方案和。
二维前缀和预处理跨过一个点的区间个数，容斥系数在 dp 里算。
AGC056B Range Argmax
x 的个数不好直接求，考虑把每个 x 唯一对应到一个 p 上，然后统计这样有用的 p 的个数。
对于固定的 x，我们这样生成一个 p：
枚举 v:n→1，每次把 v 填进最左边的能填的位置。
设 v 填进了位置 pos，那么跨过 pos 的区间都不用管了。所以 pos 的左右两边分割为两个独立的子问题。
考虑树形 dp 计数有用的 p。
设当前区间为 [l,r]，枚举填的位置 pos，考虑“有用的”对左右子问题的限制。
对于左边，设 [l,pos−1] 中最大值的位置为 k，那么要求必定存在一个限制区间同时过 k,pos。
反证：如果不存在，那么当前填到 k 上显然可以更左。
对于右边，并没有什么限制。
所以当前的决策实际上会限制左侧下一步的选择必须在 lim 右侧。
于是设状态 fl,r,lim 表示当前区间 [l,r]，当前决策必须 ≥lim 的满足“有用的”限制的方案数。
令 gl,r,i 表示[l,r] 区间内经过 i 的所有限制区间的左端点最小值。
转移 fl,r,lim←fl,r,lim+1+fl,lim−1,gl,r,limflim+1,r,lim+1。
ABC270Ex add 1
设 Ci 表示 i 当前的值，Bi=Ai−Ci，k=maxBi。终止条件是 k=0。
设当前选到了计数器 x，那么 k′←max(Ax,k−1)。
跳格子问题考虑 dp，设 fi 表示 k:i→0 的期望步数。设 Ap<i≤Ap+1，得到转移方程：
fi=(∑j=1p1nfi−1)+(∑j=p+1n1nfAj)+1=1n(pfi−1+∑j=p+1nfAj)+1fi−1=1p(nfi−n−∑j=p+1nfAj)fi=1p(nfi+1−n−∑j=p+1nfAj)
注意现在的 Ap≤i<Ap+1。
可是现在 f 的转移是反的，于是我们设 gi 表示 k:An→i 的期望步数。
fn−gi=1p[n(fn−gi+1)−n−∑j=p+1nfAj]fn−gi=1p[pfn+(∑j=p+1nfn−fAj)−ngi+1−n]fn−gi=fn+1p[(∑j=p+1ngAj)−ngi+1−n]gi=1p(ngi+1+n−∑j=p+1ngAj)
状态是 1018 的，考虑优化。
对于 i∈[Ap,Ap+1)，g 的转移都是相同的，于是我们直接矩乘（当然解线性递推也是可以的）。
ARC150D Removing Gacha
根据期望的线性性，
被
选
择
的
次
数
ans=∑iE(i被选择的次数)。
i 被选择的次数只与根到 i 的路径上的点有关，问题转化为：
di 个点，每次随机选一个前缀不全是黑的点染黑，全部涂黑时停止。求第 di 个点被选到的期望次数。
由于在过程结束之前第 di 个点的前缀不可能全黑，所以等价于下面的问题：
di 个点，每次随机选一个点染黑，全部涂黑时停止。求第 di 个点被选到的期望次数。
这个是经典问题了，所有点的期望一样，总的期望操作次数 ∑i=0di−1didi−i，所以单个点的期望 ∑i=1di1i。
所以 ans=∑i∑j=1di1j。
HAOI2015 按位或
min-max 容斥，求集合 S 中最早被覆盖的期望时间。
令 g(S)=∑T⊂SpT。则 E(mini∈Sti)=11−g(U/S)。
CF1768F Wonderful Jump
有一个简单的 O(n2) dp。
考虑优化转移，先发掘一些性质：
每次跳的区间必定满足区间最小值不在中间（非左右端点）。
证明：设最小值为 ak,k≠l,k≠r。
直接跳过去 w(l,r)=ak(r−l)2 。
从 k 中转 w(l,k)+w(k,r)=ak[(k−l)2+(r−k)2]。
不难发现第二种一定不劣。
设区间最小值为 ak，则 d=r−l≤nak。
证明：如果一步一步跳过去，代价 ≤nd。
又 w(l,r)=akd2。
由于 akd2≤nd，所以 d≤nak。
根号分治，设阈值 B。转移时钦定 ai 为最小值。
ai≤B，在满足结论 1 的情况下暴力转移。由于每一种 ai 的转移区间长度和最大为 n。所以这一部分的复杂度 O(nB)。
ai>B，向左向右各枚举 nai，这一部分复杂度 O(n2B)。
B=n 的时候，复杂度 O(nn)。
AGC046C Shift
考虑更形式化地描述这个操作。
在 S 的末尾加一个 0，设 ci 表示第 i−1 个 0 与第 i 个 0 之间的 1 的个数。
每次操作形如选择 i<j，然后 ci←ci+1,cj←cj−1。
这个的性质就好看多了：同一个 i 不能又加又减；总操作数 ≤n。
令 di=Δci，我们计数 d。
首先要求 ∑di=0，然后要求 ∑i=1jdi≥0。
设 fi,x,y 表示考虑前 i 位，用了 x 次减一，用了 y 次加一的方案数。
前缀和优化转移 O(n3)。
CF808G Anthem of Berland
显然 dp，fi,j 表示考虑 s1∼i，s[(i−j+1)…i] 与 t[1…j] 还在匹配的最大匹配数。
逐位匹配的转移是朴素的，难点在于怎么计数有重叠的模式串。
预处理出 KMP 中的 nxt 数组，匹配成功后不断跳 Boarder，用 fi,m→fi,k。
CF1039D You Are Given a Tree
假如我们能求 O(n) 求出单个 k 的答案。
根号分治，设阈值 B。
对于 k≤B，暴力求解，复杂度 O(nB)。
对于 k>B，答案一定 <nB，二分求值域连续段，复杂度 O(nnBlogn)。
取 B=nlogn，复杂度 O(nnlogn)。
现在考虑怎么 O(n) 求的答案。
从下往上模拟，令 fu 表示 u 子树中某点到 u 的未被覆盖的最长长度。
贪心：取 u 的 f 值最大的两个儿子 v1,v2。
若 fv1+fv2+1≥k，直接选这条链。
否则，fu←fv1+1。
证明：如果 fv1+fv2+1≥k 且不选过 u 的两个子树组成的链。
那么最优情况是选一条过
的
祖
先
v1,u,u的祖先 的链，显然不优。
CF1097G Vladislav and a Great Legend
显然需要把 f(X)k 拆开。
ans=∑Xf(X)k=∑X∑i=0f(X){ki}i!(f(X)i)=∑i=0k{ki}i!∑X(f(X)i)
等价于求：对于所有 X 生成的虚树，求在虚树中选择 i 条边涂黑的方案数之和。
设 fu,i 表示所有，对于所有 u 子树内的 X 生成的虚树，设根为 root，fu,i=∑X(f(X)+dist(root,u)i)。
现在要合并两棵子树 u,v，分三种情况。
只保留 u 子树里的虚树，fu,i→fu,i′。
只保留 v 子树里的虚树，注意多了一条 (u,v) 的边， fv,i→fu,i′,fv,i→fu,i+1′。
把 u,v 子树里的虚树拼接，fu,ifv,j→fu,i+j′,fu,ifv,j→fu,i+j+1′。
Q：为什么这样能考虑到不同的 X 生成相同的虚树呢？
A：如果不选 u，相当于不使用 u 的初始状态 fu,0=1 转移。
CF724F Uniformly Branched Trees
显然根确定时才方便对不同构的树 dp。
所以我们统计答案时钦定重心为根，也就是说，所有子树大小的最大值 ≤n2。
设 fi,j,k 表示当前树大小为 i，根节点度数为 j，所有子树的大小 ≤k。
转移枚举选了 t 个大小为 k 的儿子，在 fk,d−1,k−1 种树中可以重复地挑选 t 种方案数为 (fk,d−1,k−1+t−1fk,d−1,k−1−1)。
转移方程：fi,j,k←(fk,d−1,k−1+t−1t)fi−tk,j−t,k−1。
注意：如果 n 为偶数，可能存在两个重心的情况，如果此时两个重心对应的子树不同构，会被算到两次。
因此，答案要减 (fn2,d−1,n2−12)。
CF1061C Multiplicity
设 fi,j 表示，前 i 位，已经选了长度为 j 的子序列的方案数。
转移 fi,j←fi−1,j+[j|ai]fi−1,j−1。
观察 fi 的变化：第二种转移只会进行 O(nV) 次。
CF886E Maximum Element
一个排列是否正确显然与 n 的位置有关。
不妨枚举 n 的位置：ans=∑i=1n(n−1i−1)fi−1(n−i)!。
式子的含义：n 把排列分为两半，选 i−1 个数放进前一半，fi−1 表示前一半不返回的方案数，后一半随便排。
怎么求 fi 呢？发现要求 i 在最后 k 个位置上。类似的：fi=∑j=i−k+1i(i−1j−1)fj−1(i−j)!。
展开一下：
fi=∑j=i−k+1i(i−1j−1)fj−1(i−j)!=∑j=i−k+1i(i−1)!(j−1)!(i−j)!fj−1(i−j)!=(i−1)!∑j=i−k+1ifj−1(j−1)!
前缀和优化。
CF1096E The Top Scorer
钦定小明是第一个人，枚举小明得分 i，得分为 i 的选手个数 j。
ans=∑i=rs∑j=1⌊Si⌋1j(p−1j−1)f(s−ij,p−j,i)
f(n,m,k) 表示 n 个球，放进 m 个盒子里，盒子里球的个数小于 k。
考虑容斥：
f(n,m,k)=∑i=0m(−1)i(mi)(n−ik+m−1m−1)
算概率，所以要除 (s−r+p−1p−1)，复杂度 O(splns)。