2023“钉耙编程”中国大学生算法设计超级联赛（3）

真 - 坐牢（4h 过了两题。。。）

A - Magma Cave

B - King's Ruins

C - Leshphon

D - Chaos Begin

题意：给定 $2n$ 个点，是由 $n$ 个 $[10^7,10^8] \times [10^7,10^8]$ 中的随机点经过一个相同的平移之后得到的点集和原点集构成的，求所有可能的平移方法，$n \leq 5e4, \sum n \leq 3e5$，时限 $15\sf\ s$

由于时限比较长，加上有随机数据，于是考虑 $O(n^2)$ 暴力：每次 $O(n)$ 暴力枚举可能的移动方向，然后 $O(n)$ 判定是否合法。由于 hdu 特性，只要不写 STL 一般都能正常卡过去

正解是考虑将点集简化为凸包，则凸包上的点进行平移之后得到的一定还是凸包上的点。由于随机数据，凸包上的期望的点的个数是 $O(\log n)$ 的，算法复杂度便退化为 $O(n\log n)$，可以通过（标程是 $O(n\log^2 n)$，还有一个 map 的 log）

E - Out of Control

题意：求长度为 $1 \sim n$ 的不下降序列个数，要求最高项为 $i$ 的数列长度不超过给定的数中 $\leq i$ 的数的个数

考虑 dp，定义 $dp_{i,j}$ 表示长度为 $i$ ，最后一位为 $j$ 满足给定条件的序列的方案数，容易发现 $dp_{i,j}=\sum\limits_{pre=1}^{j-1}\sum\limits_{k=1}^i dp_{i-k,pre}$，前缀和优化即可，注意 $dp$ 的两维之间有约束关系：$i$ 不超过 $\leq j$ 的数的个数，时间复杂度 $O(n^2)$，可以通过

F - Dragon Seal

G - Teyberrs

H - Operation Hope

题意：给定 n 个点，每个点有两个三元组 $(a,b,c),(a',b',c'),a \leq a',b \leq b',c \leq c'$，要求每个节点选择一个三元组，最小化极差 $\max(\max a_i-\min a_i,\max b_i-\min b_i,\max c_i-\min c_i)$

考虑贪心。注意到每个点的 $a,b,c$ 均只能变大，考虑当前极差所对应的最小值，如果不把它提升起来的话后面的更无法得到更优的解（因为会与当前最小值对应的极差取 max），所以可以贪心的将每次决定极差大小的位置对应的娇小的值提升上来，边提升边更新答案，当无法再提升（最小值对应的位置已经提升过一次）时即可得到最小需要消耗的代价。更新时计算贡献需要每个数列的最大值和最小值，每个数列开两个可删堆动态维护即可，复杂度 $O(n\log n)$

标程是用的二分 + 2-SAT 判定是否合法，复杂度 $O(n\log V)$，相较之下贪心复杂度更优

I - The Mine of Abyss

题意：有一个长为 $n$ 的序列，序列上每个点的权值是一个区间，有两种操作：修改某一个点的权值或求 $[l,r]$ 范围内任意多个点的权值区间的笛卡尔积集合的大小，保证每个点的权值区间和修改的权值区间均在 $1 \sim 10^9$ 内均匀随机

由于是随机数据，所以任意多个区间的并可以用 $O(1)$ 个区间表示，所以可以直接线段树维护对应范围内区间的笛卡尔积，单点修改，区间查询，复杂度 $O(n\log n*O(1)^2) \approx O(n\log n)$，可以通过

J - 8-bit Zoom

题意：给出一张图片和放缩率，求放缩后的图片

签到题，模拟放缩过程后直接计算即可，复杂度 $O(n^2)$