dreamoon4/common_bug_list.md Secret

## common_bug_list.md

      
    Raw
  

              common_bug_list.md
            
          
    AA 競程演算法競賽 Debug 手冊

Debug 時注意事項


檢查 Debug 列表 「競程選手最常犯的四大錯誤」裡的各個項目。

這類的 bug 都和沒看清楚題目測試資料範圍有關，舉例來說：

索引值用到 1~100000，陣列宣告為 a[100000] 真的 ok 嗎?
這題的數值範圍最大值雖然只有 $10^6$，但答案可能是 $10^4$ 個輸入的數值加起來的結果耶，答案用 int 儲存真的夠嗎？
n 的上界真的是 $10^5$ 嗎？該不會其實是 $2 \times 10^5$ 吧?
這題 n 的上界是 $10^6$ 耶，你在程式碼這麼寫成 100000?
這題雖然 n 的上界是 $10^5$ 可是要讀入 $2n$ 個數呢，陣列大小只開 10^5 夠嗎？


編譯程式碼時加上 -Wall -Wextra -Wconversion -Wshadow 這幾個參數，檢查是否有潛在的錯誤。
檢查 Debug 列表 「細節(變數使用、邊界邏輯)思考不清楚造成的錯誤」。
若此題和後面列出的特定主題有關，去檢查相關主題的常見錯誤。
比較常見的錯誤都檢查過但仍有錯的話，再從頭到尾仔細想過程式每一行是否正確，連最開頭的 #define 等都不可忽略
若能找到錯誤的測試資料，就模擬自己的程式碼(可藉由 cout 一些變數來檢驗)，看看到底哪一步和自己預期的結果不符
若找不到錯誤的測試資料，先嘗試看看一些在極端情況(尤其是極小)的測試資料是否能輸出正確答案，例如：

若輸入只要一個非負整數，依序嘗試 0, 1, 2, 3,... 是否輸出正確答案
輸入只有一個數列，依序嘗試：[1], [2], [1,1], [1, 2], [2, 1] [2, 2], [1, 1, 1], [1, 1, 2], [1, 1, 3], ...
輸入為一個圖，嘗試一個點、兩個點、三個點的圖等等


請適時檢查自己到底有沒有讀錯題目或傳錯題目
若是極小測資都是不出錯誤，那可想想是不是存在一些只有在極大的測試資料會發生的 bug (尤其是整數溢位、陣列開太小、答案忘記取模等)
請仔細想想，你使用的演算法真的是對的嗎？是否有某些你覺得很顯然沒仔細證明的步驟其實是錯的呢？
情非得已時可嘗試暴力對拍
若真的想求助別人時，請先比對自己的程式碼和其他人寫的相同演算法的程式碼有哪些地方不一樣，仔細思考那些不一樣的地方是否有機會造成錯誤。(若是老師上課講解過的題，通常能在投影片或影片裡能看到老師的程式碼。若還是看不出來，就一步一步的把自己的程式碼改成和別人的程式碼一樣，每改一個小地方就測試看看是否能輸出正確答案，藉此來定位到底錯在哪。

常見情境

1. 程式碼在自己電腦上能編譯成功，但在 OJ 上卻編譯錯誤


上傳時選擇的編譯器版本是否正確呢？(例如使用了 gcd() 函式，編譯器版本卻使用 C++14)


是否忘記 include 某些函式所需的標頭檔呢？(有些環境在使用某些函式庫時，就會自動去 include 其他你沒 include 的函式庫)


是否有在全域變數裡使用了某個變數、函數、結構體名稱和 OJ 環境提供的函式庫裡的變數名稱撞名呢？例如以下程式碼在 Codeforces 上使用 GNU G++23 去編譯：
#include<iostream>
using namespace std;
int data;
int main() {
    cin >> data;
    cout << data << '\n';
}
會有以下編譯錯誤訊息：
program.cpp:5:12: error: reference to 'data' is ambiguous


是否使用了 OJ 上不支援的 C++ 擴充功能呢？(如以下程式碼在 CLANG 編譯器無法通過)
#include<iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  int d[n] = {1};
  cout << d[0] << '\n';
}


是否在全域變數裡開了一個超大(超過記憶體限制)的陣列呢？(如以下程式碼)
#include<iostream>
using namespace std;
int a[1000000000];
int main() {
    cout << a[999999999] << '\n';
}


是否在全域變數開了一個很大(如 $10^7$ 個元素) 的陣列且還給了非 0 的初始值呢？(如以下程式碼)
#include<iostream>
using namespace std;
int a[10000000] = {1};
int main() {
    cout << a[9999999] << '\n';
}


是否加了 OJ 上不支援的編譯、硬體優化呢？

目前 Codeforces 上編譯選項若選 GNU G++20 13.2 (64 bit, winlibs)，將無法使用硬體優化，必須換其他 C++ 選項
目前 NTU CPC Online Judge 不支援某些 pragma 參數


2. 在自己電腦上執行 Sample 輸出的結果正確，但在 OJ 上範例測試資料就錯時


你的程式在 Sample 的輸出真的是對的嗎？是否有多輸出 Debug 訊息呢？空白和換行的格式有符合題目需求嗎？輸出是字串時，大小寫是否正確呢？是否有拼錯單字呢？是否有輸出一些不可視字元呢？
你的程式碼是否含有未定義行為呢？最常見的有：

陣列開太小
使用到不該使用記憶體位置
區域變數未初始化


是否有使用 cin.tie(0); ios_base::sync_with_stdio(false); 時，卻把 std 的 cin、cout 和 C 語言的 scanf/printf/puts 混用的情況呢？
是否已讀入資料後才執行 cin.tie(0); ios_base::sync_with_stdio(false); 呢?
是否用了一些特殊的編譯優化(如 O3 以上的優化、unroll-loops 等)或是加了些硬體優化導致出錯呢？
該題的 I/O 格式是標準輸入/標準輸出嗎？是否其實是需要讀檔寫檔呢？
非常確定自己在 OJ 上錯的是 Sample 嗎？有沒有可能出題者並沒有把範例放在第一組測試資料？
是否有使用了執行結果並不總是一樣的內建函式呢?

例如使用 sort 函式時，若兩個被排序的不同物件被比較函式視為一樣時，並不保證誰會排前面誰會排後面。


3. 遇到 RE(Runtime Error) 的可能原因


陣列/vector 用到的索引值超出合法範圍
常見情境，使用 while 迴圈檢查陣列裡有哪些數滿足，檢查到第一個不滿足或結尾位置就要停下來，但忘記判斷結尾位置。
// 給一個長度為 n 的數列，判斷有多少數和數列第一個數一樣。
int n;
cin >> n;
for(int i = 0; i < n; i++) {
   cin >> a[i];
}
int ans = 0;
while(a[ans + 1] == a[0]) ans++;
cout << ans << '\n';

使用內建函數時傳錯參數(可參考以下例子)

例一：
    sort(d + 3, d + 2);
例二：
    set<int> d{1,2,3};
    d.erase(d.end());

使用 STL 容器時，insert/push/push_back 太多元素，記憶體不足造成函式執行失敗，因此 RE(也可能是 MLE)(可參考以下例子)

    set<int> d;
    for(int i = 0; i < 100000000; i++) d.insert(i);

在函式(包括主函式)裡面開太大的記憶體

    int main() {
        int a[1000000000];
    }

整數除法或取餘時除以 0
在 Codeforces 系統上因為 bug 造成輸出太多東西時也會得到 RE。

4. 遇到 Time Limit Exceed 的時候


請仔細分析自己程式碼的時間複雜度，是否正確
是否記得加 I/O 優化呢？
是否是因為執行太多次 cout << endl; 而超時呢?
是否不小心寫出無窮迴圈呢？(以下是一個例子)
for(int i = 0; i < n; i--) { /*...*/ }

請確認程式碼使用的內建函式的執行時間複雜度是否和你預期的一樣 (見 15. 內建函式或語法誤用導致 Time Limit Exceed)
是否有某個函式使用 pass by value 傳遞某個記憶體很大的物件且呼叫非常多次呢？ (可在 此 youtube 影片 此錯誤的示範)
是否有在多次(例如在迴圈裡或在一個被多次呼叫的函式裡)宣告一個元素非常多的 vector 或是在迴圈裡面宣告一個很大的陣列並初始化呢？要記得宣告 $N$ 個元素的 vector 或初始化一個長度 為 $N$ 的陣列時間複雜度為 $O(N)$，所以若宣告 $T$ 次，時間複雜度就是 $O(Tn)$。
程式碼含有未定義行為也有可能超時(陣列開太小等)
unordered_set/unordered_map 在測資有刻意構造時，每次操作的時間複雜度會退化到 O(容器裡元素數量)
請確認是否有寫出一些常見的大常數程式碼，如：

在元素數量量級超過 $10^6$ 時使用關聯容器會很慢
無序關聯容器比陣列慢
在使用 int 即可的陣列以 long long 宣告，如有大量的陣列曲直操作，會慢 2 倍左右
用多層迴圈去使用多維陣列裡的值時，陣列維度的順序會嚴重影響常數(可在 此 youtube 影片 看詳細例子)


在 Codeforces 上，有非常多題若使用無序關聯容器(unordered_set/map) 可能會被刻意構造的測資導致執行時間達到 worst case，也就是單個操做要花 $O(n)$

在 Codeforces 上，大量使用 long long 時，使用 32 bit 的編譯器會比較慢(也可能有其他因素造成不同 C++ 編譯器會嚴重影響程式執行時間常數)

Bug 列表


語法班學生常見錯誤


語法錯誤請見 AA 競程 hackmd:C++ 新手常見語法錯誤搜集

模板打錯

    #include<iostream>
    using namespace std;
    int main() {
    }

忘記分號
cin, cout 用錯運算子 (>>,<< 用反)
忘記宣告變數、變數宣告在使用之後
大括號位置放錯
指派運算子順序搞反
使用到全形符號
同一個 token 中出現多餘空白
變數名稱大小寫混用
誤以為 C++ 的運算式使用的括號有大中小括號之分。


輸出兩個以上的變數時，變數之間忘記以換行或空白做為分隔
在 Codeforces 上誤把 long 當成 long long 使用(Codeforces 上的 long 只有 32 bits
還沒讀入變數就先使用該變數做事了
把 = 和 == 搞混


競程新手常見錯誤

I/O 太慢 (見 5. I/O 相關)
忘記陣列、vector、string 索引值是從 0 開始
不會估算程式碼執行時間，以至於浪費大量時間寫一個一定不會通過的演算法
不知道讀入 C 語言字串時，字串末尾會多加一個 null 字元，導致字元陣列開不夠大
vector 或 string 的 size 不夠大就使用不在合法範圍的索引值
不知道浮點數無法正確儲存任何數值/不知道 float 儲存的數值誤差非常大/不知道浮點數計算、使用浮點數相關函式會有誤差

例子一：
long long v = pow(3, 39);
cout << v << endl; // 在 CF 上輸出 4052555153018976256，但應為 4052555153018976267
例子二：
long long x = 1000000000000000001;
long long y = 10;
long long v = ceil(x * 1. / y);
cout << v << endl; // 在 CF 上輸出 100000000000000000，但應為 100000000000000001

誤以為 ^ 是指數的意思


增加編譯參數後能發現的錯誤

函式忘記回傳值
忘記輸入/輸出
變數忘記給初始值
應該使用浮點數的變數宣告成整數，並且在程式碼裡有把其他浮點數指派給該變數
因為變數遮蔽導致使用錯誤的變數


競程選手最常犯的四大錯誤

integer overflow

應為 long long 的變數宣告成 int
輸出需取餘的題有某個運算因忘記取餘而 overflow
有些題(如二分搜題) 就算開 long long 也有機會 integer overflow，可用其他方式避免


    // 以下幾個例子讓大家更正確理解 C++ 運算的原理
    int a = 100000, b = 100000;
    long long x = a * b; // 錯誤
    long long x = (long long)(a * b); // 錯誤
    long long x = a * b * 1LL; // 錯誤
    long long x = a * 1LL * b; // 正確
    long long x = (long long)a * b; // 正確

陣列、vector 大小相關

陣列、vector 開太小
再多組測資的題目裡陣列、vector 開太大導致超時
用字元陣列儲存字串時，忘記陣列大小至少比字串長度多 1


初始化相關：

忘記初始化(可藉由增加編譯參數 -Wall 迅速發現)
給了錯誤的初值
多組詢問時忘記重新初始化


special case(輸入的值在範圍的極小值或極大值時) 特判錯誤或忘記特判


細節(變數使用、邊界邏輯)思考不清楚造成的錯誤

i,j,k,n,m 等變數搞混 (例如某個指令應該要使用變數 i,卻用成變數 j)
編號 0 ~ n-1 或 1 ~ n 搞混
編號從 0 或從 1 開始搞混
迴圈的起始條件或結束條件沒想清楚(差個正負 1，或是 <=、< 搞混)
continue 不小心把某個迴圈內每輪都要執行的事情跳過了


I/O 相關

不知道 endl 很慢(請參考AA 競程 Level 1 試聽課 20：影響執行時間常數的因素 4 --- I/O 處理方式)
不知道使用 cin 且輸入的資料量很大時，必須加 I/O 優化(請參考AA 競程 Level 1 試聽課 20：影響執行時間常數的因素 4 --- I/O 處理方式)
不知道使用 I/O 優化時，C 語言和 C++ 的輸入輸出不能混用
不知道 I/O 優化一定要加在第一次輸入之前


浮點數相關

使用 float 導致算出來答案誤差非常大
輸出的小數點位數不夠多(或沒使用 fixed)
不知道浮點數運算會有誤差
不知道很多數學函式擁有浮點數誤差而去使用 (請參考此篇文章：PSA: don't use these functions unless you really, really need to)
不知道使用科學記號的常數一定是浮點數，寫出類似以下的程式碼，誤以為這樣寫 INF 的值會是 $10^{18}+1$，但其實輸出 INF 看就知道，+1 會因為浮點數誤差而被忽略，實際上 INF 值為 $10^{18}$。

    long long INF = 1e18 + 1;

答案為 0 時，輸出 -0

不知道就算使用 I/O 優化，讀入浮點數還是很慢，若實際上輸入的值是整數，請依律要使用整數讀入

    calculate_circle_area_double() { // 很慢
        double x;
        cin >> x;
        cout << x * x * 3.14159;
    }
    calculate_circle_area_int() { // 比較快
        int x;
        cin >> x;
        cout << x * x * 3.14159;
    }


多組詢問相關 Bug

新的詢問忘記初始化
每次都對整個陣列或 vector 做初始化，但題目的測試資料組數很多，只保證所有測試料 n 的總和不會太大。必須改為每個詢問只初始化該組詢問會影響到的記憶體。
多組詢問裡每次詢問都開一個很大的 vector 或陣列(忘記動態的宣告 vector 或陣列時，vector 或陣列的初始化也要花時間)
一個檔案有多組測試資料時，還沒讀完所有 input 就 return 或 break 或 continue 了(尤其容易錯在有特判 case 的時候)


C 語法和 Python 的差別

比較運算子的用法
int a = 1, b = 4, c = 3;
if(a < b < c) { // 錯誤寫法
    cout << "a < b and b < c\n";
} else {
    cout << "a >= b or b >= c\n";
}
if(a < b && b < c) { // 正確寫法
    cout << "a < b and b < c\n";
} else {
    cout << "a >= b or b >= c\n";
}
a = 1
b = 4
c = 3
if a < b < c:
    print("1 < 4 < 3")
else:
    print("not 1 < 4 < 3")
a = -3
b = -2
c = -1
if a < b < c:
    print("-3 < -2 < -1")
else:
    print("not -3 < -2 < -1")

整數除法和取餘的規則 (CF 597 A. Divisibility)
if else 匹配方式

int x = 4;
if(x > 2)
    if(x == 3) cout << "x == 3\n";
else cout << "x <= 2\n";
cout << "Done\n";
x = 4
if x > 2:
    if x < 3: print("x is 3")
else: print("x <= 2")
print("Done")


C++ 語法相關

記錯運算符號的優先順序

且(&&)的優先級高於或(||)
位元運算和其他運算的優先順序


沒把型態為 unsigned int 的 size() 轉型成 int
忘記傳參數 pass by value 是複製整個 object，執行時間和 object 大小有關
函數傳的參數是陣列時，並無法使用 sizeof 取得陣列大小
對 vector 使用 Ranged-based for，卻在迴圈裡修改 vector 大小。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> d{1, 2};
    for (int x : d) {
        cout << x << '\n';
        if (x <= 5) d.push_back(x + 2);
    }
}


邏輯控制

continue, break, return 搞混
if 裡忘記 return 或 break (尤其是在判斷 special case 時)
if,else if 搞混


unspecified behavior


a[i] = i++; 這類一個 expression 裡使用對一個變數 Increment/decrement operators 卻讓該變數出現 2 次以上。

cin >> x >> a[x]; 可能會先讀入 a[x] 在讀入 x。只要在一個 expression 裡中括號取值運算以及放在索引值的那個變數也會做改變，就可能會出問題，在 C++ 17 以後才有嚴格定義。(類似狀況：https://codeforces.com/blog/entry/51324)


變數或狀態初值

以初值為 0 或 -1 代表一個還沒被處理過的狀態，但沒考慮到就算處理過也有可能是 0 或 -1
代表無限大或無限小的初值設得不夠大或不夠小
初值是無限大時，設為 INT_MAX 或 LLONG_MAX，但卻把它拿去運算造成 integer overflow


內建函式或語法誤用導致 Time Limit Exceed

誤以為 strlen() 的時間複雜度是 O(1)。
實際上執行時間是 O(len), len 為字串長度)
誤以為 vector 的 insert()、erase() 的時間複雜度是 O(1)。
實際上執行時間和插入、移除的位置至 end() 的距離有關
對於關聯容器的 lower_bound()、upper_bound() 使用方法錯誤
    set<int> s;
    auto it = lower_bound(s.begin(), s.end(), v); // 錯誤，時間複雜度和 s 大小有關
    auto it2 = s.lower_bound(v); // 正確，時間複雜度為 O(log(s.size()))

unordered_set / unordereed_map 的成員函式 clear() 的時間複雜度和 bucket 的 size 有關，若一個檔案有多組測試資料，第一個詢問就先插入很多東西，第二個詢問以後就每個詢問只插入一個東西，就會超時。(相關討論：https://codeforces.com/blog/entry/127773)


內建函式或語法誤用導致 Wrong Answer(或 RE)

accumulate() 的誤用 參考程式碼

誤以為 isdigit()、isupper()、islower() 等函式當成立時是回傳 1(實際上是回傳非零的數)
使用 pow()、sqrt() 等數學函式會造成誤差
vector 套 vector 用 resize() 調整大小會出問題，應該要使用 assign。
    vector<vector<int>> d(3, vector<int>(2));
    d.resize(4, vector<int>(3));
    /* 執行完此行後，vector 會長相如下：
     * {
     *     {0, 0},
     *     {0, 0},
     *     {0, 0},
     *     {0, 0, 0},
     * }
     */


內建函式或語法誤用發生未定義行為

sort 的比較函式在兩物件相等時回傳 true
__log()、__builtin_clz()、__builtin_ctz() 等函式傳入 0


特定主題的 Bug 列表


和排列有關的題

把排列和排列的反函數搞反，例如，題目要你輸出數字 i 的位置在哪，你卻輸出成第 i 個位置得數字是什麼。


排序

起手步是排序但忘記寫，並且範例測試資料也不會因此出錯
sort 沒有規定等價的物件會按照原來的順序排列，stable_sort 才會
排序時所用的比較函式在兩個物件相等時回傳 true 會造成錯誤， WA,RE,TLE 都是有可能再犯此錯誤使取得的評測結果。(因為比較函式是在定義「小於」的關係，若兩物 x 和 y 相等，x 並沒有小於 y。)


答案需要對某個值取餘輸出的題

最後的答案沒有取餘
計算過程中因為有減法，可能最終答案是負的，必須把它調成為非負的(也就是說最終答案要加上 if(ans<0)ans+=MOD;)
if(x >= MOD) x -= MOD; 中的 >= 寫成 >
special case、初值忘記取餘(尤其是模數為 1 的時候)
計算過程 overflow


二維地圖實作

編號從 0 開始和從 1 開始搞混
座標編號方式和題目不一樣。例如寫成 (x,y) 是從左往右第 x 個數,從下往上第 y 個數，但題目的描述卻是從上往下第 x 個數，從左往右第 y 個數。
地圖長和寬的變數使用搞混
使用到超出邊界的位置


位元運算與位元相關函式

2 的 n 次方在程式碼裡寫成 2 << n

2 的 n 次方的運算結果在 long long 範圍時，寫成 1 << n，但應為 1LL << n，就算 n 是 long long 型態也會錯，這是使用 #define int long long 也無法避免 integer overflow 的少數例子之一
搞錯位元運算和其他運算的優先級，例如說，以為 2 的 n 次方再加 1 可寫成 1 << n + 1，但實際上必須寫成 (1 << n) + 1。
不知道使用 a << b 或 a >> b 時，b 的值大於等於 a 的資料型態的位元數或 b < 0 時是未定義行為。
// 
#include <iostream>
using namespace std;           
int main() {
    int x;
    cin >> x; // try entering 128 or -1 as input
    cout << (1 << x) << '\n'; // undefined behavior: shifting left by 128 bits exceeds int width
    cout << (1 >> x) << '\n'; // undefined behavior: shifting right by 128 bits exceeds int width
}

不知道使用 a << b 時，a << b 的運算結果超過 a 的資料型態所能儲存的範圍是未定義行為
#include <iostream>
using namespace std;           
int main() {
    cout << (1 << 32LL) << '\n';
}


a << b 在 a 是負數的時候，是未定義行為

a >> b 在 a 是負數的時候，C++17 以前是實作定義行為
cout 一個含有位元運算的表達式時，忘記把表達式加括號，可能會編譯錯誤或輸出非預期的東西
    int n = 5;
    cout << 1 << n << endl; // 輸出非預期結果
    int a = 2;
    int b = 3;
    cout << a ^ b << endl; // 編譯錯誤

builtin 系列函式當傳入的參數是 long long 資料型態時，應加上 ll 的後綴
__lg()、__builtin_ctz()、__builtin_clz() 等函式傳入的參數為 0 時是未定義行為
沒使用 #pragma GCC target("lzcnt,popcnt") 導致 __builtin_popcount 和 __builtin_ctz 不夠快 (但照理說競程不該考這種東西...)


關聯容器(Associative Containers)
共通注意事項：

沒使用成員函式的 lower_bound、upper_bound，而去使用 <algorithm> 中的 lower_bound、upper_bound 造成 TLE

set<int> d{1,2,3};
lower_bound(d.begin(),d.end(), 2); // 錯誤,時間複雜度為O(d 的大小)
d.lower_bound(2); // 正確


用太多關聯容器 $O(\log{n})$ 時間複雜度的成員函式如 insert、erase、find、lower_bound、upper_bound 等導致 TLE
iterator 指在 begin() 的位置時再把此 iterator -- 是未定義(指在 end() 時再 ++ 也是未定義)(cppreference 說明)
若 iterator ptr 已失效或指在 end() 的位置，使用 erase(ptr) 或 *ptr 等都是未定義行為
當一個 iteartor 被 erase 後，該 iterator 就失效，不能再使用，舉例來說，以下程式碼會出錯：

// 讀入 n 個數的多重集，有 m 次操作，每次操作給定一個數 x，移除多重集裡 >= x 的最小的數，並把所有移除的數總和輸出
int n, m;
multiset<int> d;
cin >> n >> m;
while(n--) {
    int x;
    cin >> x;
    d.insert(x);
}
long long ans = 0;
while(m--) {
    int x;
    cin >> x;
    auto it = d.lower_bound(x);
    d.erase(it);
    ans += *it; // 此為錯誤寫法，正確寫法應把此行放在 erase 之前
    
}
cout << ans << '\n';

multiset 的陷阱：

呼叫 T.erase(x) 時，會把 container 裡所有的 x 都移除，若只想移除恰一個 x，必須使用T.erase(T.find(x));
若使用 count(x) 來判斷容器裡是否存在至少一個 x 有機會超時，因為 count(x) 的執行時間正比於 x 在 container 裡的數量，應使用 T.find(x) != T.end() 來判斷

測試程式碼


map 的陷阱：

對於 map<T1,T2> A，只要使用了 A[x] 就相當於在 A 裡面插入的 key 為 x 的東西，有些問題 map 裡只有 N 個東西，但會需要詢問 Q 次 map 是否有 key 為某個值的東西，若使用 [] 來判斷 map 裡是否有某個東西，就會讓 A 裡的元素數量高達 $O(N + Q)$，可能因此超時。


二分搜
    // 設 valid() 為先 false 再 true 的單調函式，以下為尋找使得 valid(x) = true 的最小的 x 值
    int low = 0, hi = INF; // [low, hi] 是在維護答案還有可能存在範圍
    while(low < hi) {
        int mid = low + (hi - low) / 2;
        if(valid(mid)) hi = mid;
        else low = mid + 1;
    }
    cout << "answer is " << low << '\n';

答案的範圍設錯 (low 設太大或 hi 設太小)
valid() 函式裡的運算發生 integer overflow
若使用 mid = (low + hi) / 2，可能問題有二：(1) 當答案範圍接近整數資料型態上界時，會 overflow，(2) 當答案範圍包含負數時，可能陷入無窮循環
浮點數二分搜使用 while(low + eps < hi) 但答案範圍太大時可能會超時，改執行固定次數是比較安全的寫法

若使用其他二分搜寫法，可能有其他類型的問題會發生，這裡就不列出了。


圖論相關問題

讀題時沒看清楚題目是否有所有點是連通的這個條件，若不連通可能會有更多瑣碎細節要處理。
讀題時沒看清楚題目是單向邊還是雙向邊以至於細節寫錯，且有些題在單/雙向邊的解法並不同。
讀題時沒看清楚題目會不會有重邊或自連邊，若有重邊或有自連邊可能會有更多瑣碎細節要處理。


DFS 等圖論相關問題

DFS 時，忘記標記一個點是否走過，或忘記遇到標記過的點就 return（尤其是在 DAG 的問題犯這個 Bug 也可以通過測資）
DFS 時，雖然有標記一個點已經走過，但離開地回函式時起把標既取消以至於超時(這樣的 DFS 時間複雜度是指數量級)
遇到非連通圖的問題時，忘記每個點都要當起點 DFS 一次


動態規劃問題

初始狀態的初值給錯
不合法的狀態的值也轉移到合法的狀態
用 dp 值是否大於 $0$ 來判斷是否拜一個狀態已經算喔，但實際上狀態的答案可能是 $0$ ($0$ 只是個舉例，也有可能是 $-1$)
沒有按照拓撲排序的順序計算 DP 每個狀態的值
計數題要求輸出答案對 $P$ 取餘的結果，且範圍必須落在 $[0, P-1]$ 之間，但卻因為計算過程中有減法而造成輸出有負數
push 的思維也使用 DFS 的寫法


Dijkstra

同一個點從 priority_queue 裡拿出來的每一次都會枚舉他相鄰的所有邊，時間複雜度變為 O(n^2 log n)，如下：


    while(!pq.empty()){
        now = pq.top();
        pq.pop();
        
        for(auto x : adj[now.second]){
            if( dis[now.second] + x.second <  dis[x.first] ){
               dis[x.first] = dis[now.second] + x.second ;
                pq.push(mkpr(dis[x.first], x.first));
            }
        }
   }

倍增法

倍增法時常需要計算不超過 n 的最大的 2 的幂次方，若此件事用 log(n) 的時間計算且每組詢問又重複計算這樣的事情 log(n) 次，將會使得時間複雜度變為 $O(Q \log{n}^2)$ 以致於超時。
使用 __lg() 函式時不小心傳入 0 導致不可預期結果(此為未定義行為)。


BIT

詢問時詢問到位置 0，也就是程式碼會執行 pos = 0; for(;pos <= n; pos += pos & -pos) ans += bit[pos]; 造成超時。


線段樹

線段樹大小只開 2n，而不是 4n。
線段樹區間修改或區間詢問的部分 return 的條件寫錯，導致遞迴至區間裡的每個葉子節點。


相關資源


USACO GUIDE: How to Debug
YouKn0wWho Common Mistakes