## 競賽導論及常用函式 作者：explosionnn --- ## 競程比賽介紹 1. APCS：升大學很有用 (但其實他不是競賽而是檢定) 2. NPSC：台大辦的比賽 3. YTP：精誠資訊辦的比賽，有超多食物，入選可以參加專題 4. HPC：HP Codewar，有變裝秀，感覺很有趣 ---- 5. 學科能力競賽：明道只能派兩個qwq 6. ISSC：一個全英文的比賽，前幾名可以出國比賽的樣子 7. TOI ：前進資奧！！選訓營分兩個階段 --- ## Why C++? ---- 為什麼打競程要學C++? C, Java, Python…不好嗎? ---- 沒有不好 但是所有語言都有他擅長的領域！ ---- ### C++ vs C C與C++ 語法相容 不過C++幫你寫好了很多很棒的東西！ 很多東西都可以直接用！ 這麼香還不學嗎? ---- ### C++ vs Java Java跟C++比，Java的執行效率比較慢 而且實際上Java的碼長也會比較長 ---- ### C++ vs Python 競程打Python? ~~毒瘤(X~~ Python的執行效率不是普通的慢 雖然他的程式碼也不是普通的短 Python適合用於機器學習和Deep Learning --- ## Judge系統 ---- 什麼是judge系統呢? 大家或多或少應該會用過吧 像是台中女中程式解題系統就是一個judge系統 上面會有題目，你需要寫一個程式碼來解決他的問題 ---- ### 其他常見Judge * [高中生程式解題系統(Zerojudge)](https://zerojudge.tw/)：題目有經過分類，搬運很多APCS題目 * [TIOJ](https://tioj.ck.tp.edu.tw/)：建中的解題系統，很多很電的題目 * [Codeforces](https://codeforces.com/)：每週都有比賽，不過是俄羅斯的網站，題目只有俄文或是英文 * [AtCoder](https://atcoder.jp/)：每週都有比賽，不過是日本的網站，題目只有日文或是英文 * [CSES](https://cses.fi/problemset/)：芬蘭的網站，題目只有芬蘭文或是英文 ---- ### MDjudge [明道自己的Judge](http://mdcpp.mingdao.edu.tw/) --- ## 解題狀況說明 ---- ### 之前常見的 <font color="green">AC(Accepted)</font>：通過(好耶！) <font color="red">WA(Wrong Answer)</font>：答案錯誤(測資沒通過) <font color="black">CE(Compile Error)</font>：編譯錯誤(請先在IDE上面編譯) <font color="#f1c40f">RE(Runtime Error)</font>：執行時錯誤(陣列越界、除以0) ---- ### 以後常見到的 <font color="blue">TLE(Time Limit Exceeded)</font>：超時(演算法效率太差) <font color="orange">MLE(Memory Limit Exceeded)</font>：超出空間限制 --- ## 標準輸入輸出 ---- 哭阿我是不是跑錯棚了，標準輸入輸出是什麼東東 ---- 你確定你知道你在用的是C的輸入輸出 還是C++的輸入輸出嗎？ ---- 有時候我們常常以為自己在打C++ 但其實我們壓根就是在打C！ ---- C語言使用的輸入輸出： ```c= int n; scanf("%d", &n); printf("%d\n", n); ``` ---- C++使用的輸入輸出： ```cpp= int n; cin >> n; cout << n << endl; ``` ---- 好喔那我知道這個了有什麼用嗎？ 阿反正C++跟C相容，用哪個我開心就好了吧？ ---- <font size="64px">當然(X</font> ---- 但是要注意一下 有時候你們可能用cin/cout寫好了一份程式碼 丟上去之後 <font color="red" size="64px">哭啊 TLE</font> ---- 但是你看到你旁邊的同學用scanf/printf 拿了一個可愛的 <font color="green" size="64px">AC</font> 結果你在那邊de了很久的bug 最後才發現自己的程式碼跟他的一模一樣 ---- <font size="64px">系統霸凌我qwq</font> ---- 其實並沒有！ cin/cout本身速度就會比C的輸入方法還慢 但是其實有一個方法可以匹敵C的輸入方法！ [想瞭解為什麼cin/cout比較慢可以點我](https://hackmd.io/@wiwiho/CPN-io-optimization) ---- ### I/O優化 ```cpp= ios_base::sync_with_stdio(0); cin.tie(0); ``` * 不要用endl * 用了這個之後就不可以跟scanf/printf混用 ---- ### 常用的輸入輸出表格 | C / C++ | C語言 | C++ | | -------- | -------- | -------- | | 一般輸入 | scanf | cin | | 一般輸出 | printf | cout | | 讀取整行 | fgets | getline / cin.getline | | 讀取字元 | getchar | cin.get | | 輸出整行 | puts | | | 輸出字元 | putchar | cin.put | | 字串串流 | sscanf/sprintf | stringstream | ---- ### getline 有時候我們會遇到一些很討人厭的測資輸入 會要我們輸入整行 或者是有時候要我們連空白字元都吃進去 這時候就可以使用getline ```cpp= string s; getline(cin, s); ``` --- ## 陣列宣告 ---- 有時候我們在宣告陣列的時候，題目數字比較大一點 然後宣告陣列準備要編譯的時候卻收到了CE 這代表你的陣列開太大 但其實有一種方法可以讓你的陣列開的大一點 ---- ### 把陣列開在全域變數 養成這個好習慣，除非你要開的陣列夠小 就算開在全域變數，陣列也只能開到10^7 要特別注意一下 ---- 有時候我們在宣告陣列的時候 雖然編譯過了但是輸出莫名其妙跑出一些奇怪的亂數 那可能是因為**動態宣告陣列** ```cpp= int n; cin >> n; int arr[n]; ``` ---- 我覺得這不是一個太好的習慣 所以建議大家可以先看測資範圍多大就開多大的陣列 建議可以再比測資範圍大一點避免RE ```cpp= const int MAXN = 1e5 + 50; int arr[MAXN]; ``` * int 前面記得加 const --- ## 萬用標頭檔 ---- ### BEFORE ```cpp= #include<iostream> #include<string> #include<iomanip> #include<sstream> #include<stack> #include<queue> #include<vector> #include<set> #include<map> ``` ---- 畫面很亂！！！  ---- ### AFTER ```cpp= #include<bits/stdc++.h> ``` --- ## #define ---- ### 語法 ```cpp= #define a b ``` 將b定義為a ---- ### 舉例 ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; signed main(){ int a; //a的變數型態已為long long } ``` 所有的int都變成long long了 --- ## 時間複雜度 做事要有效率啊！！！ ---- ### 想像一下 如果你要從1加到10你會怎麼做 (如果你不會梯形公式的話) 簡單啊，慢慢加 ---- 阿如果今天是1加到100或是1000呢？ 要加多久啊qwq ---- 這時候就要有更有效率的方法 也就是梯形公式 ---- 寫程式也是一樣，雖然電腦的計算速度比人還快，但是還是有限制，數字一大還是要算到天荒地老 ---- 一般來說普通電腦一秒可以執行10^8次運算 所以其實我們只要把全部的運算次數算出來就好了 ---- 全部算出來好麻煩qwq 其實可以用估算的 ---- ### 大O記號(Big O notation) 1. 對於一個多項式，只取數量級最大的 2. 省略所有係數 ---- ### 例子 以下為某段程式碼的運算次數 $f(x) = 5x^3 + 9x^2 + 2x + 48763$ STEP1：只取數量級最大的 => $5x^3$ STEP2：省略係數 => $x^3$ 因此大O記號記做：$O(x^3)$ ---- 那要怎麼估算呢？ 看迴圈跑幾次就好了！ ---- ### 練習1 ```cpp= signed main(){ int n; cin >> n; for(int i = 1; i <= n; i++){ cin >> arr[i]; } for(int i = 1; i <= n; i++){ cout << arr[i] << " "; } } ``` ---- ANS：$O(n)$ ---- ### 練習2 氣泡排序 ```cpp= for(int i = 1; i <= n-1; i++){ for(int j = 1; j <= n-i; j++){ if(arr[j] > arr[j+1]){ swap(arr[j], arr[j+1]); //swap可以把兩個變數交換 } } } ``` ---- ANS：$O(n^2)$ ---- ### 練習3 二分搜尋法 ```cpp= int l = 1, r = n; while(l <= r){ int m = (l+r)/2; if(t == arr[m]){ cout << m << endl; break; }else if(t > arr[m]){ l = m+1; }else{ r = m-1; } } ``` ---- ANS：$O(logn)$ ---- 題目通常會給你測資範圍  $1e5$指的就是$10^5$ ---- ### 數量級n的最大值  ---- ### 複雜度對應到的常見演算法 | 複雜度 | 對應演算法 | |-------|----------| |$O(1)$|各種基礎運算，數學| | $O(logn)$|二分搜，map, set, pq 一次操作| | $O(√n)$|判斷質數，找因數| | $O(n)$|遍歷陣列| | $O(nlogn)$|排序(merge, heap, quick sort等等)| | $O(2^n)$|2-subset問題，暴力枚舉| | $O(n!)$|遍歷所有排列| ---- ### 參考資料 [時間複雜度](https://drive.google.com/file/d/124wLy-bHDpfyPe6irTtq2w9_m7Aw-NhA/view) --- ## 結構體 struct ---- ### BEFORE ```cpp= #include<bits/stdc++.h> using namespace std; signed main(){ int a_age; double a_height; double a_weight; char a_gender; int b_age; double b_height; double b_weight; char b_gender; } ``` 每個人都要宣告四個變數，好麻煩 ---- ### AFTER ```cpp= #include<bits/stdc++.h> using namespace std; struct Human{ int age; double height; double weight; char gender; }; signed main(){ Human a; Human b; } ``` 好耶！輕鬆多了 ---- 所以如果你有一堆變數彼此是有關聯的， 可以用struct綁在一起 ---- ### 建構 ```cpp= struct 結構體名稱{ 變數型態1 變數名稱1; 變數型態2 變數名稱2; 變數型態3 變數名稱3; . . . 變數型態N 變數名稱N; }; ``` 每個變數要用分號隔開 struct的大括號後面要加一個分號 ---- ```cpp= struct Type{ int a; double db; char c; string s; int arr[50]; Type2 t; }; ``` 裡面可以塞很多種變數型態， 甚至可以塞另一個struct ---- ### 宣告 ```cpp= struct Human{ int age; double height; double weight; char gender; }; signed main(){ Human a; } ``` 把Human想成是一種變數型態(int, double等等) 而a是變數名稱 ---- ### dot運算子 ```cpp= #include<bits/stdc++.h> using namespace std; struct Human{ int age; double height; double weight; char gender; }; signed main(){ Human a; a.age = 18; cout << a.age << endl; } ``` 用dot運算子「.」，可以對其進行操作 --- ## 自訂函式 ---- ### 宣告 ```cpp= 回傳值型態 函式名稱(參數1型態 參數1, 參數2型態 參數2, ...){ 程式碼... return 回傳值; } ``` 回傳值型態可以是任何東西(int, double等等)， 也可以回傳你自己定義的struct ---- ### 範例1(有回傳值) ---- ### BEFORE ```cpp= signed main(){ int a, b; cin >> a >> b; cout << a + b; } ``` ---- ### AFTER ```cpp= int add(int x, int y){ int result = x + y; return result; } signed main(){ int a, b; cin >> a >> b; cout << add(a, b); } ``` 1. 將a、b傳入到add這個函式裡，現在函式裡的x是a的值，y是b的值 2. 接著將result賦予x+y的值 3. 函式執行到return，回傳result，結束函式 4. 現在add(a, b)這個東西就是剛剛回傳的result ---- ### 範例2(無回傳值) 自訂函式也可以只是單純執行一段程式碼 因此也可以不回傳任何東西 ---- ### BEFORE ```cpp= signed main(){ string name; cin >> name; cout << "hello " << name; } ``` ---- ### AFTER ```cpp= void greeting(string name){ cout << "hello " << name; return; } signed main(){ string name; cin >> name; greeting(name); } ``` 1. 將name傳到greeting函式裡 2. 執行cout << "hello " << name; 3. 函式執行到return，結束函式 ---- ### 注意 * 因為此函式不回傳任何東西，所以回傳型態要寫「void」 * return可以省略 ---- ### 幹嘛那麼麻煩？ * 將程式碼區分成小塊小塊的，可以方便分工 * 自訂函式可以取名稱，以後回來看程式碼的時候可以方便了解這段在寫什麼 * 將經常出現的程式碼寫成自訂函式，可以增加程式碼的可讀性與維護性 --- ## c++內建函式 ---- ### 比大小 min (const T& a, const T& b, Compare comp) 取兩個值中的最小值 max (const T& a, const T& b, Compare comp) 取兩個值中的最大值 ---- ### 程式碼 ```cpp= #include<bits/stdc++.h> using namespace std; signed main(){ int a, b; cin >> a >> b; cout << max(a, b) << endl; cout << min(a, b) << endl; } ``` ---- ### 交換 swap (T& a, T& b) 交換兩個對象 ---- ### 程式碼 ```cpp= #include<bits/stdc++.h> using namespace std; signed main(){ int a, b; cin >> a >> b; cout << a << " " << b << endl; swap(a, b); cout << a << " " << b << endl; } ``` ---- ### 排序 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) 第一個參數放陣列名稱 第二個參數放陣列名稱+數量 原理： 資料量大：快速排序(Quick sort)， 資料量小：插入排序(Insertion Sort) 時間複雜度：$O(nlogn)$ ---- ### 程式碼 ```cpp= #include<bits/stdc++.h> using namespace std; signed main(){ int arr[5] = {3, 5, 6, 7, 9}; sort(arr, arr+5); for(int i = 0; i < 5; i++){ cout << arr[i] << " "; } } ``` ---- ### 自訂排序方法 c++的sort預設是從小排到大， 啊如果要由大排到小怎麼辦？ ```cpp= less<Type>() //由小排到大 greater<Type>() //由大排到小 ``` ---- ```cpp= #include<bits/stdc++.h> using namespace std; signed main(){ int arr[5] = {3, 5, 6, 7, 9}; sort(arr, arr+5, greater<int>()); for(int i = 0; i < 5; i++){ cout << arr[i] << " "; } } ``` ---- ### 自訂排序函式 或著你可以自己寫一段排序方法 ```cpp= bool cmp(int a, int b){ return a > b; } signed main(){ sort(arr, arr+n, cmp); } ``` ---- ```cpp= #include<bits/stdc++.h> using namespace std; struct Element{ int value; int weight; }; Element arr[100]; bool cmp(Element a, Element b){ if(a.value == b.value){ return a.weight < b.weight; } return a.value > b.value; } signed main(){ int n; cin >> n; for(int i = 1; i <= n; i++){ cin >> arr[i].value >> arr[i].weight; } sort(arr+1, arr+1+n, cmp); for(int i = 1; i <= n; i++){ cout << arr[i].value << " " << arr[i].weight << endl; } } ``` --- # 今日證書題 http://mdcpp.mingdao.edu.tw/contest/19/problem/T001 http://mdcpp.mingdao.edu.tw/contest/19/problem/T002 --- ## 謝謝大家