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