有没有群巨教我怎么出题啊/ll
P6943 [ICPC2018 WF]Conquer The World
Analysis
Solution
还有两种做法。
一种做法是线段树模拟费用流，如 CTSC2010 产品销售一样，每次加入连向汇点的边，并维护树上每个点到当前点的流量。我们按照 dfs 序加入点，容易发现一个点的流量变为 \(0\) 的次数最多为常数次（事实上加入区间和离开区间一共两次）。
另一种做法是类似线段上动态加点的做法，将处理流量分为若干阶段，线段上的转移 \(i-1\to i\) 体现在树上为子树合并入父亲，所以可以维护每棵子树的反悔流量，树上合并即可，使用左偏树维护，权值处理是平凡的。
Conclusion
我不太清楚的大概就是这个分步处理流量，其主要的思路大概就是逐步加入边和点（感觉逐步加入边是更合理的），然后处理流量和反悔流量，这些流量可以根据权值函数的性质合并，所以处理流量较为简洁，没有线段树那么复杂。不过这题维护凸函数还是直观的。
CF772E Verifying Kingdom
Analysis
每次可以问出三个点的虚树形态，所以可以维护每个时刻的虚树形态，往里面插入点即可。插入点可以点分治。
CF1288F Red-Blue Graph
Analysis
我也不知道我在干嘛。总之就是写了个线性规划，然后发现它不是全幺模矩阵。然后对偶，发现还是不会。我甚至都忘了我最初写出的线性规划形式和我为什么要写出那个线性规划。
Solution
考虑一个最为简单直接的刻画，设 \(x_i\in[-1,1]\) 为第 \(i\) 条边的权值，限制为：\(\sum x_i>0\) 和 \(\sum x_i<0\) 两种形式，写成松弛形：\(\sum x_i-D_i=0\) 和 \(\sum x_i+D_i=0\)，其中 \(D_i>1\)。把所有右部点的平衡方程取相反数，然后就是全幺模矩阵了，将它转化为网络流模型，写个上下界费用流即可。
Conclusion
我大概想起来了我最初的线性规划形式，就是设 \(x_i,y_i\) 分别表示是否选取蓝/红，写成松弛型之后应该也能看出做法，不过我没写。
P7124 [Ynoi2008] stcm
Analysis
考虑菊花，可以分治做到一个 \(\log\)。
考虑拓展到树上，DSU 可以做到两个 \(\log\)。
不过发现在 dfs 序上分治就好了，因为树的性质，跨过分治中心的所有左端点和右端点都是单调的，可以直接扫一遍，复杂度一个 \(\log\)。
Solution
正解是 DSU 的一个扩展，发现我们可以一次解决一条重链上的所有轻子树，不过复杂度依然是 \(\mathcal{O}(n\log^2n)\)，我们需要一个子树和为 \(\mathcal{O}(n\log n)\) 级别的平衡分治结构。全局平衡二叉树是可以的，但是递归入轻儿子的时候，由于轻儿子数量比较多，所以我们需要多次递归入这些子树，复杂度就爆炸了。
考虑理论最优的分治结构：哈夫曼树，对于一条重链上的所有点（轻子树，重链上的点）建立哈夫曼树，一个点的权值为其轻儿子的子树大小或者 \(1\)。由哈夫曼树的性质可以得到，一条轻子树到根的长度为 \(\log S_{rt}-\log S_u+1\)，\(S\) 为子树大小，而走一条轻边，子树的规模至少变为原来的两倍，所以一个结点到根的路径长度是 \(\mathcal{O}(\log n)\) 级别的，执行最开始的分治算法即可。
Conclusion
哈夫曼树的应用。在树上它是比全局平衡二叉树复杂度更为优秀的结构，但是全局平衡二叉树更为实用。
CF1491E Fib-tree
Analysis
小清新。有一个暴力做法是每次枚举断哪条边，复杂度指数。观察问题结构猜想 Fib 树断掉任何一条边都是 Fib 树。归纳不难证明。
P5354 [Ynoi2017] 由乃的 OJ
Analysis
考虑对每一位考虑，问题在于怎么对每一位求出经过这条路径之后这一位权值是多少，猜想这是一个结合律信息，尝试利用矩阵刻画变换。设 \(f_0,f_1\) 分别表示这一维是否为 \(0/1\)，可以分别刻画出对应运算对应的矩阵。复杂度 \(\mathcal{O}(kn\log n)\)（全局平衡二叉树）。
由于带修，优化掉 \(\log n\) 不好做，考虑优化掉 \(k\)，可以想到 \(k\) 维并行，也就是压位，同样可以写出矩阵。复杂度 \(\mathcal{O}(n\log n)\)。
Conclusion
线段树的一个有趣应用，我们实际上维护的是一个映射 \(f:\{0,1\}\to \{0,1\}\)，更一般性的，在树上进行的连续运算实际上都是函数的复合，而维护函数最直接的方式就是维护每个权值 \(x\) 所对应的 \(f(x)\)，此处由于函数定义域不大所以可以快速维护。如果函数有较为简单的表示，比如 \(kx+b\) 的复合，就可以将函数复合展开为较为一般的形式。总而言之，维护函数最为暴力的方式为维护映射表，可以通过观察函数性质减少维护的信息规模。
CF538H Summer Dichotomy
Description
有 \(n\) 个区间，第 \(i\) 个区间为 \(r_i\)，将区间划分成两个集合 \(S,T\) 满足 \(\exists n_1,n_2,\forall x\in S,n_1\in r_x,\forall x\in T,n_2\in r_x,n_1+n_2\in[L,R]\)，此外还有 \(m\) 条限制表示第 \(x\) 和第 \(y\) 个区间不在同一个集合。构造 \(n_1,n_2\) 和划分区间的方案或者报告无解。
Analysis
暴力划分是 \(\mathcal{O}(2^n)\) 的。
限制不好处理，观察限制的形式，发现限制建图之后是二分图，每个联通块的左部点一定属于同一个集合，考虑这些元素等价于考虑它们的交，所以限制简化为两个区间一个放在 \(S\) 一个放在 \(T\)。
构造选择的方式可以考虑一个一个 DP，设 \(f_{i,l_1,r_1,l_2,r_2}\) 表示考虑到第 \(i\) 个联通块，区间交为 \([l_1,r_1]\) 和 \([l_2,r_2]\) 是否合法，复杂度 \(\mathcal{O}(n^5)\)。考虑记录三维最优化剩下一维，复杂度 \(\mathcal{O}(n^4)\)，钦定 \(l_1\) 为最大的 \(l\)，复杂度 \(\mathcal{O}(n^3)\)。
考虑枚举 \([l_1,r_1]\)（其实根据前面的钦定 \(l_1\) 没必要枚举），那么包含这个区间的所有区间可以归为 \(S\)。注意到 \(l_2,r_2\) 的范围随即确定，类似可以判断一个区间是否可以属于 \(T\)，枚举+判断 \(\mathcal{O}(n^2)\)。
枚举过程做双指针，修改数量是较小的，复杂度 \(\mathcal{O}(n)\)。注意可能存在范围限制中 \(l_2> r_2\) 的情况，可以对于 \(r\in[r_2,l_2]\) 的 \(r\) 做一遍双指针，然后在对 \(r_1\) 做双指针。细节比较多，写了 5k。
Solution
正解的切入点比较奇怪。假设 \(L=-\inf,R=\inf\)，可以直接取 \(n_1=\max l,n_2=\min r\)，调整可得它是最优的。
加上限制，发现 \(n_1\) 只会减小，\(n_2\) 只会增大，调整即可。
Conclusion
我的做法循序渐进地从五次方优化到了线性，非常爽（
正解则对 \(n_1,n_2\) 的性质做了研究，通过调整得到了一个优秀的构造，切入点还是有点意想不到的。
2-SAT 和线段树没看懂。
CF771E Bear and Rectangle Strips
Analysis
考虑 \(1\times n\) 怎么做，DP 固然是可以的，但是有个贪心：考虑做完前缀和之后选取 \(0\) 矩阵类似一个括号序列匹配的过程，所以可以从前往后贪心能选就选，正确性仍然可以调整。
考虑 \(2\times n\)，一个 DP 是 \(f_{i,j}\) 表示考虑前 \(i/j\) 列的答案。注意到 DP 的权值是 \(1\)，所以可以考虑记录二元组 \(f_i=(cnt,mx)\) 表示前 \(i\) 列，最后一个矩形在第一列上，个数为 \(cnt\)，第二列数量最后一个矩形的最小值为 \(mx\) 的答案，正确性仍然可以调整：因为 DP 的权值是 \(1\)，所以如果有个答案更小第二列答案也更小的方案完全可以扔掉一个加上一个，是不会变劣的，类似地定义 \(g_i\)。
转移考虑几种情况：\(f_i\to f_j\)，此时需要考虑 \(mx_i\) 到 \(j\) 之间左右的 \(0\) 矩阵，注意在 \(1\times n\) 矩形中一个矩形的后继是唯一的，所以可以维护一个并查集记录距离。\(f_i\to g_j\) 则需要满足新加入的矩形左端点 \(l\) 满足 \(mx_i<l\)，可以利用树状数组找到最优的 \(i\)。复杂度一个 \(\log\)。
Solution
我做法好像和 wei 老师差不多，还有个记搜是（？）
两个数数。
P3349 [ZJOI2016]小星星
前菜（不会做！！！）
Description
给定一棵树和一张图，求给树标号的方案数使得标号的树是原图生成树。
Analysis
如果考虑直接 DP，最好的 DP 方法是：\(f_{i,j,S}\) 表示 \(i\) 对应 \(j\)，\(i\) 子树内标号集合为 \(S\)，此时这个联通块和外界有关系的边只有 \(i\) 的父亲边一条。暴力转移 \(\mathcal{O}(n^33^n)\)，子集卷积是 \(\mathcal{O}(n^42^n)\)，一个优化是只记录 \(\text{ppc}(S)=sz_i\) 的 \(S\)，但是还是悬。
没啥思路，能不能容斥？考虑容易一条边不是原图的边，但是没有什么用。
然后就不会了。
Solution
容斥，但是是针对“标号是排列”这个条件容斥，DP 是平凡的，复杂度 \(\mathcal{O}(n^32^n)\)。
P8340 [AHOI2022] 山河重整
Description
求 \(\{1,2,\cdots ,n\}\) 有多少个子集 \(S\) 满足对 \(S\) 做 \(01\) 背包后能表示出 \(1\sim n\) 的所有数。
Analysis
我会平方！设 \(f_{i,j}\) 表示前 \(i\) 个数能表示出 \([1,j]\) 的数，容易转移。
好像卡住了，如果尝试转化，转化的形式大概是，计数数列 \(a\) 满足：
- \(a_i<a_{i+1}\)。
- \(\sum\limits_{j\leq i}a_j+1\geq a_i\)。
- \(\sum a_i\geq n\)。
学乖了，考虑容斥，分别尝试每个条件之后发现还是第 \(2\) 个条件比较容易下手，但是如果仍然考虑 DP 的话并没有优化的效果。弃疗。
Solution
回归原问题。条件是需要表示出所有的数，也就是说，如果所有数都可以被表示，那么贡献为 \(1\)，否则贡献为 \(0\)。考虑计算不合法状态，并从不能被表示出来的数入手，为了贡献为 \(1\)，我们钦定我们考虑的数是最小的不能被表示的数，设为 \(i\)，则可以确定的是：\([1,i]\) 中选择的数和为 \(i\)，并且能表示出 \([1,i]\) 中的所有数，设这个答案为 \(f_i\)，问题转化为求 \(f\)。
考虑 \(f\) 的转移，和为 \(i\) 的条件容易满足，能表示出 \([1,i]\) 的所有数可以考虑容斥，设 \(j\) 不能被表示，则贡献为 \(f_jw(i-j,[j+2,i])\)，\(w(n,[l,r])\) 表示值域在 \([l,r]\) 的 \(n\) 的有序拆分。发现 \(2j\leq i\)，所以可以考虑分治求出 \([1,\dfrac{n}{2}]\) 的答案再递推到 \([1,n]\) 的答案，问题在于如何快速转移。
如果直接刻画 \(w(n,[l,r])\)，发现它是 \(\sum\limits_{j\geq 1}g_{j,n-(l-1)j}\)，其中 \(g_{i,n}\) 表示 \(n\) 的 \(i-\) 有序拆分（姑且这么叫吧）。直接做仍然是不行的，一个尝试是设 \(c_{n,j}=\sum_{i}f_i g_{j,n-(j+1)i}\)，并建立 \(c\) 数组的递推式子，但是实际将 \(g\) 拆开之后发现不行，问题似乎陷入了困境。
跳出困境的方法是考虑原本的组合意义：对于 \(n-j\) 的所有值域在 \([j+2,n]\) 的有序拆分，它的权值为 \(f_j\)，考虑利用 DP 构造这个组合对象，普通的加数全局加并不适用，因为我们并不能保证新加的数的值域。考虑从下往上一行一行地构造 Ferrers 图，那么我们可以进行这样的操作：钦定初始有 \(j+2\) 行，且有初始权值 \(i(j+2)+j\)。使用拆分数的转移即可。由于 Ferrers 图最多 \(\sqrt{n}\) 列，所以复杂度是 \(\mathcal{O}(n\sqrt{n})\) 的，加上倍增，复杂度仍然是 \(\mathcal{O}(n\sqrt{n})\)。
Conclusion
先将一下从下往上一行一行构造 Ferrers 图的方法：设 \(f_{i,j}\) 表示底部的宽度为 \(i\)，和为 \(j\) 的方案。从大到小枚举 \(i\)，转移的时候考虑加入多少行 \(i\)，相当于做一次类似完全背包的过程。
一般的组合计数问题是这样的形式：有限制 \(P\)，对所有满足限制的组合对象求值。如果直接考虑限制 \(P\)，采用 DP 等方式构造组合对象，有时会陷入困境或得到一个复杂度并不优秀的做法。此时如果我们考虑 \(P\) 的组成，对其中的一部分采用容斥转化问题。容斥并不一定是 \(\sum(-1)^i\) 的形式，也可以是钦定代表元等，其目标规范贡献为我们想要的值。
这两题没有做出来的原因主要为：
- 对容斥的理解不够深刻，应用不够灵活。第一个问题我把容斥作用的对象局限在了一个条件上，没有仔细观察全局限制，忽略了一个可以用于容斥的限制。第二个问题中，我同样没有仔细观察原问题，并局限在了 \(\sum(-1)^i\) 的容斥形式。
- 进入错解后转化思路的能力不强。正确的方法应该是卡死之后回到原问题，重新对原问题进行观察。
另外最后的 DP 优化我也没有想出来，对 DP 状态设计的感觉不是一蹴而就的，还要多多练习。
最后以一个构造收尾吧，感觉不是很会构造捏。
2023.2.11 联考 T1
Description
有 \(n\) 个物品，第 \(i\) 个物品重量为 \(i\)，颜色为 \(a_i\)，每种颜色恰好 \(4\) 个数。将其分为两个集合 \(S,T\)，使得 \(S,T\) 重量相等，且每种颜色恰好两个数。
Solution
普通构造不可行，考虑加强限制：我们钦定 \(i\) 和 \(4n-i+1\) 配对，每个集合塞 \(n\) 对。那么可以建图：\(a_i,a_{4n-i+1}\) 之间连边，这样我们需要给边标上 \(0,1\)，使每个点邻边恰好 \(2\) 个 \(0\) 和 \(2\) 个 \(1\)。构造方法是跑欧拉回路，然后隔一个放一个 \(1\)。
Conclusion
构造的思维大胆地可怕。我尝试配对的时候总是想先证明存在一组解使得它可以由配对得到，但实际上这个证明又依赖于我们上面的构造，后面的建图和欧拉回路就是套路了。
标签：log,记录,复杂度,mathcal,考虑,可以,周做题,DP From： https://www.cnblogs.com/yllcm/p/17112667.html