寒假专题练习 #1 解题思路参考

这是 SCUTSE 2020 年寒假的集训队新生集训题单,感谢乐神友情提供题单(orz 银牌爷)。
下面的解题思路参考是我写的,写的也不一定好,所以题源我也写出来了,网上优质题解很多。

不要直接看题解,也不要口胡完就来看题解,一定要自己敲一下,不敲都不知道自己手残得有多厉害

有些题目是选自 POJ 的,可能没法用万能头,可能还需要 C++ 和 G++ 都交一遍。


题单一(入门算法)

SCUTSE Origin: SCUT SE 2020 day1 入门知识 - Virtual Judge
SCNUSE Fork: SCNUSE 香农先修班寒假专题练习 #1 - Virtual Judge (密码 shannon)

这个题单都是贪心、二分、三分、排序、搜索的题,很多题其实还是比较简单或者比较套路的,SCUTSE 的过题情况也还是不错的,近一半人 AK,大家看题解前可以再思考一下,也不要因为有些题是英文题面讲的又绕就不想读(英语一定要学好啊)。另外 2020 ICPC 上海的铜铁牌分割线考的就是二分,就是分类讨论有点恶心。

A. 计蒜客 T2028

遇到要令最大值最小或者要令最小值最大的通常就是二分了。

所谓二分答案,就是通过固定一个中间值作为答案,再倒过来看看符不符合题目条件,例如假设我们固定的答案是 mid ,那么我们此时我们就认定在操作完成后,跳跃距离肯定大于等于 mid ,那么如果两颗石头之间距离小于 mid ,就把后面的石头移走,直到跳跃距离大于等于 mid

mid 不一定是这轮验证中的最小值,因为你后面还要继续调整 mid 的值,最重要的是符合题目条件,也就是跳跃距离大于等于 mid ,以及移走的石头数量不能超过 M 。要是超过了,那么这个最短跳跃距离的最大值肯定得小于 mid ,否则反之。那么我们就可以调整 mid 的值,继续二分下去。

B. HDU 2899

这个函数一看就不像单调的,不然求最值岂不是取两个端点就好了。就把这道题当普通的数学题想,可以想到要求导,发现这个函数的导函数是单增的函数,当导函数为 0 时取得极值。那么就可以二分了。二分的目的就是找到一个精度满足题目条件的 x ,使得 f'(x) 可以尽可能贴近 0 ,然后再算一下 f(x) 就好了。当然这里要求的是 f(x) 要精确到 4 位小数,那么 x 的精度可以再小一些,因为 O(logn) 的时间复杂度下 n 的增加确实不会影响太多。

当然,我们注意到原函数是一个单峰凹函数,而正是因为单峰,我们也可以考虑三分答案。

至于想写模拟退火的,尽管确实可以而且代码量很小但仍建议送到 ICU 检查。

C. POJ 3069

这个问题就是一排士兵,要你标记最少数量的士兵(题目说的是给士兵发石头),使得任意任意士兵距离被标记的士兵不超过 R

点最大覆盖问题,由于你分配石头时肯定是根据这个 R 来的,最后肯定是符合题目条件的,那就不再考虑二分了。其实就是简单的贪心,思路就是从左到右扫过去,不到万不得已就不标记,也就是尽量选择靠后的位置进行标记,这样才能在覆盖到前面所有点的同时尽可能多地覆盖后面的点。

D. POJ 3617

就是给定一个字符串 s ,再给一个空串 t ,可以从 s 的头部删除一个字符,加到 t 的尾部;也可以从 s 的尾部删除一个字符,加到 t 的尾部。要你构造字典序尽可能小的字符串。

还是贪心。因为就两种操作可以选,要不选头部要不选尾部,那肯定是哪边小选哪边。但是要考虑首尾字符相同的情况:假设我们取了 s 头部的字符,接下来比较的是 s 的第二个字母和尾部的字符;如果我们取了 s 尾部的字符,接下来比较的是 s 的是倒数第二个字母和头部的字符。那么最终看的还是第二个字母和倒数第二个字母哪个小,如果还是一样的,那就这样以此类推,直到可以做出抉择。

如果始终做不出抉择,那么 s 肯定是回文字符串,那么从哪边取字符结果都是一样的。

E. POJ 3253

香农先修班之前布置过这道题,不过那节课似乎去了砺儒云空间讲课。就是若干堆物品,每次可以合并两堆物品,代价是两堆物品数量和,问最小代价。

思路就是总是取最小的两堆合并,具体实现就是优先队列,有直接对应的 STL 函数用就行了。具体来说可以把整个最优方案的合并的过程看成二叉树,大家可以思考每个结点的贡献和这个结点所在深度的联系,得出同层叶子节点互换,对总代价无影响这样的结论,然后试着反证最小的两堆一定在叶子结点,就可以发现先合并这两堆比起其他方案绝对不会更差,就这样递推下去就行。实际上这道题考的就是哈夫曼树的概念和思想。构建哈夫曼树有 O(n^2) 的方法,大家可以自行尝试。

F. POJ 1064

就是 n 条电缆,告诉你每条电缆的长度,现在让你切出 k 条长度相同的电缆,让你求出切出来电缆的最大长度。

思路就是二分答案,也就是切出来电缆的长度,接下来我就按着这个长度对着原先的 n 条电缆逐条切,看看能不能真的切出 k 条出来,如果可以的话,就可以调大答案继续二分,否则就反之。

G. HihoCoder 1524

逆序对的题目不是第一次出现啦,没有印象的可以去回顾一下今年校赛的题目。我们知道归并排序时,两个区间合并时是比较这两个区间的队头元素,每次取小的。我们发现假如左区间的队头元素大于右区间的队头元素,那么右区间的队头元素就会跟左区间的每个元素都构成逆序对,这是因为左区间已经是升序的,就是这里计算逆序对的。

H. HDU 1236

对结构体或者 pair 进行排序就行,用 sort 函数进行结构体排序几乎是万能的一定要会。

I. POJ 1321

深度优先搜索,跟八皇后问题其实非常像。从第一行开始搜索,就选择一个(列)没有被占用的位置放棋子,然后标记这一列被占用了不能再放了,接下来就枚举接下来可以搜索的行,然后 DFS。当我放的棋子数达到题目要求就停止搜索,答案加一。注意回溯的时候要解除列的占用状态,这样才枚举下一个可以搜索的行的时候才不会出错。

J. POJ 2676

解数独,实际上还是带剪枝的深度优先搜索。也不要考虑什么顺序,就是从左到右,从上到下搜索。对于每一个空位就拿 1-9 逐个试,试完就试下一个。当然每填一个数都要去检查一下所在的行列和宫格是否已经出现了这个数,这个检查使用暴力就行了。如果碰到某个格子怎么填都没法填,那就要回溯了不要继续往下试了。

K. POJ 3984

求最短路径通常使用广度优先搜索,也就是一层一层往外搜索。这题可能就难在怎么记录路径,我们知道在新的结点入队的时候记录这个结点的前驱结点是很方便的,而且新入队结点的前驱结点也是唯一的,但是一个结点的后继结点不止一个,你也不知道哪个是最终的路径。所以就直接记录每个结点的前驱结点信息。当我们搜到终点就可以直接结束整个 BFS 开始输出答案了,这时候只需要从终点开始逆序输出前驱结点就行,具体实现就是递归。

L. HDU 2717

问的是给定 x ,每步可以使 x 加一或减一或翻倍,让你用最小步数得到给定的 k

依然是广度优先搜索,试着把这道题跟图联系起来。试想对于某个结点 x_0 ,它的后继结点有三个,分别是 x_0+1,x_0-1,2x_0 。那么我们就让 x 入队开始搜索,记录每个结点被访问时需要的步数,搜索到给定的数就停下来输出答案就行。

M. CodeForces 939E

题目很直白了。当新的数字加进集合之后,要你选择子集。要是选择的子集不包含这个新加的数字,那么跟没加这个数字的各种情况是一样的。我们就考虑子集包含这个新加数字的情况,此时子集的最大值肯定是这个新加的数字,接下来就是让平均值尽可能小。那么肯定是从最小的数字开始选取,先是添加最小的数,接着添加第二小的数,第三小的数,直到平均值被拉下来。假设我们把前 x 小的数都加进去了,令此时的平均数为 f(x) ,我们发现 f(x) 是一个先减后增的单峰函数。既然是单峰那么我们又可以用三分了。

粤 ICP 备 2020080455 号