电塔
来源:
- Petrozavodsk Winter 2020 Day 5: Jagiellonian U Contest, Problem C
- https://qoj.ac/contest/445/problem/1177
首先把 xi 从小到大排序,不妨假设 xi 相对大小关系不变,那么只需满足 x′i+1−x′i≥d。
设 yi=xi−id,那么只需保证最终 yi+1≥yi。同时,在这个过程中我们需要保证 yi≥−id。
由于我们需要保证 yi≥y1≥−d,所以我们先把比 −d 小的 yi 先提升到 −d,然后就不需要考虑下界的限制了。
那么接下来就是有一个数组,每次给某个数加减一,使得最终单调不降,求最小操作数。
考虑设 fi,j 为 y′i≤j 且前 i 个数已经单调不降的最小花费,gi,j 为 y′i=j 且前 i 个数已经单调不降的最小花费,那么有 gi,j=fi−1,j+|yi−j|,容易发现我们的 j 只需要取在 {yi} 里出现过的即可,复杂度 O(n2)。
然后发现假如 (j,gi−1,j) 这些点是下凸的,f←g 相当于前缀最小值,所以 (j,fi−1,j) 这些点也是下凸的,然后 (j,|yi−j|) 也是下凸的,所以 (j,gi,j) 也是下凸的。
同时 (j,fi,j) 是呈现分段线性函数的样式,具体的,存在 0=a0≤a1≤a2≤⋯≤ai,使得 f(x)=fi,x 在 [aj,aj+1] 上斜率为 j−i,且 ∀x≥ai,f(x)=f(ai)。我们尝试用堆维护 a1,a2,…,ai 以及 w=fi,ai。那么从 fi−1 转移到 fi 时,假如 yi≥ai−1,那么直接令 ai=yi 即可;假如 yi<ai−1,那么令 w:=w+ai−1−yi,并设置 ai−1:=yi,ai=yi 即可。
复杂度 O(nlogn)。
并查集
来源:
- Toyota Programming Contest 2023 Spring Final, Problem G
- https://atcoder.jp/contests/toyota2023spring-final/tasks/toyota2023spring_final_g
考虑每条边对答案的贡献。合并 Ai,Bi 时,如果令 Ai 为 Bi 的父亲,则这条边被走的次数是 Bi 当前连通块向外连的边数。
因此只要确定了边的顺序,那么一定是让度数小的连通块成为度数大的连通块的父亲。
进一步可以发现,如果 Bi 的连通块度数非零,那么把加边的顺序修改为先合并 Bi 的连通块,再连接 (Ai,Bi) ,再按照原顺序合并 Ai 的连通块,一定不劣。
因此不难证明,最优加边顺序一定满足加入的边在任意时刻都是连通的。即存在一个根,每次加边是把儿子和父亲合并,且父亲此时一定已经与根连通。
感性理解一下,最优加边顺序里,儿子的度数应该不会比上面一整个连通块的度数要大。事实上,如若不然,把儿子选为根一定更优。
于是加入一个儿子就是给答案加上总度数,然后给总度数加上儿子的度数减一。
最后只需要把加入儿子的顺序定下来,满足父亲比儿子早加入。这是一个经典的贪心题,可以用并查集加优先队列实现。
复杂度 O(n2logn) 。
划分序列
来源:
- Petrozavodsk Summer 2019. Day 9. MEX Foundation Contest, Problem J
- https://qoj.ac/contest/1392/problem/7605
咕了,见验题人题解。