3.1 P1909《买铅笔》（枚举三种方案）#

题意：买 n 支铅笔，给出 3 种“每包数量+价格”，问最小花费。

思路：每种方案都算一次 ceil(n / pack) × price，取 min。

3.2 P1047《校门外的树》（差分优化的模拟）#

题意：路段 [0..L] 初始有树；给出 M 个区间要“砍掉”，问剩余多少棵。

方法一（朴素）：bool 标记 + 区间打掉，O(L×M)，很慢。

方法二（差分）：对每个 [l, r] 做 diff[l]++, diff[r + 1]—，最后前缀和>0 表示被砍。

3.3 P1008《三连击》（全排列枚举）#

题意：找出 3 个三位数 A、B、C，使得 A:B = 1:2:3，且 1..9 每个数字恰好出现一次。

思路：对 1..9 的全排列，每 3 位拼一个数，检查比例。

3.4 P1042《乒乓球》（字符串模拟）#

题意：输入一串 ‘W’/‘L’/‘E’，输出 11 分制与 21 分制两套比分。

做法：遍历字符，遇 E 结束，胜负分到达 limit 且相差 ≥2 就结算一局。

3.5 P1980《计数问题》（枚举数位 + 进阶做法）#

题意：统计 1..n 中数字 x 出现了多少次。

做法 A：朴素枚举每个数的每一位（n×位数）。

做法 B（进阶，推荐）：逐位统计（高位/当前位/低位法，$O(log n)$）

要点：0 的处理与前导零有关，按题意选择写法。

3.6 P1328《生活大爆炸版石头剪刀布》（规则模拟）#

题意：两人出拳模式循环给出，进行 n 次对决，规则是 5 种手势的胜负表。
做法：预先写好胜负矩阵 win[i][j]，轮流取序列 a[i%la], b[i%lb] 比较。

4.1 去重与剪枝#

• 两元对去重：强制 i < j；
• 三元组去重：i < j < k；或排序后跳过相同值；
• 非降约束：枚举划分/组合时，下一步从“当前选择及之后”开始；
• 上下界剪枝：已超出目标就提前 break；
• 对称剪枝：如果方案与镜像等价，固定一侧。

示例：枚举三元组满足 a[i]+a[j]+a[k]=T, $O(n^3)$

1
for (int i = 0; i < n; ++i)
2
  for (int j = i + 1; j < n; ++j)
3
    for (int k = j + 1; k < n; ++k)
4
      if (a[i] + a[j] + a[k] == T) ++ans;

可剪枝

• 提前排序后，若最小可能和 > T 或最大可能和 < T，则可 break / continue；
• 固定 i, j，二分或双指针找 k。

4.2 子集枚举的两种写法#

• 位掩码（通用）
• 递归/回溯（可加剪枝）

位掩码统计子集和为 T 的个数

1
long long count_subset_sum(const vector<int>& a, int T) {
2
  int n = a.size();
3
  long long ans = 0;
4
  for (int mask = 0; mask < (1 << n); ++mask) {
5
    long long s = 0;
6
    for (int i = 0; i < n; ++i)
7
      if (mask >> i & 1) s += a[i];
8
    ans += (s == T);
9
  }
10
  return ans;
11
}

4.3 区间/子串枚举#

• 所有子数组 $O(n^2)$：

1
for (int l = 0; l < n; ++l)
2
  for (int r = l; r < n; ++r)

• 所有子串 $O(n^2)$：

1
for (int i = 0; i < (int)s.size(); ++i)
2
  for (int len = 1; i + len <= (int)s.size(); ++len)
3
    // s.substr(i, len)

配合前缀和，可以 $O(1)$ 求区间和，整体 $O(n^{2})$。

4.4 数位枚举与“回文/质数/进制”#

• 判断质数：

1
bool is_prime(long long x) {
2
  if (x < 2) return false;
3
  for (long long d = 2; d * d <= x; ++d)
4
    if (x % d == 0) return false;
5
  return true;
6
}

• 判断回文（字符串法）：

1
bool is_pal(const string& t) {
2
  for (int i = 0, j = (int)t.size()-1; i < j; ++i, --j)
3
    if (t[i] != t[j]) return false;
4
  return true;
5
}

• 反转整数（去前导零）

1
long long rev_num(long long x) {
2
  long long y = 0;
3
  while (x) { y = y*10 + x%10; x/=10; }
4
  return y;
5
}

6.1 什么是对拍？#

在算法竞赛中，我们有时会写两个版本的程序来解决同一道题目：

• 暴力程序（通常写得很简单，但复杂度高，只能跑小数据）；
• 优化程序（复杂度优秀，但实现复杂，容易写错）。

对拍（double check / stress test） 的思想就是：

1. 写一个随机数据生成器（gen_input()）。

2. 用同一份输入分别喂给两个程序（如 1.exe 和 2.exe）。

3. 比较输出是否一致。

   • 如果一致，多测几次，就能增加对优化程序正确性的信心；
   • 如果不一致，就保存输入，方便 Debug。

这种方法在调试优化算法时非常有用，尤其是在数据范围较小，可以轻松跑完的情况下。

6.2 基本流程#

一个对拍脚本主要分为三步：

1. 生成输入

1
std::string gen_input() {
2
  std::ostringstream oss;
3
  int n = randomInt(1, 200);
4
  oss << n << "\n";
5
  for (int i = 0; i < n; ++i) {
6
  int x = randomInt(-200, 200);
7
  oss << x << " \n"[i == n - 1];
8
  }
9
  return oss.str();
10
}

• 使用随机数生成器（如 mt19937）保证样例覆盖面广；
• 注意输入格式必须符合题目要求。

2. 运行并获取输出

1
auto res1 = run("1.exe", input);
2
auto res2 = run("2.exe", input);
3
std::string output1 = res1.first;
4
std::string output2 = res2.first;

run(...) 函数会写入临时输入文件，再调用系统命令运行可执行文件，并读取输出。

3. 比较结果

1
if (output1 != output2) {
2
  std::cout << "Mismatch found!\n";
3
  std::cout << "Input:\n" << input << '\n';
4
  std::cout << "Output1:\n" << output1;
5
  std::cout << "Output2:\n" << output2;
6
  break;
7
}

6.3 注意事项#

• 随机性
• 速度
• 输出一致性
• 定位 bug

6.4 小结#

• 对拍不是算法本身，而是一种调试工具；
• 它能帮助我们快速发现优化代码中的细节错误；
• 日常写题时，如果一直WA还找不出错误，可以尝试写一个暴力来对拍。