二分查找

利用二段性加速搜索

• 浮点二分精度+2
• 注意二分的边界,有时候题目在某段边界才满足二段性,所以左指针右指针不要无脑0和inf

cpp自带的lower_bound是大于等于, 对于不是大于等于,可以简单的推出以下转化:

• 大于: lb(x+1)
• 小于: lb(x)-1
• 小于等于: lb(x+1)-1

双指针

双向/同向/快慢

利用决策单调性(可能要自行转换构造),即找出某种显然的顺序,使得减少无用的操作

通常还需要结合贡献法

经典类型:

• 有序数组/链表上的查找或配对
• 区间移动贡献类问题

前缀和/差分

使用O(n)的时间预处理,然后将后续的查询/操作转为O(1)的复杂度

前缀和可以支持O(1)的区间查询, 而差分支持O(1)的区间修改, 可以视为互逆的操作

• 常用于操作转换(区间转单点,单点转区间)
• 注意差分思想不局限于维护加减,实际上可以维护具备结合律的关系,比如异或关系

公式容斥一下即可得到

位运算

将集合表示为二进制数, 每个位上的0/1表示是否在集合中

基本集合操作

交集	并集	差集	全集	属于	添加	删除
a&b	a|b	a&~b	(1<<(n+1))-1	(s >> i) & 1	s | (1 << i)	s & ~(1 << i)

常用小技巧

• 删除最小元素 s&(s-1) (即lowbit)
• 元素个数__builtin_popcount(s)
• 二进制长度__lg(s)+1
• 最大__lg(s)
• 集合中的最小元素__builtin_ctz(s)
• 快速获取每一位1的下标

  while n:
      idx=int(log2(n&-n))
      n&=(n-1) # 或者n-=n&(-n)

二进制枚举

# 遍历集合
for i in range(n):
    if (s >> i) & 1:
        pass
# 枚举[0,n-1]全部集合
for s in range(1 << n):
    pass
# 枚举s的非空子集
sub = s
while sub:
    sub = (sub - 1) & s

离散化

将连续的数值映射到连续的整数, 常用于处理值域数据结构的空间问题

sort(arr.begin(),arr.end());
arr.erase(unique(arr.begin(),arr.end()),arr.end());
for(auto &x:arr) x=lower_bound(arr.begin(),arr.end(),x)-arr.begin();

贪心

基本

按照某种方式选择局部最优解

但是局部最优不保证整体最优, 所以需要证明(归纳/反证)

反悔

当有两种(多种)决策:

• 一种决策可用次数多但是效果差
• 一种决策可用次数少但是效果好

求最少决策数保证满足某种效果

此时若无法证明两种怎么选择时最优的, 所以需要反悔机制

我们先贪心的选代价低的决策,然后当不行的时候反悔效果最差的决策并改为高代价的决策(堆维护即可)

分治

分而治之

将一种问题转化为多个相同的子问题, 以此递归

倍增

下面这段源自OIWIKI的说的足够好了

我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在 k 的整数次幂位置上的值作为代表。

当需要其他位置上的值时，我们通过「任意整数可以表示成若干个 k 的次幂项的和」这一性质，使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求我们递推的问题的状态空间关于 k 的次幂具有可划分性。

通常情况下 k 取 2。