【置顶】套路集锦

经典套路集锦
早就想搞了

一、解题思路

1

需求:最大化最小值、最小化最大值
做法:二分答案
举例:一抓一大把

2

有些题可以从简单情况着手
然后拓展到复杂情况(数学归纳法或者总结经验、模仿)
或者先考虑普通情况,再考虑改进来解决特殊情况
举例:
noi2015 荷马史诗
poj2442 Sequence
平面几何,先研究三角形

3

研究原问题较复杂时,可能取补会让问题简单化
举例:
Ch6401 创世纪
各种组合数学题

4

各种拆点姿势:
按照时间等递增坐标
按照出度和入度

二、枚举方法

1

有关区间问题并用到区间最值,
求出l[i]和r[i]表示第一个比a[i]大的位置,
则l[i]+1~r[i]-1中间,用到的最大值都是a[i]
不过要小心最大值相等而重复的情况,可以强行把左边界改严格来限制
洛谷18年7月月赛T4

2

按照akc说的,碰到搜索,无脑倒序
举例:
poj1190 生日蛋糕
虫食算

3

当出现连续的$\lfloor \frac{n}{i} \rfloor$时,
值一定是单调不递增的,同值的区间可以合起来计算
复杂度:
$O(\sqrt n)$
① 当$i \leq \sqrt n$,分母只有$\sqrt n$种
② 当$i > \sqrt n$,$\lfloor \frac{n}{i} \rfloor < \sqrt n$
$last=\lfloor \frac{n}{ \lfloor \frac{n}{i} \rfloor } \rfloor$
举例:
CQOI2007 余数求和
大部分莫比乌斯反演题,如gdoi2018d2t1

4

对于许多计数类问题,如果有多个段可分,
可以分成1+(n-1),这样子能保证不会重复计数
举例:
noi2001 陨石的秘密

三、决策类

1

需求:维护前k个(方案)
做法:堆维护,堆顶为最差元素
举例:
K远点对
树上的路径
Supermarket

2

把决策转化为边,边权为代价
举例:
电路维修
循环格

四、搜索类

1

搜索去掉次序性的套路:强行限制大小关系
举例:
poj1011 Sticks

2

搜索的复杂度:
把每次决策量也就是分支数量计算出来

3

其他优化:
优化搜索顺序
排除等效的决策和物体
可行性
最优性
记忆化

4

对于一个序列,拆分成多个序列的问题
有两种不同的方向:

  1. 给每个元素分配组(通常这个更快)
  2. 通过组,找元素
    最好能仔细根据题目斟酌一下策略
    本人多次无脑用2各种剪枝,也比不过裸的1……
    举例:
    Sticks
    Missile Defence System
    Zebras

五、数论技巧

1

面对gcd、lcm的限制条件,可以从质因数上考虑,
从而变成min、max,省去log暴力判断的复杂度
举例:
Hankson的趣味题

2

由调和级数
1+1/2+1/3…1/n=logn

3

如果要在中途,用一个简单的状态去尝试满足“成为某个数的倍数”
或者需要以此简便地转移
可以考虑只保留余数
举例:
Ahoi2009 同类分布

六、树

1

在一课树上,与该点最远的一定是直径的某个端点

七、二分图

最大 匹配数:顶点两两配对的对数
最大 独立集:顶点两两不到达的点数
最小 点覆盖:选一个点就能覆盖所有与它连接的边,求点覆盖所有边的点数
最小 边覆盖:选一条边就能覆盖所有与它连接的点,求边覆盖所有点的边数

1 König定理

  1. 最大匹配数=最小点覆盖(有时称为最小覆盖)
  2. 最小边覆盖=最大独立集
  3. 最大独立集=去掉最少的点,剩下点之间没有边=n-最小点覆盖=n-匹配数

举例:
经典模型 Muddy Fields

2

在平面二分图上,如果存在使边不会重叠的方案,那么其中一定有一种是边长和最小的方案
也就是把合法性、可行性问题转化为求边长和最小的问题
证明的话,显然如果我能够选择不跨越,边长和会变小

七、感觉很假的结论

八、完全不会证明的结论

1 树上路径,覆盖所有边

需要数量:$\lceil \frac{度=1的点数量}{2} \rceil$

九、自己容易犯的sb错误

1

树剖类节点新编号题目、离散化等
一定要注意数组的下标是什么意义,避免把原编号传入

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/80c8.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%