1. 快排

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        else break;
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

2. 快选

void quick_sort(int l, int r, int k)
{
    if (l >= r) return q[l];

    int i = l - 1, j = r + 1, x = q[l];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        else break;
    }
    int sl = j - l + 1;
    if(k <= sl) return quick_sort(l, j, k);
    return quick_sort(j + 1, r, k - sl);
}

3. 归并

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

4. 二分

二分应用范围：将最优化问题转化为判定问题

整数二分

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

练习题

acwing 1227 分巧克力
acwing 680 剪绳子

5. 高精度

6. 前缀和

一维

cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];

    int l, r;
    while(m --)
    {
        cin >> l >> r;

        cout << s[r] - s[l - 1] << endl;
    }

二维

cin >> n >> m >> k;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> a[i][j];
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        }
    }

    while(k --)
    {
        int x, y, X, Y;
        cin >> x >> y >> X >> Y;

        cout << s[X][Y] - s[X][y - 1] - s[x - 1][Y] + s[x - 1][y - 1] << endl;
    }

7. 差分

一维

int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        insert(i, i, a[i]);
    }

    while(m --)
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }


}

二维

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> a[i][j];
            insert(i, j, i, j, a[i][j]);
        }
    }

    while(q --)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cout << b[i][j] << ' ';
        }

        puts("");
    }

    return 0;
}

8. 双指针

9. 位运算

• n的二进制表示，第k位是几 n >> k & 1
• 返回x的最后一位1

int lowbit(int x)
{
    return x & -x;
}

acwing 90. 64位整数乘法

10. 离散化

11. 区间合并

12. 模拟

acwing 3257 跳一跳
acwing 445 数字反转
acwing 3257 跳一跳
acwing 3227 折点计数
acwing 3203 画图
acwing 3232 最大波动
acwing 421 陶陶摘苹果
acwing 3489 星期几
acwing 441 数字统计
acwing 703 数独检查
acwing 496 机器翻译
acwing 3346 你知道你的ABC吗
acwing 3208 Z字型扫描

13.进制转化

acwing 1346 回文平方
acwing 124 数的进制转换
acwing 428 数列

14.洛谷专题

算法1-2 排序
算法1-6 二分查找与二分答案
算法2-1 前缀和与差分

15.RMQ

acwing 1273. 天才的记忆