更佳的阅读体验：2023 国庆集训 Day 2A 笔记，本文同步发表于 洛谷博客。

以下内容为个人总结，如有错误或您有不同见解，欢迎指出。

搜索

LOJ 10020 - 小木棍

• 满足 $nm = \sum a_i = N$， 则需要满足 $N \mod n = 0$。
• 较劣方案：使用 DFS 一根一根构造木棍。
• 代码实现注意细节。

#include <bits/stdc++.h>
using namespace std;

const int N = 70;
int n, a[N], L;
bool vis[N], flag;

void dfs(int s) {  // s - 当前木棍长度
    bool ok = 0;
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) ok = false;
    if (ok) return flag = true, void();
    for (int i = 1; i <= n; ++i)
        if (!vis[i] && s + a[i] <= L) {
            vis[i] = 1;
            s += a[i];
            if (s == L) s = 0;
            dfs(s);
            if (!s) s = L;
            s -= a[i];
            vis[i] = false;
            if (flag) return;
        }
}

int main() {
    // read.
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    int sum = 0;
    for (int i = 1; i <= n; ++i) sum += a[i];
    for (int i = a[1]; i <= sum; ++i) if (!(sum % i)) {
        L = i;
        flag = false;
        dfs(0);
        if (flag) return cout << i << '\n', 0;
    } return 0;
}

• 搜索优化思路：减少状态数、减少状态处理时间（较难）。

分治

逆序对

• 使用归并排序。

• 思考题：对有序数列随机交换 $k$ 次，求逆序对的期望个数。

  • 归并排序。

贪心

• 局部最优解 = 全局最优解。
• 反例：背包问题，局部最优解 $\ne$ 全局最优解。

Example

有 $n$ 个怪物，每个怪物有攻击力 $a_i$ 和 $b_i$，每一轮可以对一个怪物造成 $1$ 的伤害，每个怪物会对你造成 $a_i$ 的伤害，求你受到伤害最小的攻击顺序，$n \le 10^5$。

• 优先打 $\frac{a_i}{b_i}$ （攻血比）较高的。

• 如何证明？

  • 考虑反证法。
  • 如果先打攻血比较低的，受到的伤害一定不小于先打攻血比高的。
  • 如果 $\frac{a_i}{b_i} < \frac{a_{i + 1}}{b_{i + 1}}$，则原受到 $b_i(a_i + a_{i + 1}) + b_{i + 1}a_{i + 1}$ 的伤害，交换后受到 $b_{i + 1}(a_i + a_{i + 1}) + b_i a_i$，整理后得到 $a_{i + 1} b_i$ 和 $a_i b_{i + 1}$，则有 $a_{i + 1} b_i > a_i b_{i + 1}$。

快速幂

• 任意满足结合律的都可以使用快速幂。
• 递归实现：

ll qpow(ll a, ll b) {
    if (!b) return 1;
    ll res = qpow(a, b >> 1);
    res = res * res % p;
    if (b & 1) res = res * a % p
    return res;
}

• 循环实现：

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p, b >>= 1;
    } return res;
}

龟速乘 / 快速乘

ll mul(ll a, ll b) {
    if (!b) return 1;
    ll res = 0;
    whlie (b) {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p, b >>= 1;
    } return res;
}

矩阵快速幂

• 有结合律，但无交换律。
• 可用于求较大的递推。

Example. 求斐波那契数列在模 $p$ 意义下的第 $n$ 项。

ST表

• 用于处理 RMQ 问题。

Example

给定一个序列，询问区间最小值，$n \le 10^5$，$q \le 10^7$。

• 要做到 $O(1)$ 询问，则预处理出 $f_{i,j}=\min_{k\in[i,i+2^i)} a_k$。

LCA

Tarjan.

• 记录每个点的深度。
• 先把较低点抬高，使得两点位于同一深度。