--- ###### tags: `2020 師大附中校隊培訓` --- # 競賽導論 ## 2020 師大附中校隊培訓 #### joylintp #### 10.26.2020 --- ## bits/stdc++.h ```cpp= #include<bits/stdc++.h> ``` ---- ```bits/stdc++.h``` 引入大部分的常用標頭檔 引入此標頭檔即可使用大部分函數 --- ## 輸入優化 ```cpp= ios_base::sync_with_stdio(false); cin.tie(0); ``` ---- 加速 `cin` 函數 使用輸入優化後所有輸入會在緩衝區已滿或程式結束後全部輸出 並且不可再使用 ```scanf```、```printf``` ---- 有關於 ```cin```、```scanf```、輸入優化等說明 可參考此文章: C++的輸出入cin/cout和scanf/printf誰比較快？ 連結: https://tg.pe/x3dN --- ## define ```cpp= #define A B ``` ---- 將程式碼中的 `A` 取代成 `B` 可縮短程式碼並加快 coding 速度 ---- 在以下的程式碼中，```push_back``` 指令被自訂了一個新的名稱 ```PB``` ```cpp= #define PB push_back // ... v.push_back(5); v.PB(5); // 兩行功能相同 ``` ---- 也可以將 `for` 迴圈等 `define` 成較短的名稱 ```cpp= #define REP(i, n) for(int i=0; i<int(n); i++) // ... for (int i = 0; i < n; i++) cout << arr[i] << ' '; REP (i, n) cout << arr[i]; // 兩行功能相同 ``` ---- 注意 `define` 不會影響運算優先順序 ```cpp= #define MUL(a, b) a*b // ... cout << MUL(3+3, 5+5) << '\n'; // 3+3*5+5 = 3+15+5 = 23 ``` ```cpp= #define MUL(a, b) (a)*(b) // ... cout << MUL(3+3, 5+5) << '\n'; // (3+3)*(5+5) = 6*10 = 60 ``` ---- 以下是其他常見的用法，供大家參考。 ```cpp= #define ALL(X) X.begin(),X.end() #define SORTA(X) sort(ALL(X)) #define SZ(X) (int)X.size() ``` --- ## 重新定義型別名 ```cpp= using A = B; ``` ---- 使用 ```using``` 將資料型態自訂成較短的名稱 ```cpp= using LL = long long; // 自訂LL即代表long long型態 using pii = pair<int, int>; using pll = pair<LL, LL>; ``` --- ## auto ```cpp= auto iter = v.begin(); ``` ---- ```auto``` 可以自動判斷變數型態，使用時變數必須被賦值 例如以下程式碼中 `iter1`、`iter2` 兩者相同 ```cpp= vector<int> v; auto iter1 = v.begin(); vector<int>::iterator iter2 = v.begin(); ``` --- ## Range-based for ```cpp= vector<int> v = {1, 2, 3, 4, 5}; for (int i : v) cout << i << '\n'; ``` ---- 對於可以遍歷元素的 STL， Range-based for 的迴圈可對其中的內容逐個存取 ```cpp= vector<int> v = {1, 2, 3, 4, 5}; for (auto i : v) cout << i << '\n'; for (int i : v) cout << i << '\n'; for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) cout << *iter << '\n'; // 三迴圈功能相同 ``` ---- 若在存取的過程中想要修改資料，則需使用reference。 ```cpp= vector<int> v = {1, 2, 3, 4, 5}; for (auto &i : v) i += 5; for (auto i : v) cout << i << ' '; // 6 7 8 9 10 ``` --- ## 複雜度 在資訊競賽上，分析演算法和資料結構的複雜度是一件很重要的事 ---- ## Big O Notation 大O函數，表示函數複雜度的上界 以下為大O符號的定義： > 定義$f(n) \in O(g(n))$若且唯若 $∃c, N \in \mathbb{R}^+,∀n \ge N$有$|f(n)|\le|cg(n)|$ --- ## 估計時間複雜度 將每個運算當成花費一單位時間（$O(1)$） 把所有迴圈、遞迴等操作統合起來，即會得到程式碼的時間複雜度函數 $f(n)$ 再由 $n$ 的範圍估算程式所需的執行時間 ---- 如以下泡沫排序程式碼複雜度為 $O(n^2)$ ```cpp= void bsort(int arr[], int n) { for(int i = 0; i < n; i++) for(int j = 1; j < n - i; j--) if(arr[j] < arr[j - 1]) swap(arr[j], arr[j - 1]); } ``` ---- 在C/C++語言中，電腦每秒約能進行 10⁸ 到 10⁹ 次的運算 將題目的數字範圍代入複雜度中可以進行執行時間的估算 ---- 以下為一些常見的時間複雜度： $O(1) < O(log\ n) < O(n) < O(n\ log\ n) < O(n^2)$ $O(n^3) < O(2^n) < O(n!)$ ---- 而下圖為各時間複雜度的運算量趨勢  ---- 藉由輸入資料的大小範圍，亦可判斷應該使用哪種複雜度的演算法 |輸入資料大小|時間複雜度| |-|-| |$n \le 10$|$O(n!)$| |$n \le 20$|$O(2^n)$| |$n \le 500$|$O(n^3)$| |$n \le 5000$|$O(n^2)$| |$n \le 10^6$|$O(n\ log\ n)或O(n)$| |$n \ge 10^9$|$O(log\ n)或O(1)$| --- ## 時間複雜度判斷練習 ---- ```cpp= bool isprime = true; for (int i = 2; i * i <= n; i++) if (n % i == 0) { isprime = false; break; } ``` → $O(\sqrt{n})$ ---- ```cpp= vector<int> bin; while (n) bin.push_back(n % 2), n /= 2; reverse(bin.begin(), bin.end()); ``` → $O(\log{n})$ ---- ```cpp= int c = a + b; int d = a * c; ``` → $O(1)$ ---- ```cpp= for (int i = 0; i < n; i++) { while (i < n && arr[i] < k) i++; v.push_back(i); } ``` → $O(n)$ ---- ```cpp= priority_queue<int> pq; for (int i = 0; i < n; i++) pq.push(arr[i]); ``` → $O(n\log{n})$ → 並非所有操作都是常數時間（$O(1)$）內完成 ---- ```cpp= int gcd(int a, int b) { if (a == 0) return b; else return gcd(b % a, a); } ``` → $O(\log{max(a, b)})$