省选优化技巧

省选同样有很多杂项算法，当中不乏一些非常实用的小技巧。

更新日志

2023/10/16

完成重构。

2023/4/16

开始重构文章，整理了构成和需要写的部分。

~~实际上都是必备技能。~~

log 优化技巧

多种方式可以得到 $\log$ 级别的优化，但是当中有一些别的。

基于二分的优化

二分是对单调性的利用，只要有单调性都可以试试二分！

三分法

现在有一个函数，它是一个单峰或者单谷函数，要求出它的极值。

传统的二分法似乎并不好做，找到 mid 之后，无法确定极值在那一边。我们可以使用三分法：在 $l,r$ 内任取两点 $lmid,rmid$ ，如果 $f(lmid)<f(rmid)$ ，则函数在 $[rmid,r]$ 中必然单调递增或者单调递减（画个图，然后分类讨论，看 $lmid,rmid$ 是否分布在极值点两侧，就知道了），反之同理。那么这样就可以分出极值。

模板，代码如下：

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
const double eps = 1e-7;

int n;
double l, r, a[20];

double f(double x) {
    double ans = 0, b = 1;
    for (int i = n; i >= 0; --i, b *= x)
        ans += a[i] * b;
    return ans;
}

int main(void) {
    scanf("%d%lf%lf", &n, &l, &r);
    for (int i = 0; i <= n; ++i)
        scanf("%lf", a + i);
    while (l + eps < r) {
        double lmid = (l + r) / 2, rmid = (mid + r) / 2;
        if (f(lmid) > f(rmid)) r = mid;
        else l = mid;
    }
    printf("%.5lf\n", l);
    return 0;
}

分数规划

分数规划，一般指 01 分数规划，用来求一个分式的极值，也就求一组 $w_i=\{0,1\}$ ，最大化或者最小化：

$\frac{\sum a_i\times w_i}{\sum b_i\times w_i}$

有的时候题目还有一些限制，比如分母至少为 $W$ ，恰好有 $k$ 个 $w_i$ 是 $1$ 。

我们一般使用二分答案来解决这个问题。以最大值为例：

$\begin{aligned} &\frac{\sum a_i\times w_i}{\sum b_i\times w_i}>mid\\ \Longrightarrow& \sum a_i\times w_i - mid\times \sum b_i\times w_i > 0\\ \Longrightarrow& \sum w_i(a_i-mid\times b_i)>0 \end{aligned}$

我们使用贪心的方式就可以求出左边的最大值。

模板，要求恰好 $k$ 个 $1$ 。那么排序即可。代码如下：

查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const double eps = 1e-6;

int n, k;
double t[100005];
int a[100005], b[100005];

bool check(double x) {
    for (int i = 1; i <= n; ++i) t[i] = a[i] - x * b[i];
    sort(t + 1, t + n + 1);
    double ans = 0;
    for (int i = n - k + 1; i <= n; ++i) ans += t[i];
    return ans > 0;
}

int main(void) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) scanf("%d", b + i);
    double l = 0, r = 1e18;
    while (l + eps < r) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.4lf\n", r);
    return 0;
}

基于二分单调性的优化

将会在《DP 优化》中出现。

倍增

倍增和二分都需要具有单调性，但是倍增能够解决一些二分不能解决的问题，就像二分出 mid 之后发现 mid 无法简单 check，但是倍增却可以方便的合并信息。

倍增答案

二分答案？倍增答案！二分答案要求答案是具有单调性的，但是倍增同样可以做到！

二分上界不确定的内容的最佳方式是倍增。初始时使用倍增求出上界；求解时，类似于倍增 LCA 的方式，从上界开始，合法的最小值就是不合法的最大值 +1，那么我们从二进制位高到低枚举，如果加上这么多还不满足就一定跳!

// 使用类似于下面的方式求解上界
int st = query(); // 初始边界值
int pw = 0; 
while (1) {
    if (query(r + (1ll << pw)) != st) break;
    r += 1ll << pw; ++pw; 
}

// 使用类似于下面的方式求解答案
int ans = 0;
for (int i = 30; i >= 0; --i)
    if (!check(ans | (1 << i))) ans |= (1 << i);
ans += 1;

倍增优化 DP

这是倍增的一个重要应用，就是利用 DP 转移状态的单调性来设计一个形如 $f(i,j)$ ，其中 $j$ 代表长度为 $2^j$ 的段。

分治

~~普及组算法的复仇。~~

我们知道分治是将复杂的问题拆成多个（一般是两个）相似的子问题，直到最后分成的子问题可以简单求解，然后通过子问题的答案合并出大问题的答案。

我知道你早就知道了上面说的，所以我们还是来看点有意思的吧（在这里没出现的分治均在其它文章里出现）。

普通分治

就是正常分治，我们来看一道题：

[Luogu P7883] 平面最近点对（加强加强版）。

求一个平面上最近的点对，点数在 $4\times 10^5$ 级别。

先将所有点按照 $x$ 坐标排序，然后开始分治。关键在于如何合并：如果一个点满足 $|x[mid]-x[i]|<d$ ，其中 $d$ 代表左右两边答案的最小值，那么我们称点 $i$ 是合法的。然后将这些合法的点再按照 $y$ 坐标排序，再进行枚举， $y$ 坐标距离大于 $d$ 就 break 掉。

这样可以保证合并的时间复杂度是 $O(n)$ 的（需要采用归并排序），具体证明需要通过一些几何的方式，不打算研究。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const i64 INF = 1e15;

int n;
struct Point {
    int x, y;
    bool operator < (const Point &a) const {
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
} a[400005];

i64 dist(int i, int j) {
    i64 x = 1ll * (a[i].x - a[j].x) * (a[i].x - a[j].x);
    i64 y = 1ll * (a[i].y - a[j].y) * (a[i].y - a[j].y);
    return x + y;
}

bool cmp(const int &x, const int &y) {
    return a[x].y < a[y].y;
}

int g[400005];
i64 merge(int l, int r) {
    if (l == r) return INF;
    if (l + 1 == r) return dist(l, r);
    int mid = l + r >> 1;
    i64 d1 = merge(l, mid), d2 = merge(mid + 1, r);
    i64 d = min(d1, d2);
    int tot = 0;
    for (int i = l; i <= r; ++i) {
        i64 k = abs(a[mid].x - a[i].x);
        if (k < INF && k * k < d) g[++tot] = i;
    }
    sort(g + 1, g + tot + 1, cmp);
    for (int i = 1; i < tot; ++i)
        for (int j = i + 1; j <= tot && 1ll * (a[g[j]].y - a[g[i]].y) * (a[g[j]].y - a[g[i]].y) < d; ++j)
            d = min(d, dist(g[i], g[j]));
    return d;
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a + 1, a + n + 1);
    printf("%lld\n", merge(1, n));
    return 0;
}

二维分治

其实就是对两个东西进行分治，每次将其中一个东西切半（为了保证效率，一般选择其中区间更长的一个切半），然后合并答案。

[CF364E] Empty Rectangles.

给定一个 $n\times m(1\le n, m\le 2.5\times 10^3)$ 的 01 矩阵，询问有多少个子矩阵满足只有 $k(1\le k\le 6)$ 个 1。

本题要求恰好有 $k$ 个 1 的子矩形数量，我们将当前矩形劈成两半（以劈成左一半和右一半为例），那么符合条件的子矩形要么在左半，要么在右半，要么跨越中线。

考虑跨越中线的如何合并。我们枚举子矩形的上下边界，然后开个桶 $p$ 统计左半矩形所含 $1$ 数量小于 $i$ 时左边界的最小值（右半矩形同理），然后直接枚举左半边的 $1$ 的个数就可以统计了。

查看代码

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

int n, m, K;
i64 ans = 0;
int s[2505][2505], p[10], q[10];
int F(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) return 0;
    return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}
void divide(int xl, int yl, int xr, int yr) {
    if (xl > xr || yl > yr) return;
    if (xl == xr && yl == yr) {
        ans += (F(xl, yl, xr, yr) == K);
        return;
    }
    int d = (xr - xl > yr - yl);
    if (d) {
        int mid = xl + xr >> 1;
        divide(xl, yl, mid, yr);
        divide(mid + 1, yl, xr, yr);
        for (int i = yl; i <= yr; ++i) {
            p[0] = mid + 1; q[0] = mid;
            for (int k = 1; k <= K + 1; ++k) p[k] = xl, q[k] = xr;
            for (int j = i; j <= yr; ++j) {
                for (int k = 1; k <= K + 1; ++k) {
                    while (F(p[k], i, mid, j) >= k) ++p[k];
                    while (F(mid + 1, i, q[k], j) >= k) --q[k];
                }
                for (int k = 0; k <= K; ++k)
                    ans += (p[k] - p[k + 1]) * (q[K - k + 1] - q[K - k]);
            }
        }
    } else {
        int mid = yl + yr >> 1;
        divide(xl, yl, xr, mid);
        divide(xl, mid + 1, xr, yr);
        for (int i = xl; i <= xr; ++i) {
            p[0] = mid + 1; q[0] = mid;
            for (int k = 1; k <= K + 1; ++k) p[k] = yl, q[k] = yr;
            for (int j = i; j <= xr; ++j) {
                for (int k = 1; k <= K + 1; ++k) {
                    while (F(i, p[k], j, mid) >= k) ++p[k];
                    while (F(i, mid + 1, j, q[k]) >= k) --q[k];
                }
                for (int k = 0; k <= K; ++k)
                    ans += (p[k] - p[k + 1]) * (q[K - k + 1] - q[K - k]);
            }
        }
    }
}

int main(void) {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= n; ++i) {
        char t[2505]; scanf("%s", t + 1);
        for (int j = 1; j <= m; ++j)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (t[j] - '0');
    }
    divide(1, 1, n, m);
    printf("%lld\n", ans);
    return 0;
}

CDQ 分治

记得归并排序吗？我们要求计算分治中心左右两边部分的信息合并，这部分求值的先后顺序没有要求。这样信息可能可以简单地合并以得到一个分治做法。这种做法用来对时间维度进行降维（就是去掉一个偏序限制），也可以处理带有时间限制的问题（限定合并方向）。这种操作被称为 CDQ 分治。

三维偏序问题。给定 $n$ 个三维空间上的点，设 $f(i)$ 表示满足 $x_j\le x_i,y_j\le y_i,z_j\le z_i$ 的 $j$ 的数量，求满足 $f(i)=d$ 的 $i$ 的数量，要求对所有 $d$ 给出相应的答案。

解决这类问题的流程如下：

找到这个序列的中点 $mid$ ；
将所有点对 $(i,j)$ $(i, j)$ 划分为三类：
- $1\le i,j\le mid$ ，
- $1\le i\le mid,mid+1\le j\le n$ ，
- $mid+1\le i,j\le n$ 。
拆成左右两半的子序列，然后递归求解；
设法处理第二种点对。

也就是说，CDQ 分治就是不断把点对通过递归的方式分给左右两个区间。现在我们来看如何解决三维偏序问题：

分别处理三个信息。第一维可以将原数组按照 $x$ 排序， $x_i\le x_j$ 转化为 $i<j$ 。注意此时如果数都相同会出问题，因此去个重。

第二维可以在分治时采用类似于归并排序的方式解决（求正序对），不过由于第三维的限制，并不是所有的信息都可以加到答案里的，需要整一个权值树状数组来处理第三维的信息：左半段序列的信息加入树状数组，右半段信息进行统计。

查看代码

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

int n, m, k; 
struct Node {
    int a, b, c, cnt, ans; 
    bool operator< (const Node &a) const {
        if (this->a != a.a) return this->a < a.a; 
        if (b != a.b) return b < a.b; 
        return c < a.c; 
    }
} a[100005], T[100005]; 
int ans[100005]; 

int C[200005]; 
void add(int x, int t) { for (; x <= k; x += x & -x) C[x] += t; }
int sum(int x) { int s = 0; for (; x; x -= x & -x) s += C[x]; return s; }
void CDQ(int l, int r) {
    if (l == r) return a[l].ans += a[l].cnt - 1, void(); 
    int mid = l + r >> 1; CDQ(l, mid); CDQ(mid + 1, r); 
    int p = l, q = mid + 1; 
    for (int i = l; i <= r; ++i) {
        if (p <= mid && (q > r || a[p].b <= a[q].b)) add(a[p].c, a[p].cnt), T[i] = a[p++]; 
        else a[q].ans += sum(a[q].c), T[i] = a[q++]; 
    }
    for (int i = l; i <= mid; ++i) add(a[i].c, -a[i].cnt); 
    for (int i = l; i <= r; ++i) a[i] = T[i]; 
}

int main(void) {
    scanf("%d%d", &n, &k); 
    for (int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c), a[i].cnt = 1; sort(a + 1, a + n + 1); 
    for (int i = 1; i <= n; ++i) if (a[i].a != a[m].a || a[i].b != a[m].b || a[i].c != a[m].c) a[++m] = a[i]; else ++a[m].cnt;  
    CDQ(1, m); 
    for (int i = 1; i <= m; ++i) ans[a[i].ans] += a[i].cnt; 
    for (int i = 0; i < n; ++i) printf("%d\n", ans[i]); 
    return 0;
}

整体操作上来讲，CDQ 分治的过程与归并排序基本无异。

CDQ 分治在其它地方的应用都是将各类信息转化为偏序关系然后求解，具体可以见 Problemset。

整体二分

如果分治中遵循先递归左子树，再递归右子树的法则，那么维护一个指针去“跟踪”分治中心，这个指针的移动距离是 $O(n\log n)$ 的。

很多题目都可以使用二分来解决，但是它们只有一组询问。如果有多组询问怎么办？整体二分！又称基于值域的分治算法。

记 $[l,r]$ 为答案的值域， $[L,R]$ 为答案的定义域（人话：考虑下标在区间 $[L,R]$ 内的操作和询问，询问的答案在 $[l,r]$ 内）。

我们把所有操作按照时间顺序存入数组中，然后开始分治，并利用合适的数据结构（Fenwick 树最为常用）统计当前查询的答案和分治中心 $mid$ 之间的关系，根据查询出来的结果将序列按照分成两份递归处理，最后只有一个点就找到了答案。

你确定这是人话？！~~嗯，确实不是。~~
那么我们使用题目来讲人话：

静态区间 $k$ 小问题。

静态区间 $k$ 小，但是空间限制 10MB。想写主席树和树套树的人洗洗睡吧

我们考虑使用整体二分解决这个题目。先想一想，正常用二分解决全局 $k$ 小问题怎么做？我们先将数组排序，然后再二分。而多次询问的话，就猜测当前的答案是 $mid$ ，依次验证每个询问的答案应该是小于等于 $mid$ 还是大于 $mid$ ，根据此将询问划分成两个部分。注意，如果一个询问的答案是大于 $mid$ ，那么需要更新它的 $k$ ：减去在值域 $[l,mid]$ 上比它小的数。理由很简单，接下来对右半段询问时不会再考虑之前在左半段比它小的，需要提前把这些减去。

还有一点，不要真的去二分值域，将原数组排序后二分答案的位置。

查看代码

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
using namespace std;
typedef pair<int, int> pii;

int n, m, C[200005], id[200005];
struct Query {
    int l, r, k;
} Q[200005];
struct Number {
    int x, id;
    bool operator < (const Number &a) const {
        return x < a.x;
    }
} a[200005];
void add(int x, int k) { for (; x <= n; x += lowbit(x)) C[x] += k; }
int sum(int x) { int res = 0; for (; x; x -= lowbit(x)) res += C[x]; return res; }

int ans[200005], t1[200005], t2[200005], cur[200005];
void solve(int l, int r, int ql, int qr) { // 值域 [l, r]，询问区间 [ql, qr]
    if (ql > qr) return; // 没有操作，再见
    if (l == r) {
        for (int i = ql; i <= qr; ++i) ans[id[i]] = a[l].x;
        return;
    }
    int mid = l + r >> 1;
    for (int i = l; i <= mid; ++i) add(a[i].id, 1); // 将值域的前一半加上 1
    int p = 0, q = 0;
    for (int i = ql; i <= qr; ++i) {
        int u = id[i];
        int s = sum(Q[u].r) - sum(Q[u].l - 1); // 在区间内比小于等于 mid 的数
        if (s >= Q[u].k) t1[++p] = u; // 在 [l, mid] 中比它小的数大于其排名，答案应在 [l, mid]
        else t2[++q] = u, Q[u].k -= s;
    }
    int tot = ql - 1; 
    for (int i = 1; i <= p; ++i) id[++tot] = t1[i];
    for (int i = 1; i <= q; ++i) id[++tot] = t2[i];
    for (int i = l; i <= mid; ++i) add(a[i].id, -1); // 撤销修改操作
    solve(l, mid, ql, ql + p - 1); // 前 p 个询问的答案在 [l, mid]
    solve(mid + 1, r, ql + p, qr); // 剩下的在 [mid+1, r]
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i].x), a[i].id = i;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= m; ++i) scanf("%d%d%d", &Q[i].l, &Q[i].r, &Q[i].k), id[i] = i;
    solve(1, n, 1, m);
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

整体二分还可以用来解决具有单调性的 DP 转移问题：

[CF868F] Yet Another Minimization Problem.

题目描述：给定一个序列 $a$ ，要把它分成 $k$ 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。

$2 \leq n \leq 10^5$ ， $2 \leq k \leq \min(n,20)$ ， $1 \leq a_i \leq n$ 。

最暴力的做法是设将序列前 $i$ 个数划分为 $j$ 段的最小费用为 $f_{i,j}$ ，转移为 $f_{i,j}=\min\{f_{x,j-1}+w_{x+1,i}\}$ 。

这个转移是具有单调性的，也就是说如果 $j_1=j_2,i_1<i_2$ ，那么转移过来的地方一定满足 $x_1\le x_2$ 。

证明

假定 $x_1>x_2$ ，那么有 $f_{x_1,j-1}+w_{x_1+1, i_1}\le f_{x2,j-1}+w_{x_2+1, i_1},f_{x_2,j-1}+w_{x_2+1,i_2}\le f_{x_1,j-1}+w_{x_1+1,i_2}$ 。

当两个等号同时成立时，令 $x_2\ge x_1$ 一定能取到一个最优解。

否则可以得到 $w_{x_2+1,i_1}-w_{x_1+1,i_1} > w_{x_2+1,i_2} - w_{x_1+1,i_2}$ ，由于 $i_2>i_1$ ，这个东西显然是不成立的。

这个 DP 我们可以看作是做 $k$ 轮。我们可以采用整体二分的思想，求解的询问是当前这一轮 DP 数组的值，每一次分治我们要求解 $mid$ 的答案，找到其转移点作为单调性的分界点。

时间复杂度 $O(kn\log n)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const i64 INF = 1e12;

int n, k, m;
int a[100005], cnt[100005], L = 1, R;
i64 f[22][100005], sum;

i64 calc(int cl, int cr) {
    for (; L > cl; --L) sum += cnt[a[L - 1]], ++cnt[a[L - 1]];
    for (; R < cr; ++R) sum += cnt[a[R + 1]], ++cnt[a[R + 1]];
    for (; L < cl; ++L) --cnt[a[L]], sum -= cnt[a[L]];
    for (; R > cr; --R) --cnt[a[R]], sum -= cnt[a[R]];
    return sum;
}

void divide(int ql, int qr, int l, int r) { // 求 [ql, qr] 的 DP 值，最优决策点在 [l, r]
    if (l > r) return;
    int mid = ql + qr >> 1, pos;
    i64 minn = INF;
    for (int i = l; i <= min(mid, r); ++i) { // 最大只能到 mid
        i64 val = f[k - 1][i - 1] + calc(i, mid);
        if (val < minn) minn = val, pos = i;
    }
    f[k][mid] = minn;
    if (ql == qr) return;
    divide(ql, mid, l, pos);
    divide(mid + 1, qr, pos, r);
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    f[0][0] = 0; for (int i = 1; i <= n; ++i) f[0][i] = INF;
    for (k = 1; k <= m; ++k) divide(1, n, 1, n);
    printf("%lld\n", f[m][n]);
    return 0;
}

实际上这一类问题的共同特征是转移点单调，所以维护指针来跟踪分治重心，时间复杂度为 $O(n\log n)$ 。

线段树分治

其实之前就见过线段树分治：数学计算。我们基于时间用线段树进行操作。基于时间？这不就是 CDQ 分治吗？

实际上线段树分治就是一种维护时间区间的数据结构，而且这玩意是可以在线的（只需要每次都查询一下即可，虽然这样可能很慢）！而且还可以支持撤销操作！这是普通 CDQ 达不到的高度！

[CF601E] A Museum Robbery.

维护一个固定体积的 01 背包，支持添加、删除物品和查询答案。

背包添加物品好做删除不好做。建立一棵基于询问时间的线段树，统计每一个物品的有效期并在线段树上区间修改添加物品，最后统一查询计算一遍即可。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int B = 10000019;
const int M = 1000000007;

int n, k, m, tot = 0, tt = 1, tmp[1005];
struct item {
    int l, r, v, w;
} E[15005];
vector<item> T[120005];

void update(int o, int l, int r, int x, int y, int val) {
    if (x <= l && r <= y) return T[o].emplace_back(E[val]), void();
    int mid = l + r >> 1;
    if (x <= mid) update(o << 1, l, mid, x, y, val);
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, val);
}

void solve(int o, int l, int r, int *f) {
    int g[1005]; memcpy(g, f, sizeof(g));
    for (item x : T[o])
        for (int j = k; j >= x.v; --j)
            g[j] = max(g[j], g[j - x.v] + x.w);
    if (l == r) {
        int res = 0;
        for (int i = k; i >= 1; --i) res = (1ll * res * B + g[i]) % M;
        return printf("%d\n", res), void();
    }
    int mid = l + r >> 1;
    solve(o << 1, l, mid, g);
    solve(o << 1 | 1, mid + 1, r, g);
}

int main(void) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        int v, w; scanf("%d%d", &w, &v);
        E[++tot] = {tt, -1, v, w};
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int v, w; scanf("%d%d", &w, &v);
            E[++tot] = {tt, -1, v, w};
        } else if (op == 2) {
            int x; scanf("%d", &x);
            E[x].r = tt - 1;
        } else ++tt;
    } --tt;
    for (int i = 1; i <= tot; ++i) {
        if (E[i].r == -1) E[i].r = tt;
        if (E[i].l <= E[i].r) update(1, 1, tt, E[i].l, E[i].r, i);
    }
    solve(1, 1, tt, tmp);
    return 0;
}

树分治

参考《树形问题进阶》。

经典问题

这里记录了一些经典问题，但是往往遇到时又不知该如何处理。

随机化算法

有的时候不知道怎么做？或者遇到神秘的提交答案题（有些提交答案是不可做优化题）？可以考虑使用随机化。

随机化有两种，一种是操作次数一定，正确性与进行的轮数有关（模拟退火等）；另一种是期望操作次数，要求数据随机（除非你的方法很神秘，出题人没想到，但是如果交互库是自适应的就没辙了）。

随机化函数

mt19937 Rnd(time(0));
int rndint(int l, int r) {
    return uniform_int_distribution<>(l, r)(Rnd);
}
double rnddb(int l, int r) {
    return uniform_real_distribution<>(l, r)(Rnd);
}

爬山法

对于单峰函数，三分可能很难实现，那么可以考虑使用爬山。如果当目前无法直接到达最优解，但是可以判断两个解哪个更优的时候，根据一些反馈信息生成一个新的可能解。

[JSOI2008] 球形空间产生器。

给出 $n$ 维空间的 $n+1$ 个点，求出球心（保证存在）。

对于每一个维度都是单峰函数，因此可以采用爬山法。

假定球心为所有点的重心，然后求出所有点到球心距离的平均值，然后可以计算每个维度上球心距离的改变值（到某个点的距离与平均距离差 $\times$ 差距贡献）。

查看代码

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

int n; double dis[15]; // 答案到点的距离
double ans[15], cans[15], a[15][15];  

void check(void) {
    double tot = 0; 
    for (int i = 1; i <= n + 1; ++i) {
        dis[i] = cans[i] = 0; 
        for (int j = 1; j <= n; ++j) dis[i] += (a[i][j] - ans[j]) * (a[i][j] - ans[j]); 
        tot += (dis[i] = sqrt(dis[i])) / (n + 1); 
    }
    for (int i = 1; i <= n + 1; ++i) 
        for (int j = 1; j <= n; ++j)
            cans[j] += (dis[i] - tot) / tot * (a[i][j] - ans[j]); 
            // dis[i] - tot 为当前点与原球心的距离差与平均距离的差，除以 tot 以计算这一维度对平均距离的贡献占比
            // a[i][j] - ans[j] 为在当前维度的当前点与原球心距离差，根据此值进行移动
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n + 1; ++i) 
        for (int j = 1; j <= n; ++j) 
            scanf("%lf", &a[i][j]), ans[j] += a[i][j]; 
    for (int i = 1; i <= n; ++i) ans[i] /= (n + 1); // 放到重心
    for (double T = 20000; T > 1e-4; T *= 0.99996) {
        check(); 
        for (int i = 1; i <= n; ++i) ans[i] += cans[i] * T; 
    }
    for (int i = 1; i <= n; ++i) printf("%.3lf ", ans[i]); 
    return putchar('\n'), 0;
}

模拟退火

[JSOI2004] 平衡点。

给出模拟退火的一般实现方式：新的答案选择要为随机整数乘上当前的温度，然后以 $e^{\Delta / T}$ 的概率接受当前非最优解（保证 $\Delta$ 为正，大于 rnd(0, 1) 接受，小于不接受）。

查看代码

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

int n; 
int x[1005], y[1005], w[1005]; 
mt19937 Rand(20070521); 

double energy(double X, double Y) {
    double r = 0; 
    for (int i = 1; i <= n; ++i) r += hypot(X - x[i], Y - y[i]) * w[i]; 
    return r; 
}

int rndint(int l, int r) {
    return uniform_int_distribution<int>(l, r)(Rand); 
}

void sa(double a, double b) {
    double ax = a, ay = b, T = 100, ans = energy(ax, ay); 
    const double delta = 0.99; 
    while (T > 1e-14) {
        double xx = ax + rndint(-INT_MAX, INT_MAX) * T, yy = ay + rndint(-INT_MAX, INT_MAX) * T;  
        double now = energy(xx, yy), cmp = ans - now; 
        if (cmp > 0) ans = now, ax = xx, ay = yy; 
        else if (exp(cmp / T) * INT_MAX > rndint(0, INT_MAX)) ax = xx, ay = yy; 
        T *= delta; 
    }
    printf("%.3lf %.3lf\n", ax, ay); 
}

int main(void) {
    scanf("%d", &n); double a = 0, b = 0; 
    for (int i = 1; i <= n; ++i) scanf("%d%d%d", x + i, y + i, w + i), a += x[i] * w[i] / n, b += y[i] * w[i] / n; 
    return sa(a, b), 0;
}

实际上对于模拟退火，只有在 $\Delta T$ 较小的时候，取所有情况的最优答案会得到非常棒的答案，但是 $\Delta T$ 足够大时没什么区别，直接将答案也改成不优的也可。

其它随机化

没有统一的方式。有些套路如随机撒点，随机化贪心等，更多的还是要根据具体的问题进行分析。

其它优化技巧

这里放置了一些杂项优化技巧。

简单内容

在《提高优化技巧》出现。

贪心：包括排序贪心和反悔贪心。
双指针：扫描具有单调性的内容。
前缀和与差分：必备技能。
单调栈与单调队列：维护单调性的常见手段。

根号分治

根号分治是一种按规模大小分类讨论的思想。对于规模为 $x$ 的问题，如果我们可以使用 $O(x)$ 和 $O(\frac{n}{x})$ 的复杂度解决，那么可以在 $x\le \sqrt{n}$ 时使用 $O(x)$ 算法，否则使用 $O(\frac{n}{x})$ 算法。这样的时间复杂度为 $O(\sqrt{n})$ 。

[Luogu P3396] 哈希冲突。

B 君对 hash 冲突很感兴趣。他会给出一个正整数序列 $\text{value}$ 。

自然，B 君会把这些数据存进 hash 池。第 $\text{value}_k$ 会被存进 $(k \bmod p)$ 这个池。这样就能造成很多冲突。

B 君会给定许多个 $p$ 和 $x$ ，询问在模 $p$ 时， $x$ 这个池内 数的总和。

另外，B 君会随时更改 $\text{value}_k$ 。每次更改立即生效。

对于 $100\%$ 的数据，有 $n\leq 150000,m\leq 150000$ .

当 $x>\sqrt{n}$ 的时候，暴力即可。

当 $x\le\sqrt{n}$ ，考虑在修改时就更新答案，询问时直接输出。

这样的时间复杂度为 $O(m\sqrt{n})$ 。

查看代码

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

int n, m, t;
int a[150005];
int res[400][400];

int main(void) {
    scanf("%d%d", &n, &m); t = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        for (int j = 1; j <= t; ++j)
            res[j][i % j] += a[i];
    }
    char s[5]; int x, y;
    while (m--) {
        scanf("%s%d%d", s, &x, &y);
        if (s[0] == 'A') {
            if (x > t) {
                int ans = 0;
                for (int i = y; i <= n; i += x) ans += a[i];
                printf("%d\n", ans);
            }
            else printf("%d\n", res[x][y]);
        } else {
            for (int i = 1; i <= t; ++i)
                res[i][x % i] += y - a[x];
            a[x] = y;
        }
    }
    return 0;
}

省选优化技巧

log 优化技巧

基于二分的优化

三分法

分数规划

基于二分单调性的优化

倍增

倍增答案

倍增优化 DP

分治

普通分治

二维分治

CDQ 分治

整体二分

线段树分治

树分治

经典问题

随机化算法

随机化函数

爬山法

模拟退火

其它随机化

其它优化技巧

简单内容

根号分治

无向图三元环计数

四元环计数

Problemset

二分与三分

[JXOI2017] 加法

[CF1661F] Teleporters

[ZJOI2018] 胖

[USACO18OPEN] Talent Show G

倍增

[SCOI2015] 国旗计划

[CF1809F] Traveling in Berland

[???] 最小生成树

「Wdoi-2」死亡之后愈发愉悦

分治

[UVA1608] Non-boring sequences

[CF1442D] Sum

CDQ 分治

[CQOI2011] 动态逆序对

[Violet] 天使玩偶

[SDOI2011] 拦截导弹

整体二分

[POI2011] MET-Meteors

[CTSC2018] 混合果汁

整体二分带修 | [Luogu P2617] Dynamic Rankings

线段树分治

[Luogu P5787] 二分图 /【模板】线段树分治

[CF576E] Painting Edges

[CF603E] Pastoral Oddities

随机化算法

[CF1305F] Kuroni and the Punishment

[THUSCH2017] 巧克力

根号分治

[CF797E] Array Queries

[CF710F] String Set Queries

[CF1446D2] Frequency Problem (Hard Version)

[Ynoi2011] 初始化

[CF1039D] You Are Given a Tree