# 演算法小補帖

## 必備前置技能

### 語言常識

大數題一律選 Python，否則強烈建議選 C++。

- C 寫起來太不方便，Python 容易逾時。C++ 最主流。

### 題目判讀結果

- AC：過關
- WA：答案輸出錯誤
- TLE：逾時
- RE：丟出例外或 exit code 非零
- 除以 0
- stack overflow (e.g. 遞迴太深)
- MLE：記憶體用量太多
- 有些題庫網站沒有 MLE，將此歸類為 RE
- CE：編譯錯誤
- 像是漏掉一個分號之類的

### C++ 一次性 include 所有 std 的東東

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

### C++ 改善 IO 的技巧

當輸出量大時效果十分顯著。

cin.tie(false);                 // faster IO
ios::sync_with_stdio(false);    // faster IO

cout << "hello world" << endl;  // (X) bad; don't use endl
cout << "hello world\n";        // (O) good

注意此時 `cin` 不可與 `scanf` 並用；同理 `cout` 不可與 `printf` 並用。

### 複雜度評估

理想的複雜度為每秒 $O(5\times10^7)$ 至 $O(2\times10^8)$。

例如，某題目限時 2 秒，牽涉到一個數字 $N=3000$，你可以猜測答案複雜度是 $O(N^2 \log N)$，但不太可能是 $O(N^3)$。又例如某題目限時 1 秒。牽涉到兩個數字 $N=50, k=20$，也許答案的複雜度會是 $N(2^k)$，絕對不可能是 $N(k!)$。

用這種方式，你可以在寫題目先限制所需的時間複雜度，以及在 submit 之前預判自己的 code 是否會 TLE。

注意在討論演算法時，$\log$ 一律指 $\log_2$，這是一個共識。

## 練題網站

- [Zero Judge](https://zerojudge.tw/)
- [NCTU Formosa OJ](https://oj.nctu.edu.tw/signin/)
- [Kattis](https://open.kattis.com/)
- [Codeforces](https://codeforces.com/)
- [LeetCode](https://leetcode.com/)
- [AtCoder](https://atcoder.jp/)