# 競程班第二堂社課 :::spoiler 目錄: [TOC] ::: ## 開始之前 來稍微複習一下上一堂的內容 ### 程式架構: ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ //code return 0; } ``` --- ### 變數型態: ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int a = 1234; string s1 = "qwerty", s2 = "This is a string."; char c = 'a'; float f = 1.234; bool b = true; //bool b = 1; return 0; } ``` --- ### 輸入輸出、四則運算: ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int a,b; string s1,s2; cin>>a>>b>>s1>>s2; cout<<"a + b = "<<a+b<<endl; cout<<"s1 is "<<s1<<endl; cout<<"s2 is "<<s2<<endl; return 0; } ``` --- ### 條件式: ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; if(n == 0){ cout<<"n is 0"<<endl; } else if(n == 1){ cout<<"n is 1"<<endl; } else if(n < 0){ cout<<"n is negative"<<endl; } else{ cout<<"n is very big"<<endl; } return 0; } ``` :::warning :warning: == 用於判斷 = 用於賦值 ::: --- ### 布林運算子: 計算布林值之間的關係，回傳布林值 **AND: && OR: || NOT: !** | AND | True | False | |----| ---- | ----- | | True | True | False | | False | False | False | | OR | True | False | |----| ---- | ----- | | True | True | True | | False | True | False | | NOT | True | False | |----| ---- | ----- | |----| False | True | ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int a; cin>>a; if(a > 0 && !( a % 2 == 0)){ cout<<a<<" is a positive odd number"<<endl; } else{ cout<<a<<" is not a positive odd number"<<endl; } return 0; } ``` :::warning :warning: 多用括號 ::: --- ## IDE 整合開發環境 通常包含編輯器、除錯器、編譯器or直譯器。 ### [vscode](https://code.visualstudio.com/) ![](https://hackmd.io/_uploads/HkC9q2jep.png) 不含編譯器，安裝過程麻煩 ### [Code::Blocks](https://www.codeblocks.org/) ![](https://hackmd.io/_uploads/ryflihoep.png) APCS指定IDE ### [Dev-C++](https://www.bloodshed.net/) ![](https://hackmd.io/_uploads/SJbPh3ila.png) 介面簡潔、適合入門。但版本很舊，所以我都用[embarcadero dev-c++](https://www.embarcadero.com/free-tools/dev-cpp/free-download)（語言記得選英文） ![](https://hackmd.io/_uploads/S1_Lh2sxT.png) ## OJ online judge，線上解題系統 ### [Codeforces](https://codeforces.com/) 題目、比賽超多，打競程的通常用這個最多，不過很多怪題。 ### [CSES](https://cses.fi/problemset/list/) 只有300題，但都是很經典的題型，刷這個對APCS、TOI很有幫助。 ### [Atcoder](https://atcoder.jp/home) 日本網站，因此比賽時間比Codeforces舒服多了。 ### [ZeroJudge](https://zerojudge.tw/) 台灣網站，有APCS和很多比賽的考古題 ### [TCIRC](https://judge.tcirc.tw/) 一中電研的OJ，有AP325的習題。 ### [TIOJ](https://tioj.ck.tp.edu.tw/) 建中的，有IOICamp和NPSC的題目 ## 學習資源 [USACO Guide](https://usaco.guide/) 英文，各個難度都有，有很多參考code [AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m) 中文，適合APCS 3級 ## 如何寫題目 以Codeforces為例。 在problemset裡面可以照難度或通過人數排序，假設你選了通過人數最多的[這一題](https://codeforces.com/problemset/problem/4/A) ![](https://hackmd.io/_uploads/ryvpf6sx6.png) 題目大意:給你一個正整數$w$，問它是否可以拆成兩個正偶數之和。 解法: $w$必須要是不為2的正偶數才會是`Yes`，否則都是`No`。 打開你的Dev-C++，打程式: ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int w; cin>>w; if(w % 2 == 0 && w != 2){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } return 0; } ``` 存檔後(xxx.cpp)按下compile and run ![](https://hackmd.io/_uploads/HJ2dwTsla.png) 會出現一個exe檔，你可以在這裡測試範例測資，輸入8，按Enter，應該輸出YES ![](https://hackmd.io/_uploads/HyxG_6je6.png) 回到Codeforces，在右方找到這個。 ![](https://hackmd.io/_uploads/rypRdpsga.png) Luaguage選擇GNU C++20 11.2.0 (64bit,winlbs)，檔案選擇剛剛的cpp檔(不是exe檔) submit後會到這個畫面 ![](https://hackmd.io/_uploads/SJd3K6oxa.png) 按 # 可以看到詳細資料 Verdict大致可能有以下結果(各OJ皆如此): * AC (Accept): 你通過了，你超電 * WA (Wrong Answer): 表示答案錯誤 * TLE (Time Limit Exceed): 表示執行超過時間限制 * MLE (Memory Limit Exceed): 表示程序執行超過記憶體限制 * OLE (Output Limit Exceed): 表示程序輸出檔超過限制 * RE (Runtime Error): 表示執行時錯誤，通常為記憶體配置錯誤 如：使用了超過陣列大小的位置 * CE (Compile Error): 表示編譯錯誤。 ## 迴圈 ### while 使用方式: while(繼續的條件){} 會重複大括號內的程式直到判斷式為`false`(0) --- ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int a = 10; while(a > 0){ cout<<a<<' '; a -= 1; } return 0; } ``` 輸出: ![](https://hackmd.io/_uploads/SJK42J2e6.png) --- :::info 補充: ```cpp while(a > 0) ``` 也可以寫成 ```cpp while(a) ``` 因為當把一個`int`當作條件式時，$0$會視為`false`，而其他數字會被視為`true`。 因此，`while(1)`會是一個無限迴圈。 ::: --- :::info 補充: ```cpp= int n; while(cin>>n){ //code } ``` cin >> n是取得n之後，把n賦予給cin，如果能賦予，就會回傳true，則條件式成立，進入while迴圈 反之，如果輸入無效或EOF(End of File)，n無法賦予給cin，則條件式不成立，跳脫迴圈 ::: --- ### for 使用方式: for(開始迴圈前做的事;繼續的條件;每跑一圈**後**會做的事){} ![](https://hackmd.io/_uploads/By4yoenla.png) --- ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ for(int i = 0; i <= 10; i++){ cout<<i<<' '; } return 0; } ``` 寫成while的話就是: ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int i = 0; while(i <= 10){ cout<<i<<' '; i++; } return 0; } ``` 輸出: ![](https://hackmd.io/_uploads/HkM8oenea.png) --- ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ for(int i = 1; i < 1000; i *= 2){ cout<<i<<' '; } return 0; } ``` 輸出: ![](https://hackmd.io/_uploads/r1dpig3l6.png) --- ### 巢狀迴圈 就字面上的意思 ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ for(int i = 1; i <= 4; i++){ for(int j = 0; j < i; j++){ cout<<'*'; } cout<<endl; } return 0; } ``` 輸出: ![](https://hackmd.io/_uploads/rJDmAe2la.png) --- ### break 與 continue break: 跳脫迴圈 continue: 結束這一圈 --- ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ for(int i = 0; ; i++){ //for迴圈沒有條件式會視為無限迴圈 if(i > 10){ break; } cout<<i<<' '; } return 0; } ``` 輸出: ![](https://hackmd.io/_uploads/r1eYFfhe6.png) --- ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ for(int i = 0; i < 10; i++){ if(i % 2 == 0){ continue; } cout<<i<<' '; } return 0; } ``` 輸出: ![](https://hackmd.io/_uploads/BJuE5G2g6.png) --- ### 變數的有效範圍 對於在for迴圈內宣告的變數，只會在大括號範圍內有效。 ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ for(int i = 0; i < 10; i++){ //code } cout<<i; //<---這裡會報錯 } ``` ## 陣列 一串東西 宣告: ```cpp int a[3], b[4]={0,1,10000,-1}; string s[2]={"qwerty","123456"}; ``` 中括號內是大小 :::warning :warning: 索引值(index)從0開始，大小為3的陣列裡面分別是第0項、第1項、第2項。 ::: ### 存取 ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int a[3]={100, 1, -10}; a[1] = 6; //{100,6,-10} a[0] += 99; //{199,6,-10} a[2] -= a[1]; //{199,6,-16} a[0] ++; //{200,6,-16} return 0; } ``` ### 遍歷陣列 --- ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int a[4] = {-1, 2, 1000, 0}; for(int i = 0; i < 4; i++){ cout<<a[i]<<' '; } return 0; } ``` 輸出: ![](https://hackmd.io/_uploads/BJ9p2zne6.png) --- 題目要輸入一個陣列時，通常會先跟你說它的大小，像[這一題](https://cses.fi/problemset/task/1094): ![](https://hackmd.io/_uploads/rJANxmhxa.png) ![](https://hackmd.io/_uploads/HJWvx72ga.png) ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int a[n]; for(int i = 0; i < n; i++){ cin>>a[i]; } //code } ``` --- ### 二維陣列 即陣列的陣列，可以想成是一個表格。 宣告: ```cpp int a[2][3]={{1, 9, 10}, {4, 0, -6}}; bool b[100][3][4]; //三維陣列 ``` 基本上和一維一樣。 --- ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int n, m; cin>>n>>m; int a[n][m]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> a[i][j]; } } } ``` --- ## 常用函式 需`#include<algorithm>`，如果已經用了`#include<bits/stdc++.h>`就不用。 ```cpp= int a = 3, b = 4, c = 5; int mn = min({a, b, c}); int mx = max({a, b, c, -100000}); //如果只有兩項可以不用大括號，如 max(a,b) swap(a, b); //a 變為 4，b 變為 3 ``` ## 練習題 :::warning :warning: 如果運算過程會超過`int`範圍($-2^{31}$到$2^{31}-1$)，請改用`long long` ::: [b016: 山谷的回聲](https://judge.tcirc.tw/ShowProblem?problemid=b016) :::spoiler AC code ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; for(int i = 0; i < n; i++){ cout<<"Hello, World!"<<endl; } return 0; } ``` ::: \ [b021: 電電找因數](https://judge.tcirc.tw/ShowProblem?problemid=b021) :::spoiler AC code ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ for(int i = 1; i <= n;i++){ if(n % i == 0){ cout<<i<<" "; } } cout<<endl; } } ``` ::: \ [b026: 乖乖寫作業](https://judge.tcirc.tw/ShowProblem?problemid=b026) :::spoiler AC code ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; long long a[n]; for(int i = 0; i < n; i++){ cin>>a[i]; } for(int i = n - 1; i >= 0; i--){ cout<<a[i]<<" "; } cout<<endl; return 0; } ``` ::: \ [b027: 找出學霸](https://judge.tcirc.tw/ShowProblem?problemid=b027) :::spoiler AC code ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ int mxpos, mxval = -1, mnpos, mnval = 101; for(int nowpos = 0; nowpos < n; nowpos++){ int nowval; cin>>nowval; if(nowval > mxval){ mxval = nowval; mxpos = nowpos; } if(nowval < mnval){ mnval = nowval; mnpos = nowpos; } } cout<<mxpos + 1<<' '<<mxval<<' '<<mnpos + 1<<' '<<mnval<<endl; } return 0; } ``` ::: \ [Weird Algorithm](https://cses.fi/problemset/task/1068) :::spoiler AC code ```cpp= #include<bits/stdc++.h> using namespace std; signed main(){ long long n; cin>>n; cout<<n<<" "; while(n != 1){ if(n % 2 == 1){ n = n * 3 + 1; cout<<n<<" "; } else{ n /= 2; cout<<n<<" "; } } return 0; } ``` ::: \ [Missing Number](https://cses.fi/problemset/task/1083) :::spoiler 提示: 可以用數學解 ::: :::spoiler AC code ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ long long n,sum; cin>>n; sum=n * (n + 1) / 2; for(int i = 0; i < n - 1; i++){ int a; cin>>a; sum-=a; } cout<<sum<<endl; ``` ::: \ [Increasing Array](https://cses.fi/problemset/task/1094) :::spoiler AC code: ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int n, pre, now; long long ans=0; cin>>n; cin>>pre; for(int i = 1; i < n; i++){ cin>>now; if(pre > now){ ans += pre - now; now = pre; } pre = now; } cout<<ans; return 0; } ``` :::
Last changed by  
 
tmting39
345

Read more

位元dp與基礎捲積

先直接看題目

3/22/2024
CSES Dynamic Programming 題解

#Dice Combinations

3/17/2024
基礎資料結構練習題

含有線段樹、BIT、稀疏表。有一些可能不需要用到

3/6/2024
競程班第四堂社課

[]

2/27/2024
Read more from tmting39
Published on HackMD