基本算法

位运算

快速幂：

1
2
3
4
5
6
7
8
int powmod(int a, int b, int p) {
  int ans = 1 % p;
  for (; b; b >>= 1) {
    if (b & 1) ans = ((long long)ans * a) % p;
    a = ((long long)a * a) % p;
  }
  return ans;
}

大数乘法取模（可能溢出）：

1
2
3
4
5
6
7
long long mul(long long a, long long b, long long p) {
  long long ans = 0;
  for (; b; b >>= 1) {
    if (b & 1) ans = (ans + a) % p;
    a = (a * 2) % p;
  }
}

lowbit 算法：

1
2
3
int lowbit(int n) {
  return n & (-n);
}

枚举、模拟、递推

递归

二分

二分的实现需要注意细节：

对于整数域上的二分，需要注意终止边界、左右区间取舍时的开闭情况，避免遗漏答案造成死循环；
对于实数域上的二分，需要注意精度问题。

模版：在单调递增序列中查找 >=x 的数中最小的一个：

1
2
3
4
5
while (l < r) {
  int mid = (l + r) / 2;
  if (a[mid] >= x) r = mid; else l = mid + 1;
}
return a[l];

模版：在单调递增序列中查找 <=x 的数中最小的一个：

1
2
3
4
5
while (l < r) {
  int mid = (l + r + 1) / 2;
  if (a[mid] <= x) l = mid; else r = mid - 1;
}
return a[l];

模版：实数域二分，保留 k 位小数时：

1
2
3
4
5
while (l + 1e-5 < r) {
  double mid = (l + r) / 2;
  if (calc(mid)) r = mid; else l = mid;
}
return l

模版：求单峰函数极值（三分法）：

1
2
3
4
5
6
7
while (l + 1e-5 < r) {
  double lmid = (2 * l + r) / 3, rmid = (l + 2 * r) / 3;
  if (f(lmid) < f(rmid)) l = lmid;
  else if (f(lmid) > f(rmid)) r = rmid;
  else l = lmid, r = rmid;
}
return l;

例题（贪心，将二分答案转化为判定）：

有 N 本书排成一行，已知第 i 本书的厚度是 $A_i$。
把它们连续地分成 M 组，使得 T 最小化，其中 T 表示厚度之和最大的一组的厚度。

注意到这样的一个函数是单调的：

以分组数 M 作为定义域，在作为分组方式中，T 最小的一组，其中的 T 作为值域。

排序

排序算法分为三类：

$$O(n^2)$$ 算法: ”选择排序“、”插入排序“、”快速排序“；
$$O(n logn)$$ 算法: ”堆排序“、”归并排序“、”快速排序“；
最优 $$O(n)$$ 算法: ”计数排序“、”基数排序“、”桶排序“；

货仓选址问题：

背景：一条数轴上有 N 个商店，需要在数轴上建立一个货仓，是的货仓到每个商店的距离之和最小；
解决方案：容易得之，把货仓建在中位数的位置，是满足题意的最优解位置；

均分纸牌问题：

背景：有 M 个人排成一排，它们手中分别有 C[1]~C[M] 张纸牌，在每一步操作中，可以让某个人把手中的一张纸牌交给旁边的一个人，求至少需要多少步操作才能让每个人手中的纸牌数量相等；
解决方案：从第一个人开始分情况递归可以得到公式：$$\displaystyle \sum_{i = 1}^{M}|i * \frac{T}{M} - S[i]|$$，其中 S 表示前缀和；

环形均分纸牌问题：

背景：在均分纸牌问题的背景下，第一个人和最后一个人可以交换纸牌；
解决方案：
- 假设每个人手中的纸牌减去 $$\displaystyle \frac{T}{M}$$，使得 $$S[M] = 0$$（负数的持有牌数并不会影响结论的讨论）；
- 可以证明一定存在一对相邻的人之间没有发生纸牌的交换，枚举这个位置得到：$$\displaystyle \sum_{i = 1}^M |S[i] - S[k]|$$
- 求解上述公式在 k 为变量情况下的最小值，即“货仓选址”问题，对 S[i] 进行排序既得结果；

动态中位数问题：

背景：依次输入一个整数序列，每当已经读入的每当已经读入的整数个数为奇数时，输出已经读入的证书构成的序列的中位数；
解决方案：可以建立两个二叉堆：一个大根对（1~M/2 个元素）、一个小根堆（M/2 + 1~M 个元素）；

第 k 大数：

背景：给定 n 个整数，如何求出第 k 大的数；
解决方案：类似快排的思想，选出一个 pivot，每次排序后与 k 进行比较，只需要在一侧继续递归查找；时间复杂度 $$O(n) + O(n/2) + \cdots + 1 = O(n)$$；

求逆序对：

背景：对于一个序列 a，如果存在 i>j, a[i]<a[j]，则它们称作一对逆序对。求一个给定序列中逆序对数量；
解决方案：逆序对可以通过在归并排序的过程中计算，也可以通过数状数组计算。以下是归并的解法：

1
2
3
4
5
6
7
8
void merge(int l, int mid, int r) {
	int i = l, j = mid + 1;
  for (int k = l; k <= r; k++) {
    if (j > r || i < mid && a[i] < a[j]) b[k] = a[i++];
    else b[k] = a[j++], rcnt += mid - i + 1;
  }
  for (int k = l; k <= r; k++) a[k] = b[k];
}

奇数码问题（拼图问题）：

背景：
- 在一个 n*n 的网格中进行，其中 n 为奇数，1 个空格和 1~(n-1)*n 个数字，它们恰好不重不漏地分布在 n*n 的网格中，空格移动的规则和拼图类似。
- 现在给定两个奇数码游戏的局面 A、B，请判断 A 是否能通过移动得到局面 B；
解决方案：上述命题只需要考虑一个充分必要条件：
- 如果按顺序将网格展开序列，AB 两个局面的逆序对奇偶性相同；

基本算法

位运算

枚举、模拟、递推

递归

二分

排序

倍增