知识点和套路

发布于 2021-06-03  168 次阅读


发现自己还是太菜了,许多别人老早知道的东西还是完全不会 /kk。

不管了,先把遇到的东西记下来吧。

图论

拓扑排序

  1. 求字典序最小的拓扑序。

我们直接开一个优先队列,每次在所有入度为 $0$ 的点中取出编号最小的进行更新即可。

例题:HDU1285

Code: Here

  1. 拓扑排序建反图。

我们希望使得某一个东西在拓扑序中出现的尽可能早,这个时候就可以建出一张反图来,使得这个东西在反图中的拓扑序尽量靠后,从而使得其出现的尽可能地早。

我们考虑到字典序是贪心的,如果前面的一位能小就尽可能的小,并不保证最小的数出现尽量靠前。但是如果建一个反图,求一个反向字典序最大的拓扑序,那么就会有较大的数尽量靠前的情况出现,于是较小的数尽量靠后,于是把整个答案序列反过来就是小的数尽量靠前了。

例题:[HNOI2015] 菜肴制作

Code: Here

  1. 在一个平面内选取两个不相交的矩形,则一定可以找到一条平行于坐标轴的直线把它们分开。

证明显然。

由此可以对一些找出两个矩形的问题进行优化。可能通常是从 $O(n^4)$ 到 $O(n^3)$?

注意要分类讨论这条直线是横着的还是竖着的!

例题:[IOI2005] gar

Code: Here

  1. 在遇到物品有标号的计数时,可以钦定第一个位置,退环为链,转化为无标号计数。

退环为链,记得看清有无标号,多考虑隔板法,最后乘上物品数量的阶乘即可。

例题:校内模拟赛某题。

Code: 无

  1. 在做形如某种操作能否把一个序列转化成另一个序列的题目中($Yes/No$ 题),往往需要观察一些序列的特征值来进行判断。

比如可以用逆序对、交换距离($\sum |a_i-i|$)等值,与一次操作的特征值(减少多少个逆序对,移动距离多少等等)进行比对。

例题:校内模拟赛某题。

Code: 暂时不提供

Update:做这类题时注意考虑操作的本质

对于两个数之间的操作,可以考虑把数作为一个个体考虑,而不是单纯地考虑一个操作,更不是用操作去模拟一些看起来很直观实际上根本无法有效转化的所谓“突破点”

比如,CF1546C这道题中给定的操作是对于两个数之间的先交换数值和朝向再把各自的朝向相反。但是我们注意到开始和结束的状态都是全部朝右,由此自然可以想到应该让一个数参与交换(移动)偶数次从而达到最后与最初状态相同的目的。

再进行一步转化,由移动偶数次可以想到坐标的奇偶性是不变的,从而可以想出判断方法:排序前后的数组,每种数字出现在奇数位置和出现在偶数位置的数量相同即可。

例题:CF1546C

Code: Here

STL

  1. 优先队列

优先队列格式:priority_queue <元素类型,容器类型,比较函数>

如果不写后两个参数,它们分别默认为 vectoroperator <

也即,优先队列默认是大根堆。


我们无法选择过去,但我们可以改变未来。