NOI 一轮复习 I：优化技巧

本文是 NOI 一轮复习的第一篇，包括无法归成大类的杂项算法。

更新日志

2023/11/04

更新了曼哈顿距离和切比雪夫距离的转化。

2023/10/25

文章大致完成。

二分与倍增

两者的本质均基于单调性，寻找题目中具有单调性的函数关系，然后施展二分或者倍增。二分答案可以用来解决分数规划问题，三分法可以求解单峰/谷函数。同时，二分上界不确定的内容的最佳方式是倍增，通过先倍增到上界，再倍增答案来解决。

ST 表

ST 表使用倍增结构来实现，支持在末尾插入一个数。大概长这样：

f[0][n] = a[n];
for (int j = 1; 1 << j <= n; ++j)
    f[j][n - (1 << j) + 1] = max(f[j - 1][n - (1 << j) + 1], f[j - 1][n - (1 << j - 1) + 1]);

wqs 二分

学名带权二分。常用于 2D /1D 的 DP，状态的其中一维是物品个数。这是它的明显标志，因此它比较套路。$f_i$ 表示恰好（最多/至少）选取 $i$ 个物品时的答案，如果 $f$ 是凸函数那么则可以使用 wqs。我们可以猜测 $O(nk)$ 过不去就是凸的，或者也可以打表。

由于 $f$ 是凸的，因此我们可以选择二分斜率，以此计算出它的切线。有时它能直接用，有时可以对 DP 进行降维，有时和斜率优化等内容一起出现。

具体来说，我们画出所有点 $(i,f(i))$，假设它们构成一个上凸壳。二分斜率 $k$，发现随着 $k$ 的减小，直线的切点会越来越靠右。

因此二分 $k$ 直到横坐标切到我们想要的位置（比如恰好选择 $m$ 个数），那么此时的纵坐标就是答案了。

如何求出切点？我们希望这个切点的 $y$ 坐标最大，也就是在 $y$ 轴上的截距最大。设截距为 $g(x)$，那么切点 $(x,f(x))$ 在 $y$ 轴上的截距就是 $g(x)=f(x)-kx$。问题就是如何求出 $g(x)$ 的值了。

考虑 $g(x)$ 的意义，相当于钦定的 $x$ 个物品的代价都比原来少 $k$，$g(x)$ 相当于每个物品代价减 $k$ 之后的最优解。

$l,r$ 如何调整？要逼近 $(m,f(m))$ 如果此时切点 $(x,f(x))$ 满足 $x<m$ 时，那么应该将斜率减小，才能让切点右移。

下凸壳大致是一样的。

设白边数量为 $k$ 的最小生成树是 $f(k)$，那么 $f$ 是一个下凸函数（其实挺显然的）。直接 wqs 即可。

int n, m, need; 
struct edge {
    int u, v, w, c; 
    bool operator< (const edge &a) const {
        if (w != a.w) return w < a.w; 
        return c < a.c; 
    }
} a[100005]; 

int fa[50005], res; 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool check(int x) {
    for (int i = 1; i <= m; ++i) if (a[i].c == 0) a[i].w -= x; 
    sort(a + 1, a + m + 1); 
    for (int i = 1; i <= n; ++i) fa[i] = i; 
    int wc = 0; res = 0; 
    for (int i = 1; i <= m; ++i) {
        int u = find(a[i].u), v = find(a[i].v); 
        if (u == v) continue; 
        fa[u] = v; res += a[i].w; wc += (a[i].c == 0); 
    }
    for (int i = 1; i <= m; ++i) if (a[i].c == 0) a[i].w += x; 
    return wc >= need; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m >> need; 
    for (int i = 1; i <= m; ++i) cin >> a[i].u >> a[i].v >> a[i].w >> a[i].c, ++a[i].u, ++a[i].v; 
    int L = -500, R = 500, ans; 
    while (L + 1 != R) {
        int mid = L + R >> 1; 
        if (check(mid)) ans = res + need * mid, R = mid; 
        else L = mid; 
    }
    cout << ans << "\n"; 
    return 0; 
}

例题

虽然都是很简单的思想，但是两者能解决的问题不少，而且各有特点。

* [CF1661F] Teleporters

Portal.

可以将原问题划分成几段，然后对于每一段放置传送器的话分的约均匀越好，全局的最小两相邻传送机距离应该是一个（尽可能满足平均），这样就可以用 $f(x,k)$ 来表示 $0\rightarrow x$ 中额外插入 $k$ 个的最小代价，显然是好求的。

直接二分需要安装的传送机数量？我们好像没有办法 check，只知道最多传送机数量的话没有一个合适的贪心策略。我们对另一个条件——总花费进行考虑。因为花费越大直接意味着传送机数量越少。

注意到 $f(x,k-1)-f(x,k)$ 随着 $k$ 的增大单调不增，这样可以在外层二分其值 $v$ 来代表一个段内的最小传送机距离（类似 wqs 的思想），找出一个 $f(x,k-1)-f(x,k)\ge v$ 的最大 $k$，而 $k$ 越大花费越小，直接利用 $k$ 来进行贪心求出每一段的最小代价，与 $m$ 比较来确定二分的答案。

设二分出来的答案是 $k$，选完之后 $m$ 的值还有剩余，我们尽可能多的值选择 $k+1$ 来榨干 $m$ 的剩余价值。

时间复杂度 $O(n\log^2 V)$，代码。

我们发现，二分答案不仅需要有单调性，而且需要有一个贪心策略来 check，并不一定是直接二分最终的答案。当发现无法 check 时可以找找我们缺少了什么导致无法贪心，然后改为二分这个缺少的东西。

[ZJOI2018] 胖

Portal.

从 $0$ 号点到达某一个点后，可以被更新的瞭望塔显然是一段连续的区间，这样我们就可以分别对左右端点进行二分。

设要从 $p$ 更新，这条路的距离为 $l$，到达第 $x$ 个点，那么令 $d=|l-x|$，在 $[x-d,x+d]$ 当中不应该存在距离小于 $p$ 时距离的点。预处理出图上距离的前缀和 $dis$，距离的最小值要分在 $x$ 的左右讨论，在 $x$ 左边时是 $dis_x+(l-dis_p)$，右边时是 $-dis_x+(l+dis_p)$，询问前 ST 表预处理两个信息即可求出距离的最小值（建立大小为 $K$ 的 ST 表，询问的时候直接二分出左右端点的位置）。

注意距离相等时更新顺序的问题，二分右端点时要对 $x+d$ 的位置做一个单独的讨论。代码。

** [CF1764G] Doremy’s Perfect DS Class

询问能告诉我们什么？好奇怪啊，不知道。尝试从给定的 $k$ 值开始分析。$k=1$ 没什么意义，然后尝试从特殊的，比如 $k=2,n$ 开始分析。$k=n$ 比较好说，只有 $n$ 可以被记入答案，可以根据此找出 $n$ 的位置。$k=2$ 则可以将数分为两组，在 $n$ 为奇数时只有 $1$ 是单独一组，$n$ 为偶数时只有 $1,n$ 是单独一组。

从别的地方再想一想，都要求 $\log$ 级别的询问，不难想到二分。设 solve(l, r) 代表答案在 $[l,r]$ 的位置中，我们需要确定 $1$ 在 $[l,mid]$ 还是 $[mid+1,r]$ 里。咦，感觉不太对，不是严格的子问题！但是我们只需要寻找答案在哪里，因此只需要分别答案在 $[1,mid]$ 还是 $[mid+1,n]$ 就好了。

选择从 $k=2$ 入手，$x,y$ 分为一组仅当它们除以二下取整后的值相等。我们可以求出两个区间中在自己区间内没有匹配的数的数量，然后这个数量大的，答案就在那里（因为剩下的每有一个都是成对的）。

$n$ 是偶数怎么办呢？我们只需要找到 $n$ 就行，不难发现 $k=n$ 可以很好的完成这个任务。当两个区间的值相等时，说明 $1,n$ 各占一个，我们令 $k=n$，询问其中一个，看 $n$ 是否在其中。找到 $n$ 的位置之后发现之后的递归不会受到影响（如果 $p_n> mid$，我们会递归到 $[l,mid]$，必定有 $p_n>mid'$）。

这个做法可以通过 G2，代码。想过掉 G3，我们需要想方法杀掉那一次多余的询问。

怎么杀？对于 $r-l+1=2$ 的情况，使用两次询问有点扯皮，我们看能不能只用一次询问杀掉它。核心思想是，充分利用我们之前问出来的信息。当我们递归到 $[l,r]$ 时，曾令一个 $mid=l-1$，也令了一个 $mid=r$，因此我们知道 $Q(1,l-1,2),Q(1,r,2),Q(l,n,2),Q(r+1,n,2)$ 的答案。现在 $l,r$ 中一个是 $1$，一个是和其他数能匹配上的某个奇怪的东西，吗？注意，另一个可能是 $n$，如果我们还没有确定 $n$ 的位置，那么通过询问 $Q(r,n,n)$ 或 $Q(1,l,n)$ 将其判掉。

现在再看怎么搞 $l,r$ 一个是 $1$，另一个是可匹配数。可匹配数只能配在 $[1,l-1]$ 或 $[r+1,n]$，如果 $Q(1,l-1,2)+1=Q(1,r,2)$，那么说明可匹配数的匹配数是开在 $[1,l-1]$ 的（这个数除以二下去整的值与 $[1,l-1]$ 中的某个数撞了），否则开在 $[r+1,n]$。确定了这一点之后，我们就可以锁定 $1$ 的位置了！以开在 $[1,l-1]$ 为例，如果 $Q(1,l-1,2)=Q(1,l,2)$，说明 $l$ 处开可匹配数，与 $[1,l-1]$ 中的某个数匹配，$1$ 就开在 $r$ 处。

这样在 $r-l+1=2$ 时我们只花费了一次询问，可以通过 G3。代码。

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

Portal.

$i+1$ 个可爱数连着 $i$ 个非可爱数。设 $j(a)$ 代表 $a$ 是否为可爱数。求出 $j(a)=j(a+p)$ 的最大 $p$，$j(a+p+1)=j(a+p+q)$ 的最大 $q$，则容易根据 $p,q,j(a)$ 解出 $a$。

对于求解 $p,q$，考虑倍增。注意倍增时要先跳两个 $2^0$，这样保证每一次跳跃的长度不大于以前跳跃的长度，因为区间并不是严格单调的，这样防止跳出区间。

对于 $q$ 的倍增并不需要从 $0$ 开始，可以发现 $p\le q$，因此可以直接先跳一个不超过 $p-1$ 的数，代码。

[SCOI2016] 萌萌哒

Portal.

并查集？复杂度不对，考虑倍增并查集。使用类似于 ST 表的结构，操作时直接操作高层节点的并查集，处理完之后将高层内容下放，这样可以得到完整的答案。代码。

* [CF802O] April Fools’ Problem

Portal.

关于题目个数的是一个下凸函数，而且斜率单调不降，可以采用 wqs 二分。

如何贪心 check？对于每个 $b_i$，找到之前没选过的 $a_j$，如果 $a_j+b_i\le 0$ 那么选择 $a_j$。让它支持反悔，可以顶替掉一个 $b_j$，贡献为 $b_i-b_j$。代码。

分治

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

仿照分治的结构可以衍生出一大堆静态分治算法。

普通分治

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

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

二维分治

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

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

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

CDQ 分治

树套树的本质作用是降维，但是如果允许离线，则可以使用 CDQ 分治高效地完成这个问题。

最重要的应用是解决三维偏序问题。分别处理三个信息。第一维可以将原数组按照 $x$ 排序，$x_i\le x_j$ 转化为 $i<j$。注意此时如果数都相同会出问题，因此去个重。第二维可以在分治时采用类似于归并排序的方式解决（求正序对），不过由于第三维的限制，并不是所有的信息都可以加到答案里的，需要整一个权值树状数组来处理第三维的信息：左半段序列的信息加入树状数组，右半段信息进行统计。代码。

CDQ 分治的写法非常灵活，像三维偏序问题是对分治树进行后序遍历来统计答案的。对于一些 DP 问题，往往可以在中序遍历时统计前面一半对后面一半的影响。

---

高维 CDQ 分治。以 CDQ 套 CDQ 为例子，实际上也很简单，对于外层 CDQ 采用中序遍历计算来处理第一维偏序，然后对于 $[l,r]$ 进行内层 CDQ。时间复杂度为 $O(n\log^2 n)$（内层只归并）。

以下是四个关键字的最长上升子序列的例子。

void CDQ2(int l, int r) {
    if (l == r) return; int mid = l + r >> 1; 
    CDQ2(l, mid); CDQ2(mid + 1, r); 
    for (int i = l; i <= mid; ++i) if (b[i].op == 0) b[i].op = 2; 
    for (int i = mid + 1; i <= r; ++i) if (b[i].op == 1) b[i].op = 3; 
    sort(b + l, b + r + 1, cmp2); 
    for (int i = l; i <= r; ++i) {
        if (b[i].op == 2) add(b[i].d, f[b[i].id]); 
        else if (b[i].op == 3) f[b[i].id] = max(f[b[i].id], sum(b[i].d)), b[i].op = 1; 
    }
    for (int i = l; i <= r; ++i) if (b[i].op == 2) clr(b[i].d), b[i].op = 0; 
}
void CDQ1(int l, int r) {
    if (l == r) return f[a[l].id] += a[l].cnt, void(); 
    int mid = l + r >> 1; CDQ1(l, mid); 
    for (int i = l; i <= r; ++i) b[i] = a[i]; 
    for (int i = mid + 1; i <= r; ++i) b[i].op = 1; 
    sort(b + l, b + r + 1, cmp1); CDQ2(l, r); 
    CDQ1(mid + 1, r); 
}

整体二分

如果分治中遵循先递归左子树，再递归右子树的法则，那么维护一个指针去“跟踪”分治中心，这个指针的移动距离是 $O(n\log n)$ 的。过程类似于将多次二分合并到一起进行，可以借此得到优秀的复杂度。

本身常数极小，解决区间 $k$ 小问题的时间复杂度是 $O(n\log^2 n)$，但却跟主席树的 $O(n\log n)$ 的速度差不多。

可以二分出美味度的答案，而又有多组询问，因此考虑整体二分。先加入一个美味度为 $-1$，可以无限买的免费果汁方便处理。将果汁按照美味度从大到小排序。

我们将美味度 $\le mid$ 的果汁全部加入树状数组。对当前询问的分组需要二分出满足其体积限制的最小价格，只需要考虑比这个价格低的果汁一定要全买，不足的用价格等于这个的果汁补即可。

时间复杂度 $O(n\log^3 n)$，换成树状数组倍增可以做到 $O(n\log^2 n)$，代码。

线段树分治

按时间建立线段树，将操作覆盖到线段树上的点，那么处理一个时间的答案就是从叶子到根所有节点信息的并。利用可撤销数据结构可以通过在线段树上 DFS 即可得到每个时间的答案。

使用 $k$ 个可撤销并查集维护每一个颜色。但是如果答案是 NO 不执行此操作如何处理？

线段树分治的特性是 $1\rightarrow q$ 依次处理，第 $i$ 次询问的生效区间是 $[i+1,y-1]$（$y$ 代表下一次修改这条边的时间）。可以在每个叶子上再考虑是否满足二分图的条件（每个询问只会多一条边），然后不满足的话这个修改的颜色改为边当前的颜色。代码。

猫树分治

在分治时维护前后缀的信息，然后通过这些信息求出跨过分治中心的答案。

考虑分治，对于 $r\le mid$ 的询问，划分到左边处理，对于 $l>mid$ 的询问，划分到右边处理，对于跨越 $mid$ 的询问，从 $mid$ 开始向左右遍历，合并背包即可。时间复杂度 $O((n\log n+ q)t)$。

int n, m, h[40005], w[40005]; 
struct Query {
    int l, r, V; 
} Q[200005]; 
int ans[200005], p[200005], T[200005]; 
int f[40005][205]; 

void solve(int l, int r, int ql, int qr) {
    if (ql > qr) return; 
    int mid = l + r >> 1; 
    for (int i = 0; i <= 200; ++i) f[mid][i] = 0; 
    for (int i = mid + 1; i <= r; ++i) {
        for (int j = 0; j < h[i]; ++j) f[i][j] = f[i - 1][j]; 
        for (int j = h[i]; j <= 200; ++j)
            f[i][j] = max(f[i - 1][j], f[i - 1][j - h[i]] + w[i]); 
    }
    for (int i = h[mid]; i <= 200; ++i) f[mid][i] = w[mid]; 
    for (int i = mid - 1; i >= l; --i) {
        for (int j = 0; j < h[i]; ++j) f[i][j] = f[i + 1][j]; 
        for (int j = h[i]; j <= 200; ++j)
            f[i][j] = max(f[i + 1][j], f[i + 1][j - h[i]] + w[i]); 
    }
    int qmid = ql - 1, tm = 0; 
    for (int i = ql; i <= qr; ++i) {
        int id = p[i]; 
        if (Q[id].r <= mid) p[++qmid] = id; 
        else if (Q[id].l > mid) T[++tm] = id;  
        else {
            int &res = ans[id]; 
            for (int x = 0; x <= Q[id].V; ++x) 
                res = max(res, f[Q[id].l][x] + f[Q[id].r][Q[id].V - x]); 
        }
    }
    for (int i = 1; i <= tm; ++i) p[qmid + i] = T[i]; 
    qr = qmid + tm; 
    solve(l, mid, ql, qmid); solve(mid + 1, r, qmid + 1, qr); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> h[i]; 
    for (int i = 1; i <= n; ++i) cin >> w[i]; 
    int tm = 0; 
    for (int i = 1; i <= m; ++i) {
        cin >> Q[i].l >> Q[i].r >> Q[i].V; 
        if (Q[i].l == Q[i].r) ans[i] = (Q[i].V >= h[Q[i].l] ? w[Q[i].l] : 0); 
        else p[++tm] = i; 
    }
    solve(1, n, 1, tm); 
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n"; 
    return 0; 
}

例题

多种多样！

* [CF1442D] Sum

注意到数组是单调不降的，因此要取一个数组就会一直取下去直到不能取或者取光了。

所以可以想到一个暴力一点的做法：将一个数组视为一个有体积有价值的物品，然后正反做两遍 01 背包，枚举没取满的那个数组和这个数组取多少个，再枚举前面取的体积，这样就可以得出后面取的体积，并计算出总价值，时间复杂度为 $O(nk^2)$。

这样肯定过不去，发现就是合并太慢了，考虑使用分治算法合并：求解 $(l,r)$ 时，我们先将 $(l,mid)$ 加入背包，然后递归求解 $(mid+1,r)$，当 $l=r$ 时就可以枚举当前体积了。时间复杂度 $O(nk\log n)$。

这个问题被称为缺一背包，意思是其中有一个可以取不满，一般采用上述分治法解决。

int n, k;
vector<i64> a[3005];
i64 ans = 0, f[3005];

void merge(int l, int r) {
    if (l == r) {
        for (int i = 0; i <= min(k, (int)a[l].size() - 1); ++i)
            ans = max(ans, a[l][i] + f[k - i]);
        return;
    }
    int mid = l + r >> 1;
    i64 g[3005];
    memcpy(g, f, sizeof(g));
    for (int i = mid + 1; i <= r; ++i)
        for (int j = k; j >= a[i].size() - 1; --j)
            f[j] = max(f[j], f[j - a[i].size() + 1] + a[i][a[i].size() - 1]);
    merge(l, mid);
    memcpy(f, g, sizeof(f));
    for (int i = l; i <= mid; ++i)
        for (int j = k; j >= a[i].size() - 1; --j)
            f[j] = max(f[j], f[j - a[i].size() + 1] + a[i][a[i].size() - 1]);
    merge(mid + 1, r);
}

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

[Ynoi2016] 镜中的昆虫

Portal.

维护 $pre_x$ 代表 $x$ 上一次出现的位置，$x$ 在区间第一次出现当且仅当 $pre_x<l,x\in [l,r]$。那么这个问题就变成了允许离线的带修二维数点。

这个修改存在颜色段均摊，可以直接做。具体地，使用 set 维护颜色段，也记录所有颜色对应的段，然后对于修改的东西的后继都重新计算 $pre$。

于是就变成了三维偏序模板。代码。

[CF603E] Pastoral Oddities

Portal.

满足题目条件意味着所有连通块的大小都是偶数。将边按照权值从小到大排序，然后线段树分治从右到左依次处理每一条边，计算每一条边可以被记入答案的范围。代码。

随机化算法

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

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

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);
}

爬山法

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

答案为单峰函数时可以采用爬山法，每次计算答案应该的改变 $cans$，然后 $ans\leftarrow ans+cans\times T$。

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] 为在当前维度的当前点与原球心距离差，根据此值进行移动
}

// 给 ans 赋一个近似的初值
for (double T = 20000; T > 1e-4; T *= 0.99996) {
    check(); 
    for (int i = 1; i <= n; ++i) ans[i] += cans[i] * T; 
}

模拟退火

新的答案选择要为随机整数乘上当前的温度（或考虑随机调整之类的），以 $e^{\Delta / T}$，即 exp(Delta / T) 的概率接受当前非最优解（保证 $\Delta$ 为正，大于 rnd(0, 1) 接受，小于不接受）。实际上，只有在 $\Delta T$ 较小的时候，取所有情况的最优答案会得到非常棒的答案，但是 $\Delta T$ 足够大时没什么区别，直接将答案也改成不优的也可，这种方式可以用于某些提交答案题。

实际上有时反而将模拟退火接受错解的概率改成固定的能得到更好的结果，但是这时它应该不叫退火了。

其它随机化

对于最优化问题和存在类问题，通常答案的构造方式不止一种，这时可以考虑随机化。也有随机化贪心、随机撒点等做法。具体见题车。

例题

比较考验选手的乱搞能力。

* [CF1556H] DIY Tree

Portal.

给生成树定义估价函数 $f(T)=\sum_{i=1}^K \max\{0,D_i-d_i\}$，其中 $D_i$ 代表实际度数。

先求出最小生成树，然后对其进行调整。每次选择一条边权最大的，删去后 $f$ 会减小的边 $e_1$，替换成加上后 $f$ 不会变大的边权最小的边 $e_2$，时间复杂度为 $O(n^3)$。

随机化这个过程，我们给 $e_1$ 和 $e_2$ 的选择加上一个概率，不选就接着扫。代码。

提交答案题

直接给定输入文件，让你不择手段求解答案的题目类型。曾在 2016 以前频繁在考场上出现，不过近年来非传统题的地位正逐步被交互题霸占。

常见类型

通常以下类型的数据点会被组合成提交答案题：

• 可以被手玩或者超级大暴力解出来的数据点；
• 特殊构造的数据点，可以使用特别的解法；
• 需要使用乱搞方法解决的数据点。

例题

由于现在考的不是很多，因此只看一些比较常规的。

[eJOI2018] 互素树

Portal.

由于题目中保证存在 $X=0$，随机一个排列然后按照条件贪心往树里填都是很容易出解的，因此直接随机化加贪心，跑半个小时就行。

[JRKSJ R2] Dark Forest

Portal.

使用增量法 $O(1)$ 计算交换位置的贡献，然后随机接受时把答案也给接受了就行（因为方案不好存储，这样的退火也很优），然后尽量调低 $\Delta$。注意特判 #3。

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

int n, p[1005]; 
i64 a[1005], ans; 
mt19937 Rand(time(0)); 

inline int rndint(int l, int r) { return uniform_int_distribution<>(l, r)(Rand); }
inline double rnddb(double l, double r) { return uniform_real_distribution<>(l, r)(Rand); }

inline int P(int x) {
    if (x <= 0) return x + n; 
    if (x > n) return x - n; 
    return x; 
}
void calc(int x, int y) { // 将 p[x] 赋值为 y 时答案改变
    int A = p[P(x - 2)], B = p[P(x - 1)], &C = p[x], D = p[P(x + 1)], E = p[P(x + 2)]; 
    ans -= (B * a[A] * a[B] + C * a[B] * a[D] + D * a[D] * a[E]) * a[C]; 
    C = y; 
    ans += (B * a[A] * a[B] + C * a[B] * a[D] + D * a[D] * a[E]) * a[C]; 
}

void SA(double T, const double ET, const double delta) {
    for (int i = 1; i <= n; ++i) calc(i, i); 
    while (T > ET) {
        int x = rndint(1, n), y = rndint(1, n), px = p[x], py = p[y]; 
        i64 tmp = ans; calc(x, py); calc(y, px); 
        if (ans <= tmp && exp((ans - tmp) / T) < rnddb(0, 1)) // 回退答案
            ans = tmp, swap(p[x], p[y]); 
        T *= delta; 
    }
    cerr << "ans = " << ans << "\n"; 
    for (int i = 1; i <= n; ++i) printf("%d ", p[i]); 
    putchar('\n');  
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i); 
    return SA(1e15, 1e-15, 0.99999), 0; 
}

哈希方法

哈希的种类有很多种，如果一个东西看起来只能 $O(n)$ 进行比较，但是我们必须 $O(1)$ 比较时，可以考虑使用哈希。

序列哈希

即字符串哈希，快速比较两个序列的相等情况。一般来讲我们采用 $b$ 进制方式的哈希，即 $f(s)=\sum_{i=1}^{l}s_i\times b^{l-i}$。

配合二分，字符串哈希可以以 $O(kn\log n)$ 的时间复杂度完成允许失配 $k$ 次的字符串匹配问题。

集合哈希

针对集合哈希我们通常将每个元素随机映射成一个数，然后哈希函数定义为异或和之类的东西。

[CSP-S 2022] 星战。说的是所有点的出度为 $1$，但是这样不好维护，转化为入度进行维护，搞一个哈希提高正确率。代码。

树哈希

模板。我们给子树定义一个哈希函数，然后将子树加起来，就可以判断是否同构了。

int n; 
vector<int> G[1000005]; 
u64 h[1000005]; 

mt19937_64 Rand(time(0)); 
map<u64, u64> mp; 
inline u64 get(u64 x) {
    if (mp.find(x) == mp.end()) return mp[x] = Rand(); 
    return mp[x]; 
}

set<u64> s; 
void dfs(int x, int fa) {
    h[x] = 1; 
    for (int y : G[x]) if (y != fa) dfs(y, x), h[x] += get(h[y]); 
    s.emplace(h[x]); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n; 
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v; 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    } dfs(1, 0); 
    cout << s.size() << "\n"; 
    return 0; 
}

例题

也很多种多样！

[CF1746F] Kazaee

Portal.

将每个数哈希成一个随机数，然后树状数组维护区间和，如果能被 $k$ 整除那就应该是对的。正确率是 $\frac 1 k$，跑个 $30$ 轮即可。代码。

[CF1794E] Labeling the Tree with Distances

Portal.

根据树上距离进行树哈希，换根 DP 求解树哈希，然后必须是这个根节点占一个 $B^i$，判一下就行。代码。

*【XR-3】系统设计

Portal.

二分跳转用到的序列长度，如果在 $x$ 为根的子树中能够找到一条链和此时 Hash 值相等，那么就能跳。序列的 Hash 值使用线段树维护即可。

快速查询树上 Hash？先看看固定根的时候怎么做？很显然，预处理出根到当前节点的哈希就可以。由于保证了是有根树，因此直接差分即可处理别的根。时间复杂度为 $O(n\log n)$，非常高效。代码。

[NOI2022] 挑战 NPC II

Portal.

题目已经告诉我们这是一个树哈希，而且 $k$ 小的离谱，因此往最暴力的想！

简单！能匹配的子树直接匹配掉，不能匹配的最多只有五个，枚举全排列向下递归，记忆化爆搜就行！代码。

杂项优化技巧

一些其它内容。

贪心

比较靠猜，比较人类智慧。

分为排序贪心和反悔贪心两种。

不删除双指针

给定一个长度为 $n$ 的序列，定义 $f(l,r)$ 为区间进行某种运算后的结果。有一些合法区间，合法区间左端点给定，右端点是连续的，且不存在包含的合法区间。

双指针！对啦！但是有一些问题无法快速删除（如 $\gcd$），我们可以使用不删除双指针。

条件是，信息可以快速归并。

其大致思想是提前预处理一遍 $l$ 右移时的信息，倒着扫一遍 $l$ 的移动路径即可。

具体来说，维护左右指针 $l,r$，还有中间指针 $m$。初始时所有指针都指向 $1$，然后重复以下步骤直到 $r$ 移到了 $n$。

1. 将 $l,m$ 指向 $r$，然后左移 $l$，直到 $[l,m]$ 不合法，记录 $p_i=f(i,m)$。
2. $r$ 右移一次，右移 $l$ 指针使得区间重新合法，$f(l,r)$ 通过 $f(l,m)$ 和 $f(m+1,r)$ 求出。当 $l>m$ 时，返回步骤 $1$。

由于 $l$ 的左移不会超过上一次的 $m$（大概是左移之后再右移回来的样子，会移动 $2n$ 次），因此时间复杂度为 $O(n)$。

刚好可以使用不删除双指针！

cin >> n; 
for (int i = 1; i <= n; ++i) cin >> a[i]; 
for (int i = 1; i < n; ++i) a[i] = abs(a[i + 1] - a[i]); 
int ans = 0; 
for (int m, l, r = 1; r < n; ) {
    for (m = l = r, p[l + 1] = 0; l >= 1; --l) {
        p[l] = gcd(p[l + 1], a[l]); 
        if (p[l] == 1) break; 
    } 
    ++l; i64 w = 0; 
    while (1) {
        ans = max(ans, r - l + 1); ++r; 
        if (r >= n) break; 
        for (w = gcd(w, a[r]); l <= m && gcd(p[l], w) == 1; ) ++l; 
        if (l > m) break; 
    }
}
cout << ans + 1 << "\n"; 

前缀和与差分

这里主要重提一下高维的情况。可以使用 sosDP 来进行求解，也就是枚举子集。

for (int j = 0; j < n; ++j)  
    for (int i = 0; i < (1 << n); ++i)
        if (i >> j & 1) f[i] += f[i ^ (1 << j)];

高维差分还是考虑容斥来计算。

根号分治（平衡）

有关于根号数据结构，请参考 NOI 一轮复习 IX：数据结构 B。由于大部分根号分治都会和其它数据结构结合，因此这里只介绍基本方法。

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

值得注意的是，这种思想很常用，且复杂度不一定是根号的。

根号平衡

考虑这样一个问题：

$O(1)$ 单点修改，$O(\sqrt{n})$ 查询区间和。

简单！分块维护块内的和，每次修改的时候更新块内和即可。

$O(\sqrt{n})$ 单点修改，$O(1)$ 查询区间和。

分块维护块内块外前缀和，也就是每个块内前 $x$ 个数的和和前 $x$ 块的和，那么查询就是 $O(1)$ 的了。

$O(1)$ 区间修改，$O(\sqrt{n})$ 查询单点。

将第一个差分掉直接做即可。

维护一个集合，$O(\sqrt{n})$ 插入数，$O(1)$ 查询 $k$ 小。

考虑值域分块，每个数维护其所在的块，对块维护一个有序表，插入的时候直接归并，$k$ 小就可以直接查询。

图上三四元环计数

无向图三元环计数。让度数小的点向度数大的点连边，然后暴力 for 查找。如果一个点的度数大于 $\sqrt{m}$，这样的点不超过 $\sqrt{m}$ 个；如果一个点度数小于 $\sqrt{m}$，那么这样的点最多 $m$ 个。因此时间复杂度为 $O(m\sqrt{m})$。

int n, m, ans, deg[100005];
int u[200005], v[200005], vis[100005];
vector<int> G[100005];

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", u + i, v + i);
        ++deg[u[i]]; ++deg[v[i]];
    }
    for (int i = 1; i <= m; ++i) {
        int x = u[i], y = v[i];
        if (deg[x] > deg[y] || (deg[x] == deg[y] && x > y)) swap(x, y);   
        G[x].emplace_back(y);
    }
    for (int u = 1; u <= n; ++u) {
        for (int v : G[u]) vis[v] = u;
        for (int v : G[u]) for (int w : G[v])
            if (vis[w] == u) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}

四元环计数。整体思路跟三元环计数一样，考虑怎样数的不重不漏。枚举一个起点 $u$，保证它是排名最大的点，然后枚举与它距离为 $2$ 的点，统计其中无序对 $(x,y)$ 的个数即可。代码。

bitset 优化

bitset 可以使用 string 来赋初值：

bitset<N> b(string("000100101")); 

使用 set() 将 bitset 赋值为全 $1$，reset() 将 bitset 清空。

bitset 可以进行随机访问，是 $O(1)$ 的。而其所有位运算操作都是 $O\left(\frac n w\right)$ 的。cin, cout 都可以直接输入输出 bitset。

可以使用 b.to_ullong() 来将其转化为 u64 类型。

可以使用 _Find_first() 和 _Find_next(x) 来找到第一个和下一个为 1 的位置。

另外有一些位运算函数：

• __builtin_clz：返回最高位左边的 $0$ 的个数；
• __builtin_ctz：返回最低位开始右起的连续的 $0$ 的个数。

---

CF1584B。如果前 $k$ 个能恰好被解锁，那么答案是 $\sum_{i=1}^k a_i - (k-1)$。对于解锁情况可以使用 DP 来解决：设 $f_i$ 代表前缀 $i$ 是否恰好能被解锁，那么 $f_{j+a_i}\leftarrow f_j(j\ge i)$，这个过程可以使用 bitset 加速。代码。

可行性背包

CF1856E。只要更改子树内的权值分布，就可以达到贡献最大化，所以是个树上背包状物，可以通过 E1，代码。

对于 E2，我们要思考如何高效解决“把儿子大小构成的数集合分成差尽可能小的两部分”。子树中不同的 $siz$ 最多只有 $\sqrt{n}$ 种，二进制拆分掉保证物品个数不多于 $\log n$ 个，然后是可行性背包采用 bitset 优化，单次时间复杂度是 $O\left(\dfrac{n\sqrt{n}}{w}\right)$ 的。

以下是 bitset 实现可行性背包的代码：

bitset<524288> b; 
b = 0; b[0] = 1; 
for (int x : a) b |= (b << x); 

如何将其搬到树上？简单。如果存在一个重儿子，它比所有轻儿子都重，这样可以直接得出答案。否则会造成一个分治的效果，每次问题规模必定减半，时间复杂度为 $O\left(\dfrac{n\sqrt{n}\log n}{w}\right)$。实际效率非常高。代码。

字符串匹配

假定文本串为 $s$，对于每一个字符开一个大小为 $|s|$ 的 bitset $N_c$。对于询问，新建一个 bitset，初始都是 $1$，从前到后枚举询问串的每个位置 $y_i$，和这个字母对应的 bitset 右移 $i$ 位取按位与，最后就是所有匹配成功的位置。时间复杂度为 $O\left(\frac{nm}{w}\right)$，而且支持带修，直接修改或者位移 bitset 即可。

模板，代码如下：

char t[N]; 
bitset<N> a[10], ans, _1, res; 

int main(void) {
    int q; scanf("%d", &q); _1.set(); 
    while (q--) {
        int op, l, r; scanf("%d", &op); 
        if (op == 0) {
            scanf("%d%s", &l, t); ++l;
            int m = strlen(t); res = ~(_1 << l); 
            for (int i = 0; i < 10; ++i) 
                a[i] = (a[i] & _1 << l) << m | (a[i] & res); 
            for (int i = 0; i < m; ++i) a[t[i] - '0'][l + i] = 1; 
        } else if (op == 1) {
            scanf("%d%d", &l, &r); ++l; res = ~(_1 << l); 
            for (int i = 0; i < 10; ++i) 
                a[i] = (a[i] & _1 << r + 1) >> r - l + 1 | (a[i] & res); 
        } else {
            scanf("%d%d%s", &l, &r, t); ++l; 
            int m = strlen(t); 
            if (m > r - l + 1) { puts("0"); continue; } ans.set(); 
            for (int i = 0; i < m; ++i) ans &= a[t[i] - '0'] >> i; 
            printf("%d\n", (ans >> l).count() - (ans >> r - m + 2).count()); 
        }
    }
    return 0;
}

矩阵乘法

对于定义乘法为与运算，加法为或运算的广义矩阵乘法可以使用 bitset 优化。

按照边权从小到大排序，然后依次考虑。维护一个数组代表当前能到达的节点，然后每次更新当前时间，“解锁”每一条边。

如果我知道当前的可达性，那么我要知道走一条边的可达性，用 bitset 加速需要记录所有的入边，因此建反图即可。

int n, m; i64 d[N]; 
struct Edge {
    int u, v, w; 
    bool operator< (const Edge &a) const { return w < a.w; }
} e[N];  

bitset<N> vis; 
struct Matrix {
    bitset<N> a[N]; 
    friend bitset<N> operator* (const bitset<N> &x, const Matrix &y) {
        bitset<N> r; 
        for (int i = 1; i <= n; ++i) r[i] = (x & y.a[i]).any(); 
        return r; 
    }
    friend Matrix operator* (const Matrix &x, const Matrix &y) {
        Matrix z; 
        for (int i = 1; i <= n; ++i)
            for (int k = 1; k <= n; ++k)
                if (x.a[i][k]) z.a[i] |= y.a[k]; 
        return z; 
    }
} a; 

inline void poww(Matrix a, int b, bitset<N> &ans) {
    for (; b; b >>= 1, a = a * a) if (b & 1) ans = ans * a; 
}

int main(void) {
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); 
    sort(e + 1, e + m + 1); 
    i64 ans = INF; vis[1] = 1; 
    for (int i = 1, t = 0; i <= m; ++i) {
        if (e[i].w >= ans) break; 
        poww(a, e[i].w - t, vis); a.a[e[i].v][e[i].u] = 1; t = e[i].w; 
        queue<int> q; 
        for (int x = 1; x <= n; ++x)
            if (vis[x]) q.push(x), d[x] = 0; 
            else d[x] = INF; 
        while (!q.empty()) {
            int u = q.front(); q.pop(); 
            for (int v = 1; v <= n; ++v)
                if (a.a[v][u] && d[v] == INF) d[v] = d[u] + 1, q.emplace(v); 
        }
        ans = min(ans, t + d[n]); 
    }
    if (ans == INF) puts("Impossible"); 
    else printf("%lld\n", ans); 
    return 0;
}

偏序

可以用来解决高维偏序问题，设求解 $m$ 维，则时间复杂度为 $O\left(\frac{n^2m}{w}\right)$，也就是一维偏序做 $m$ 轮，每轮比较每个数，然后把这 $m$ 轮的结果都与起来。可能需要逐块处理 bitset。模板，代码如下：

int n; 
int p[3][N], a[3][N], w[N];
bitset<N> b[10005], s;

int main(void) {
    scanf("%d%*d", &n); 
    for (int i = 1; i <= n; ++i) for (int j = 0; j < 3; ++j) scanf("%d", a[j] + i), p[j][i] = i;
    for (int i = 0; i < 3; ++i) sort(p[i] + 1, p[i] + n + 1, [i](int x, int y) { return a[i][x] < a[i][y]; }); // 按每一维排序
    for (int l = 1, r = 0; l <= n; l = r + 1) { 
        r = min(l + 10000, n); 
        for (int i = l; i <= r; ++i) b[i - l].set();
        for (int i = 0; i < 3; ++i) {
            s.reset(); 
            for (int j = 1, k = 1; j <= n; ++j) {
                int o = p[i][j]; 
                for (; k <= n && a[i][p[i][k]] <= a[i][o]; ) s[p[i][k++]] = 1; 
                if (l <= o && o <= r) b[o - l] &= s;
            }
        }
        for (int i = l; i <= r; ++i) ++w[b[i - l].count()]; 
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", w[i]);
    return 0;
}

有向图连通性

bitset 可以加速传递闭包的计算（通常是加速 Floyd），另一个高效做法是缩点后 bitset 加速 BFS。

for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        if (b[i][k]) b[i] |= b[k]; 

逐块处理 bitset

有时直接开 $n$ 个 bitset 会 MLE，因此考虑每次只处理 $B$ 个 bitset，然后处理 $\frac n B$ 次即可。

例题

以下内容将告诉你 bitset 为什么是神。

[Luogu P6328] 我是仙人掌

Portal.

用 bitset 求图的可达性的模板。代码。

* [CF1239E] Turtle

Portal.

由于第一行走的是前缀和，第二行走的是后缀和，因此将第一行排为不降，第二行排为不升。这样它要么在 $1$ 往下走，要么在 $n$ 往下走。

也就是说，去掉 $a_1,a_2$ 后，将剩下数分为两堆 $A,B$，最小化 $\max\{\sum A,\sum B\}$。

考虑 DP，$f_{i,j,k}$ 表示前 $i$ 个数，$j$ 个放入 $A$，$\sum A=k$ 的存在性。对 $(i,j)$ 开大小为 $k$ 的 bitset，直接转移即可。代码。

* [JSOI2015] 最小表示

Portal.

注意到图是一个 DAG，因此对于一条边 $(u,v)$，如果删了这条边依然存在 $u\rightarrow v$ 的间接路径，那么这条边必定被删去。

对于每个点求出它能到达的点和能到达它的点（不含自己）。如果 $u$ 能到达的点和能到 $v$ 的点有交集，那么这条边可以被删去。

前者每个点维护一个 bitset，按照拓扑序从大到小转移即可。后者建反图后跟前者一样。时间复杂度 $O\left(\frac{nm}{w}\right)$。代码。

特殊问题处理方法

本节会介绍一些经典问题的处理方法。

位运算

位运算本身的性质几乎只针对位运算本身，因此和其它运算组合起来的时候不是那么好看。

这时往往考虑按位处理，因为这样只需要考虑 01 两种数字，经常可以使用数据结构来维护。

枚举子集和枚举超集：

for (int i = s; i; i = (i - 1) & s)
for (int i = s; i <= u; i = (i + 1) | s)

括号序列

常用的思路是令 ( = 1, ) = -1，性质什么的很显然。

最长上升子序列

将一个序列改为非严格单调递增的，至少需要修改这个序列长度减去单调不降子序列的长度。

而严格单调递增呢？考虑 1 1 2 2 3 3，用序列长度减去它的 LIS 长度是错误的。因此构造 $B_i=A_i-i$ 可以将问题转化为非严格单调递增。

先转化为要变成非严格单调递增。对于之前的数维护一个大根堆，如果当前的 $a_i$ 比之前最大的数小，那么就将那个最大的数强行改为 $a_i$。发现这样构造出来的答案一定不会更劣，但是是否合法呢？

定义“微调”为在不改变花费的前提下改变数对的值。我们现在要找将 $y$ 修改为 $x$ 后是否会使得一个 $y$ 前面的 $z$ 满足 $z>y$。

当 $z>y$ 时矛盾，那么考虑将 $x,y$ 微调成 $z$，此时花费为 $(y-z)+(z-x)=y-x$，这样答案依然合法。

如何输出答案？令 $b_i$ 为 $i$ 时刻的堆顶，对 $b$ 取一遍后缀最小值即可。

for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i); q.push(a[i]); 
    if (q.top() > a[i]) {
        ans += q.top() - a[i]; 
        q.pop(); q.push(a[i]); 
    }
    b[i] = q.top(); 
}
printf("%lld\n", ans); 
for (int i = n - 1; i >= 1; --i) b[i] = min(b[i], b[i + 1]); 
for (int i = 1; i <= n; ++i) printf("%d ", b[i]); 

曼哈顿与切比雪夫距离

曼哈顿距离是指 $x,y$ 坐标的差的和，而切比雪夫距离指的是差的最大值。

从曼哈顿距离转化成切比雪夫距离，令 $x_i'=x_i+y_i,y_i'=x_i-y_i$，反着转的时候反过来解一下二元一次方程组就行。

容易解出转为曼哈顿距离后点的坐标为 $\left(\cfrac{x+y}{2},\cfrac{x-y}{2}\right)$。枚举中心点 $i$，分别讨论横纵坐标的贡献即可直接计算。代码。

有序序列的交换数

给定一个排列，要让它变得有序。

每次交换一个相邻数，最小操作数是逆序对数。

每次交换一个任意数，最小操作数是序列长度减置换环数。

常用公式

题车

对于对应的组别来说，中档题会附带一个星号，难题会附带两个星号。

刷基础 1

巩固所学内容，训练思维的熟练度、准确度和速度。本身难度不大。

[CF1114E] Arithmetic Progression

Portal。操作二用于二分出等差数列的最大数，随机几个数求出公差 gcd 即可。代码。

[HNOI2009] 最小圈

Portal。分数规划，SPFA 检查是否存在负环。代码。

* [CF1354G] Find a Gift

Portal。如果知道其中 $x$ 个是石头，那么就能用这 $x$ 个去确定另外 $x$ 个数当中有没有石头。先找到 $1$ 个石头，然后从头开始倍增找到第一个没有石头的区间。要确定这段有石头的区间的第 $1$ 个石头位置，可以二分。如何找到一个石头？不知道，采用随机化。随机找到一些位置，找到当中最重的，那么可以确定那个是石头。代码。

* [TJOI2017] 异或和

Portal。按位处理最终答案的第 $k$ 位是否为 $1$。记录序列的前缀和，第 $k$ 位能否出现 $1$ 仅跟当前位和后面的低位（需要考虑借位）有关，树状数组维护低位即可。代码。

[CF1175F] The Number of Subpermutations

Portal。考虑枚举 $1$ 的位置，然后向右扫最大值，用哈希判断是否所有数都恰好出现一次。这种情况统计了最大值在 $1$ 的右边，于是反过来再做一遍即可。代码。

[Luogu P5631] 最小 mex 生成树

Portal。不难想到线段树分治，在答案值域上建立线段树维护即可。代码。

* [CF1418G] Three Occurrences

Portal。扫描线从左往右扫找到数最多出现三次的区间，然后哈希维护即可。代码。

[CF1795E] Explosions?

Portal。总花费更少，那么我们就希望炸掉的血量更多。当变成一个严格单峰函数的时候（令 $a_i\leftarrow a_i-i$ 变成单峰来处理），也就是搞成一段一段公差为 $1$ 的等差数列，就可以炸了。容易想到通过单调栈处理这个东西，正反做两遍然后合并即可。代码。

[CF1237D] Balanced Playlist

Portal。破环成链，单调队列维护最大值，根据此来判断什么时候砸掉播放器即可。代码。

* [CF1500B] Two chandeliers

Portal。由于 $a,b$ 中出现的数完全不同，因此考虑找出它们第一次出现相同的位置，最后二分 check 即可。怎么找位置？首先判掉无解，然后 excrt 找位置即可。

[ARC067D] Yakiniku Restaurants

Portal。发现走的必定是一条线段。从右端点开始枚举左端点，维护数组 $ans_i$ 表示右端点在 $i$ 的最优答案。每次考虑是否将贡献换到左端点，单调栈维护前缀最大值来计算贡献即可。代码。

刷基础 2

另一些基础题。

[2nd ucup #21] Festival Decorating

Portal.

我们考虑对于每个灯开一个 bitset 维护距离它右边 $x$ 的灯是否存在，那么时间复杂度 $O(n^2/w)$，空间开不下。我们可以有 $50\%$ 的误差，因此开对数个 bitset，存到对数里即可。代码。

刷提升

稍有一定难度的题目。

[CF232E] Quick Tortoise

Portal.

由于这个问题可以用 DP 的方式进行扩展，因此不难想到离线。又发现其好扩展不好撤销，因此不难想到猫树分治处理。

考虑按照 $x$ 坐标进行分治，考虑：

1. $x$ 的起点终点跨越了 $mid$，设 $f_{i,j,k}$ 代表 $(i,j)$ 能否达到 $(mid,k)$，$g_{i,j,k}$ 代表 $(mid,k)$ 能否达到 $(i,j)$。$f$ 的转移为 $f_{i,j,k}=f_{i+1,j,k}\operatorname{or}f_{i,j+1,k}$，$g$ 同理，两者都可以使用 bitset 优化。
2. 否则递归下去处理。

时间复杂度 $O\left(\cfrac{nm\log n}{w}\right)$。代码。

* [CF793E] Problem of offices

路径上的叶子个数等同于路径外的，而且有两条路径，手玩之后不难发现这两条路径必定相交，不妨先令其为 a c b d。

欧拉序一定会选取全部的子树。对于 $a,b,c,d$ 来说，其内部的子树一定会被选取。考虑 $a\rightarrow b$，$a$ 向上走到根，这条路径上内部的子树可以自由决定是否被计入 $a\rightarrow b$，$b$ 也是同理。但其中 $c$ 所对应的子树的答案一定要被计入。

$c\rightarrow d$ 也是一样，$b$ 的答案一定要被计入。最后 $c\rightarrow b$ 这部分的答案是两条路径的交集。

bitset 优化可行性背包即可。代码。

[AGC020D] Min Max Repetition

Portal.

字符串填写的方式不难得出，最小连续长度 $k=\max\left\{\left\lceil\cfrac{A}{B+1}\right\rceil,\left\lceil\cfrac{B}{A+1}\right\rceil\right\}$。

字符串一定是 $(A^kB)$ 的一个前缀加上 $(AB^k)$ 的一个后缀。如何找到分界点？最优情况下分界点一定是一个 $A$，是前后缀公用的。假设分界点之前有 $b$ 个 $B$ 和 $a$ 个 $A$，那么应满足 $b\le \max\left\{0,\left\lfloor\cfrac{a-1}{k}\right\rfloor\right\}$，也就是 $a=A-\left\lceil\cfrac{B-b}{k}\right\rceil+1$。二分找到最大的 $b$ 即可确定一切。代码。

[CF1795G] Removal Sequences

Portal.

$a_i=0$ 一定是最后被删去的，考虑逆时旅人，令 $d_i\leftarrow \operatorname{deg}(i)-a_i$，按照这个进行拓扑排序即可求出一组合法解。

考虑求出不美好的点对，如果这张有向图的两个点直接互相可达，那么这是不美好的。bitset 直接统计即可。由于会 MLE，因此逐块处理，每次只统计 $1\sim n$ 对于 $l\sim r$ 的可达性即可。代码。

[ARC065C] Manhattan Compass

Portal.

将曼哈顿距离转为切比雪夫距离，排序二分不难找出合法的点的区间。如何求方案数？对于 $i$ 所对应的合法区间 $[l,r]$，$i$ 向 $l$ 连边，然后区间内依次连边。对于连到了 $a$ 点的点，其方案数均可以被统计。

为了避免重复统计，需要注意对于 $y$ 统计时不能计算 $x$ 相等的情况。代码。

刷综合

综合应用。

[Ptz 2023 Winter Day 6] 4

Portal.

依然是小度数连向大度数。对于 $u$ 能到达的点 $v$，统计 $v$ 能到达哪些 $u$ 能到达的点。然后枚举三元环，就能 $O(\sqrt{m}/w)$ 统计出 K4。代码。

[CF1237G] Balanced Distribution

Portal.

一个长度为 $l$ 的区间一定可以用 $\lceil\frac{l-1}{k-1}\rceil$ 次操作完成。可以先令 $a_i\leftarrow a_i-avg$。

一般情况下，合并两个区间进行操作看上去都不劣，但一种情况除外：两个区间都满足 $(k-1)\mid (l-1)$。也就是说，切断的位置的元素前缀和一定相等。

因此最优解由若干段区间拼成，每段都能独立操作完成，而且每一段都满足 $l\bmod (k-1)=1,\sum a_i=0$。倍增维护这样的段，贪心尽可能多的选取这样的段。

输出方案时直接从右到左枚举每一段，段右边的内容平均数 $\ge avg$ 时就从这里开始向右扫答案，将多余数留在左边。代码。

* [JSOI2019] 精准预测

* [NOI2020] 制作菜品