# 110 選手班 - 基礎複習 ###### tags: `宜中資訊` `CP` Ccucumber12 2021.08.02 --- ## Outline - C/C++ - CP Techniques - CP knowledge - Complexity - Compiler - Competition --- ## C / C++ ---- ### Data Types - int (2e9) - long long (9e18) - char (ASCII) - string - double ---- ### Pointer / Reference - pointer to - int *pa ; - reference to - int &ra = a ; - dereference - cout << *ra << endl ; - address of - pa = &a ; ---- ### Ternary Operator ```c= int a = 3 ; int n = (a % 2 == 1 ? 10 : 20) ; // n = 10 // <statement> ? <if true> : <if false> ``` ---- ### Subroutine - parameter - Pass by value - Pass by reference - stack overflow ```c= int sum (int a, int b = 1) { return a + b ; } void swap(int &a, int &b) { int c = a ; a = b ; b = c ; } ``` ---- ### Struct ```c= struct info { int a, b; char c ; info (int _a, char _c) { a = _a ; c = _c ; b = 1 ; } int sum () { return a + b ; } }; ``` ---- ### Bitwise Operation - OR: `|` - AND: `&` - XOR: `^` - NOT: `~` - shift: `<<` / `>>` ---- ### STL - stack - queue - deque - priority_queue - vector - pair ---- ### STL - set - map - unordered_set - unordered_map - multiset - bitset ---- ### Functions - sort() - stable_sort() - reverse() - unique() - next / prev _ permutation() ---- ### Functions - lower / upper _ bound() (set/map) - fixed + setprecision() - max() / min() - swap() - pow() * ---- ### Iterator - vector / set / map - next() / prev() ```c= #include<iostream> #include<iterator> #include<vector> using namespace std; int main(){ vector<int> ar = { 1, 2, 3, 4, 5 }; vector<int>::iterator ptr; for (ptr = ar.begin(); ptr < ar.end(); ptr++) cout << *ptr << " "; } ``` ---- ### Stringstream ```c= #include <sstream> strinstream ss ; string s ; getline(cin, s) ; ss << s ; int n ; while(ss >> n) { cout << n << endl ; } ``` ---- ### Random - rand() * - random_shuffle * - mt19937 ```c= #include <random> #include <chrono> unsigned seed = chrono::steady_clock::now().time_since_epoch().count(); mt19937 rng(seed); uniform_int_distribution<ll> dist(1, 1e18); int main(){ cout << rng() << endl; cout << dist(rng) << endl; shuffle(arr, arr+n, rng); } ``` ---- ### Fstream ```c= #include <fstream> fstream fin, fout ; fin.open("file_in.txt", ios::in) ; fout.open("file_out.txt", ios::out) ; int n ; fin >> n ; fout << n + 1 << endl ; fin.close() ; fout.close() ; ``` ---- ### C++ 11 - using - auto - range-based for - lambda - tie - tuple ---- ### Resource - https://www.cplusplus.com/ - https://en.cppreference.com/w/ - (accessible in competition) --- ## Competitive Programming Techniques ---- ### IO Optimization ```c= ios::sync_with_stdio(false); cin.tie(0) ; cout.tie(0) ; #define endl '\n' ``` ---- ### Define ```c= #define F first #define S second #define ALL(v) v.begin(),v.end() #define rep(i,n) for(int i=0;i<(n);++i) #define REP(i,a,b) for(int i=(a);i<=(b);++i) ``` ---- ### Debug ```c= #ifdef local #define debug(...) cerr<<"#"<<#__VA_ARGS__<<" = ";dbg(__VA_ARGS__); #else #define debug(...) template<typename T> void dbg(T x){ cerr<<x<<endl; } template<typename T, typename ...A> void dbg(T x, A ...y){ cerr<<x<<", "; dbg(y...);} ``` ---- ### Using ```c= using ll = long long using pii = pair<int,int> ; using pll = pair<ll, ll> ; ``` ---- ### Const Variable - less bug - run faster ```c= const int INF = 0x3f3f3f3f ; const ll LLINF = 0x3f3f3f3f3f3f3f3f ; const MOD = 1e9 + 7 ; ``` ---- ### Modulo ```c= void pmod(ll &a, ll b) {a = (a+b)%MOD;} void mmod(ll &a, ll b) {a = (a-b+MOD)%MOD;} void tmod(ll &a, ll b) {a = (a*b)%MOD;} ``` ---- ### Useful Functions ```c= template<typename T> void amax(T &a, T b) {if(a < b) a = b;} template<typename T> void amin(T &a, T b) {if(a > b) a = b;} template<typename T> bool INR(T a, T b, T c) {return b <= a && a <= c;} ``` ---- ### <bits/stdc++.h> - include all libraries - not always available ---- ### Default Code - online competition - 東區學科 - ICPC - https://pastebin.com/nft7fWe6 ---- ### Type Casting ```c= int a = 1, b = 2 ; ll c = 1LL * a * b ; double d = 1.0 * b / a ; // 1.0f is float ll e = (1LL << 60) ; ``` ---- ### EOF ```c= int n ; while(cin >> n) { // do something } ``` ```c= int n ; while(scanf("%d", &n) != EOF) { // do something } ``` ---- ### Repeat T Times ```c= void solve() { // solution } int main() { int T = 1 ; cin >> T ; while(T--) { solve() ; } } ``` ---- ### Counting Down - n to 1 ```c= for(int i=n; i; --i) { // do something } ``` - n to 0 ```c= for(int i=n; ~i; --i) { // do something } ``` ---- ### Last Space ```c= for(int i=0; i<n; ++i) { cout << a[i] << " \n"[i == n-1] ; } ``` ---- ### Better Choice | Good | Bad | | ------------ | ----------- | | double | float | | emplace_back | push_back | | n >>= 1 | n /= 2 | | global array | local array | | ++i | i++ | ---- ### Locality - quick sort / merge sort - matrix multiplication - D&Q (std::sort) - power-of-two sized data --- ## Competitive Programming Knowledge ---- ### Brute Force - simulation - recursion - $O(2^n)$ - steal points ---- ### Sort - std::sort - bubble / insertion / merge / quick - bucket / radix / counting * ---- ### Greedy - instinct - proof * ---- ### Dynamic Programming - Fibonacci sequence - LIS / LCS - slimes - knapsack ---- ### Divide & Conquer - merge sort - segment tree * ---- ### Graph - input & construct - DFS / BFS - DAG - topological sort - shortest path - Minimum Spanning Tree ---- ### Tree - input & construct - DFS / BFS - DP - Binary Search Tree - Binary Heap --- ## Complexity ---- ### Notations - Big $O$ notation : upper bound - Big $\Omega$ notation : lower bound - Big $\Theta$ notation : combination - $o$ / $\omega$ ---- ### Big $O$ Notation - $f(n)\in O(g(n))\Rightarrow \exists c,n_0\ \\S.T.\ 0\leq f(n) \leq cg(n),\ \forall n>n_0$ - ex. $f(n) = 3x^2 + 10x,\ g(x)=x^2\\ c=4,\ n_0=100$ ---- ### Examples - $f(n) = 2n^3 + 8n^2 - 2021n + 313$ - $f(n) \in O(n^3)$ - $f(n) = O(n^3)$ ---- ### Examples - $f(n) = (n^2 + n) * (log\ n)$ - $f(n) \in O(n^2log\ n)$ ---- ### Examples - $f(n) = log\ (n^2) * log_3(n)$ - $f(n) \in O(log^2\ n)$ ---- ### Time Complexity - 1 sec $\approx\ 10^8 \sim 10^9$ actions - $O(n!):n\leq10$ - $O(2^n):n\leq20$ - $O(n^3):n\leq200$ - $O(n^2):n\leq3000$ - $O(n\sqrt n):n\leq10^5$ - $O(n\ log\ n):n\leq10^6$ ---- ### Time Complexity - sort : $O(n\ log\ n)$ - bitset : $O(\frac{n}{32})\ or \ O(\frac{n}{64})$ - map / set : $O(log\ n)$ - unordered : $O(1) \sim O(n)$ - strlen(s) : $O(len)$ - s.size() : $O(1)$ - string ---- ### Space Complexity - DP - Dynamic Segment Tree - Persistent DS --- ## Compiler ---- ### 東區 - windows - Dev C++ (c++11) - codeblocks (c++11) ---- ### 全國 - linux - codeblocks - vim ---- - editor 編輯器: 記事本, word, gedit, vim - compiler 編譯器: gcc(g++), clang++, VC++ - IDE 整合開發環境: Dev C++, codeblocks, Visual Studio ---- ### DEV C++ - very easy - mostly windows - ugly - old ---- ### Code::Blocks - easy - accessible - not stable / crash ---- ### Visual Studio Code - medium - big project - pretty  ---- ### Gedit - easy - pretty - linux ---- ### Command Compile - terminal (CLI) - g++ source.cpp - g++ -std=c++17 -O2 -Wall -Wextra -Wshadow -Wno-unused-variable -Dcc12 -o a.cpp ---- ### Bash ```bash= clear rm -f a.out g++ -std=c++17 -O2 -Wall -Wextra -Wshadow -Wno-unused-variable -Dcc12 -o a.cpp echo “------ running ------” ./a.out echo “------ finished ------” ``` ---- ### Linux - competition - CSIE - work - virtual machine (server) https://hackmd.io/@Ccucumber12/SkCA49B-v ---- ### VIM - hard - linux / macOS - COOL - personal - plugins --- ## Competition ---- ### Taiwan - 10: HP Codewars - 11: NPSC - 11: 東區 - 12: 全國(NHSPC) - 3: TOI Pre - 6: YTP - 8: ISSC ---- ### Online - regular - Codeforces - AtCoder - annual - Facebook Hacker Cup - Google Code Jam - Google Kick Start ---- ### Codeforces - 通靈 - 數學 - 一步登天 - 實作 ---- ### AtCoder - 思考 - 看起來數學 - 演算法 / 資料結構 ---- ### System - OI - single - less problem - more thinking - partial - ICPC - team - more problem - no partial ---- ### Online Judges - Codeforces / AtCoder - Green Judge / TOJ / TIOJ - 洛谷 / CSES / CS Academy - LOJ / oj.uz - POJ / Uva ---- ### Verdict - AC: congrats - WA: generate test data / read question again - TLE: infinite loop / no output - MLE: stack overflow - RE: array / function / infinite loop - CE / PE --- ## 刷好題