競程初探 - HackMD

--- title: competitive programming type: slide --- 競程初探 === #### CS --- **進度** | 3/4 | 3/11 | 4/1 | 4/8 | 4/15 | |:---:|:---:|:---:|:---:|:---:| | 競程初探 | 資料結構 | 資料結構 | 數學課 | 動態規劃 | | 4/22 | 4/29 | 5/20 | 5/27 | 6/3 | |:---:|:---:|:---:|:---:|:---:| | 動態規劃 | 模擬賽 | 圖論 | 圖論 | 模擬賽 | --- ### 競程？ ---- 程式競賽 ---- 利用有效的演算法解題 (用程式) ---- #### 目標學會基礎演算法 --- ### Online Judge ---- 刷題的地方 ---- * [Zerojudge](https://zerojudge.tw/)：題海，但品質差 * [**TCIRC Judge**](https://judge.tcirc.tw/)：**之後我們主要練題的Judge** * [TIOJ](https://tioj.ck.tp.edu.tw/)：建中的Judge 很難 * [CSES](https://cses.fi/problemset/)：全英文，題單式 * [Atcoder](https://atcoder.jp/home)：全英文，會定期辦比賽 * [Codeforces](https://codeforces.com/)：全英文，定期會辦比賽 * [luogu 洛谷](https://www.luogu.com.cn/)：中國的Judge * [**Virtual Judge**](https://vjudge.net/)：全英文整合所有的Judge ---- #### 最U質的Judge [MDjudge](http://mdcpp.mingdao.edu.tw/) 之後我們的證書題都會放在這ㄛ 證書題要滿12題才可以拿到證書哦 ---- #### 解題狀況說明 * AC：恭喜太電了 * WA：答案錯誤 * CE：先去Compile過再丟吧 * RE：很麻煩(🌰超過陣列範圍...) * TLE：效率太低，想新的演算法 * MLE：超過記憶體限制 --- ### 競程比賽 ---- #### 團體 YTP NPSC ---- #### 個人 TOI初選/海選 APCS 資訊學科能力競賽 (for 高中生) --- ### 資源 ---- [AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m) [CP HandBook](https://usaco.guide/CPH.pdf) --- ### I/O優化 ---- 主要是 **輸入輸出的優化** 之後遇到的題目資料讀取量可能很大此時我們就必須I/O優化 ---- ### 加這兩行就好了！ ```cpp! ios_base::sync_with_stdio(0); cin.tie(0); ``` ---- 加了這兩行後只能用 cin/cout 不能用 scanf/printf ---- ### 不要用endl endl會增加程式執行時間 **改用 '\n'** ---- ### 如果已經習慣用endl怎麼辦？ **#define** --- ### #define ---- 之後可能會遇到很多很長的資料結構資料結構的操作也很長 long long pair<int,int> push_back priority_queue\<int\> priority_queue\<int,vector\<int\>,greater\<int\>\> ---- ### #define 用法 #define A B 用A來取代B 🌰 #define ctrl+C 複製 ---- **#define** ```cpp= #include <bits/stdc++.h> //萬用標頭檔 #define int long long #define pii pair<int,int> #define pb push_back #define F first #define S second #define pq priority_queue<int,vector<int>,greater<int>> #define endl '\n' #define ac ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; signed main(){ //注意這邊要用signed ac int a; //long long a; pii p; //pair<int,int> p; pq q; //priority_queue<int,vector<int>,greater<int>> q; vector<pii> v; v.pb({1,2}); for (auto i:v){ cout<<i.F<<" "<<i.S<<endl; } } ``` ---- ### 優點程式內容看起來乾淨很多 --- ### 時間複雜度 **(Time Complexity)** ---- 可想像成是一個衡量演算法好壞的工具 ---- ### 何謂有效率？ * 程式跑的時間短 * 使用的記憶體小(空間複雜度) ---- 因為程式運行時有很多複雜的東東所以我們只能**估算**時間複雜度 ---- ### 表示方法：Big O Notation (大O符號) $O(n)$ ---- ### 計算規則 1. 通常以 $n$ 的多項式表示 2. 取數量級最高的 3. 省略係數 ---- $O(3n^2+2n+1)$ $O(3n^2)$ $O(n^2)$ ---- 前提：程式運行時間取決於要處理的數字大小 $n$ 就代表要處理的數字大小 ---- ### 為什麼可以省略係數？ 這不代表係數不重要 而係數的重要性 **取決於 $n$ 的大小** ---- 🌰 假如你算出$O(2n)$ 但是我們會把係數省略掉變成$O(n)$ 那如果 $n是2$ 的話 跟$O(n^2)$不是一樣嗎 ---- 但我們主要處理的都是$n$很大的情況所以不會特別討論$n$很小的問題 ---- 只取數量級高的一項 **也是同樣的道理** ---- ### 如何估算？ ---- 我們會想像成程式跑了幾次利用 $n$ 來表示如果你有數學的基本的代數概念這應該很簡單 ---- 🌰1 ```cpp= [|5|6] //等差級數 int main(){ int n,sum=0; cin>>n; for (int i=1;i<=n;i++) cout<<i<<" "; for (int i=1;i<=n;i++) sum+=i; cout<<sum; } ``` ---- $O(n)$ ---- 🌰2 ```cpp= [|5-7|4-9] //nxn乘法表 int main(){ int n; cin>>n; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ cout<<i<<" x "<<j<<" = "<<i*j<<" "; } cout<<"\n"; } } ``` ---- $O(n^2)$ ---- 🌰3 ```cpp= //Binary Search int binary_search(){ int l=0,r=n; while (l<=r){ int mid=(l+r)/2; if (arr[mid]==target) return mid; if (arr[mid]<target) l=mid+1; else r=mid-1; } } ``` ---- $O(log n)$ **注意:這裡的log是以2為底數的log** ---- 🌰4 ```cpp= //印出字串中的字元 int main(){ char s[1000]; cin>>s; for (int i=0;i<strlen(s);i++) cout<<s[i]<<" "; } ``` ---- O(n)? ---- ~~O(n)?~~ ---- $O(n^2)$ ---- 執行了$strlen(s)$次為什麼不是$O(n)$？ 因為$strlen(s)$這個動作是$O(n)$ 所以每跑一次迴圈會$O(n)$ n次迴圈就是$O(n^2)$ ---- 所以我們不能這樣寫 ---- ### 知道複雜度能幹嘛？ ---- ![](https://hackmd.io/_uploads/H15-7oOAn.png) (from CP Handbook) ---- ![](https://hackmd.io/_uploads/HJ66Qo_03.png) ---- ### 小技巧我們可以從 **競程題目** 給的數值範圍推斷題目希望你使用哪個複雜度 p.s.簡單題不適用 也不見得每個題目都可以這樣推 但你沒想法的時候可以試試看 ---- 我們也可以利用時間複雜度 **估看看你會不會TLE** ---- * $O(1)$: 基本運算 * $O(n)$: 線性搜、遍歷陣列 * $O(n^2)$: 氣泡排序、某些情況下的枚舉 * $O(logn)$: 二分搜、快速冪 * $O(nlogn)$:merge sort、某些分治演算法 * $O(n!)$: 排列枚舉 * $O(2^n)$: 位元枚舉 --- ### 其他技巧 ---- ### 技巧一 ---- 剛剛有講到$strlen(s)$的複雜度是$O(n)$ 所以要怎麼寫才會比較快？ ---- ```cpp= [|4] //印出字串中的字元 int main(){ char s[1000]; cin>>s; int k=strlen(s); for (int i=0;i<k;i++) cout<<s[i]<<" "; } ``` $O(n)$ ---- 或者用$string$ 然後直接用$size()$也可以而且$size()$的複雜度是$O(1)$ ---- 之後如果有遇到需要使用函數取值的話如果我們不確定函數的時間複雜度是多少 **建議多設一個變數存值** ---- ### 技巧二 ---- 每次設超大陣列都 RE ---- ![](https://hackmd.io/_uploads/B1EU4xqCn.png) ---- ![](https://hackmd.io/_uploads/ryuuElqAn.png) ---- 把陣列設在全域就好啦 ---- ### 原因 ![](https://hackmd.io/_uploads/SJOOBxqAn.png) ---- 可以想像成主程式$main()$的天花板比較低全域的天花板比較高所以在主程式很容易就頂到天花板了但在全域可以長更高 ---- ### 陣列宣告錯誤用法 ```cpp= int n; cin>>n; int arr[n]; ``` 這雖然有時候可以AC 但是這不是一個好習慣 可能會出現亂數因為這屬於動態宣告 ---- 那要怎麼宣告？ **事先宣告** ---- 假如題目的範圍是 $n ≤ 2e5$ 範圍多大就開多大(一點點) ```cpp= [|1] const int N=2e5+10; //比範圍大一點 int arr[N]; ``` **int前面記得加const** --- ### 前綴和與差分 ---- ``` Description: 給定兩整數 n, q 以及一個長為 n 的序列a[n] 接下來有 q 筆詢問，每筆詢問會有兩數 c,d 式求出a[c]~a[d]的和 Range: n,q<=1e8, a[i]<=1e5 ``` ---- ### 直覺做法 ```cpp= #include <bits/stdc++.h> using namespace std; #define int long long const int N=1e8+10; int n,q,a[N],sum=0,c,d; signed main(){ cin>>n>>q; for (int i=0;i<n;i++) cin>>a[i]; for (int i=0;i<q;i++){ cin>>c>>d; sum=0 for (int j=c;j<=d;j++) sum+=a[j]; cout<<sum<<"\n"; } } ``` ---- 我們試著分析這段程式碼不難發現複雜度$=O(n^2)$ 但是這題的 $n$ 很大 很顯然用這種方法會TLE ---- ### 前綴和 $\begin{cases}S_{100}=a_1+a_2+...+a_{100}\\ S_{200}=a_1+a_2+...+a_{200} \end{cases}$ $\to S_{200}-S_{100}=a_{101}+a_{102}+...+a_{200}$ $\to a_n+a_{n+1}+...+a_k=S_k-S_{n-1}$ ---- ```cpp= [|12|15-16] #include <bits/stdc++.h> using namespace std; #define int long long const int N=1e8+10; int n,q,a[N],b[N],sum=0,c,d; signed main(){ // a 是原始數列 // b 是前綴和數列 cin>>n>>q; for (int i=0;i<n;i++) cin>>a[i]; b[0]=a[0]; for (int i=1;i<n;i++) b[i]=b[i-1]+a[i]; for (int i=0;i<q;i++){ cin>>c>>d; if (c>0) cout<<b[d]-b[c-1]; else cout<<b[d]; cout<<'\n'; } } ``` $O(n)$ ---- ``` Description: 有一長為 n 的數列。給定 m 個操作。每個操作包含 l, r, c三整數，代表將數列中[l,r]的所有數加上c。請輸出經過 m 次操作後的結果 Range: 1<=n,m<=1e5, 1<=l<=r<=n, -1e3<=c<=1e3 ``` ---- ### 直覺做法 ```cpp= #include <bits/stdc++.h> using namespace std; #define int long long const int N=1e5+10; int n,m,a[N],l,r,c; signed main(){ cin>>n>>m; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=0;i<m;i++){ cin>>l>>r>>c; for (int j=l;j<=r;j++) a[j]+=c; } for (int i=1;i<=n;i++) cout<<a[i]<<" "; } ``` $O(n^2)$ ---- $n \leq 10^5$ 複雜度 $O(n^2)$ $\rightarrow TLE$ ---- ### 差分 $\begin{cases} a[0]=0 \\ b[i]=a[i]-a[i-1]，i\geq 1 \\ a[i]=a[i-1]+b[i]，i\geq 1 \end{cases}$ $a[i+1]=a[i]+b[i+1]$ $a[i+1]=(a[i-1]+b[i])+b[i+1]$ $a[n]=a[0]+b[1]+b[2]+...+b[n]$ ---- $\begin{cases} a[n]=b[1]+b[2]+...+b[n] \\ b[1]+k \\ a[1]=(b[1]+k) \\ a[2]=(b[1]+k)+b[2] \\ a[n]=b[1]+..+b[n]+k \end{cases}$ ---- ```cpp= [|12|15-16|19] #include <bits/stdc++.h> using namespace std; #define int long long const int N=1e5+10; int n,m,a[N],b[N],l,r,c; //a 是原始數列 //b 是差分數列 signed main(){ cin>>n>>m; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=n;i++) b[i]=a[i]-a[i-1]; for (int i=0;i<m;i++){ cin>>l>>r>>c; b[l]+=c; b[r+1]-=c; } for (int i=1;i<=n;i++){ a[i]=a[i-1]+b[i]; cout<<a[i]<<" "; } } ``` ---- [CSES Static Range Sum Queries](https://cses.fi/problemset/task/1646) [luogu P2367 語文成績](https://www.luogu.com.cn/problem/P2367) --- ### 自訂結構 struct ---- ### struct 一種自訂的資料結構 ---- ```cpp! [|5] struct 結構名稱{ 資料型態成員一; 資料型態成員二; ... }; ``` **大括號後面要記得加 ;** ---- 🌰 ```cpp= struct f{ string a,b; int c; }; int main(){ f d={"abc","ABC",123}; //指派須按照上面自訂的順序 } ``` ---- ### 存取資料成員 **使用成員運算子 .** ---- 🌰 ```cpp= struct f{ string a,b; int c; }; int main(){ f d; d.a="abc"; d.b="ABC"; d.c=123; } ``` ---- ### 結構陣列宣告法一 ```cpp= struct num{ int x,y; }arr[100]; ``` ---- ### 結構陣列宣告法二 ```cpp= struct num{ int x,y; }; int main(){ num arr[100]; } ``` --- ### Sort ---- 一個C++內建函式可以從小排到大 **標頭檔：algorithm** ---- ### 用法 $sort(begin,end,函式)$ ---- ### begin & end 類似 [指標](https://hackmd.io/@cccccsssss/SyFQR6Wya) 的概念 ---- ```cpp= int main(){ int arr[10]={5,2,4,7,1,9,0,343,33,52}; sort(arr,arr+4); for (int i:arr) cout<<i<<" "; //based for loop } ``` ---- ### Result ``` 2 4 5 7 1 9 0 343 33 52 ``` ---- end 不是指在 arr+4 也就是 1 的位置嗎為什麼 1 沒有被sort到？ ---- 因為在程式中這種設定範圍的都屬於 **左閉右開** ---- ### 左閉右開？ $[a,b)$ 範圍大於等於 a 且小於 b 如果會寫python for迴圈的參數設定也是一樣的概念 ---- ### 第三個傳遞值-函式 1. 可以是自訂函式(boolean) 2. 可以是改變升降冪的語法 會1. 就不太會用到2. ---- 🌰 ```cpp= bool cmp(int a, int b){ return a>b; //由大排到小 } int main(){ int arr[5]={8,7,1,5,4}; sort(arr,arr+5,cmp); } ``` --- ### 例題 [二維點排序](http://mdcpp.mingdao.edu.tw/problem/A007) ---- $Code$ ```cpp= [|7-9|20|11-14] #include <bits/stdc++.h> using namespace std; #define int long long #define ac ios_base::sync_with_stdio(0);cin.tie(0); int n; struct num{ int x,y; }arr[100]; bool cmp(num a, num b){ if (a.x==b.x) return a.y>b.y; return a.x<b.x; } signed main(){ ac cin>>n; for (int i=0;i<n;i++) cin>>arr[i].x>>arr[i].y; sort(arr,arr+n,cmp); for (int i=0;i<n;i++) cout<<arr[i].x<<" "<<arr[i].y<<"\n"; } ``` --- ### [遞迴](https://hackmd.io/@cccccsssss/recursion#/) --- ### 今天學到了 1. 競程介紹 2. I/O優化 3. 時間複雜度 4. 競程小技巧 5. 前綴和 / 差分 6. 自訂結構 struct 7. 內建排序 sort 8. **遞迴** ---- 因為今天教的內容比較偏向概念及小細節所以實作的練習題比較少 ---- 但這節課的很多概念及技巧之後都會在其他演算法或資料結構使用到ㄛ ---- 有不懂的都可以到 **MDCPP Discord 算法班 #題目討論區** 發問 ---- ### DC ![](https://hackmd.io/_uploads/HJFo3VN1p.png) https://discord.gg/vzW6WuReCd --- # 謝謝大家

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.