# 競賽基本知識
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 過
---
去寫練習題
Google Drive
Gist
Clipboard
Sign in with Wallet
