2026Fall SUSTech DSAA(H) 编程题做题记录
这学期上 Prof. Pietro S. Oliveto 的数据结构与算法分析(H)!助教选了一些很有意思的算法题当做作业,基本都能找到原题(见 zzq 维护的 原题机),这里选一些有意思的题目出来看看。
[USACO17DEC] Haybale Feast G:标准写法是二分答案,这需要注意到单调性:最大辣度增大,能取得的最大风味是不减的。当时我写的时候,虽然课上讲了二分查找,但因为太久没有写二分答案,都忘记了这种方法。于是写了一种用 ST 表来维护区间 max,正面求答案的解法。
[CCPC 2023 Shenzhen Site] A Good Problem:数据范围 $n\leq 1000$,那么要求的操作次数 20,000 大约是 $2n\log n$,结合题意,容易想到分治。显然目标值相同的位置可以一起操作,那么只需考虑值域,对值域 $[l,r]$ 进行二分,假设当前的值全都在 $l-1$,我们只需把目标值大于 $mid$ 的那些位置,先分别通过一次操作 2 剥离开,再通过操作 1 不断加到 $mid$,然后接着递归 $[l,mid]$ 和 $[mid+1,r]$ 进一步处理即可。操作次数:考虑递归树,由于每一层操作 2 最多执行约 $n/2$ 次,操作 1 最多执行约 $n$ 次,一共约 $\log n$ 层,那么一个上界是 $(n / 2+n)\log n=1.5n\log n \approx 1.5 \times 1000 \times 10 = 15000$,满足题目要求。
An Optimal Problem:把上面这题改成,必须给出最小的操作次数以及对应的操作方法。这可以通过值域上的区间 DP 得到!上面我们的二分只是一种随意的分法,没办法保证最优。假设所有可能的目标值从小到大排列成 $v_1,v_2, \dots, v_d$。设 $dp[i][j]$ 表示区间 $[i \dots j]$ 所有值都已经到了 $v_i$,还需要的最小操作次数,那么枚举断点 $k$,让 $k+1\dots j$ 这些元素先分裂(通过操作 2)并跳到 $v_{k+1}$(通过操作 1)。取最优的一个断点即可。转移方程为:
\[dp[i][j]= \min_{i\leq k<j} [dp[i][k] + dp[k+1][j] + C(k+1\dots j) + (v_{k+1} - v_i - 1)]\]这里 $C(k+1\dots j)$ 表示 $v_{k+1}, v_{k+2}, \dots , v_j$ 对应的元素个数之和。按区间长度从小到大进行 DP 即可。输出解法,只需要 DP 的同时记录一下最优的断点,最后递归地输出即可。
[NOIP 2011 普及组] 瑞士轮:核心想法是,注意到每一轮比赛后的结果可以分为两个分别具有单调性的数组,于是通过类似于 MergeSort 中 Merge 操作的方法,来重新排序每一轮后的结果。
[SDCPC 2019] Heap:一个很自然的想法是,我们按 $v$ 数组的倒序,从最后一个插入的元素开始往前推,每次“还原”这个插入的操作,顺便看看能不能找出这次插入操作的 is_max 是否为 1。具体的实现还需要一些思考。考虑操作之后得到的数组 $a$ 形成的二叉树,假设当前我们已经还原到了 $a[1\dots i]$。要“还原”插入 $v_i$ 这个操作,我们考虑题目中的伪代码给出的算法:从 $i$ 处不断往上跳,直到遇到第一个大于或小于它的节点处停下来。这启发我们,如果我们再次从 $i$ 处不断往上跳,遇到的第一个 $v_i$ 就是我们关心的被插入的值,而跳的这个路径恰恰就是这个插入操作所影响的节点。那么 is_max=1 需要满足的条件就是:确实能跳到 $v_i$,且跳的路径上的值都比 $v_i$ 小(除了停下来的地方恰好等于 $v_i$),而且停下来的地方的父节点要大于或等于 $v_i$。当然 is_max=0 的条件也类似。若 is_max=1 或 is_max=0 对应的条件都不满足,那就说明无解。若都满足,为了最小化字典序,优先考虑 is_max=0。若有解,我们就通过把路径上的值平移到它们的父节点,来“还原”这次插入操作。时间复杂度显然是 $O(n\log n)$ 的。
[Codeforces 681] Heap Operations:使用一个堆或者优先队列来模拟即可。具体来说,如果 getMin 操作不对,不断 removeMin 直到堆顶元素大于或等于 $x$,然后如果堆顶元素大于 $x$ 就插入一下 $x$,再 getMin 就对了;如果 removeMin 时堆是空的,就随便 insert 一个值。
[ICPC 2022 Jinan R] Quick Sort:
一种做法是线段树上二分。另一种做法:
考虑一次 PARTITION 操作对数组的影响。设此时递归的区间为 $[l\dots r]$,这时候的 pivot 的值为 $x$,它的位置为 $m$。那么直观来看,这次操作会把数组左边 $\geq x$ 的大元素放到右边,把数组右边 $\leq x$ 的小元素放到左边。
那么一次操作后,$x$ 本身最后会去哪呢?玩一些样例会发现,它并不一定会跑到正确的位置。那我们就会去想,它会到数组的左边还是右边呢?容易想到,如果左指针已经跑到 $x$,但是右指针还找到了右边 $<x$ 的一个小元素,那 $x$ 就会被交换到右边;反之,如果左边还有剩余的 $>x$ 的大元素,那 $x$ 就会被交换到左边。
所以,我们可以试试去比较“$m$ 左边的 $>x$ 的大元素”的数量 $X$ 与“$m$ 右边的 $<x$ 的小元素”的数量 $Y$。
注意,当前区间 $[l\dots r]$ 中的元素恰好是 $l,\dots,r$。于是有这样的数量关系:
\[\underbrace{(m-l-X)}_{[l,m-1]\text{ 中 }<x\text{ 的元素个数}} + \underbrace{Y}_{[m+1,r]\text{ 中 }<x\text{ 的元素个数}} = \underbrace{x-l}_{\text{当前区间中 }<x\text{ 的元素个数}}\]于是有:
\[Y-X=x-m\]这里 $x$ 和 $m$ 都可以直接知道!那么可以直接分三种情况:
-
$x<m$。这种情况下 $Y<X$,也就是左边剩下了大元素,$x$ 就会被交换到左边。
-
$x>m$。这种情况下 $Y>X$,也就是右边剩下了小元素,$x$ 就会被交换到右边。
-
$x=m$。这种情况下 $Y=X$,那么 $x$ 不动,它也正好到了正确的位置上。
假设返回的位置为 $p$,那么数组会分为两部分:$[l\dots p]$ 和 $[p+1\dots r]$。
上面的分析就派上用场了:
-
若 $x$ 在左边,$[l\dots p]$ 的最大元素就是 $x$,又由于当前区间的元素恰好是 $l,\dots,r$,那么就应该有 $p=x$。
-
若 $x$ 在右边,$[l\dots p]$ 的最大元素就是 $x-1$,又由于当前区间的元素恰好是 $l,\dots,r$,那么就应该有 $p=x-1$。
-
若 $x$ 不动,也有 $p=x$。
所以我们也可以直接得到这个分界线 $p$:
\[p= \begin{cases} x & x\leq m\\ x-1 & x>m \end{cases}\]提前知道了这个分界线 $p$ 在哪,每次 PARTITION 操作就可以改为只扫描长度较小的那一侧!
以 $p-l+1\leq r-p$,也就是左边的长度较小为例。用 $pos[v]$ 表示元素 $v$ 所在的位置下标。扫描区间 $[l\dots p]$ 的时候,我们维护两个集合 $I$ 和 $J$,分别记录左边和右边要交换的元素下标。每次扫描到 $i$ 时,若 $a[i]>p$,就把 $i$ 加入 $I$ 中;若 $pos[i]>p$,也就是说 $i$ 这个值在右区间内,那我们把 $pos[i]$ 加入 $J$。最后自然有 $\lvert I\rvert=\lvert J\rvert$。我们把 $J$ 按下标降序排序,就可以匹配到交换的顺序,再枚举 $I,J$ 中的元素并交换对应的数组元素,并更新 $pos$ 数组与答案计数即可。
右边的长度较小也类似。
时间复杂度是这样的递归式:
\[T(n)=T(k)+T(n-k)+O(s\log s)\]这里 $s=\min(k,n-k)$ 是较小的区间长度。
可以证明 $T(n)=O(n\log^2n)$。上式与启发式合并的递归式类似。
若把排序换成基数排序,还可以将理论时间复杂度优化到 $O(n\log n)$。
邻值查找:维护一个有序的链表,从后往前枚举 $A_i$,不断查找邻值后删掉元素即可。
[CSP-S 2021] 廊桥分配:总算出现一个以前做过的题!这题的核心想法是用优先队列贪心地模拟,分别求出国内和国际航班的情况下,$i$ 个廊桥能容纳的最大航班数量,然后枚举分配方案取最优的一种即可。这个想法我觉得相当自然,很容易想到。
[CSP-J 2020] 表达式:显然需要去预处理答案,但是有一点难想到怎么快速地预处理。切入点是,答案只可能有两种情况:不变,或反转。考虑原表达式树,我们想要求出哪些叶子节点的变化会影响根节点的值,那么可以从上至下地传递:如果是 &,那么一个子节点会有影响,当且仅当另一个子节点的值是 1;如果是 |,那么会有影响,当且仅当另一个子节点的值是 0。这里隐含了一次修改只会影响一个子树的值这个条件。不断传递这个“影响”到叶子节点即可。
[NOI1995] 石子合并:又是一个做过的题!解法还是相对容易想到的。经典的区间 DP,注意要断环成链,不妨让数组 $a$ 重复两次,最后取长度为 $n$ 的区间的答案的最值即可。
[IOI 2002] 任务安排:一个有点难想的 DP。显然可以去枚举最后一批的位置来实现转移。关键的问题是,转移时启动时间怎么算!如果要用状态记住,就需要用 $dp[i][k]$ 表示前 $i$ 个任务分 $k$ 批的最小费用,这样去转移,复杂度是不对的,会变成 $\Theta(n^3)$。一个巧妙的方法是,注意到如果在 $i$ 处新开一批,这个启动时间其实只是会让 $i\dots n$ 的时间全部加 $s$!所以可以直接记 $dp[i]$ 表示前 $i$ 个任务的最小费用,加上它对后面的任务增加的启动时间对应的代价即可,转移方程为
\[dp[i]=\min_{0\leq j < i} \{ dp[j]+s\cdot \mathrm{sum}(C[j+1\dots n]) + T[i] \cdot \mathrm{sum}(C[j+1\dots i])\}\]这里 $j$ 就表示最后一批任务为 $j+1 \dots i$。这样的时间复杂度就变成了 $\Theta(n^2)$。
评论
阅读 加载中 次
评论服务暂时无法加载,请稍后再试。