📖 第 7.3 章 ⏱️ 约 50 分钟 🎯 Bronze → Silver

第 7.3 章：Ad Hoc 题型

「Ad hoc」 是拉丁语，意为「为此目的」。Ad hoc 题目没有标准算法——你必须专门为这道题发明一个解法。

Ad hoc 题目是竞赛编程中最有创意、也往往最令人沮丧的类别，它们不能整齐地归入「BFS」「DP」或「贪心」，而是要求你观察到题目的某个关键性质并直接利用它。

在 USACO Bronze 中，大约 10–15% 的题目是 ad hoc。在 Silver 中出现频率较低，但往往是当场最难的一道。学会识别和解决它们是一项关键技能。

7.3.1 什么是 Ad Hoc 题目？

定义

Ad hoc 题目具有以下特点：

  • 没有标准算法（BFS、DP、贪心等）直接适用
  • 解法依赖于特定于这道题的巧妙观察或数学洞察
  • 一旦看到关键洞察，实现通常很简单

如何识别 Ad Hoc 题目

读题时，如果你问自己「这是什么算法？」而答案是「……以上都不是」，那它很可能是 ad hoc。

常见信号：

  • 题目涉及小的特定结构（如 3×3 网格、长度 ≤ 10 的序列）
  • 题目询问看似难以直接计算的性质
  • 约束条件不寻常（如 N ≤ 50，或值很小）
  • 题目有一个让它比看起来简单得多的「技巧」
  • 题目看起来是模拟，但有隐藏的捷径

Ad Hoc vs 其他类别

类别关键特征示例
模拟逐步按规则执行；不需要捷径「模拟 N 头奶牛移动 T 步」
贪心局部最优选择导致全局最优「排期工作最小化延迟」
DP重叠子问题，最优子结构「最少硬币找零」
Ad Hoc巧妙观察消除暴力「找规律；直接实现」

💡 关键区别： 模拟题在精神上也是「ad hoc」的，但一旦理解就很直接实现。真正的 ad hoc 题目需要从题目描述中并不明显的洞察。

7.3.2 Ad Hoc 思维方式

解 ad hoc 题目需要与算法题不同的心理方法。

第一步：深入理解题目

不要急着编码。花 5-10 分钟只是思考题目：

  • 题目真正问的是什么？
  • 什么让这道题难？
  • 什么会让它变简单？

第二步：试小例子

手动推演 N = 2, 3, 4 的例子，寻找规律：

  • 答案遵循某个公式吗？
  • 有对称性或不变量吗？
  • 能把题目化简为更简单的形式吗？

第三步：寻找不变量

不变量是随问题演化而不变化的性质。找到不变量通常能解锁 ad hoc 解法。

示例： 在能交换相邻元素的题目中，逆序对数量的奇偶性是不变量。若初始和目标配置奇偶性不同，答案是「不可能」。

第四步：考虑极端情况

  • 所有值相等时会怎样？
  • N = 1 时会怎样？
  • 所有值都取最大时会怎样？

极端情况往往揭示解法的结构。

第五步：思考你真正在计算什么

有时题目描述掩盖了更简单的底层计算。问：「这有公式吗？」

7.3.3 Ad Hoc 题目类别

USACO Bronze/Silver 的 ad hoc 题目分为几种重复出现的模式：

类别一：观察/找规律

关键是找到数学规律或公式。

典型结构： 给定某个序列或结构，找一个可以直接计算的性质。

示例题目： N 头奶牛围成一圈，每头朝左或朝右，若朝向与两个邻居相同则「开心」，有多少头开心？

暴力： 检查每头牛的邻居——O(N)。这已经是最优了，洞察是认识到只需数「相同-相同-相同」三元组。

类别二：有捷径的模拟

题目看起来是模拟，但朴素模拟太慢，有数学捷径。

典型结构： 「重复这个操作 T 次」，T 很大（最大 10^9）。

关键洞察： 状态空间有限，所以序列最终必定循环。找到循环长度，然后用模运算。

📄 C++ 完整代码 
// 朴素：模拟 T 步——O(T)，T = 10^9 时太慢
// 聪明：找循环长度 C，然后模拟 T % C 步——O(C)

int simulate(vector<int> state, int T) {
    map<vector<int>, int> seen;
    int step = 0;
    while (step < T) {
        if (seen.count(state)) {
            int cycle_start = seen[state];
            int cycle_len = step - cycle_start;
            int remaining = (T - step) % cycle_len;
            for (int i = 0; i < remaining; i++) {
                state = next_state(state);
            }
            return answer(state);
        }
        seen[state] = step;
        state = next_state(state);
        step++;
    }
    return answer(state);
}

类别三：构造/直接建立答案

不是搜索答案，而是构造它。

典型结构： 「找任何满足这些约束的配置」或「能否达到 X？」

关键洞察： 思考必须满足哪些约束，然后构建满足它们的解。

类别四：不变量/不可能性

通过找到目标状态违反的不变量来证明某件事不可能。

典型结构： 「能否用这些操作将状态 A 变换为状态 B？」

关键洞察： 找一个在每次操作下保持（或以可预测方式变化）的量。若 A 和 B 的这个量不同，变换不可能。

经典示例： 15 拼图（滑动方块），可解性取决于排列的奇偶性加上空格位置。

类别五：贪心观察

题目看起来需要 DP，但一个简单的贪心观察让它变得平凡。

典型结构： 贪心选择不显然的优化问题。

示例： 有 N 件物品，价值 v[i]，最多取 K 件，最大化总价值。

显然的贪心： 按价值降序排，取前 K 件。（一旦看到就很平凡，但题目可能伪装得很好。）

类别六：几何/网格观察

网格或有几何约束的题目往往有优雅的观察。

典型结构： 统计网格上的某物，或确定配置是否可达。

关键洞察： 通常涉及奇偶性（棋盘染色）、对称性或巧妙的坐标变换。

7.3.4 工作示例

示例一：围栏涂色

题目： FJ 有长度为 N 的围栏，先将 a 到 b 涂成红色，再将 c 到 d 涂成蓝色（蓝色覆盖红色）。多少根栏杆是红色？蓝色？

Ad hoc 洞察： 涂色区域是两个区间的并集，用容斥原理：

  • 涂色 = |[a,b]| + |[c,d]| - |[a,b] ∩ [c,d]|
📄 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 inter_start = max(a, c);
    int inter_end = min(b, d);
    int overlap = max(0, inter_end - inter_start);

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

示例二：循环检测

题目： 从 X 开始，反复用各位数字之和替换 X，直到 X < 10。需要多少步？（X 最大 10^18）

朴素做法： 逐步模拟。但若需要数百万步怎么办？

Ad hoc 洞察： 10^18 的各位数字之和最多是 9×18 = 162。一步后值 ≤ 162。两步后 ≤ 9+9 = 18。三步后是个位数。所以任意起始值最多 3 步！

📄 C++ 完整代码 
#include <bits/stdc++.h>
using namespace std;

long long digit_sum(long long x) {
    long long s = 0;
    while (x > 0) { s += x % 10; x /= 10; }
    return s;
}

int main() {
    long long x;
    cin >> x;
    int steps = 0;
    while (x >= 10) {
        x = digit_sum(x);
        steps++;
    }
    cout << steps << "\n";
    return 0;
}

示例三：网格染色不变量

题目： N×M 网格，可以翻转任意 2×2 方块（切换全部 4 个格子的 0/1）。从全零开始，能否达到目标配置？

Ad hoc 洞察： 考虑「棋盘奇偶性」。把网格染成棋盘格（黑/白）。每次 2×2 翻转恰好切换 2 个黑格和 2 个白格。因此，为 1 的黑格数量和为 1 的白格数量始终有相同的奇偶性（两者从 0 开始，每次翻转都变化 ±2 或 0）。

若目标有奇数个为 1 的黑格或奇数个为 1 的白格，则不可能。

📄 若目标有奇数个为 1 的黑格或奇数个为 1 的白格，则**不可能**。 
#include <bits/stdc++.h>
using namespace std;

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

    int black_ones = 0, white_ones = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                if ((i + j) % 2 == 0) black_ones++;
                else white_ones++;
            }
        }
    }

    if (black_ones % 2 == 0 && white_ones % 2 == 0) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
    return 0;
}

7.3.5 常用 Ad Hoc 技术

技术一：奇偶论证

很多不可能性来自奇偶性。若一个操作总是将某个量改变偶数，则该量的奇偶性是不变量。

使用场景：「能否将 A 变换为 B？」类题目。

应用方法：

  1. 确定每个操作对某个量 Q 做了什么
  2. 若每个操作将 Q 改变偶数，则 Q mod 2 是不变量
  3. 若 A 和 B 的 Q mod 2 不同，答案是「不可能」

技术二：鸽巢原理

N+1 件物品在 N 个类别中，至少有一个类别有 ≥ 2 件物品。

使用场景：「证明某物必然存在」或「找一个必然的碰撞」。

技术三：坐标压缩

当值很大但不同值的数量少时，将值映射到下标 0, 1, 2, ...

vector<int> vals = {1000000, 3, 999, 42, 1000000};
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
// vals 现在是 {3, 42, 999, 1000000}

auto compress = [&](int x) {
    return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
};

技术四：对称化简

若题目有对称性，只需要考虑每个等价类的一个代表元。

技术五：逆向思考

有时从目标状态反向到初始状态更容易。

技术六：重新表述题目

用不同形式重新陈述题目，揭示结构。

7.3.6 USACO Bronze Ad Hoc 示例

以下是来自实际 USACO Bronze 题目的模式（已改写）：

模式：最少操作排序

题型： 给定一个序列，求排序所需的最少交换/移动次数。

关键洞察： 答案通常是 N 减去最长已排序子序列的长度，或与排列中的循环数有关。

循环分解方法：

📄 C++ 完整代码 
// 用最少交换次数排序排列：
// 答案 = N - (排列中的循环数)
vector<int> perm = {3, 1, 4, 2};  // 1-indexed 值
int n = perm.size();
vector<bool> visited(n, false);
int cycles = 0;
for (int i = 0; i < n; i++) {
    if (!visited[i]) {
        cycles++;
        int j = i;
        while (!visited[j]) {
            visited[j] = true;
            j = perm[j] - 1;  // 跟随排列（0-indexed）
        }
    }
}
cout << n - cycles << "\n";  // 最少交换次数

模式：有约束的可达性

题型： 用给定的移动规则能否从 A 到达 B？

关键洞察： 通常化简为奇偶性或模运算条件。

示例： 在数轴上可以移动 +3 或 -5，能否从 0 到达位置 T？

洞察： 能到达 gcd(3, 5) = 1 的任意倍数，所以能到达任意整数。但若移动是 +4 和 +6，只能到达 gcd(4, 6) = 2 的倍数。

📄 C++ 完整代码 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, target;
    cin >> a >> b >> target;
    if (target % __gcd(a, b) == 0) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
    return 0;
}

7.3.7 练习题

🟢 简单

P1. 围栏涂色 (USACO 2012 November Bronze) FJ 先把 a 到 b 的栏杆涂成红色，再把 c 到 d 涂成蓝色（蓝色覆盖红色），多少根是红色？蓝色？

💡 提示

用大小为 100 的数组（栏杆编号 1–100），先标记红色，再标记蓝色（覆盖），统计各颜色。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c, d; cin >> a >> b >> c >> d;
    vector<char> post(101, '.');
    for (int i = a; i <= b; i++) post[i] = 'R';
    for (int i = c; i <= d; i++) post[i] = 'B';
    int R = 0, B = 0;
    for (int i = 1; i <= 100; i++) {
        if (post[i] == 'R') R++;
        else if (post[i] == 'B') B++;
    }
    cout << R << " " << B << "\n";
}

复杂度： O(100)——直接模拟。

P2. 各位数字之和步骤 从整数 X（1 ≤ X ≤ 10^9）开始，反复将 X 替换为各位数字之和，直到 X < 10，需要多少步？

💡 提示

直接模拟！值下降如此之快（9 位数的各位数字之和最多 81），最多 3 步就能到达个位数。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long x; cin >> x;
    int steps = 0;
    while (x >= 10) {
        long long s = 0;
        while (x > 0) { s += x % 10; x /= 10; }
        x = s;
        steps++;
    }
    cout << steps << "\n";
}

为什么这么快？ 9 位数的各位数字之和 ≤ 9×9 = 81（2 位数），第二步 ≤ 8+1 = 9（1 位数），最多 3 步。

P3. 奶牛棋盘格 (ad hoc 网格) N×N 网格（N ≤ 100）像棋盘一样染色，可以交换任意两个相邻格子（水平或垂直），能否将初始配置变换为目标配置？

💡 提示

统计两个配置中为「1」的黑格数和为「1」的白格数。每次交换使两个计数各变化相同的量（各±1），所以差值（black_ones - white_ones）是不变量。若初始和目标差值不同，不可能。

🟡 中等

P4. 排列排序 给定 1..N 的一个排列，找将其排序所需的最少相邻交换次数。

💡 提示

最少相邻交换次数等于排列中的逆序对数（满足 i < j 但 perm[i] > perm[j] 的对数），用归并排序或树状数组在 O(N log N) 内统计。

✅ 完整题解（归并排序） 
#include <bits/stdc++.h>
using namespace std;
long long mergeCount(vector<int>& a, int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    long long inv = mergeCount(a, l, mid) + mergeCount(a, mid+1, r);
    vector<int> tmp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else { tmp.push_back(a[j++]); inv += mid - i + 1; }
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= r) tmp.push_back(a[j++]);
    for (int k = 0; k < (int)tmp.size(); k++) a[l+k] = tmp[k];
    return inv;
}
int main() {
    int n; cin >> n;
    vector<int> a(n); for (int& x : a) cin >> x;
    cout << mergeCount(a, 0, n-1) << "\n";
}

为什么逆序对 = 最少交换次数？ 每次相邻交换恰好消除一个逆序对。复杂度： O(N log N)。

P5. 循环模拟 (USACO 风格) 函数 f 将 {1, ..., N} 映射到自身，从位置 1 开始反复应用 f，恰好 K 步后（K 最大 10^18）在哪里？

💡 提示

从 1 开始的序列最终必定循环（状态空间有限），用弗洛伊德算法或 visited 数组找循环起点和长度，然后用模运算找 K 步后的位置。

P6. 矩形并集面积 给定 M 个轴对齐矩形（M ≤ 100，坐标 ≤ 1000），求总覆盖面积（重叠区域只计一次）。

💡 提示

坐标 ≤ 1000，用 1000×1000 布尔网格，标记至少被一个矩形覆盖的每个格子，统计标记格子数。

🔴 困难

P7. 环面上的可达性 (不变量题) N×M 网格（带环绕——环面），从 (0,0) 出发，每步移动 (+a, 0) 或 (0, +b)（模 N 和模 M）。能否到达每个格子？

💡 提示

当且仅当 gcd(a, N) = 1 且 gcd(b, M) = 1 时，能到达每个格子。

P8. 最少交换次数分组 (USACO 2016 February Bronze) N 头奶牛站成一圈，每头是 A 型或 B 型，想让所有 A 型奶牛相邻，最少需要多少次相邻交换？

💡 提示

设 K = A 型奶牛数，对圆形排列中大小为 K 的所有窗口，统计每个窗口内的 B 型奶牛数（这些需要被换出），答案是所有窗口的最小值。用滑动窗口 O(N) 解决。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    string s; cin >> s;
    int K = count(s.begin(), s.end(), 'A');
    if (K == 0 || K == n) { cout << 0 << "\n"; return 0; }
    string d = s + s;
    int curB = 0;
    for (int i = 0; i < K; i++) if (d[i] == 'B') curB++;
    int best = curB;
    for (int i = K; i < (int)d.size(); i++) {
        if (d[i] == 'B') curB++;
        if (d[i-K] == 'B') curB--;
        best = min(best, curB);
    }
    cout << best << "\n";
}

复杂度： O(N)。

🏆 挑战

P9. 关灯 (经典 ad hoc) 5×5 的灯光网格，每个格子开或关。按下一个灯会切换它和所有正交邻居的状态，从初始配置开始，找让所有灯熄灭的最少按键次数，或报告不可能。

💡 提示

关键洞察：按一个灯两次等于没按，所以每个灯按 0 或 1 次，有 2^25 ≈ 3300 万种可能——直接暴力太多。

更好的洞察：一旦决定第一行的按键（2^5 = 32 种），其余行是被迫的（后续每行的按键由上一行是否全灭决定）。尝试所有 32 种第一行配置，检查最后一行是否全灭。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int grid[5][5];

int solve(int firstRow) {
    int g[5][5]; memcpy(g, grid, sizeof(grid));
    int presses = 0;
    auto toggle = [&](int i, int j) {
        if (i>=0 && i<5 && j>=0 && j<5) g[i][j] ^= 1;
    };
    auto press = [&](int i, int j) {
        presses++;
        toggle(i,j); toggle(i-1,j); toggle(i+1,j); toggle(i,j-1); toggle(i,j+1);
    };

    for (int j = 0; j < 5; j++)
        if (firstRow & (1 << j)) press(0, j);

    for (int i = 1; i < 5; i++)
        for (int j = 0; j < 5; j++)
            if (g[i-1][j] == 1) press(i, j);

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

int main() {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) cin >> grid[i][j];
    int best = INT_MAX;
    for (int mask = 0; mask < 32; mask++)
        best = min(best, solve(mask));
    if (best == INT_MAX) cout << "impossible\n";
    else cout << best << "\n";
}

为什么有效： 一旦选定第一行的按键，后续每行的按键被迫：当且仅当上一行某格仍亮时才按下面的格。检查最后一行的可行性。复杂度： 32 × O(25) ≈ O(800)。

7.3.8 USACO Silver 中的 Ad Hoc

Silver 级别的 ad hoc 题目更少但更难，通常将观察与标准算法结合。

Silver Ad Hoc 模式

模式描述示例
观察 + BFS关键洞察缩小状态空间，然后 BFS「奶牛只能移动到同色格子」→ 在化简后的图上 BFS
观察 + DP洞察揭示 DP 结构「最优解总有这个性质」→ 带该性质的 DP
观察 + 二分洞察让检查函数变简单「答案是单调的」→ 二分答案
纯粹观察不需要标准算法「答案总是 ⌈N/2⌉」

如何处理 Silver Ad Hoc

  1. 无法识别算法类型时不要慌
  2. 试小例子 — N=2, 3, 4 — 寻找规律
  3. 问：这道题特别在哪里？ — 是什么性质让它与一般版本不同？
  4. 考虑：如果能解决更简单的版本怎么办？ — 然后推广
  5. 相信你的观察 — 若在小例子中发现了规律，大概率是正确的

本章总结

📌 核心要点

概念要点
定义Ad hoc = 无标准算法；需要特定于题目的洞察
识别无法识别算法类型 → 可能是 ad hoc
方法小例子 → 找规律 → 证明 → 实现
不变量找操作保持的量 → 证明不可能性
模拟捷径T 很大 → 找循环 → 用模运算
奇偶性很多不可能性来自奇偶论证
构造直接建立答案而非搜索

🧩 Ad Hoc 解题检查清单

当你怀疑一道题是 ad hoc 时：

  • 试 N = 1, 2, 3, 4 — 手动计算答案
  • 寻找公式 — 答案遵循简单规律吗？
  • 检查奇偶性 — 有排除某些配置的不变量吗？
  • 寻找循环 — 若在模拟，状态会重复吗？
  • 考虑极端情况 — 所有值相等怎么样？全部最大？
  • 重新表述 — 能把题目改写成更简单的形式吗？
  • 逆向思考 — 逆问题更简单吗？
  • 相信小例子的规律 — 若 N=2,3,4,5 都成立，一般情况大概率也成立

❓ 常见问题

Q1：怎么判断一道题是 ad hoc 还是我还没学到的标准算法？

A：这确实很难判断。一个好的经验法则：若题目约束小（N ≤ 100）且没有明显涉及图、DP 或排序，很可能是 ad hoc。若 N ≤ 10^5 且无法识别算法，可能是你遗漏了某个标准技术——解完后检查题目标签。

Q2：我在小例子中找到了规律但无法证明，应该提交吗？

A：竞赛中，应该——提交后继续。实际练习中，尝试理解为什么规律成立。未经证明的规律有时在边界情况下失败。但基于规律的解法获得部分分好过什么都没有。

Q3：Ad hoc 题感觉不可能解，如何提高？

A：只有练习才能提高。解 20-30 道 ad hoc 题，每道之后写下：「关键洞察是什么？我怎么能更快找到它？」随着时间推移，你会积累一个技术库（奇偶性、循环、不变量等），在新题中能识别出来。

Q4：有没有系统的方法找不变量？

A：有。对题目中的每个操作，问：「这个操作对某个量 Q 做了什么？变化了多少？」若一个操作总是将 Q 改变 K 的倍数，则 Q mod K 是不变量。常见不变量：奇偶性（mod 2）、总和 mod K、逆序对数 mod 2。

🔗 与其他章节的联系

  • 第 7.1 章（了解 USACO）：Ad hoc 是 10 个 Bronze 题目类别之一；本章给了它应得的深度
  • 第 7.2 章（解题策略）：算法决策树以「贪心/模拟」结尾——ad hoc 题完全在树之外
  • 第 3.4 章（双指针）：滑动窗口技术出现在几道 ad hoc 题中（如上面的 P8）
  • 第 3.2 章（前缀和）：很多 ad hoc 计数题以前缀和为子步骤
  • 附录 E（数学基础）：GCD、模运算和数论是很多 ad hoc 洞察的基础

🐄 最后的想法： Ad hoc 题是竞赛编程成为一门艺术的地方。没有公式——只有细心的观察、创造性的思考，以及找到看似不可能的题目的优雅解法时的满足感。拥抱这种挣扎。