OI 做題的常見錯誤

會引起 Compile Error 的錯誤

由於這類錯誤過於簡單，相信是個正常人都會修，故略寫。

  • int main() 寫為 int mian() 。

  • 寫完 struct 或 class 忘記寫分號。

  • 數組開太大，（在 OJ 上）使用了不合法的函數（例如多線程），或者函數聲明但未定義，會引起鏈接錯誤。

  • 使用 algorithm 中的 max 函數時，一個參數類型為 int 而另一個參數類型為 long long

    • 示例：

      printf("%lld\n", max(0, query(1, 1, n, l, r)); // query 返回 long long 類型

  • goto 的時候，跳過了一些局部變量的初始化。

-    `switch-case` 的時候，跳過了一些局部變量的初始化。

不會引起 Compile Error 但會引發 Warning 的錯誤

這類錯誤較難發現，但會在使用 -W{warningtype} 參數編譯時被編譯器指出，所以要多學會使用 -W{warningtype} 參數，常見的有 -Wall ， -Wextra ， -Wshadow 等。

  • 由於運算符優先級產生的錯誤。
    • 1 << 1 + 1 : 1 左移了 2，即該表達式返回的值是 4。
  • 不正確地使用 static 修飾符。
  • -1 >> 1 == 1 。
  • 賦值運算符和 == 不分。
    • 示例： cpp if (n = 1) puts("Yes"); else puts("No"); 無論 \(n\) 的值之前為多少，輸出肯定是 Yes 。 Tips: 如果你的確是想在 if / while 直接用賦值運算符（比如 while (foo = bar) ），又不想收到 Warning，可以使用 雙括號 ： while ((foo = bar)) 。
  • 使用 scanf 讀入的時候沒加取地址符 & 。更一般地，使用 scanf 或 printf 的時候參數類型與格式指定符不符。
  • 沒有考慮數組下標出現負數的情況。
  • 同時使用位運算和邏輯運算符（ == ）並且未加括號（例如 (x>>j)&3==2 ）。
  • int 字面量溢出，例如： long long x = 0x7f7f7f7f7f7f7f7f ， 1<<62 。
  • 未初始化局部變量，導致局部變量被賦予垃圾初值。
  • 局部變量與全局變量重名，導致全局變量被意外覆蓋。（開 -Wshadow 就可檢查此類錯誤。）

既不會引起 Compile Error 也不會引發 Warning 的錯誤

這類錯誤無法被編譯器發現，所以在調試時只能依靠你自己。

會導致 WA

  • 多組數據未清空數組。

  • 讀入優化未判斷負數。

  • 所用數據類型不夠大導致溢出，即常見的「三年 OI 一場空，不開 long long 見祖宗」，意思是因為沒有使用 long long （開 long long ）導致大量丟分從而賽季作廢。

  • 存圖時，節點編號 0 開始，而題目給的邊中兩個端點的編號從 1 開始，讀入的時候忘記 -1。

  • 大/小於號打錯或打反。

  • 在執行 ios::sync_with_stdio(false); 後混用兩種 IO，導致輸入/輸出錯亂。

    • 可以參考這個例子。

      // 這個例子將說明，關閉與 stdio 的同步後，混用兩種 IO 的後果
// 建議單步運行來觀察效果
#include <cstdio>
#include <iostream>
int main() {
  std::ios::sync_with_stdio(false);
  // 關閉同步後，cin/cout 將使用獨立緩衝區，而不是將輸出同步至 scanf/printf
  // 的緩衝區，從而減少 IO 耗時
  std::cout << "a\n";
  // cout 下，使用'\n'換行時，內容會被緩衝而不會被立刻輸出，應該使用 endl
  // 來換行並立刻刷新緩衝區
  printf("b\n");
  // printf 的 '\n' 會刷新 printf 的緩衝區，導致輸出錯位
  std::cout << "c\n";
  return 0;  //程序結束時，cout 的緩衝區才會被輸出
}

    • 特別的，也不能在執行 ios::sync_with_stdio(false); 後使用 freopen 。

  • 由於宏的展開，且未加括號導致的錯誤：

    #define square(x) x* x
printf("%d", square(2 + 2));

    該宏返回的值並非 \(4^2 = 16\) 而是 \(2+2\times 2+2 = 8\) 。

  • 哈希的時候沒有使用 unsigned ，因為對負數的右移運算會在最高位補 1，詳見 位運算

  • 沒有刪除調試信息。

  • 誤加了 ; 。

    • 可以參考這個例子：

      /* clang-format off */
while (1);
    printf("OI Wiki!\n");

  • 沒有正確設置哨兵值。例如，平衡樹的 0 節點。

  • 在類或結構體的構造函數中，使用 : 初始化變量，且變量聲明順序不符合初始化時候的依賴關係。因為成員變量的初始化順序只與它們在類中聲明的順序有關，而與在初始化列表中的順序無關。

  • 並查集合併集合時沒有把兩個元素的祖先合併：

f[a] = b;              //錯誤
f[find(a)] = find(b);  // 正確

會導致 RE

  • 對整數除以 \(0\) 。

    • 對 \(0\) 求逆元。

  • 沒刪文件操作（某些 OJ）。

  • 排序時比較函數的錯誤 std::sort 要求比較函數是嚴格弱序： a<a 為 false ；若 a<b 為 true ，則 b<a 為 false ；若 a<b 為 true 且 b<c 為 true ，則 a<c 為 true 。其中要特別注意第二點。 如果不滿足上述要求，排序時很可能會 RE。 例如，編寫莫隊的奇偶性排序時，這樣寫是錯誤的：

    bool operator<(const int a, const int b) {
  if (block[a.l] == block[b.l])
    return (block[a.l] & 1) ^ (a.r < b.r);
  else
    return block[a.l] < block[b.l];

    上述代碼中 (block[a.l]&1)^(a.r<b.r) 不滿足嚴格弱序的要求 2。 改成這樣就正確了。

    bool operator<(const int a, const int b) {
  if (block[a.l] == block[b.l])
    return (block[a.l] & 1) ? (a.r < b.r) : (a.r > b.r);
  else
    return block[a.l] < block[b.l];

  • 解引用空指針。

會導致 TLE

  • 分治未判邊界導致死遞歸。

  • 死循環。

    • 循環變量重名。
    • 循環方向反了。

  • BFS 時不標記某個狀態是否已訪問過。

  • 使用宏展開編寫 min/max

    這種做法雖然算不上是「錯誤」，但是這裡還是要拎出來說一下。

    常見的寫法是這樣的：

    #define Min(x, y) ((x) < (y) ? (x) : (y))
#define Max(x, y) ((x) > (y) ? (x) : (y))

    這樣寫雖然在正確性上沒有問題，但是如果你直接對函數的返回值取 max，如 a = Max(func1(), func2()) ，而這個函數的運行時間較長，則會大大影響程序的性能，因為宏展開後是 a = func1() > func2() ? func1() : func2() 的形式，調用了三次函數，比正常的 max 函數多調用了一次。

    這種錯誤在初學者寫線段樹時尤為多見，會大大增加程序的運行時間，甚至直接影響代碼的時間複雜度。例如這份錯誤代碼：

    #define max(x, y) ((x) > (y) ? (x) : (y))

int query(int t, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) {
    ++ti[t];  // 記錄結點訪問次數方便測試
    return vi[t];
  }

  int mid = (l + r) >> 1;
  if (mid >= qr) {
    return query(lt(t), l, mid, ql, qr);
  }
  if (mid < ql) {
    return query(rt(t), mid + 1, r, ql, qr);
  }
  return max(query(lt(t), l, mid, ql, qr), query(rt(t), mid + 1, r, ql, qr));
}

    會被卡到單次查詢 \(\Theta(n)\) 導致 TLE。

  • 沒刪文件操作（某些 OJ）。

  • for (int i = 0; i < strlen(s); ++i) ：在循環中重複執行複雜度非 \(O(1)\) 的函數。（嚴格來說，這可能會引起時間複雜度的改變。）

會導致 MLE

  • 數組過大。
  • STL 容器中插入了過多的元素。
    • 經常是在一個會向 STL 插入元素的循環中死循環了。
    • 也有可能被卡了。

未定義行為

  • 數組越界。上下都算。（多數是 RE。）
    • 未正確設置循環的初值導致訪問了下標為 -1 的值。
    • 無向圖邊表未開 2 倍。
    • 線段樹未開 4 倍空間。
    • 看錯數據範圍，少打一個零。
    • 錯誤預估了算法的空間複雜度。
    • 寫線段樹的時候， pushup 或 pushdown 葉節點。
  • 解引用野指針。
    • 未初始化就解引用指針。
    • 指針指向的區域已經 free 或 delete 。

會導致常數過大

  • 定義模數的時候，使用了全局變量（如 int mod = 998244353 ，為方便編譯器按常量處理，正確做法是 const int mod = 998244353 ）。
  • 使用了不必要的遞歸（需要注意的是，尾遞歸不在此列）。
  • 將遞歸轉化成迭代的時候，引入了大量額外運算。

只在程序在本地運行的時候造成影響的錯誤

  • 文件操作有可能會發生的錯誤：
    • 對拍時未清除文件指針即 fclose(fp) 就又令 fp = fopen() , 這會使得進程出現大量的文件野指針。
    • freopen() 中的文件名未加 .in / .out 。
  • 使用堆空間忘記 delete 或 free 。
Tags:

VirMach 便宜 VPS

QNews

QNews