AGC027D Modulo Matrix
Description
构造 \(n\times n\) 的矩阵，满足：
- 矩阵内的数互不相等。
- 存在正整数 \(m\)，使得矩阵中两个相邻的数 \(x,y\)，满足 \(\max(x,y)\bmod\min(x,y)=m\)。
Analysis
考虑如果 \(1\times n\) 的矩阵并且保证要整除能怎么做。可以按照类似 dfs 的顺序做到一个 \(d(n)\) 做法。然后就不会了，只能想出这么多东西。
Solution
复读鱼大题解，感觉自己对构造题的思考方式还是缺乏了。
考虑加强限制，设 \(m=1\)。
不妨设矩阵是单调的，即右边大于左边，下面大于上面。那么一个位置需要满足的限制是 \(\text{lcm}(a_{i,j-1},a_{i-1,j})|a_{i,j}-1\)，发现只要确定了第一行和第一列，就可以构造出整个矩阵。但是这样值域过大了。
题面中“相邻数”的限制提示我们建立二分图模型，不妨设右部点大于左部点，那么就需要保证 \(\text{lcm}(N(i,j))|a_{i,j}-1\)，\(N(i,j)\) 表示和 \((i,j)\) 相邻的所有点。
不妨考虑往左部点中填入质数，这样右部点就是四个质数相乘的级别，质数可能很大。为了减少质数的使用，不妨钦定一个位置是两个质数相乘。这样，我们给每个对角线分配一个质数，左部点的权值为对角线上质数的乘积，这样质数的使用降低到了 \(\mathcal{O}(n)\) 级别。合适地分配质数可以通过本题。
启示：对于条件建立图论模型，矩阵上的二分图模型是常见的。还有就是多钦定一些条件，此题大小关系的情况复杂，难以处理，不妨通过钦定将其转化为简单的情况。
CF708D Incorrect Flow
Analysis
一条边类似绝对值的贡献函数比较难处理，不妨钦定每条边都调整成 \(0\)，然后再调大，这个时候贡献就是一个分三段的函数了，具体地：
- \(f\leq c\)，连流量和费用为 \((f,-1),(c-f,1),(\inf,2)\) 的三条边。
- \(f>c\)，连流量和费用为 \((c,-1),(f-c,0),(\inf,2)\) 的三条边。
容易发现代价是凸的，所以可以直接流。
但是写了一下样例跑出了负环，用这个处理一下就好了。
CF1060F Shrinking Tree
Analysis
https://www.luogu.com.cn/blog/yllcmQAQ/solution-cf1060f
后面两天专门训练一下构造吧学多项式。
P5290 [十二省联考 2019] 春节十二响
Analysis
这个题竟然是我最近能做的最思维的一个题（
发现最大的元素一定会被选，考虑一个贪心：每次从大到小选，如果它可以归到前面的其中一个反链，那么就归进去，否则新建一个反链。但是这里实际上涉及到一个决策，就是归到哪个反链的问题。我没有很好的处理方式。
发现一条祖先链的颜色互不相同，考虑以 dfs 序为阶段做一个 DP。虽然出现了和上面一样的问题，但是至少可以发现一个事实：假设最长链长度为 \(l\)，那么只会选 \(l\) 种颜色。证明可以考虑调整，若选择了超过 \(l\) 种颜色，那么至少存在一个点，没有最长链上的点和它在同一条反链。那么可以把它归到其中一条链上面，这样我们就把这条反链的大小减少了 \(1\)，并且调整是不劣的。
先考虑链怎么做，发现反链长度最多为 \(2\)，直接归并两条链就好了。
考虑以子树为阶段做一个 DP，设 \(f_u\) 为 \(u\) 的最优答案。虽然发现根本不能 DP，但实际上可以维护以 \(u\) 为根的反链的最大值，然后贪心地用链的方法合并。看起来很对，暴力合并是 \(\mathcal{O}(n^2)\) 的，不会证，但是交上去发现有 \(60\) 分，说明确实是对的（
考虑怎么加速合并，常见的树上快速合并的方法都要求以 \(\mathcal{O}(\min(x,y))\) 的复杂度合并两个集合。考虑插入一个集合后对原集合的影响，这步不是很难，用 set 维护就好了。
长链剖分维护，复杂度 \(\mathcal{O}(n\log n)\)。
Solution
启发式合并似乎可以做到相同的复杂度，复杂度不会证明。
启示：上面一步步推导贪心的过程，我都是以 DP 为引入，因为不太会贪心（。实际上贪心和 DP 也有着相似的讨论方法，树上问题同样可以类似 DP 地给贪心划分子树阶段，因为实际上贪心也是需要阶段的。
CF266D BerDonalds
求图的半径。
先 floyd 求出最短路，中心在点上很好处理，关键是中心在边上。对于一个点 \(i\)，它在边 \((u,v,w)\) 上的最短路表现为函数 \(\min(dis_{i,u}+x,dis_{i,v}+w-x)\)，设 \(f(x)\) 表示所有点在 \(x\) 处的最大值，我们的问题是求 \(\min f(x)\)。
建立图形直观：
发现只要求出折线的交点就能求出最小值。考虑折线由哪些点构成，发现它就是按照 \(dis(u,i)\) 从大到小排序之后，\(dis(v,i)\) 的前缀最大值，不难给出证明。
排序之后随便算算就好了。复杂度 \(\mathcal{O}(n^3+n^2\log n)\)。
P5540 [BalkanOI2011] timeismoney | 最小乘积生成树
Strange Problem，貌似适用于所有求 \(\min f(A)g(A)\) 的问题。
这里的 \(f(A)\) 为所有 \(a_e\) 的和，\(g(A)\) 为所有 \(b_e\) 的和。将其看做二维平面上的点 \((f(A),g(A))\)，发现所有这些点都在左下凸包上。算法流程大致为：
- 找到凸包上的两个点。
- 找到这两个点的对踵点，将这个点加入答案，并分治两边。
这样可以找到所有凸包上的点。
找到两个点是简单的，只需要求出横坐标最小的点和纵坐标最小的点，这个可以以 \(a_e\) 或者 \(b_e\) 作为边权。
找到对踵点相当于最大化三角形面积，拆个叉积式子发现就是求和形式了。
这样只会执行凸包点数次最小生成树，而值域为 \(V\) 的凸包点数是 \(\mathcal{O}(V^{2/3})\) 级别的，总复杂度 \(\mathcal{O}(m\log m(na)^{2/3})\)。
ABC221H Count Multiset
不知道为什么做了好久！今天已经下班了，明天写。
标签：贪心,质数,营业,mathcal,日志,反链,复杂度,DP,2022.1 From： https://www.cnblogs.com/yllcm/p/17035565.html