1. 求逆序对数：用归并排序，计数交换的次数

  2. 用 scanf 读 string （即使关了同步，cin 读 string 太慢）：——2019.7.20

    用 scanf 读 char，然后使用 string operator +=。

  3. 看到 1e18 就可以考虑二分了。二分天下第一。 ——2019.7.21

  4. 给定 $0 \leq k \leq 1e18$，在 $1e9$ 内找到四个数 $x_1, x_2, y_1, y_2$，使得 $x_1 y_2 - x_2 y_1 = k$。（AGC 036A）——2019.7.22

    令 $x_1=1e9, y_1=1$，即可算出符合条件的 $x_2, y_2$。

  5. 线段覆盖问题中，要求用尽量少的边，覆盖指定区域（Vjudge）——2019.7.24

    按左边界从先到后（相同时右边界从后到先）插入优先队列。当前处理的边的左边界若早于当前时间，则修改为当前时间再重新入队。

  6. 给定长度为 $n$ 迭代无序数列，$O(n)$ 求第 $k$ 大 ：

    使用快排，但是一次排序以后，只排 k 存在的那部分。若快排选的中间数合适，均摊下来是 $O(n + \frac{n}{2} + \frac{n}{4} + …) = O(n)$。

  7. 分治复杂度计算：——2019.9.19

    若 $T(n) = k \cdot O(\frac{n}{2}) + \Theta(n)$，则 $T(n) = O(n^{log_2 k})*T(1)$。（构造等比数列证明）

  8. 矩阵求逆：——2019.9.20

    目前最快的矩阵求逆法仍然是 $O(n^3)$ 的。
    但是将矩阵用高斯消元法分解为上三角形矩阵和下三角形矩阵的乘积，然后分别求逆矩阵，该算法（LU）虽然和高斯消元法是时间复杂度相同，但是可以进行并行计算。

  9. $\Theta(n)$ 生成 1-n 的随机排列—— Fisher–Yates Shuffle 洗牌算法。

1
2
3
for (int i = 0; i < n; i++) arr[i]=i+1;
for (int i = 0; i < n; ++i)
    swap(arr[i],arr[random(i, count) ]); //random(i, count) 指 [i, count] 区间上的随机数

可以用数学归纳法证明其正确性。——2019.10.16

  1. $O(\log s)$ 计算二进制数中有多少个 1—— 2020.10.23：
1
2
3
4
5
6
7
8
int bitCount(int z) {
    z = (z & 0x55555555) + ((z >> 1) & 0x55555555);
    z = (z & 0x33333333) + ((z >> 2) & 0x33333333);
    z = (z & 0x0f0f0f0f) + ((z >> 4) & 0x0f0f0f0f);
    z = (z & 0x00ff00ff) + ((z >> 8) & 0x00ff00ff);
    z = (z & 0x0000ffff) + ((z >> 16) & 0x0000ffff);
    return z;
}