競賽導論及常用函式

--- title: 競賽導論及常用函式 image: "https://besthqwallpapers.com/Uploads/27-1-2019/78554/thumb2-megumin-artwork-protagonist-konosuba-series-manga.jpg" slideOptions: theme: moon --- ## 競賽導論及常用函式作者：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/) --- ## 解題狀況說明 ---- ### 之前常見的 AC(Accepted)：通過(好耶！) WA(Wrong Answer)：答案錯誤(測資沒通過) CE(Compile Error)：編譯錯誤(請先在IDE上面編譯) RE(Runtime Error)：執行時錯誤(陣列越界、除以0) ---- ### 以後常見到的 TLE(Time Limit Exceeded)：超時(演算法效率太差) MLE(Memory Limit Exceeded)：超出空間限制 --- ## 標準輸入輸出 ---- 哭阿我是不是跑錯棚了，標準輸入輸出是什麼東東 ---- 你確定你知道你在用的是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相容，用哪個我開心就好了吧？ ---- 當然(X ---- 但是要注意一下有時候你們可能用cin/cout寫好了一份程式碼丟上去之後 哭啊 TLE ---- 但是你看到你旁邊的同學用scanf/printf 拿了一個可愛的 AC 結果你在那邊de了很久的bug 最後才發現自己的程式碼跟他的一模一樣 ---- 系統霸凌我qwq ---- 其實並沒有！ 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> ``` ---- 畫面很亂！！！ ![](https://i.imgur.com/lw4Z3Ca.jpg) ---- ### 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)$ ---- 題目通常會給你測資範圍 ![](https://i.imgur.com/HJhqYYj.png) $1e5$指的就是$10^5$ ---- ### 數量級n的最大值 ![](https://i.imgur.com/S0zutD1.png) ---- ### 複雜度對應到的常見演算法 | 複雜度 | 對應演算法 | |-------|----------| |$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 --- ## 謝謝大家 ![](https://i.imgur.com/TFx8FRj.jpg)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.