Day 1
被 ly 干碎。
T1 矩乘，带一个常数 1 和答案总和即可。
T2 等价于找两个相同的子序列并且第一个的结尾位置小于等于第二个的开头位置。枚举第二个的开头位置 \(j\)，设 \(f_{k,a,b}\) 表示分别以 \(a,b\) 结尾的长度为 \(k\) 的子序列有多少个，二维前缀和优化转移可以做到 \(\mathcal O(n^4)\)。发现可以不枚举 \(k\)，\(f_{a,b}\) 表示以 \(a,b\) 结尾的对数，\(g_{a,b}\) 表示以 \(a,b\) 结尾的长度和，转移方程：
\[\begin{align*} f_{a,b}=\sum_{x=1}^{a-1}\sum_{y=j}^{b-1}f_{x,y}\\ g_{a,b}=f_{a,b}+\sum_{x=1}^{a-1}\sum_{y=j}^{b-1}g_{x,y}\\ \end{align*} \]同样可以用二维前缀和优化到 \(\mathcal O(n^3)\)。
T3 咕咕咕
T4 咕咕咕
Day 2
被 ly 干碎。
T1 快速幂然后随便做。
T2 双指针+树状数组求逆序对即可。我是 SB，开始没把左端点右移，疯狂挂分。
T3 等价于重心。以重心为根，这是一个点子树内一定满足要求，字数外用值域线段树维护能删那些子树的 \(siz\)，线段树上二分。另一种 corner case 是直接把重心接到这个点上然后从重心上删子树，和答案取 \(\min\) 即可。
T4 在 LCA 处统计 \(dep\)，每个子树内只关心跳出来了多少次，不关心内部怎么跳的。设 \(f_{i,j}\) 表示 \(i\) 子树内有 \(j\) 个连续段。合并子树的转移方程：
\[f_{x,k}=\sum_{i=0}^{siz_x}\sum_{j=max(0,k-i)}^{siz_to}f_{x,i}f_{to,j}g_{i,j,k} \]\(g_{i,j,k}\) 表示 \(i\) 条和 \(j\) 条线段拼成 \(k\) 条的方案数。还是计数 DP 基本思路，考虑第一个线段有几个 \(i\)，此时一定有 \(j=i-1,i,i+1\)，只枚举 \(i\) 即可。
\[g_{i,j,k}=2\times\sum_{t=0}^{min(i,j)}g_{i-t,j-t,k-1} \sum_{t=0}^{min(i,j-1)}g_{i-t,j-t-1,k-1} \sum_{t=0}^{min(i-1,j)}g_{i-t-1,j-t,k-1} \]复杂度 \(\mathcal O(n^4)\)，前缀和优化到 \(\mathcal O(n^3)\)。
Day 3
被 ly 干碎。
T1 行列连边，看是否是 DAG 即可。
T2 神奇计数，赛时推的式子极其麻烦，实际上可以十分优雅的推出来。
\(m\) 个数里选 \(n-1\) 个 \(\binom{n}{m-1}\)（一共 \(n\) 个，两个相同），找一个相同的（不能是最大的） \(\times m-2\)，最大值 \(\times n\)，其余的任意分配位置 \(2^{n-3}\)。
T3 容斥 DP，设 \(f_{i,j}\) 表示考虑 \(i\) 种数字至少不合法 \(j\) 个的容斥系数乘方案数。
转移方程 \(f_{i,j}=\sum_{k=1}^{siz_i}f_{i-1,j-k}(-1)^k\binom{siz_i}{k}\)。
注意到最后剩下的是一个多重集排列数，答案是 \(f_{i,j}j!\)，但是这是不考虑同样的数字的情况。所以前面需要除去这个贡献。
转移方程 \(f_{i,j}=\sum_{k=1}^{siz_i}f_{i-1,j-k}(-1)^k\binom{siz_i}{k}\dfrac{1}{(siz_i-k)!}\)。
复杂度 \(\mathcal O(n^2)\)。
T4 '(' 为 \(1\)，')' 为 \(-1\)，等价于全局和为 \(0\) 切任意前缀和非负，线段树维护区间 \(sum\) 和区间 \(\min\) 即可。
Day 4
ly 被干碎/cf/cf。
T1 难点在于读题。先加一次 \(\dfrac{L+1}{2}\)，再加 \(\dfrac{L+3}{2}\)，然后一定是一边加 \(2\) 一边加 \(2\)。赛时忘了特判 \(0\)，-10/kk/kk。
T2 有意义的只有只有一个质因子的数。一一匹配一定是最优的，此时只有一种情况：区间存在绝对众数。开一个线段树维护区间绝对众数，另一个动态开点线段树或者平衡树或者主席树维护区间值的个数来 \(check\)，复杂度 \(\mathcal O(n\log n)\)。
T3 边双内部的点一定互相可达，缩点成一棵树然后树剖线段树区间覆盖 01 即可。
T4 析合树。
评价是，只强制了，没有在线。ans 为什么永远都是 \(0\)？？？/cf/cf/cf/cf/cf，-70，痛失 rk1。
另一种做法：类似全局连续段，扫描右端点，类似比赛，点上维护 \(\max_i^ra_i-\min_i^ra_i-r+l\) 维护区间历史 \(0\) （这是最值）的个数。强制在线的话主席树。历史历史和，比较逆天。
标签：NOIP,min,siz,sum,cf,BCT,mathcal,线段 From： https://www.cnblogs.com/WrongAnswer90-home/p/17810941.html