跳转至

常見技巧

本頁面主要列舉一些競賽中的小技巧。

利用局部性

局部性是指程序傾向於引用鄰近於其他最近引用過的數據項的數據項，或者最近引用過的數據項本身。局部性分為時間局部性和空間局部性。

具體可參見 循環展開 (Loop Unroll)、代碼佈局優化 (Code Layout Optimizations) 等內容

循環宏定義

如下代碼可使用宏定義簡化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
for (int i = 0; i < N; i++) {
  // 循環內容略
}

// 使用宏簡化
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)

// 這樣寫循環代碼時，就可以簡化成 `f(i, 0, N)` 。例如：
// a is a STL container
f(i, 0, a.size()) { ... }

另外推薦一個比較有用的宏定義：

1
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)

善用 namespace

使用 namespace 能使程序可讀性更好，便於調試。

例題：NOI 2018 屠龍勇士 
 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
// NOI 2018 屠龍勇士 40分部分分代碼
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
long long n, m, a[100005], p[100005], aw[100005], atk[100005];

namespace one_game {
// 其實namespace裏也可以聲明變量
void solve() {
  for (int y = 0;; y++)
    if ((a[1] + p[1] * y) % atk[1] == 0) {
      cout << (a[1] + p[1] * y) / atk[1] << endl;
      return;
    }
}
}  // namespace one_game

namespace p_1 {
void solve() {
  if (atk[1] == 1) {  // solve 1-2
    sort(a + 1, a + n + 1);
    cout << a[n] << endl;
    return;
  } else if (m == 1) {  // solve 3-4
    long long k = atk[1], kt = ceil(a[1] * 1.0 / k);
    for (int i = 2; i <= n; i++)
      k = aw[i - 1], kt = max(kt, (long long)ceil(a[i] * 1.0 / k));
    cout << k << endl;
  }
}
}  // namespace p_1

int main() {
  int T;
  cin >> T;
  while (T--) {
    memset(a, 0, sizeof(a));
    memset(p, 0, sizeof(p));
    memset(aw, 0, sizeof(aw));
    memset(atk, 0, sizeof(atk));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> aw[i];
    for (int i = 1; i <= m; i++) cin >> atk[i];
    if (n == 1 && m == 1)
      one_game::solve();  // solve 8-13
    else if (p[1] == 1)
      p_1::solve();  // solve 1-4 or 14-15
    else
      cout << -1 << endl;
  }
  return 0;
}

使用宏進行調試

編程者在本地測試的時候，往往要加入一些調試語句。而在需要提交到 OJ 時，為了不使調試語句的輸出影響到系統對程序輸出結果的判斷，就要把它們全部刪除，耗時較多。這種情況下，可以通過定義宏的方式來節省時間。大致的程序框架是這樣的：

1
2
3
4
5
6
7
8
#define DEBUG
#ifdef DEBUG
// do something when DEBUG is defined
#endif
// or
#ifndef DEBUG
// do something when DEBUG isn't defined
#endif

#ifdef 會檢查程序中是否有 #define 定義的對應標識符，如果有定義，就會執行後面的語句。而 #ifndef 會在沒有定義相應標識符的情況下執行後面的語句。

這樣，只需在 #ifdef DEBUG 裏寫好調試用代碼，#ifndef DEBUG 裏寫好真正提交的代碼，就能方便地進行本地測試。提交程序的時候，只需要將 #define DEBUG 一行註釋掉即可。也可以不在程序中定義標識符，而是通過 -DDEBUG 的編譯選項在編譯的時候定義 DEBUG 標識符。這樣就可以在提交的時候不用修改程序了。

不少 OJ 都開啓了 -DONLINE_JUDGE 這一編譯選項，善用這一特性可以節約不少時間。

對拍

對拍是一種進行檢驗或調試的方法，通過對比兩個程序的輸出來檢驗程序的正確性。可以將自己程序的輸出與其他程序的輸出進行對比，從而判斷自己的程序是否正確。

對拍過程要多次進行，因此需要通過批處理的方法來實現對拍的自動化。

具體而言，對拍需要一個 數據生成器 和兩個要進行輸出結果比對的程序。

每運行一次數據生成器都將生成的數據寫入輸入文件，通過重定向的方法使兩個程序讀入數據，並將輸出寫入指定文件，最後利用 Windows 下的 fc 命令比對文件（Linux 下為 diff 命令）來檢驗程序的正確性。如果發現程序出錯，可以直接利用剛剛生成的數據進行調試。

對拍程序的大致框架如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <stdlib.h>

int main() {
  // For Windows
  // 對拍時不開文件輸入輸出
  // 當然，這段程序也可以改寫成批處理的形式
  while (true) {
    system("gen > test.in");  // 數據生成器將生成數據寫入輸入文件
    system("test1.exe < test.in > a.out");  // 獲取程序1輸出
    system("test2.exe < test.in > b.out");  // 獲取程序2輸出
    if (system("fc a.out b.out")) {
      // 該行語句比對輸入輸出
      // fc返回0時表示輸出一致，否則表示有不同處
      system("pause");  // 方便查看不同處
      return 0;
      // 該輸入數據已經存放在test.in文件中，可以直接利用進行調試
    }
  }
}

內存池

當動態分配內存時，頻繁使用 new/malloc 會佔用大量的時間和空間，甚至生成大量的內存碎片從而降低程序的性能，可能會使原本正確的程序 TLE/MLE。

這時候需要使用到「內存池」這種技巧：在真正使用內存之前，先申請分配一定大小的內存作為備用。當需要動態分配時直接從備用內存中分配一塊即可。

在大多數 OI 題當中，可以預先算出需要使用到的最大內存並一次性申請分配。

示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// 申請動態分配 32 位有符號整數數組：
int* newarr(int sz) {
  static int pool[maxn], *allocp = pool;
  return allocp += sz, allocp - sz;
}

// 線段樹動態開點的代碼：
Node* newnode() {
  static Node pool[maxn << 1], *allocp = pool - 1;
  return ++allocp;
}

參考資料

洛穀日報 #86

《算法競賽入門經典 習題與解答》

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：H-J-Granger, Ir1d, ChungZH, Marcythm, StudyingFather, billchenchina, Suyun514, Psycho7, greyqz, Xeonacid, partychicken
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用