算法竞赛中的制胜秘笈

YZY Lv3
  2025-06-17 00:41:26 2025-06-17 00:41:26 Created   2025-06-17 00:43:46 2025-06-17 00:43:46 Updated      

算法竞赛中的制胜秘笈：从基础优化到思维突破

本文并非旨在提供“银弹”或“捷径”，而是希望通过分享一些实战中总结出的高效实现方法、常用优化策略、特定问题模式的应对思路以及比赛中的元技能，帮助大家在坚实的基础上更进一步。我们将从编码细节的优化，到算法层面的巧思，再到比赛策略的运用，逐步深入。

准备好了吗？让我们开始这场技巧之旅。

一、编码细节：毫厘之优，积少成多

在分秒必争的赛场上，编码效率和代码的稳定性至关重要。一些看似微小的细节，往往能累积成显著的时间优势或避免不必要的罚时。

1.1 输入输出优化（IO Optimization）

这是最基础也是最常用的技巧。对于 C++ 选手，标准 cin/cout 流在处理大量数据时可能会因为与 C 风格 stdio 的同步、以及自身的缓冲机制而变得缓慢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h> // 包含了几乎所有常用头文件

using namespace std; // 使用标准命名空间

int main() {
    // 关闭 C++ 流与 C 标准 IO 的同步
    ios::sync_with_stdio(0);
    // 解除 cin 与 cout 的绑定，进一步加速
    cin.tie(0);
    cout.tie(0);

    // ... 你的主逻辑代码 ...
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    // ... 处理 ...
    for (int i = 0; i < n; ++i) {
        cout << a[i] << (i == n - 1 ? "" : " "); // 输出时注意末尾空格
    }
    cout << "\n"; // 推荐使用 '\n' 而非 endl，后者会强制刷新缓冲区

    return 0;
}
// 时间复杂度: 取决于主逻辑，IO部分优化后接近理论下限
// 空间复杂度: 取决于主逻辑

解释:

  • ios::sync_with_stdio(0); 关闭了 C++ 标准流与 C 标准 IO（printf, scanf 等）的同步。默认情况下，它们是同步的，以保证混合使用时的顺序正确性，但这带来了性能开销。关闭后，通常 cin/cout 会更快。注意： 关闭同步后，不要混用 C++ 流 IO 和 C 风格 IO，否则可能导致输出顺序混乱。
  • cin.tie(0); 或 cin.tie(nullptr); 解除了 cin 和 cout 的绑定。默认情况下，每次 cin 操作前会先刷新 cout 缓冲区，以确保屏幕输出与输入提示的顺序。解除绑定后，cout 不再自动刷新，可以进一步提速。通常与 ios::sync_with_stdio(0) 一起使用。
  • 使用 \n 代替 endl。endl 除了输出换行符外，还会强制刷新输出缓冲区。在大量输出时，频繁的刷新会带来性能损失。\n 只输出换行符，缓冲区会在合适的时机（如缓冲区满、程序结束、或遇到 cin 操作（如果未解绑））自动刷新。

1.2 数据类型选择与精度控制

  • long long 的滥用与必要: 很多时候，题目数据范围看似在 int 范围内，但中间计算过程可能溢出。养成检查中间结果是否可能超过 的习惯。如果可能，坚决使用 long long。
    • 例如，计算两个 int 的乘积，即使结果保证在 int 内，也可能在乘法时溢出。标准做法是 long long res = 1LL * a * b;，其中 1LL 强制将 a 提升为 long long。
  • 浮点数精度: 避免直接用 == 比较浮点数。设置一个极小的正数 eps (epsilon)，如 1e-8 或 1e-9。比较 a 和 b 是否相等时，应判断 fabs(a - b) < eps。
    • 需要高精度时，考虑 double 或 long double。有时甚至需要手写大数类或使用 Java 的 BigDecimal（但在 C++ 竞赛中较少）。
    • 涉及三角函数、开方等操作时，注意库函数的精度限制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-9; // 定义精度常量

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int x = 1e9, y = 1e9;
    // 错误: x * y 会溢出 int
    // int prod_wrong = x * y;
    // 正确: 使用 long long 存储结果，并确保计算过程中至少一个操作数是 long long
    long long prod_ok = 1LL * x * y;
    cout << "Product: " << prod_ok << "\n";

    double a = 0.1 + 0.2;
    double b = 0.3;
    // 错误: 直接比较可能因精度问题失败
    // if (a == b) { ... }
    // 正确: 使用 eps 比较
    if (fabs(a - b) < eps) {
        cout << "a is approximately equal to b\n";
    } else {
        cout << "a is not equal to b\n";
        cout << fixed << setprecision(18) << "a = " << a << ", b = " << b << "\n"; // 查看实际值
    }

    return 0;
}
// 时间复杂度: O(1)
// 空间复杂度: O(1)

1.3 STL 的高效运用

标准模板库 (STL) 是 C++ 竞赛的利器，但用好它也有讲究。

  • vector vs list vs deque: vector 是最常用的动态数组，随机访问 O(1)，尾部插入/删除均摊 O(1)，中间插入/删除 O(N)。list 是双向链表，任意位置插入/删除 O(1)，但随机访问 O(N)。deque 是双端队列，支持头尾高效插入/删除 (均摊 O(1)) 和随机访问 (O(1) 但常数比 vector 大)。根据操作需求选择。竞赛中 vector 最常用。
  • set vs map vs unordered_set/map:
    • set/map: 基于红黑树，元素有序，操作复杂度 O(log N)。适用于需要有序性或查找邻近元素的场景。
    • unordered_set/map: 基于哈希表，元素无序，平均操作复杂度 O(1)，最坏 O(N) (哈希碰撞)。适用于对顺序无要求，且追求更高平均性能的场景。注意: 哈希冲突可能导致性能急剧下降，有时会被特殊数据卡掉。自定义结构体放入 unordered_ 容器需要提供哈希函数和等于运算符。
  • lower_bound / upper_bound: 在 已排序 的容器（如 vector, set, map 的键）或数组上进行二分查找，复杂度 O(log N)。lower_bound(x) 返回第一个 不小于 x 的元素的迭代器/指针。upper_bound(x) 返回第一个 大于 x 的元素的迭代器/指针。常用于查找、计数、判断存在性等。
  • pair 和 tuple: 方便地组合多个值，常用于存储坐标、状态，或作为 map/set 的元素。
  • 算法库 (<algorithm>): 熟练使用 sort, reverse, unique, next_permutation, min_element, max_element, accumulate 等函数，能大大简化代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    sort(v.begin(), v.end()); // O(N log N) 排序
    // v: {1, 1, 2, 3, 4, 5, 6, 9}

    // 查找第一个不小于 3 的元素
    auto it_l = lower_bound(v.begin(), v.end(), 3); // O(log N)
    if (it_l != v.end()) {
        cout << "Lower bound of 3: " << *it_l << " at index " << (it_l - v.begin()) << "\n";
    }

    // 查找第一个大于 3 的元素
    auto it_u = upper_bound(v.begin(), v.end(), 3); // O(log N)
    if (it_u != v.end()) {
        cout << "Upper bound of 3: " << *it_u << " at index " << (it_u - v.begin()) << "\n";
    }

    // 计算 [lower_bound, upper_bound) 之间的元素个数，即等于 3 的元素个数
    cout << "Count of 3: " << (it_u - it_l) << "\n";

    // 使用 map 统计频率
    map<int, int> freq; // O(log N) per insertion/access
    for (int x : v) {
        freq[x]++;
    }
    cout << "Frequency of 1: " << freq[1] << "\n";

    // 使用 unordered_map 统计频率 (平均 O(1))
    unordered_map<int, int> ufreq; // Average O(1) per insertion/access
    for (int x : v) {
        ufreq[x]++;
    }
    cout << "Frequency of 1 (unordered): " << ufreq[1] << "\n";

    return 0;
}
// 时间复杂度: 主要由 sort 和容器操作决定
// 空间复杂度: O(N) for vector and maps

1.4 位运算 (Bit Manipulation)

位运算是竞赛中的常客，常用于状态压缩、集合表示、优化计算等。

  • 基本操作:

    • x & (1 << k): 检查 x 的第 k 位是否为 1 (0-indexed)。
    • x | (1 << k): 将 x 的第 k 位设为 1。
    • x & (~(1 << k)): 将 x 的第 k 位设为 0。
    • x ^ (1 << k): 翻转 x 的第 k 位。
    • x & (x - 1): 将 x 最右边的 1 变为 0。
    • x & (-x) 或 x & (~x + 1): 得到 x 最右边的 1 所代表的值 (lowbit)。常用于树状数组。
    • __builtin_popcount(x) (GCC/Clang): 计算 x 中 1 的个数。
    • __builtin_clz(x): 计算前导零个数。
    • __builtin_ctz(x): 计算末尾零个数。

  • 应用:

    • 状态压缩 DP: 用一个整数表示一个集合或状态（如棋盘上棋子的摆放）。
    • 子集枚举: for (int sub = s; sub; sub = (sub - 1) & s) 可以枚举 s 的所有非空子集。
    • 快速幂/矩阵快速幂中的二进制分解。
    • 图论中的集合操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int x = 21; // 二进制: 10101
    int k = 2;  // 第 2 位 (0-indexed)

    // 检查第 k 位
    if (x & (1 << k)) {
        cout << "Bit " << k << " of " << x << " is 1\n"; // 输出
    } else {
        cout << "Bit " << k << " of " << x << " is 0\n";
    }

    // 将第 1 位设为 1 (变成 10111, 即 23)
    int y = x | (1 << 1);
    cout << "Set bit 1: " << y << "\n";

    // 将第 0 位设为 0 (变成 10100, 即 20)
    int z = x & (~(1 << 0));
    cout << "Clear bit 0: " << z << "\n";

    // lowbit (最右边的 1 的值)
    int lb = x & (-x); // 10101 & (complement(10101) + 1) = 10101 & 01011 = 00001 = 1
    cout << "Lowbit of " << x << ": " << lb << "\n";

    // 计算 1 的个数
    cout << "Popcount of " << x << ": " << __builtin_popcount(x) << "\n"; // 输出 3

    // 枚举集合 s = 11 (二进制 1011) 的子集
    int s = 11;
    cout << "Subsets of " << s << " (binary " << bitset<4>(s) << "):\n";
    for (int sub = s; sub; sub = (sub - 1) & s) {
        cout << bitset<4>(sub) << " (" << sub << ")\n";
    }
    // 输出: 1011 (11), 1010 (10), 1001 (9), 1000 (8), 0011 (3), 0010 (2), 0001 (1)

    return 0;
}
// 时间复杂度: O(1) for bit operations, O(3^k) for subset enumeration where k is number of set bits in s (roughly)
// 空间复杂度: O(1)

1.5 预处理与打表

对于一些计算量大但输入范围有限，或具有重复子问题性质的问题，预处理（在主逻辑开始前计算并存储结果）或打表（预先计算好所有可能输入的结果，直接查询）是常用技巧。

  • 前缀和/后缀和/差分数组: O(N) 预处理，O(1) 查询区间和/进行区间修改。二维前缀和/差分也类似。
  • 预计算阶乘、逆元、组合数: 在模运算下，如果模数是质数且不大，可以 O(N) 预处理阶乘和阶乘逆元，然后 O(1) 计算组合数 。
  • 筛法求素数: 如埃氏筛 (Eratosthenes) O(N log log N) 或线性筛 O(N) 预处理一定范围内的素数。
  • 离线算法: 如莫队算法，将查询离线处理，通过巧妙的区间移动顺序优化总复杂度。
  • 打表: 对于输入范围极小（如 N <= 15 或 20）的某些难题，或者需要找规律的题目，可以本地写程序打出小数据的解，观察规律，或者直接将表嵌入代码中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
long long fact[MAXN]; // 阶乘
long long invFact[MAXN]; // 阶乘逆元
long long P = 1e9 + 7; // 模数

// 快速幂求 a^b mod p
long long power(long long base, long long exp) {
    long long res = 1;
    base %= P;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % P;
        base = (base * base) % P;
        exp /= 2;
    }
    return res;
}

// 求 a 在模 P 下的逆元 (要求 P 是质数)
long long modInverse(long long n) {
    return power(n, P - 2); // 费马小定理
}

// 预处理阶乘和阶乘逆元
void precompute(int n) {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % P;
        invFact[i] = modInverse(fact[i]); // 也可以递推求逆元: invFact[i] = invFact[i+1] * (i+1) % P 从后往前
    }
    // 更好的递推求逆元方法 (O(N))
    // invFact[n] = modInverse(fact[n]);
    // for (int i = n - 1; i >= 0; i--) {
    //     invFact[i] = (invFact[i + 1] * (i + 1)) % P;
    // }
}

// 计算组合数 C(n, k) mod P
long long nCr(int n, int k) {
    if (k < 0 || k > n) return 0;
    return (((fact[n] * invFact[k]) % P) * invFact[n - k]) % P;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int max_n = 100000;
    precompute(max_n); // O(N log P) 或 O(N) 取决于逆元求法

    int n = 10, k = 3;
    cout << "C(" << n << ", " << k << ") mod " << P << " = " << nCr(n, k) << "\n"; // O(1) 查询

    return 0;
}
// 时间复杂度: 预处理 O(N) (使用递推逆元) 或 O(N log P) (使用快速幂求逆元), 查询 O(1)
// 空间复杂度: O(N) for storing factorials and inverse factorials

二、算法思维：巧破难局，洞见本质

除了具体算法，一些通用的解题思维模式和技巧同样重要。

2.1 双指针 (Two Pointers / Sliding Window)

适用于处理序列或数组上的区间问题，特别是当区间的某个性质随端点单调移动而呈现单调性时。通过维护两个指针（通常是 l 和 r），并根据条件移动它们来扫描序列，可以将 O(N^2) 的暴力枚举优化到 O(N)。

  • 典型应用:

    • 查找和为定值的两个数（需先排序）。
    • 查找满足特定条件的最长/最短子数组（滑动窗口）。
    • 合并两个有序数组。
    • 字符串匹配中的某些问题。

  • 核心思想: 维护一个“窗口” [l, r] 或两个指针 l, r。当窗口不满足条件时，移动一个指针（通常是 r 向右扩展）；当窗口满足条件时，尝试优化结果，并移动另一个指针（通常是 l 向右收缩）。保证每个元素最多被 l 和 r 指针各访问一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

// 例子：找到数组中和 >= target 的最短子数组长度
int shortestSubarraySum(const vector<int>& a, int target) {
    int n = a.size();
    if (n == 0) return 0;

    long long cur_sum = 0;
    int min_len = n + 1; // 初始化为不可能的最大长度+1
    int l = 0;

    for (int r = 0; r < n; ++r) {
        cur_sum += a[r]; // 扩展右端点

        // 当窗口和满足条件时，尝试收缩左端点
        while (cur_sum >= target) {
            min_len = min(min_len, r - l + 1); // 更新最短长度
            cur_sum -= a[l]; // 收缩左端点
            l++;
        }
    }

    return (min_len == n + 1) ? 0 : min_len; // 如果没找到，返回 0 或其他约定值
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> arr = {2, 3, 1, 2, 4, 3};
    int k = 7;
    int len = shortestSubarraySum(arr, k);
    cout << "Shortest subarray length with sum >= " << k << ": " << len << "\n"; // Output: 2 (for [4, 3])
    return 0;
}
// 时间复杂度: O(N), 因为 l 和 r 指针都最多移动 N 次
// 空间复杂度: O(1) (不计输入数组空间)

2.2 折半查找/折半搜索 (Meet-in-the-Middle)

当问题的规模太大以至于无法直接进行指数级搜索（如 ），但可以将其分解为两个规模大致相等的子问题时，可以考虑使用 Meet-in-the-Middle。

  • 核心思想: 将原问题（大小为 N）分解为两个子问题（大小约为 N/2）。分别对两个子问题进行搜索，得到所有可能的部分解。然后将两个子问题的解集合并起来，寻找满足最终条件的组合。
  • 复杂度: 如果原问题复杂度为 ，分解后两个子问题复杂度为 ，合并过程如果能做到较优（如排序后双指针或哈希查找），总复杂度可能降至 '_' allowed only in math modeO(k^{N/2} \times \text{merge_cost})。
  • 典型应用: 子集和问题（找一个子集和为 target），4-Sum 问题，某些路径计数问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

using namespace std;

// 例子: 求解子集和问题 (Subset Sum)
// 给定一个集合 a 和目标值 T, 是否存在一个子集和为 T?
// 这里用 Meet-in-the-Middle 查找所有和为 T 的子集个数

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n = 40; // 假设 n 较大, 比如 40, 2^40 太大
    long long target = 1e10;
    vector<long long> a(n);
    // ... 读入数组 a ... (假设已读入)
    // for(int i=0; i<n; ++i) cin >> a[i];

    // 实际应用中，需要填充 a 的值
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for(int i=0; i<n; ++i) a[i] = uniform_int_distribution<long long>(1, 1e9)(rng);


    int n1 = n / 2;
    int n2 = n - n1;
    vector<long long> sum1, sum2;

    // 1. 计算前半部分的子集和
    for (int i = 0; i < (1 << n1); ++i) {
        long long current_sum = 0;
        for (int j = 0; j < n1; ++j) {
            if ((i >> j) & 1) {
                current_sum += a[j];
            }
        }
        sum1.push_back(current_sum);
    }
    // 复杂度 O(2^(N/2))

    // 2. 计算后半部分的子集和
    for (int i = 0; i < (1 << n2); ++i) {
        long long current_sum = 0;
        for (int j = 0; j < n2; ++j) {
            if ((i >> j) & 1) {
                current_sum += a[n1 + j];
            }
        }
        sum2.push_back(current_sum);
    }
    // 复杂度 O(2^(N/2))

    // 3. 合并结果
    sort(sum2.begin(), sum2.end()); // 排序 sum2, O(2^(N/2) * log(2^(N/2))) = O(N * 2^(N/2))

    long long count = 0;
    for (long long s1 : sum1) {
        long long needed = target - s1;
        // 在 sum2 中查找等于 needed 的元素个数
        auto range = equal_range(sum2.begin(), sum2.end(), needed); // O(log(2^(N/2))) = O(N)
        count += (range.second - range.first); // 累加找到的个数
    }
    // 合并复杂度 O(2^(N/2) * N)

    cout << "Number of subsets summing to " << target << ": " << count << "\n";

    return 0;
}
// 时间复杂度: 大约 O(N * 2^(N/2))
// 空间复杂度: O(2^(N/2))

2.3 随机化 (Randomization)

在某些确定性算法复杂度过高或难以设计的场景下，随机化算法可以提供一个概率上正确或近似最优的解。

  • 应用场景:

    • 数值积分: 蒙特卡洛方法。
    • 快速排序: 随机选择 pivot 可以使得期望复杂度为 O(N log N)。
    • 哈希: 随机选择哈希函数参数可以降低碰撞概率。
    • 最小圆覆盖、凸包等几何问题: 某些随机增量算法有很好的期望复杂度。
    • 爬山、模拟退火: 用于求解优化问题，概率性地跳出局部最优。
    • 交互题: 猜测或探测。

  • 注意事项:

    • 随机化并不保证总是得到正确答案或最优解，通常是高概率正确或期望性能好。
    • 需要好的随机数生成器 (mt19937 比 rand() 更好)。
    • 对于判定性问题，可能需要多次随机尝试来提高正确率。
    • 竞赛中，如果时间允许且确定性算法困难，可以尝试，但要评估风险。

2.4 哈希 (Hashing)

将复杂或大的数据结构（如字符串、子树、集合）映射到一个简单的整数值（哈希值），使得比较操作可以在 O(1) 或接近 O(1) 的时间内完成。

  • 字符串哈希 (Polynomial Rolling Hash): 最常用的哈希技巧。选择一个基数 B 和一个模数 P (通常是大质数)。字符串 S = s_1s_2...s_n 的哈希值定义为：

    可以通过预处理 B 的幂次和字符串前缀哈希值，在 O(1) 时间内计算任意子串的哈希值。

    注意处理负数取模。

  • 冲突处理: 哈希冲突是可能的（不同的输入得到相同的哈希值）。解决方法：

    • 选择好的参数: B 和 P 尽量随机，P 足够大。B 通常选一个大于字符集大小的质数（如 131, 13331）。P 选大质数（如 ）。
    • 双哈希: 使用两个不同的模数 P1, P2 计算两个哈希值，只有当两个哈希值都相同时才认为原数据相同。冲突概率大大降低。
    • 结构哈希: 对树、图等结构进行哈希，通常基于子结构的哈希值递归计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull; // 使用 unsigned long long 自然溢出代替取模，更快但碰撞概率稍高

const int MAXL = 1000005;
const ull B = 131; // Base for hashing

ull pB[MAXL]; // pB[i] = B^i
ull h[MAXL];  // h[i] = hash of prefix s[1..i]

// 预计算 B 的幂次
void precompute_powers(int max_len) {
    pB[0] = 1;
    for (int i = 1; i <= max_len; ++i) {
        pB[i] = pB[i - 1] * B;
    }
}

// 计算字符串 s 的前缀哈希值
void compute_hash(const string& s) {
    int n = s.length();
    h[0] = 0;
    for (int i = 0; i < n; ++i) {
        h[i + 1] = h[i] * B + (s[i] - 'a' + 1); // 假设小写字母, 映射到 1-26
    }
}

// 获取子串 s[l..r] (1-based index) 的哈希值
ull get_hash(int l, int r) {
    return h[r] - h[l - 1] * pB[r - l + 1];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    string s = "ababa";
    int n = s.length();
    precompute_powers(n);
    compute_hash(s);

    // 比较 s[1..3] ("aba") 和 s[3..5] ("aba")
    ull hash1 = get_hash(1, 3);
    ull hash2 = get_hash(3, 5);

    if (hash1 == hash2) {
        cout << "Substring s[1..3] and s[3..5] are likely the same.\n";
    } else {
        cout << "Substrings are different.\n";
    }

    // 比较 s[1..2] ("ab") 和 s[2..3] ("ba")
    ull hash3 = get_hash(1, 2);
    ull hash4 = get_hash(2, 3);

    if (hash3 == hash4) {
        cout << "Substring s[1..2] and s[2..3] are likely the same.\n";
    } else {
        cout << "Substrings s[1..2] and s[2..3] are different.\n"; // 输出这个
    }

    return 0;
}
// 时间复杂度: 预处理 O(N), 查询 O(1)
// 空间复杂度: O(N)

2.5 离散化 (Discretization)

当问题涉及的坐标或数值范围很大，但实际用到的值的数量有限时，可以将这些值映射到一个较小的连续整数区间（它们的排名），而不改变它们之间的相对大小关系。

  • 应用场景:

    • 坐标范围达到 但点数只有 的几何问题或数据结构问题（如扫描线、树状数组/线段树维护）。
    • 值域很大但只关心大小关系的计数问题。

  • 方法:

    1. 收集所有需要离散化的值。
    2. 排序并去重。
    3. 将每个原始值映射到它在去重后有序列表中的索引（0-based 或 1-based）。通常使用 lower_bound 或 map 来实现映射。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

using namespace std;

struct Query {
    int l, r, id; // 假设是区间查询
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    vector<int> coords = {10, 500, 1, 1000000000, 500, 10};
    vector<Query> queries = {{1, 500, 0}, {10, 1000000000, 1}}; // 示例查询

    // 1. 收集所有涉及的坐标
    vector<int> all_coords;
    for (int x : coords) all_coords.push_back(x);
    for (const auto& q : queries) {
        all_coords.push_back(q.l);
        all_coords.push_back(q.r);
    }

    // 2. 排序并去重
    sort(all_coords.begin(), all_coords.end());
    all_coords.erase(unique(all_coords.begin(), all_coords.end()), all_coords.end());
    // all_coords 现在是: {1, 10, 500, 1000000000}

    // 3. 建立映射 (可以使用 map 或直接用 lower_bound)
    auto get_id = [&](int val) {
        // 返回 val 在 all_coords 中的索引 (0-based)
        return lower_bound(all_coords.begin(), all_coords.end(), val) - all_coords.begin();
    };

    // 现在可以使用离散化后的坐标
    vector<int> discrete_coords(coords.size());
    for (size_t i = 0; i < coords.size(); ++i) {
        discrete_coords[i] = get_id(coords[i]);
        cout << "Original: " << coords[i] << " -> Discrete: " << discrete_coords[i] << "\n";
    }
    // Output:
    // Original: 10 -> Discrete: 1
    // Original: 500 -> Discrete: 2
    // Original: 1 -> Discrete: 0
    // Original: 1000000000 -> Discrete: 3
    // Original: 500 -> Discrete: 2
    // Original: 10 -> Discrete: 1

    vector<Query> discrete_queries(queries.size());
    for (size_t i = 0; i < queries.size(); ++i) {
        discrete_queries[i].l = get_id(queries[i].l);
        discrete_queries[i].r = get_id(queries[i].r);
        discrete_queries[i].id = queries[i].id;
        cout << "Query " << queries[i].id << ": [" << queries[i].l << "," << queries[i].r << "] -> ["
             << discrete_queries[i].l << "," << discrete_queries[i].r << "]\n";
    }
    // Output:
    // Query 0: [1,500] -> [0,2]
    // Query 1: [10,1000000000] -> [1,3]


    // 可以在离散化后的坐标上使用数据结构，其大小只与不同值的数量有关
    int m = all_coords.size(); // 离散化后的值域大小
    vector<int> data_structure(m, 0); // 例如，用于树状数组或线段树

    return 0;
}
// 时间复杂度: 排序 O(M log M), 映射 O(log M) per value, M 是不同值的数量
// 空间复杂度: O(M)

2.6 平方分割 / 根号算法 (Square Root Decomposition)

一种平衡预处理和查询复杂度的思想。将数据或操作序列分成大约 块，每块大小约为 。对整块进行预处理，对零散部分暴力处理。

  • 应用场景:

    • 区间查询与单点/区间修改问题，当线段树等 O(log N) 结构难以实现或常数过大时。
    • 某些图论问题，如动态连通性（可能需要更复杂的根号数据结构）。

  • 基本思想 (以区间和/单点修改为例):

    • 分块: 将数组 a 分成 B = ceil(sqrt(N)) 块。第 i 个元素属于块 idx = i / B。
    • 预处理: 计算并存储每个块的和 block_sum[idx]。O(N)
    • 修改: 单点修改 a[i] 时，更新 a[i] 的值，并更新其所在块 idx 的和 block_sum[idx]。O(1)
    • 查询: 查询区间 [l, r] 的和时：
      • 如果 l 和 r 在同一块内，直接暴力求和。O()
      • 如果 l 和 r 不在同一块：
        • 处理 l 所在的块的零散部分 (从 l到块尾)。O()
        • 处理 r 所在的块的零散部分 (从块头到 r)。O()
        • 处理中间的完整块，直接累加预计算的 block_sum。O()
      • 总查询复杂度 O()。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
int a[MAXN];         // 原数组
long long block_sum[320]; // 块的和 (sqrt(100000) approx 316)
int blk_sz;          // 块大小
int n;               // 数组大小

// 获取元素 i 所属的块编号 (0-based)
int get_block_id(int i) {
    return i / blk_sz;
}

// 更新单点值
void update(int idx, int val) {
    int bid = get_block_id(idx);
    block_sum[bid] -= a[idx]; // 先减去旧值
    a[idx] = val;             // 更新数组值
    block_sum[bid] += a[idx]; // 再加上新值
}

// 查询区间 [l, r] 的和
long long query(int l, int r) {
    long long sum = 0;
    int bid_l = get_block_id(l);
    int bid_r = get_block_id(r);

    if (bid_l == bid_r) { // l 和 r 在同一块
        for (int i = l; i <= r; ++i) {
            sum += a[i];
        }
    } else {
        // 处理 l 所在块的后缀
        int end_l_block = (bid_l + 1) * blk_sz - 1;
        for (int i = l; i <= end_l_block; ++i) {
            sum += a[i];
        }
        // 处理中间的完整块
        for (int bid = bid_l + 1; bid < bid_r; ++bid) {
            sum += block_sum[bid];
        }
        // 处理 r 所在块的前缀
        int start_r_block = bid_r * blk_sz;
        for (int i = start_r_block; i <= r; ++i) {
            sum += a[i];
        }
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    n = 10; // 示例大小
    // cin >> n;
    blk_sz = sqrt(n);
    if (blk_sz == 0) blk_sz = 1; // Avoid division by zero for small n

    // 初始化数组和块和 (示例数据)
    for(int i=0; i<n; ++i) {
        a[i] = i + 1;
        // cin >> a[i];
        block_sum[get_block_id(i)] += a[i];
    }

    // 查询 [2, 7] (0-based index) -> a[2]+...+a[7] = 3+4+5+6+7+8 = 33
    cout << "Query [2, 7]: " << query(2, 7) << "\n";

    // 更新 a[4] = 10
    update(4, 10); // 原 a[4]=5, 块 1 (假设 blk_sz=3) 的和减少 5, 增加 10

    // 再次查询 [2, 7] -> 3+4+10+6+7+8 = 38
    cout << "Query [2, 7] after update: " << query(2, 7) << "\n";

    return 0;
}
// 时间复杂度: 预处理 O(N), 修改 O(1), 查询 O(sqrt(N))
// 空间复杂度: O(N + sqrt(N)) = O(N)

2.7 构造性算法 (Constructive Algorithms)

这类问题要求你构造一个满足特定条件的解（如一个排列、一个图、一个序列等），而不是计算一个值或判断是否存在。

  • 思维方式:
    • 从特殊情况入手: 考虑 N=1, 2, 3 等小规模情况，或者边界条件（如完全图、空图、全排列等），寻找规律或突破口。
    • 贪心: 每一步做出局部最优的选择，看是否能导向全局最优解。需要证明贪心的正确性。
    • 归纳/递归: 假设 N-1 的问题已经解决，如何构造 N 的解？
    • 模式识别: 观察约束条件，看是否暗示了某种结构（如奇偶性、周期性、对称性）。
    • 随机+调整: 有时可以先随机生成一个结构，然后逐步调整使其满足条件（较少见于构造题，更多用于优化问题）。
    • 分治: 将问题分解，构造子问题的解，然后合并。
    • 反向思考: 从目标状态出发，逆向操作，看能否回到初始状态或简单状态。

构造题往往没有固定套路，需要灵活运用各种思想，并进行大量的观察和尝试。

2.8 简单博弈论 (Simple Game Theory)

主要是指公平组合游戏 (Impartial Games)，特别是基于 Sprague-Grundy 定理的 Nim 游戏及其变种。

  • Nim 游戏: 有 n 堆石子，每堆有 a_i 个。两个玩家轮流操作，每次可以从任意一堆中取走至少一个石子。取走最后一个石子的人获胜。
  • 必胜/必败态:
    • 必败态 (P-position): 当前玩家无论如何操作，都会转移到必胜态。
    • 必胜态 (N-position): 当前玩家存在至少一种操作，可以转移到必败态。
  • Nim 和 (Nim-Sum): 定义为所有堆石子数量的异或和：。
    • 结论: 当前局面是必败态当且仅当 Nim 和为 0。否则是必胜态。
  • Sprague-Grundy (SG) 定理:
    • SG 函数: 对于游戏中的一个状态 g，其 SG 值 SG(g) 定义为所有它能到达的后继状态 g' 的 SG 值的 mex (Minimum Excluded value，即不属于该集合的最小非负整数)。mex(S) = min{k | k >= 0, k \notin S}。
    • 终止状态 (无法操作的状态，如 0 个石子) 的 SG 值为 0。
    • 定理: 一个组合游戏（由多个独立子游戏组成）的 SG 值等于其所有子游戏 SG 值的异或和。
    • 应用: 任何公平组合游戏都可以看作一个 Nim 堆，其石子数量就是该游戏状态的 SG 值。因此，可以通过计算每个子游戏的 SG 值，然后求异或和，来判断整个游戏的胜负状态（异或和为 0 则必败，否则必胜）。

掌握 SG 函数的计算和 Nim 和是解决许多基础博弈问题的关键。

三、竞赛策略与调试：稳定发挥，减少失误

算法实力是基础，但优秀的竞赛策略和调试能力是稳定发挥、冲击高排名的保障。

3.1 读题与分析

  • 仔细阅读: 不要漏掉任何细节、约束条件、输入输出格式。特别是注意 N, M 的范围，数据类型，时间限制，内存限制。
  • 理解题意: 确保完全理解问题要求什么。可以手动模拟小样例，或者自己构造边界样例来加深理解。
  • 抓住关键: 找出问题的核心难点和约束。是数据结构？动态规划？图论？还是数学？
  • 估算复杂度: 根据数据范围大致判断所需算法的时间复杂度级别 (O(N), O(N log N), O(N^2), O(sqrt(N)), O(2^N)等)，排除不合适的算法。
  • 思考多种解法: 不要满足于第一个想到的思路。尝试从不同角度思考，评估不同解法的复杂度、实现难度和正确性。

3.2 时间管理

  • 开局通览: 快速阅读所有题目，大致评估难度，确定开题顺序（通常先做签到题和自己擅长的题目）。
  • 分配时间: 对每道题预估一个大致的思考和编码时间。不要在某一道难题上投入过多时间而导致简单题没时间做。
  • 及时止损: 如果一道题长时间没有进展，或者调试陷入僵局，果断切换到其他题目，稍后再回来也许会有新思路。
  • 预留时间: 留出一些时间用于检查、优化和应对突发情况（如发现之前的题目有 bug）。

3.3 调试技巧

调试是竞赛中最耗时也最考验心态的环节之一。

  • 静态查错: 提交前，通读代码，检查：

    • 变量名是否写错？
    • 数组下标是否越界？
    • 循环边界是否正确？
    • long long 是否使用得当？
    • 初始化是否完成？
    • 多组数据是否清空全局变量/数据结构？
    • 模运算是否正确处理负数？(a % P + P) % P
    • 函数参数传递是否正确？

  • 输出中间结果 (cerr): 使用 cerr 输出变量值、程序执行路径等信息。cerr 输出到标准错误流，不会影响标准输出结果。

    1
    cerr << "Debug: i = " << i << ", value = " << arr[i] << endl;

  • assert: 在你认为某个条件必须成立的地方加上 assert(condition)。如果条件不满足，程序会异常终止并报告位置，有助于快速定位不变量被破坏的地方。

    1
    assert(index >= 0 && index < n); // 断言下标合法

  • 对拍 (Stress Testing):

    • 编写一个暴力但保证正确的解法 (brute_force)。
    • 编写一个数据生成器 (generator)，生成各种随机或边界测试数据。
    • 写一个脚本，循环执行以下步骤：
      1. 用 generator 生成一组输入数据 input.txt。
      2. 运行你的解法 (my_solution)，得到输出 my_output.txt。
      3. 运行暴力解法 (brute_force)，得到输出 correct_output.txt。
      4. 比较 my_output.txt 和 correct_output.txt 是否相同。如果不同，保存 input.txt 并停止。
    • 这是找出复杂算法 bug 的强力武器。

  • 小数据/边界数据: 手动构造或用程序生成一些简单、边界、特殊的数据进行测试（如 N=0, 1，最小值，最大值，全相等，单调等）。

  • 二分调试: 如果怀疑错误发生在某个循环或递归过程中，可以通过二分的方式逐步缩小错误范围。

3.4 团队协作 (ICPC)

  • 有效沟通: 清晰地表达自己的思路、遇到的问题。及时同步进度和发现。
  • 合理分工: 根据队员的特长分配任务（如一人读题思考，一人编码，一人准备模板或对拍）。
  • 代码复审: 队友写的代码可以互相检查，更容易发现潜在问题。
  • 心态调整: 互相鼓励，保持积极心态。即使遇到困难也要冷静分析，共同解决。

四、结语：技巧是翼，基础为根

算法竞赛的征途，道阻且长。今天我们探讨的这些“技巧”，更像是工具箱里的高效工具，它们能让你在搭建算法大厦时更加得心应手。然而，请务必牢记，所有技巧的运用都建立在扎实的算法理论基础和编程能力之上。没有稳固的根基，再华丽的技巧也只是空中楼阁。

  • 持续学习: 算法世界日新月异，保持学习的热情，不断吸收新知识、新思想。
  • 刻意练习: 大量的、有针对性的练习是提升实力的不二法门。不仅要刷题，更要总结、反思。
  • 享受过程: 享受思考的乐趣，享受克服困难的成就感。竞赛不仅是为了奖牌，更是提升自我、结交同好的宝贵经历。

希望本文分享的这些技巧和心得，能为正在算法竞赛道路上奋斗的你提供一些启发和帮助。愿你们在未来的赛场上，思维如电，斩获佳绩！

  • Title: 算法竞赛中的制胜秘笈
  • Author: YZY
  • Created at : 2025-06-17 00:41:26
  • Updated at : 2025-06-17 00:43:46
  • Link: https://blog.dtoj.team/2025/06/17/算法竞赛制胜秘笈/
  • License: 三金家的Y同学
Comments
On this page
算法竞赛中的制胜秘笈
  1. 算法竞赛中的制胜秘笈：从基础优化到思维突破
    1. 一、编码细节：毫厘之优，积少成多
      1. 1.1 输入输出优化（IO Optimization）
      2. 1.2 数据类型选择与精度控制
      3. 1.3 STL 的高效运用
      4. 1.4 位运算 (Bit Manipulation)
      5. 1.5 预处理与打表
    2. 二、算法思维：巧破难局，洞见本质
      1. 2.1 双指针 (Two Pointers / Sliding Window)
      2. 2.2 折半查找/折半搜索 (Meet-in-the-Middle)
      3. 2.3 随机化 (Randomization)
      4. 2.4 哈希 (Hashing)
      5. 2.5 离散化 (Discretization)
      6. 2.6 平方分割 / 根号算法 (Square Root Decomposition)
      7. 2.7 构造性算法 (Constructive Algorithms)
      8. 2.8 简单博弈论 (Simple Game Theory)
    3. 三、竞赛策略与调试：稳定发挥，减少失误
      1. 3.1 读题与分析
      2. 3.2 时间管理
      3. 3.3 调试技巧
      4. 3.4 团队协作 (ICPC)
    4. 四、结语：技巧是翼，基础为根