大概每天从以前攒下来的题里面随机三道做，时间有多的话就多做一点。
希望明年省选能苟进去吧（
P3346 [ZJOI2015]诸神眷顾的幻想乡
Analysis
链的情况就是本质不同子串数量，可以用 SAM。
扩展到树的情况， 如果对每个点为根的树都造一个 SAM 太浪费了，因为我们其实塞了很多重复的串，如果一个串被另一个串包含那么我们显然没必要塞进去。于是可以想到对每个叶子为根建广义 SAM。然后就做完了。
P8329 [ZJOI2022] 树
Analysis
可以暴力枚举树，然后记录一个 \(S\) 表示叶子的集合，那么两个集合 \(S,T\) 合法需要满足 \(S\cup T=[n]\land S\cap T=\varnothing\)，状压加高维前缀和可以做到 \(\mathcal{O}(n2^n)\) 的复杂度。
考虑对每个位置的条件容斥一下，题意相当于 \(i\) 在两棵树中恰好一棵树中成为叶子，那么可以钦定在第一个树里面成为叶子，钦定在第二棵树里成为叶子，减去两倍同时成为叶子。感性理解大概就是 \(x+y=x+xy+y+xy-2xy\)。更为严谨的推导方法是：
\[\sum_{S\cup T=[n]\land S\cap T=\varnothing} f_1(S)f_2(T)=\sum_{S\cup T=[n]\land S\cap T=\varnothing}\sum_{S\subseteq S_1}\sum_{T\subseteq T_1}g_1(S_1)g_2(T_1)(-1)^{|S_1|+|T_1|-|S|-|T|} \]交换求和号，然后后面两个 \(\sum\) 可以化成 \(2^{n-|S_1|-|T_1|}\)，然后就是上面的式子了。
考虑拿这个做一个 DP，叶子的限制相当于一些点不能选，第一棵树只关注个数的前缀和，第二棵树只关注后缀和，所以可以设 \(f_{i,j,k}\) 表示递推到 \(i\) 的时候，前缀和为 \(j\)，后缀和为 \(k\)，可以得到：
- \((i-1-j)(n-i-k)f_{i,j,k}\to f_{i,j,k}\)。
- \((i-1-j)(n-i-k+1)f_{i,j,k}\to f_{i,j,k-1}\)。
- \(-2(i-1-j)(n-i-k+1)f_{i,j,k}\to f_{i,j+1,k-1}\)。
对于每个 \(n\) 都做一遍可以做到 \(\mathcal{O}(n^4)\)。
Solution
我们要求 \(1\sim n\) 所有数的答案，容斥已经没有什么改进空间，考虑增量地维护 DP 数组，但是在现有定义上已经不好维护，考虑修改 DP 定义。定义 \(f_{i,j,k'}\) 表示 \(n-i-k\) 为 \(k'\) 的答案，这样就可以增量维护了。
启示：如果要求多组答案，必须增量维护 DP 数组的时候，可以修改 DP 数组的定义，比如把某一步系数塞进去这样的。
P8291 [省选联考 2022] 学术社区
Analysis
先考虑性质 ABC 怎么做。观察可以发现题目要求找到一组路径覆盖，如果直接套用二分图做法，那么可以会出现环覆盖这种情况。
继续观察，发现这个部分实际上要让我们找到一条路使得它经过了每个点恰好一次，考虑恰当建图使得每条边也恰好被经过一次，这样可以套用欧拉回路的做法。基本的想法是对于一条信息 \((x,y,\text{loushang})\)，将信息 \(x\) 向网友 \(y\) 连边，然后网友 \(y\) 向它的信息连边。唯一的问题是路径的起点，也就是说起点 \(S\) 需要连多少条边过去，稍加考虑发现只需要让其入度和出度平衡即可。
然后尝试考虑 BC 咋做，以为路径是 loushang 和 louxia 两种链，然后不会了。
Solution
观察 BC 的形态，发现是 loushang 接一条学术接一条 louxia，所以可以考虑分层图，套用 ABC 的做法即可。
考虑 AC 怎么做，此时加上了一个最优化，仔细观察 ABC 的做法，发现有些点的入度和出度可能并不平衡，猜想问题就出现在这里。那么入度少多少答案就会少多少，此时强行加一些出边表示废掉一些边即可。
考虑 C 怎么做，套用 AC 的做法就不行了。尝试一下可以发现有些边直接丢弃其实可惜了，我们可以把它充当学术消息的衔接作用。那么原图中一条 \(x\to y\) 就变成了 \(x\to x'\)，这时 \(in_y\) 少 \(1\)，\(in_{x'}\) 多 \(1\)，观察出入度，发现如果 \(x',y\) 都会少一些的话，那么调整之后两个都会多 \(1\)，总的答案增加了 \(1\)。可以考虑一个网络流模型，直接流复杂度是 \(\mathcal{O}(m\sqrt{m})\) 的。
没有 C 的话，把这类边贪心地凑起来就好了。
启示：转化错了问题导致思路卡住了，以后推导的时候不要想当然！另外这题循序渐进的思路非常自然，在我看来难点主要在于发现不能全部合法的关键在于入度和出度不能通过加边平衡，还有 C 部分将废掉的部分用作学术消息优化答案这两步，看似简单的结论实则需要大量的观察作为支撑，在考场上能观察并且坚定结论并非容易的事情。
标签：出度,考虑,sum,30,叶子,DP,日志,可以,2022.12 From： https://www.cnblogs.com/yllcm/p/17016058.html