1. 暴力（DFS / 暴力枚举）打底#

任何题目，拿到手如果 20 分钟内没有正解思路，第一件事就是写暴力。

• $N \le 10 \implies O(N!)$ 全排列枚举。
• $N \le 20 \implies O(2^N)$ 子集折半或 DFS 爆搜。
• $N \le 100 \implies O(N^3)$ 或 $O(N^4)$ 多重循环。

原则：不要嫌弃暴力只有 20~30 分。四道题的暴力全部拿到，往往就已经接近一等奖分数线了！

2. 针对“特殊性质”单独写逻辑#

题目说明里经常包含类似这样的字眼：

• “另外 20% 的数据，满足树退化为一条链” $\implies$ 当作一维数组处理。
• “另外 20% 的数据，保证 $A_i \ge 0$” $\implies$ 无需考虑负数，直接贪心。
• “另外 15% 的数据，满足 $K=1$” $\implies$ 特殊单次询问，推导简单公式。

3. 用 if-else 拼凑得分（分段得分法）#

把不同 Subtask 的代码写在不同的函数里，在 main 函数中用 if-else 分流。这是最标准的“拼分”架构：

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

4
int n, m;
5

6
bool is_chain() {
7
    // 检查输入数据是否符合“链”的特征
8
    return true;
9
}
10

11
void solve_dfs() { /* 20% 分数：暴力爆搜 */ }
12
void solve_chain() { /* 20% 分数：链的特殊性质 */ }
13
void solve_k1() { /* 20% 分数：K=1 的情况 */ }
14
void solve_rand() { /* 剩余数据：随机化 / 贪心 */ }
15

16
int main() {
17
    cin >> n >> m;
18
    if (n <= 10) {
19
        solve_dfs();
20
    } else if (is_chain()) {
21
        solve_chain();
22
    } else if (m == 1) {
23
        solve_k1();
24
    } else {
25
        solve_rand(); // 拿不到全分，撞大运拿几分
26
    }
27
    return 0;
28
}

1. “卡时”大法（Time-based Exit）#

评测机单点限时通常为 1.0 秒（$1000\text{ ms}$）。如果你的搜索或随机算法可能会 TLE（超时），可以利用 <chrono> 或 clock() 在超时前强行终止并输出当前找到的最优解！

1
#include <iostream>
2
#include <chrono>
3

4
using namespace std;
5

6
auto start_time = chrono::steady_clock::now();
7

8
bool time_out() {
9
    auto now = chrono::steady_clock::now();
10
    double elapsed = chrono::duration<double>(now - start_time).count();
11
    return elapsed > 0.92; // 超过 0.92 秒立刻停止，留 0.08 秒做收尾和输出
12
}
13

14
void dfs(int state) {
15
    if (time_out()) return; // 随时检查时间
16
    // 正常的 DFS 逻辑...
17
}

2. 贪心 + 随机打乱（Random Shuffle）#

在图论、背包、NP 难问题中，单纯的贪心可能会被构造数据卡掉。但是：“贪心不够，随机来凑”！ 我们可以将输入数据的顺序随机打乱（std::shuffle），然后运行 100 次贪心，取所有运行结果中的最优值：

1
int best_ans = 0;
2
while (!time_out()) { // 在限时内反复跑
3
    shuffle(a.begin(), a.end(), rnd); // 打乱输入顺序
4
    int current_ans = greedy_solve();
5
    best_ans = max(best_ans, current_sum);
6
}
7
cout << best_ans << endl;

真实战绩：这种“随机化贪心”在许多复杂的求解/优化题中，经常能把 30 分的暴力骗到 70~80 分甚至奇迹 AC！

3. 模拟退火（Simulated Annealing）与爬山法#

对于求解极值（最大值/最小值）的几何、图论或组合优化问题，如果在考场上想不到 DP 或高级数据结构，直接写一个模拟退火模板。调好参数后，大概率能刷过大半测试点。

1. 本地打表（Precomputation）#

当题目要求输出某个特定数学序列或小范围状态（例如 $N \le 50$ 的某种方案数），但你的算法运行一次需要 10 秒（本地能跑，提交会 TLE）：

• 在本地电脑上运行你的暴力程序，把 $N=1 \dots 50$ 的答案全部算出来。
• 复制这些结果，在代码里硬编码写成一个全局数组：

  1
  int ans[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...};
  2
  int main() {
  3
      int n; cin >> n;
  4
      cout << ans[n] << endl; // O(1) 瞬间输出
  5
  }
  

2. 猜测特例输出（无脑偏分）#

当题目时间所剩无几（比如只剩最后 3 分钟），实在写不出任何代码时：

• 如果题目问“是否存在解，不存在输出 -1”：直接全输出 -1。评测数据中往往有 10%~20% 的点是没有解的！
• 如果题目问“YES 或 NO”：全输出 YES 或全输出 NO（通常能拿到 10%~30% 的分数）。
• 如果题目求最小值/最大值：输出 0 或 1 或题目中给定的某个边界极值。

3. 样例反推（打表找规律）#

如果题目看起来像数学题或博弈论，先写个小暴力把 $N=1 \sim 20$ 的输出答案打出来，观察数列：

• 是不是等差/等比数列？
• 是不是斐波那契数列？
• 是不是 N % 4 == 0 时先手必胜？ 很多时候，甚至不需要严谨的数学证明，找出了规律，写出单行公式就能直接 AC！