第 7.3 章：Ad Hoc 题型

Ad hoc 的意思是“为此目的专门设计”。在竞赛编程里，Ad Hoc 题通常没有一个现成模板可以直接套用；你必须观察题目的特殊结构，设计一个专门解法。

很多同学害怕 Ad Hoc，因为它不像 BFS、前缀和、DSU 那样有固定代码。但从教练角度看，Ad Hoc 并不是“靠灵感玄学做题”。它有可以训练的步骤：

1. 做小例子：从 N=1、2、3、4 开始手算。
2. 找结构：观察奇偶、单调、对称、循环、极端情况。
3. 提出猜想：把规律写成一句话。
4. 证明猜想：用不变量、交换论证、反证或构造证明。
5. 实现最简版本：关键洞察出现后，代码往往很短。

本章会把 Ad Hoc 从“凭感觉”变成“有步骤的观察训练”。

7.3.1 什么是 Ad Hoc 题

定义

Ad Hoc 题通常具备以下特征：

• 题目不直接对应标准算法模板。
• 难点在于发现某个特殊性质，而不是写复杂数据结构。
• 一旦发现性质，实现常常很简单。
• 题面可能像模拟、数学、构造、几何或贪心，但真正解法依赖特定观察。

一个典型例子

题目：给定 N 个整数，每次可以把一个数加 2。问能否让所有数变成相等？

初看像模拟或搜索，但关键观察是：

• 加 2 不改变一个数的奇偶性。
• 因此所有数最终相等时，它们必须有相同奇偶性。
• 如果初始奇偶性不全相同，不可能。
• 如果奇偶性全相同，总可以把较小的数加 2 追上较大的数。

这就是典型 Ad Hoc：关键在奇偶不变量，代码只需检查 parity。

Ad Hoc 与其他题型的区别

注意：Ad Hoc 可以和标准算法组合。例如“先发现只需考虑相邻元素，再排序扫描”，这就是 Ad Hoc 观察 + 排序。

7.3.2 如何识别 Ad Hoc

当你读完题后，如果出现以下感觉，很可能是 Ad Hoc：

• “这不像我学过的任何模板。”
• “N 不大，但直接暴力又不够优雅。”
• “题目有很强的特殊规则。”
• “操作看起来复杂，但可能存在不变量。”
• “题目问的是能否、最少几步、任意构造。”
• “样例似乎暗示某个规律。”

常见信号

7.3.3 Ad Hoc 的五步训练法

第一步：把题目降到最小

不要从最大数据开始想。先问：

• N = 1 时答案是什么？
• N = 2 时有哪些情况？
• N = 3 时是否出现新现象？
• 所有元素相等时怎样？
• 已经满足条件时怎样？
• 完全相反的极端情况怎样？

很多规律只在小例子中最清楚。

第二步：记录表格

对小数据列一个表：

如果答案序列是 1, 2, 4, 8，可能是指数或子集。 如果是 1, 3, 6, 10，可能是三角数。 如果只和奇偶有关，可能有 parity 不变量。

第三步：找“不变”和“单调”

Ad Hoc 中最重要的两个问题：

1. 什么永远不会变？
2. 什么每次都朝一个方向变化？

常见不变量：

• 总和。
• 总和模 K。
• 奇偶性。
• 黑白格数量差的奇偶性。
• 排列逆序对奇偶性。
• 连通块数量的某种限制。

常见单调量：

• 未完成元素数量减少。
• 最大值不增或最小值不减。
• 区间长度变短。
• 距离目标越来越近。

第四步：提出一句话猜想

不要让规律停留在模糊感觉中。把它写成一句话：

• “答案只取决于最大值和最小值。”
• “只需要检查相邻排序后的元素。”
• “如果总和不是 K 的倍数，一定不可能。”
• “最优解一定可以调整成先做 A 再做 B。”
• “每个状态最多出现一次，重复后进入循环。”

一句话猜想越清晰，越容易证明和实现。

第五步：证明或找反例

证明前先尝试找反例。若找不到，再考虑证明。

常见证明方式：

7.3.4 核心技术一：不变量

不变量是 Ad Hoc 中最强的工具之一。它回答：无论怎么操作，什么量不会变？

例 1：奇偶不变量

题目：有一个整数 x，每次可以加 2 或减 2。能否从 a 变成 b？

观察：每次操作都不改变奇偶性。

因此：

• 如果 a 和 b 奇偶性不同，不可能。
• 如果奇偶性相同，可以通过反复加减 2 到达。

代码：

if ((a % 2 + 2) % 2 == (b % 2 + 2) % 2) {
    cout << "YES\n";
} else {
    cout << "NO\n";
}

例 2：总和模 K

题目：有 N 个数，每次选择一个数加 K。能否让所有数相等？

每个数对 K 取模的值不会变。所以所有数最终相等的必要条件是：所有数模 K 相同。

如果都模 K 相同，也可以把较小的数不断加 K 追到最大值或更高，因此条件也是充分的。

bool ok = true;
for (int i = 1; i < n; i++) {
    if (((a[i] - a[0]) % k + k) % k != 0) {
        ok = false;
    }
}
cout << (ok ? "YES\n" : "NO\n");

例 3：网格 2×2 翻转

题目：从全 0 的 N×M 网格出发，每次可以选择一个 2×2 方块，并把其中 4 个格子全部翻转（0 变 1，1 变 0）。给定目标网格，问能否达到？

错误的想法是只看黑白格数量奇偶性。更精确的不变量是：

• 每次翻转某个 2×2，会在两行中各翻转 2 个格子，因此每一行的 1 的个数奇偶性不变。
• 同理，每一列也翻转 2 个格子，因此每一列的 1 的个数奇偶性不变。
• 初始全 0，所以每行、每列的 1 的个数都必须是偶数。

对于这个操作，这个条件也是充分的：可以从左上到右下贪心消去所有 1，最后只需检查最后一行和最后一列。

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (string& row : g) cin >> row;

    vector<int> rowParity(n, 0), colParity(m, 0);
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (g[r][c] == '1') {
                rowParity[r] ^= 1;
                colParity[c] ^= 1;
            }
        }
    }

    bool ok = true;
    for (int x : rowParity) ok &= (x == 0);
    for (int x : colParity) ok &= (x == 0);

    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

7.3.5 核心技术二：下界 + 构造

很多“最少操作次数”题可以这样解：

1. 证明答案至少是多少（下界）。
2. 给出一种方法恰好达到这个下界（构造）。
3. 因此答案就是这个数。

示例：把所有数变成最大值

题目：给定数组，每次可以把一个元素加 1。问最少多少次让所有元素相等？

下界：最终值至少是当前最大值 mx，每个 a[i] 至少要增加 mx - a[i] 次。

构造：把每个元素都加到 mx，正好需要这些次数。

所以答案：

long long ans = 0;
int mx = *max_element(a.begin(), a.end());
for (int x : a) ans += mx - x;

示例：圆桌换座

题目：N 头奶牛坐成一圈，其中 K 头是 A 型。每次可以交换任意两个相邻奶牛。问最少交换多少次，让所有 A 型连续。

一个简化版本中，如果允许“任意交换”而不是相邻交换，那么答案是：选一个长度 K 的连续窗口，让窗口内 B 的数量最少。这些 B 需要被换出去。

这类题的思路是：

• 下界：最终 A 连续时，一定有某个长度 K 的窗口全是 A。原来窗口内有多少 B，就至少要换出多少个。
• 构造：把窗口外的 A 与窗口内的 B 交换，正好这么多次。

于是答案是所有长度 K 窗口内 B 数的最小值。

7.3.6 核心技术三：循环与周期

当题目要求模拟很多次操作，T 可能达到 (10^9) 或 (10^{18})，直接模拟不可能。此时问：状态会不会重复？

若状态空间有限，重复后就进入循环。

循环检测模板

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

vector<int> nextState(vector<int> state) {
    // 根据题意生成下一个状态
    return state;
}

int main() {
    long long T;
    int n;
    cin >> n >> T;
    vector<int> state(n);
    for (int& x : state) cin >> x;

    map<vector<int>, long long> seen;
    long long step = 0;

    while (step < T) {
        if (seen.count(state)) {
            long long cycleStart = seen[state];
            long long cycleLen = step - cycleStart;
            long long remaining = (T - step) % cycleLen;
            for (long long i = 0; i < remaining; i++) {
                state = nextState(state);
            }
            break;
        }

        seen[state] = step;
        state = nextState(state);
        step++;
    }

    for (int x : state) cout << x << " ";
    cout << "\n";
    return 0;
}

什么时候适合找循环

• 状态数量有限。
• 每一步由当前状态唯一决定下一状态。
• T 很大。
• 题目类似“重复操作直到第 K 次”。

函数图、排列反复应用、有限状态模拟，都经常用循环。

7.3.7 核心技术四：重新表述

Ad Hoc 题常常被故事包装得很复杂。重新表述能把它变成你熟悉的问题。

例：从“奶牛移动”到“区间覆盖”

题面可能说：奶牛在数轴上走来走去，经过的草地都会被踩踏。问最终有多少长度被踩过。

重新表述：每段行走是一段区间，问题是求多个区间的并集长度。

此时可以：

• 坐标小：用布尔数组标记。
• 坐标大：排序区间后合并。

例：从“照片顺序”到“排列”

题面说：有 N 头奶牛，每头有唯一编号，照片中顺序被打乱，问最少交换多少次恢复顺序。

重新表述：这是一个排列排序问题。

如果允许任意交换，最少交换次数 = N - 循环个数。

如果只允许相邻交换，最少交换次数 = 逆序对数。

7.3.8 核心技术五：分类讨论

Bronze 中大量 Ad Hoc 题可以通过仔细分类解决。分类讨论不是低级技巧，而是严谨处理小规模结构的方法。

分类讨论原则

• 分类必须覆盖所有情况。
• 不同类别之间最好互斥。
• 每类内部逻辑要简单。
• 写代码时顺序要与分类一致。

示例：两个区间的关系

两个区间 [a,b] 和 [c,d] 的关系只有几类：

1. 完全不相交：b < c 或 d < a。
2. 部分相交。
3. 一个包含另一个。
4. 端点刚好接触。

如果使用半开区间 [l, r)，许多情况可以统一为：

int overlap = max(0, min(b, d) - max(a, c));

这就是从分类讨论升级为公式。

7.3.9 核心技术六：交换论证

有些 Ad Hoc 看起来像贪心，但需要证明为什么某种顺序是最优。

交换论证的基本形式：

1. 假设存在一个最优解，但其中有两个相邻选择顺序“不符合贪心规则”。
2. 交换这两个选择后，答案不会变差。
3. 不断交换，最终得到一个符合贪心规则的最优解。
4. 因此贪心正确。

示例：按结束时间选择最多不重叠区间

要选最多不重叠活动。贪心选择结束最早的活动。

证明思路：

• 设某个最优解第一个选择的活动不是结束最早的。
• 用结束最早的活动替换它，不会影响后面活动，因为结束更早只会留下更多空间。
• 所以存在一个最优解以结束最早活动开头。
• 递归处理剩余部分。

虽然这是标准贪心，但很多 Ad Hoc 贪心观察都可以用类似方法证明。

7.3.10 工作示例一：区间涂色

题目

一条围栏被编号为整数位置。FJ 先把区间 [a,b) 涂成红色，再把 [c,d) 涂成蓝色。蓝色会覆盖红色。问最终红色长度和蓝色长度。

思考过程

这题看似模拟涂色，但本质是两个半开区间的覆盖关系。

• 蓝色长度一定是 d - c。
• 红色原本长度是 b - a。
• 被蓝色覆盖的红色部分是两个区间交集。
• 最终红色长度 = 红色原长 - 交集长度。

交集长度：

max(0, min(b, d) - max(a, c))

代码

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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    int red = b - a;
    int blue = d - c;
    int overlap = max(0, min(b, d) - max(a, c));

    cout << red - overlap << " " << blue << "\n";
    return 0;
}

教练点评

这题的关键不是代码，而是统一使用半开区间 [l,r)。半开区间能避免端点是否重复计算的混乱。

7.3.11 工作示例二：丢失的奶牛式模拟

题目模型

从位置 x 出发，要到达位置 y。第 1 次向右走 1，第 2 次向左走 2，第 3 次向右走 4，第 4 次向左走 8……方向交替，距离每次翻倍。问第一次经过 y 时走过的总距离。

为什么是 Ad Hoc

它看起来只是模拟，但有两个细节：

• 每一步是一段线段，不是只检查终点。
• 目标 y 可能在当前移动路径中间被经过。

解法

每次移动从 cur 到 next。如果 y 在这段区间内，就加上 abs(y - cur) 后结束；否则加上整段距离并继续。

代码

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

int main() {
    long long x, y;
    cin >> x >> y;

    long long cur = x;
    long long ans = 0;

    for (int k = 0; ; k++) {
        long long offset = 1LL << k;
        if (k % 2 == 1) offset = -offset;
        long long nxt = x + offset;

        long long lo = min(cur, nxt);
        long long hi = max(cur, nxt);

        if (lo <= y && y <= hi) {
            ans += llabs(y - cur);
            break;
        }

        ans += llabs(nxt - cur);
        cur = nxt;
    }

    cout << ans << "\n";
    return 0;
}

教练点评

这类题的陷阱是把“到达终点”误写成“终点等于 y”。实际上，只要移动线段经过 y 就结束。

7.3.12 工作示例三：最少交换恢复排列

题目

给定 1..N 的一个排列。每次可以交换任意两个位置。问最少多少次交换能把排列变成升序。

小例子

排列 2 1 3：交换 1 次。

排列 2 3 1：

• 1 应到位置 1，当前位置 3。
• 2 应到位置 2，当前位置 1。
• 3 应到位置 3，当前位置 2。

形成一个长度 3 的循环，需要 2 次交换。

关键观察

一个长度为 L 的循环，需要 L-1 次交换修好。

如果排列分解成 C 个循环，总交换次数：

N - C

代码

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int& x : p) cin >> x;

    vector<bool> vis(n, false);
    int cycles = 0;

    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            cycles++;
            int cur = i;
            while (!vis[cur]) {
                vis[cur] = true;
                cur = p[cur] - 1;
            }
        }
    }

    cout << n - cycles << "\n";
    return 0;
}

教练点评

同样是“排序”，不同操作导致不同答案：

• 任意交换：循环分解。
• 相邻交换：逆序对数量。

读题时必须先确认操作类型。

7.3.13 工作示例四：第一行决定全部

题目

5×5 灯阵，每盏灯为开或关。按一个格子会切换它自己和上下左右相邻灯。问最少按几次能让所有灯关闭。

暴力想法

每个格子按或不按，共 (2^{25}) 种，太多。

关键观察

每个格子按两次等于没按，所以只需考虑按 0 或 1 次。

更重要的是：只要第一行怎么按确定了，后面每一行都被迫确定。

原因：

• 第一行处理完后，如果第 0 行某个灯还亮，那么唯一能影响它的未决定按钮是它正下方的按钮。
• 所以第 1 行对应按钮必须按。
• 依次类推，每一行都由上一行是否熄灭决定。

因此只需枚举第一行 (2^5=32) 种情况。

代码

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

int originalGrid[5][5];
int dr[5] = {0, -1, 1, 0, 0};
int dc[5] = {0, 0, 0, -1, 1};

int solve(int firstMask) {
    int g[5][5];
    memcpy(g, originalGrid, sizeof(originalGrid));
    int presses = 0;

    auto press = [&](int r, int c) {
        presses++;
        for (int k = 0; k < 5; k++) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (0 <= nr && nr < 5 && 0 <= nc && nc < 5) {
                g[nr][nc] ^= 1;
            }
        }
    };

    for (int c = 0; c < 5; c++) {
        if (firstMask & (1 << c)) {
            press(0, c);
        }
    }

    for (int r = 1; r < 5; r++) {
        for (int c = 0; c < 5; c++) {
            if (g[r - 1][c] == 1) {
                press(r, c);
            }
        }
    }

    for (int c = 0; c < 5; c++) {
        if (g[4][c] == 1) return INT_MAX;
    }
    return presses;
}

int main() {
    for (int r = 0; r < 5; r++) {
        for (int c = 0; c < 5; c++) {
            cin >> originalGrid[r][c];
        }
    }

    int best = INT_MAX;
    for (int mask = 0; mask < (1 << 5); mask++) {
        best = min(best, solve(mask));
    }

    if (best == INT_MAX) cout << "impossible\n";
    else cout << best << "\n";

    return 0;
}

教练点评

这类题的关键词是“局部操作影响邻居”。常见突破口是：枚举边界，然后内部被迫确定。

7.3.14 Ad Hoc 模式速查表

7.3.15 如何训练 Ad Hoc

训练一：每题写“关键观察”

不要只写“这题 AC 了”。要写：

关键观察：每次操作不改变所有数模 K 的余数。
因此只需检查所有数是否同余。

长期积累后，你会拥有自己的观察库。

训练二：强制手算小例子

每道 Ad Hoc 题至少手算 3 个小例子。即使你已经有思路，也要验证。

建议格式：

N=1：...
N=2：...
N=3：...
极端情况：...

训练三：先写暴力找规律

如果你猜不出公式，可以写小范围暴力，然后打印答案表。

例如：

for (int n = 1; n <= 10; n++) {
    cout << n << " " << brute(n) << "\n";
}

答案表经常会暴露规律。

训练四：对每个操作问三个问题

遇到操作题时，问：

1. 这个操作改变了什么？
2. 这个操作不改变什么？
3. 这个操作能不能反过来做？

这三个问题常常直接导向不变量或逆向思考。

7.3.16 练习题

下面练习按难度排列。建议你先只看提示，独立完成后再看题解。

🟢 P1. 同余变换

给定 N 个整数和 K。每次可以选择一个数加 K。问能否让所有数最终相等。

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

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n);
    for (long long& x : a) cin >> x;

    long long r = ((a[0] % k) + k) % k;
    bool ok = true;
    for (long long x : a) {
        if (((x % k) + k) % k != r) ok = false;
    }

    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

🟢 P2. 两个矩形覆盖面积

给定两个轴对齐矩形，坐标均为整数，求它们覆盖的总面积。

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

struct Rect {
    long long x1, y1, x2, y2;
};

long long area(Rect r) {
    return (r.x2 - r.x1) * (r.y2 - r.y1);
}

int main() {
    Rect a, b;
    cin >> a.x1 >> a.y1 >> a.x2 >> a.y2;
    cin >> b.x1 >> b.y1 >> b.x2 >> b.y2;

    long long ix = max(0LL, min(a.x2, b.x2) - max(a.x1, b.x1));
    long long iy = max(0LL, min(a.y2, b.y2) - max(a.y1, b.y1));
    long long overlap = ix * iy;

    cout << area(a) + area(b) - overlap << "\n";
    return 0;
}

🟡 P3. 重复函数应用

有函数 f，把 1..N 中每个数映射到 1..N。从 x 出发，反复应用 f，问 K 步后在哪里。K 最大 (10^{18})。

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

int main() {
    int n, x;
    long long k;
    cin >> n >> x >> k;

    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++) cin >> f[i];

    vector<int> order;
    vector<long long> first(n + 1, -1);

    int cur = x;
    long long step = 0;
    while (first[cur] == -1) {
        first[cur] = step++;
        order.push_back(cur);
        cur = f[cur];
    }

    long long cycleStart = first[cur];
    long long cycleLen = step - cycleStart;

    if (k < (long long)order.size()) {
        cout << order[k] << "\n";
    } else {
        long long idx = cycleStart + (k - cycleStart) % cycleLen;
        cout << order[idx] << "\n";
    }

    return 0;
}

🟡 P4. 任意交换排序

给定 1..N 的排列，每次可以交换任意两个位置。求最少交换次数排序。

🟡 P5. 相邻交换排序

给定 1..N 的排列，每次只能交换相邻两个位置。求最少交换次数排序。

🔴 P6. 2×2 翻转可达性

从全 0 的 N×M 网格出发，每次翻转一个 2×2 方块。给定目标网格，问能否达到。

🔴 P7. 灯阵

N×M 灯阵，每次按一个灯会翻转自己和四邻。N 很小，M 可以较大。问能否全部关闭或求最少次数。

🏆 P8. 构造排列

给定 N 和 K，构造一个 1..N 的排列，使它恰好有 K 个逆序对；若不可能输出 -1。

本章总结

核心要点

Ad Hoc 检查清单

当你怀疑一道题是 Ad Hoc 时：

• 我是否手算了最小样例？
• 我是否列出了极端情况？
• 每个操作改变了什么？不改变什么？
• 是否存在奇偶性或模 K 不变量？
• 是否可以从目标反向思考？
• 是否可以把问题重新表述为区间、排列、图或网格？
• 是否能先证明一个下界，再构造达到它？
• 是否有循环或周期？
• 是否可以枚举边界，让内部被迫确定？
• 我的猜想有没有被小反例推翻？

常见问题

Q1：Ad Hoc 题是不是只能靠天赋？

不是。Ad Hoc 的“灵感”通常来自大量见过的不变量、构造、分类讨论和小例子训练。你见过的模式越多，新题越容易触发联想。

Q2：我找到规律但不会证明，比赛中怎么办？

比赛中可以先提交，尤其是在 Bronze/Silver。提交后继续找反例或补证明。但平时训练必须补上证明，否则下次容易被相似但不同的题坑到。

Q3：怎么判断我的不变量够不够？

不变量通常先给必要条件。你还要问：这个条件是否充分？如果不充分，还需要补充什么条件或给出构造。

Q4：为什么我看题解觉得简单，自己却想不到？

因为题解只展示最终洞察，隐藏了试错过程。训练时不要只记答案，要记录“我应该通过什么信号想到这个观察”。

🐄 教练寄语： Ad Hoc 是 USACO 中最能区分“会背模板”和“会思考”的题型。每次做完一题，都把关键观察写成一句话。几个月后，你会发现自己并不是更有天赋了，而是拥有了更大的观察工具箱。