补充的算法

参考资料

• oiwiki 算竞圣经, 但讲的不好, 是 wiki - 不是书 - 3
• 左程云 - 大佬, 比 oiwiki 还全, 就是人太墨迹 - 4

分治

第 k 小算法

• 分组排序 (快速找到接近中位数, 并划分集合), 如此分治找 k 小
• 锦标赛算法找第二大 (直接输给第一大)
• 分组找最大最小

TOP K 问题

• 减治法, 类似快速排序, 每次划分后, 只需要递归处理其中一个子问题

分治颠倒整数二进制位

// 分治法颠倒二进制位
int reverseBits(int n) {
    // 交换 16 位
    n = (n >> 16) | (n << 16);
    // 交换 8 位
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
    // 交换 4 位
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
    // 交换 2 位
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
    // 交换 1 位
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
    return n;
}

二分搜索

• 二分搜索的前提是有序的, 定区间的

两个正序数组的中位数

• 第一种解法, 每次选取两数组各 k/2 个数, 去掉较小集合, 更新 k
• 第二种, 稳定选取数量和为 k 的, 二分搜索位置, 直到满足交叉小于关系

组合问题

组合枚举

位掩码

• n 位二进制整数, 可以表示 n 个 bit 的组合 (废话), 可以用以枚举组合 / 二叉树结点

DFS/BFS 枚举组合

• 使用 DFS 回溯时, 以剩余元素数量 < 需要数量作为剪枝条件

字典序迭代

• 初始化组合为 [1-k]
• 每次找到最后一个可递增的位置, 递增后调整后续元素

位运算

• 位运算可以模拟加减, 但是进位退位得单独计算保存
• 异或多个数, 按位独立
• 偶数次相同数异或为零

求所有子集的异或总和再求和

• 所有元素按位与后乘以 \(2^{n-1}\)
• 所有元素该位都为 0, 所有子集异或总和中该位均为 0
• 反之, 所有子集异或总和中该位为 0 的个数与为 1 的个数相等, 均为 \(2^{n-1}\)
• 因此按位或看有没有 1, 若有贡献为对于该位位数 \(n_1\) 而言 \(2^{n_1-1} \cdot 2^{n-1}\)

状态压缩 DP

• SWAR 算法计算汉明重量
• 可以用 Brian Kernighan 算法 n&n-1 去掉最右边 1

// SWAR 算法统计 1 的个数
int swar_popcount(uint32_t x) {
    x = x - ((x >> 1) & 0x55555555); // 每 2 位统计 1 的个数
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333); // 每 4 位统计 1 的个数
    x = (x + (x >> 4)) & 0x0F0F0F0F; // 每 8 位统计 1 的个数
    x = x + (x >> 8); // 每 16 位统计 1 的个数
    x = x + (x >> 16); // 每 32 位统计 1 的个数
    return x & 0x3F; // 返回最终结果
}

• 汉明重量 (popcount) 在状态压缩 DP 中非常有用
• 将 0-n 按汉明重量排列算法如下

for (int i = 0; (1<<i)-1 <= n; i++) {
    for (int x = (1<<i)-1, t; x <= n; t = x+(x&-x), x = x ? (t|((((t&-t)/(x&-x))>>1)-1)) : (n+1)) {
        // 写下需要完成的操作
    }
}

• 对于二进制数表示的集合, 可以用位运算进行枚举子集

for (int m = 0; m < (1 << n); ++m)
  // 枚举 n 位的所有子集 m
  for (int s = m; s; s = (s - 1) & m)
    // 枚举 m 的非空子集

数学

高精度计算

• 反转存储字符串
• 竖列式计算即可, 实现加减乘除
• 对于高精度 - 低精度乘法, 进位需要取模等操作
• 压位高精度计算, \(1234 \cdot 12\) 在传统方法等效 \((1000+200+30+4) \cdot (10+2)\), 压位成 \((1200+34) \cdot 12\), 可以减少计算次数

Karasuba 算法

• 分治算法, 时间复杂度 \(O(n^{1.585})\) / \((log_23)\)
• 两个大数相乘, 将大数分为两部分 \((x_1 \cdot 10^m+x_0)\) 再相乘, 幂数固定, 计算系数即可
• 可能整数溢出!!!
• 数太大时, 考虑分成多项式计算 (依旧是 \(n^2\)), 并用 FFT 加速计算 (\(nlogn\))

袖珍计算器法

• \(a^n = e^{nlna}\)

快速幂

• 任何正整数可以唯一表示为若干个 2 的幂次的和 (同转换为二进制)

• 若一个运算 a 具有结合律, 运算 A 为 a 的幂运算 , 则 \(A (x, n)\) 为 n 次 \(a (x, x)\), 将 n 转换为二进制

• 可得 \(A (x, n) = a (A (x, n_1), A (x, n_2), ...)\) 当 \(n = n1+n2+...\)

• 快速幂可以用于求模意义下的大整数乘法

long long binmul(long long a, long long b, long long m) {
  unsigned long long c =
      (unsigned long long)a * b -
      (unsigned long long)((long double)a / m * b + 0.5L) * m;
  if (c < m) return c;
  return c + m;
}

• 若多次模意义幂询问中底数与模数不变, 可以预处理前 s 个数, 将幂次拆分, 查表加速计算

int pow1[65536], pow2[65536];

void preproc(int a, int mod) {
  pow1[0] = pow2[0] = 1;
  for (int i = 1; i < 65536; i++) pow1[i] = 1LL * pow1[i - 1] * a % mod;
  int pow65536 = 1LL * pow1[65535] * a % mod;
  for (int i = 1; i < 65536; i++) pow2[i] = 1LL * pow2[i - 1] * pow65536 % mod;
}

int query(int pows) { return 1LL * pow1[pows & 65535] * pow2[pows >> 16]; }

代数

快速傅里叶变换

• FFT 是一种高效实现 DFT (离散傅里叶变换) 的算法, 它是一种分治算法
• 在 \(O(nlogn)\) 的时间内计算两个 n 次多项式的乘法

/*
 - 做 FFT
 - len 必须是 2^k 形式
 - on == 1 时是 DFT, on == -1 时是 IDFT
 */
void fft(Complex y[], int len, int on) {
  change(y, len);
  for (int h = 2; h <= len; h <<= 1) {             // 模拟合并过程
    Complex wn(cos(2 * PI / h), sin(2 * PI / h));  // 计算当前单位复根
    for (int j = 0; j < len; j += h) {
      Complex w(1, 0);  // 计算当前单位复根
      for (int k = j; k < j + h / 2; k++) {
        Complex u = y[k];
        Complex t = w * y[k + h / 2];
        y[k] = u + t;  // 这就是把两部分分治的结果加起来
        y[k + h / 2] = u - t;
        // 后半个 「step」 中的ω一定和 「前半个」 中的成相反数
        // 「红圈」上的点转一整圈「转回来」, 转半圈正好转成相反数
        // 一个数相反数的平方与这个数自身的平方相等
        w = w * wn;
      }
    }
  }
  if (on == -1) {
    reverse(y + 1, y + len);
    for (int i = 0; i < len; i++) {
      y[i].x /= len;
      y[i].y /= len;
    }
  }
}

其它变换

• NTT 解决的是多项式乘法带模数的情况
• 沃尔什转换是在频谱分析 (没有浮点数系数) 上作为离散傅立叶变换的替代方案的一种方法

Fiduccia 算法

• 求解常系数齐次线性递推

Berlekamp–Massey 算法

• 给定一个长为 n 的数列, 如果它的最短递推式的阶数为 m, 则 Berlekamp–Massey 算法能够在 \(O(nm)\) 时间内求出数列的每个前缀的最短递推式

数论

素数筛

• 埃拉托色尼筛法, 时间复杂度 \(O(nloglogn)\)

vector<int> prime;
bool is_prime[N];

void Eratosthenes(int n) {
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; ++i) is_prime[i] = true;
  // i * i <= n 说明 i <= sqrt(n)
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i])
      for (int j = i * i; j <= n; j += i) is_prime[j] = false;
  }
  for (int i = 2; i <= n; ++i)
    if (is_prime[i]) prime.push_back(i);
}

• 分块筛求素数数量

int count_primes(int n) {
  constexpr static int S = 10000;
  vector<int> primes;
  int nsqrt = sqrt(n);
  vector<char> is_prime(nsqrt + 1, true);
  for (int i = 2; i <= nsqrt; i++) {
    if (is_prime[i]) {
      primes.push_back(i);
      for (int j = i * i; j <= nsqrt; j += i) is_prime[j] = false;
    }
  }
  int result = 0;
  vector<char> block(S);
  for (int k = 0; k * S <= n; k++) {
    fill(block.begin(), block.end(), true);
    int start = k * S;
    for (int p : primes) {
      int start_idx = (start + p - 1) / p;
      int j = max(start_idx, p) * p - start;
      for (; j < S; j += p) block[j] = false;
    }
    if (k == 0) block[0] = block[1] = false;
    for (int i = 0; i < S && start + i <= n; i++) {
      if (block[i]) result++;
    }
  }
  return result;
}

• 线性筛 (欧拉筛), 同时也得到了每个数的最小质因子

vector<int> pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.push_back(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之, i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的, 所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉, 就不需要在这里先筛一次, 所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

• 线性筛可求欧拉函数 / 莫比乌斯函数 / 约数个数 / 约数和

Pollard Rho 算法

• 随机算法, 快速分解大整数

数论分块

• 一个范围内的数具有相同的性质, 可以分块处理
• 如除以一个数的商向下取整

求贝祖系数

• 拓展欧几里得算法, 求 \(ax+by=gcd (a, b)\) 的解

求数字根 (各位数之和)

• \((n-1) \bmod 9 + 1\)

概率

贝叶斯定理用于垃圾邮件分类

• 利用贝叶斯公式计算后验概率

线性等概率采样

• 文件中随机拿出一个字符串, \(O(N)\) 的时间 \(O(1)\) 的空间, 每拿出一个, 就在两个之间以 \((n-1):1\) 的概率选一 个, 综合概率相同

博弈论

公平组合游戏

• 游戏有两个人参与, 二者轮流做出决策, 双方均知道游戏的完整信息
• 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关, 而与游戏者无关 (否则为非公平)
• 游戏中的同一个状态不可能多次抵达, 游戏以玩家无法行动为结束, 且游戏一定会在有限步后以非平局结束

分析

• 定义 必胜状态 为 先手必胜的状态, 必败状态 为 先手必败的状态 (对于此时的先手)
• 没有后继状态的状态是必败状态
• 一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态
• 一个状态是必败状态当且仅当它的所有后继状态均为必胜状态
• 有向图游戏是一个经典的博弈游戏 —— 大部分的公平组合游戏都可以转换为有向图游戏
• 在一个有向无环图中, 只有一个起点, 上面有一个棋子, 两个玩家轮流沿着有向边推动棋子, 不能走的玩家判负

\[ \begin {cases} G = \text {mex}({G (y_1), G (y_2), \dots, G (y_k)}) \\ \text {总 Grundy 数} = G_1 \oplus G_2 \oplus \cdots \oplus G_n \\ \text {当且仅当} \bigoplus_{i=1}^n G_i \neq 0 \text {时先手必胜} \end {cases} \]

其中:

• $mex(S) $ 表示集合 ( S ) 中未出现的最小非负整数
• \(\oplus\) 表示异或操作 (Nim 和)
• \(G_i\) 表示第 i 个子游戏的 Grundy 数
• \(y_1, y_2, \dots, y_k\) 是当前状态的所有可能后继状态

反常游戏

• 其胜者为第一个无法行动的玩家, 如尼姆博弈

数据结构

跳表

• Redis 中 zset 使用跳表 + 哈希表实现
• 插入时有一个随机因子, 每过一次概率, 升高一级
• 查找时, 从最高级开始, 如果下一个节点大于目标, 则下降一级, 否则继续向右走

优势

• 相较于红黑树, 区间操作更方便
• 相较于 B+ 树, 跳表的实现更简单, 常数时间复杂度低

劣势

• 缓存不友好, 只适用于内存, 否则 IO 次数太多

过滤器

• 哈希表的一种变体, 用于判断一个元素是否属于一个集合 (短时大量, 但允许一定假阳性, 不允许假阴性)
• 平衡信息与空间占用
• 平衡常数与空间占用
• 平衡时空与错误率

布谷鸟过滤器

• 就是哈希表不存数据, 改存指纹, 确定是否存在就行
• 优化成双哈希函数 + 桶 + 第三哈希函数用于冲突探测 (一直测不到就扩容 rehash)

布隆过滤器

• 对于预计 \(n\) 个元素, 错误率为 \(p\)
• 计算 \(m = \lceil -n \ln p \rceil\) 为哈希表大小
• 计算 \(k = \lceil \ln (1 - p) \rceil\) 为哈希函数数量
• 仅用 1bit 表示是否存在, 0 表示不存在, 1 表示可能存在
• 用多哈希函数平衡错误率

计数布隆过滤器

• 解决不能删除元素的问题

指纹多数同意布隆过滤器

• 解决 CBF 假阴性问题
• 每个 hash 位置都存一个指纹, 多数同意用于判断是否存在

分层布隆过滤器

• 解决 \(n\) 不可预测后, rehash 问题
• 一层布隆过滤器判断完, 再用下一层 (可以动态加)
• 在明显阴性时, 不需要继续判断下一层

商过滤器

• 哈希值 -> 除 \(2^r\) 取余, 得到商作为桶号
• 同商的元素, 线性探测往后存 (保持余数递增)
• 每个桶依旧是布隆 (用一个 bit 存, 方便明显错误)
• 用一个 bit 存是否是上一段的后继, 另外一个 bit 存是否落在理想位置 (解决线性探测不好溯源)
• 实现了线性探测的高空间利用 + 链地址的可合并性 (隐式利用了商后分布可能更均匀)

缓存

LCU

• 维护一个双向链表, 最近使用的放在链表头, 最近不使用的放在链表尾
• 使用哈希表维护每个节点的指针, 快速找到节点
• 当缓存满时, 淘汰链表尾的节点

LFU

• 维护多个双向链表, 每个链表维护一个频率, 最近使用的放在链表头, 最近不使用的放在链表尾 (LCU)
• 使用哈希表维护每个节点的指针, 快速找到节点
• 当缓存满时, 淘汰最后链表尾的节点

ARC

• 同时维护一个 LRU 链表和一个 LFU 链表以及对应垃圾桶
• 未命中时, 看一下谁的责任更大, 然后缩减对应缓存的长度

字典树

• 每个节点有 \(26\) 个指针, 分别指向 \(26\) 个字母
• 每个根节点到叶子节点的路径表示一个单词

路径压缩

• 路径出现差异时, 将所有差异的节点合并为一个节点

场景

• 路径补全 / 前缀匹配

链表

判断循环

• 快慢指针

- 判断链表交点

• 双指针走完后交换到另一个链表的头节点, 就能同时到达交点

堆

非常多的数找前 n 大的数

• 维护最小堆, 放前 n 大的数

图

沃舍尔算法

• 计算传递闭包, 时间复杂度 \(O(n^2)\)

int warshall(int a[][N]) {
  int i, j, k;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      if (a[j][i]) {
        for (k = 0; k < N; k++) {
          a[j][k] = a[j][k] | a[i][k];
        }
      }
    }
  }
}

二叉树

\(O(1)\) 空间遍历二叉树

• morris 算法, 利用叶子的孩子空间放另一半子树

字符串

Manacher 算法计算回文子串的最大长度

• 利用回文中心对称的特点跳过中心拓展的大部分计算, \(O(n)\) 时间

判断子串是否存在

• 预处理对于每个字符, 下一个字符 c 出现的位置

ST 表

• 用于求区间最大/最小值, 时间复杂度 \(O(n \log n)\) 预处理, \(O(1)\) 查询
• 其实就是更细分割的线段树, 保证任何一个区间都能仅用两个预处理区间覆盖, 但不能保证是刚好覆盖, 因为完全覆盖是 \(O(n^2)\) 时间复杂度, 只能求类似区间最大和, 并且不能插入

特殊用途

常数时间内检索到最小元素的栈

• 维护两个栈, 一个栈维护最小值, 一个栈正常

\(O(1)\) 时间随机线性表元素

• 线性表 + 哈希表

元素一一对应

• 哈希双射

其它

摩尔投票

• 随便抓一个数和不同的数对对碰, 相同的数累加
• 我的朴素理解就是集合当中一半以上的数都是同一个, 对对碰的最坏情况就是完全是该数与其他数对碰, 还会剩下该数 其他情况更是

延迟接受算法 (Deferred Acceptance Algorithm)

• 也称为 Gale-Shapley 算法, 时间复杂度 \(O(n^2)\)

• 将所有人标记为 "free" 1

• 每个 free 的求婚者按照自己的偏好列表, 向自己最偏好的被求婚者提出求婚
• 每个被求婚者收到求婚请求后如果被求婚者更喜欢新求婚者, 则接受
• 被拒绝的求婚者从自己的偏好列表中移除被拒绝的被求婚者, 并继续向下一个偏好的被求婚者求婚
• 直到所有求婚者都匹配成功或无法继续匹配
• 稳定的匹配: 使得不存在任何一对参与者愿意离开当前的匹配对象而选择彼此
• 匹配结果是求婚者可能获得的最优结果, 是被求婚者可能获得的最差结果 (在所有稳定匹配中)

验证回文整数

• 逐步反转整数, 直到反转数不大于剩余数, 等于回文, 小于不回

计算当天是星期几

• 有很多公式不介绍

中缀转后缀

• 双栈遍历, 数输出, 左括号 (最低优先级) 入栈, 右括号出栈 (直到上一个左括号出栈), 操作符先出栈 (直到栈顶优先级低于该操作符) 再入栈, 遍历结束后全出栈

勾长公式

• 将 1~n 填入一个杨表 (需满足每行从左到右, 每列从下到上都是递增的)
• 定义勾长 \(hook (v) = 方格右边的格数 + 上面格数 + 1\)
• 填入的方案数 \(dim = \frac n {\prod_{i=1}^{所有格子} hook (v)}\)