# 競賽基本知識 Wiwi Ho ###### tags: `CRC` --- https://hackmd.io/@wiwiho/crc1082algo  --- # 複雜度分析 --- # 什麼是複雜度？ ---- 有一個函數 $f(n)$ 它的值跟 $n$ 有什麼關係？ ---- $f(n)=n^2+2n-1$ ---- $n^2$ 對 $f(n)$ 的值影響最大 $\Rightarrow$ $f(n) \in O(n^2)$ ---- ## Big-O notation 對於兩個函數 $f(n)$ 和 $g(n)$ 若存在正數 $c$ 和 $n_0$ 滿足所有的 $n \geq n_0$ 都符合 $f(n) \leq cg(n)$ 則 $f(n) \in O(g(n))$ ----  ---- ## 複雜度怎麼求 只留最高次項 且把係數拿掉 ---- ## 比大小 複雜度越大 表示函數值成長越快 ---- ## 怎麼比（嚴謹定義） $\lim_{n \to \infty} \frac{g(x)}{f(x)}$ - 無限大：$O(g(n))>O(f(n))$ - $0$：$O(g(n))<O(f(n))$ - 非零常數：$O(g(n))=O(f(n))$ ---- 如果 $O(g(n))>O(f(n))$ $O(f(n)) \in O(g(n))$ $\Rightarrow 2n^2+n-1 \in O(2n^2+n-1) \in O(n^2) \in O(n^3)$ ---- 複雜度非唯一 通常會選最小而且寫出來最簡單的 --- # 用詞 ---- 常數：$O(1)$ ---- 線性：$O(n)$ ---- 其他應該很好懂 (? e.g. 對數（$O(\log n)$）、根號（$\sqrt{n}$）…… --- # STL 的複雜度 ---- 查表 cppreference.com --- # 時間複雜度 ---- 表示程式的執行時間如何隨輸入的數值成長 $\Rightarrow$ 用來比較演算法好壞的方法 ---- ## 會用多少時間？ ---- 不能準確計算 ---- 把所有參數的最大值代入後 約 $10^8$ 到 $10^9$ 為一秒 ---- ## 範例 ---- ```cpp int n; cin >> n; vector<int> v(n); for(int i = 0; i < n; i++) cin >> v[i]; for(int i = 0; i < n - 1; i++){ //迴圈 1 for(int j = 0; j < n - i - 1; j++){ //迴圈 2 if(v[j] > v[j + 1]) swap(v[j], v[j + 1]); } } for(int i = 0; i < n; i++) cout << v[i] << " "; cout << "\n"; ``` ---- ```cpp int n; cin >> n; stack<int> st; for(int i = 0; i < n; i++){ int t; cin >> t; while(!st.empty() && st.top() <= t) st.pop(); if(st.empty()) cout << "-1 "; else cout << st.top() << " ", st.pop(); st.push(t); } cout << "\n"; ``` --- # 常數 ---- 被丟掉的常數 ---- 常數重要嗎？ ---- 當然重要！ ---- ```cpp for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < 10; k++) /*...*/; } } ``` ---- 時間複雜度 $O(n^2)$ 如果 $n \leq 10000$ $n^2=10^8$ ---- 好像勉強還行？ ---- 那個 10 呢？ $10n^2=10^9$ ---- 可能不太行 ---- 如果常數會造成時間剛好超過 那就很重要 ---- ## 看不到的常數 ---- 加、減、乘、除、模都是 $O(1)$ 但除和模需要比較多時間 ---- unordered_set、unordered_map 的插入刪除尋找都是 $O(1)$ 但常數很大 --- # 輸入輸出 --- # 各種流 ---- 輸入流、輸出流？ ---- 什麼是流？ ----  ---- 輸出流：把東西給它，它會負責輸出到某地方 輸入流：跟它要一個東西，它會負責從某個地方拿給你 ----  --- # 標準流 ---- - 標準輸入流 - cin - 標準輸出流 - cout - 標準錯誤流 - cerr ---- 預設：在 terminal 輸入輸出 可以重新導向成在檔案輸入輸出 ---- ## 錯誤流 一種輸出流 用來輸出錯誤訊息 不會被 judge 讀到 ---- ## 重新導向 ---- ## 在程式碼 ```cpp freopen("filename", "w", stdout); freopen("filename", "w", stderr); freopen("filename", "r", stdin); ``` ---- ## 在 terminal ``` command < in command > out command 2> err command < in > out 2> err command < in > out ``` ---- ## 緩衝區 ---- ## cin 輸入的東西先到緩衝區 程式讀取的時候會從緩衝區拿資料 ---- ## cout 輸出的東西先到緩衝區 flush 後再真的輸出到它該去的地方 ---- ## cerr 沒有緩衝區 會馬上輸出到它該去的地方 --- ## stringstream ---- 一種 iostream $\Rightarrow$ 是輸入流也是輸出流 ---- ```cpp stringstream ss; ss << 5; int t; ss >> t; cout << t << "\n"; ``` --- # 輸入輸出優化 ----  ---- 效率太差？ ---- 來看看它為什麼差 ---- 輸出到 terminal 或檔案裡的常數很大 ---- ## cout 自動 flush - endl = << '\n' << flush - 使用 cin 時會自動 flush cout - 使用 cerr 時會自動 flush cout - 程式結束時強制 flush ---- - 不要用 endl - cin.tie(0) - cerr.tie(0) - 在最後讓程式自己 flush 就好了 ---- ## 歷史因素 要和 scanf/printf 同步 ---- ios_base::sync_with_stdio(false) --- # 運算子重載 ---- ```cpp ostream& operator<<(ostream& o, pair<int, int> p){ return o << p.first << " " << p.second; } istream& operator>>(istream& i, pair<int, int> p){ return i >> p.first >> p.second; } ``` --- # 輸入格式 ---- ## EOF ---- EOF = End Of Line ---- 某些題目： 一個檔案有多筆測資 而且不告訴你有幾筆 ---- ```cpp while(cin >> /*...*/){ //... } ``` ---- ## terminal 不是 file？ 按 ctrl+z 或 ctrl+d 製造 EOF ---- ## 輸入一整行 ---- ```cpp string s; getline(in, s); //in 是輸入流 ``` ---- ## 跟 >> 混用 ---- ``` abc abcd abcd ``` ```cpp string a, b; cin >> a; getline(cin, b); ``` ---- 預期：a=abc，b=abcd abcd 實際：a=abc，b=空字串 ---- 多 getline 一次 ---- ## 忽略輸入 ZJ c268： 給你一堆數字，找三個數字當三角形邊長 ---- $O(n \log n)$ 可以嗎？ ---- $n \leq 10^7$ 太多了吧 ---- $n \geq 50$ 保證有解 所以超過 50 項就可以不用讀了 ---- 可是一個檔案多測資，怎麼辦？ ---- 把輸入忽略掉 ```cpp cin.ignore(1000000000, '\n'); ``` --- # 輸出格式 ---- ## 小數位數 ---- ```cpp cout << fixed << setprecision(10) << ...; ``` ---- ## 數字寬度 ---- ```cpp cout << setw(n) << setfill(c) << ...; ``` --- # 前置處理器 --- # 什麼是前置處理器？ ---- 在編譯之前，會先做前置處理 ---- ```cpp #include ... #define ... ``` 都是前置處理器的指令 ---- ## 什麼是前置處理？ 根據指令修改程式碼 ---- ## include ---- 把別的檔案的內容在該處貼上 ---- ## 引號、角括號？ ```cpp #include <iostream> #include "test.cpp" ``` ---- 找檔案的地方不同 - 角括號：找函式庫 - 引號：找同個目錄 --- ## define ---- macro/ 巨集 / 宏 ---- ```cpp //#define NDEBUG #include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define mp(a, b) make_pair(a, b) #define pb(a) push_back(a) #define eb(a) emplace_back(a) #define pf(a) push_front(a) #define pob pop_back() #define pof pop_front() #define F first #define S second #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} #define pii pair<int, int> #define pll pair<ll, ll> #define tiii tuple<int, int, int> #define mt make_tuple #define gt(t, i) get<i>(t) #define iceil(a, b) ((a) / (b) + !!((a) % (b))) //#define TEST typedef long long ll; typedef unsigned long long ull; using namespace std; using namespace __gnu_pbds; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } int main(){ StarBurstStream return 0; } ``` ---- ```cpp #define a b ``` 把所有單字 a 換成 b ---- 也可以用 function ```cpp #define f(a) a+4 ``` ---- 換行 ```cpp #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ ``` ---- 一樣嗎？ ```cpp #define f(a) a + 5 //... cout << (3 * f(1)); ``` ```cpp int f(int a){ return a + 5; } //... cout << (3 * f(1)); ``` ---- ## 條件判斷 ---- ```cpp #if ... ... #elif ... ... #else ... #endif ``` ---- 符合條件的地方才會留下來 ---- ```cpp #if defined(a) #ifdef (a) #if !defined(a) #ifndef (a) ``` 判斷 a 有沒有被 define 過 --- 去寫練習題