# C++基礎語法與演算法自主學習
# C++ 課程學習計畫
| 週次 | 日期 | 節次 | 課程 | 自學內容 |
|------|------|------|----------------|------------------------------------------------------------|
| 1 | 8/31 | 5 | 基本架構 | 學習基本架構，編寫 `Hello World` 程式，確保編譯並執行成功 |
| 1 | 8/31 | 6 | 變數、輸出輸入 | 學習 C++ 的輸出、輸入，以及變數的宣告與使用。編寫程式，要求使用者輸入數字並顯示它 |
| 2 | 9/7 | 5 | 算術運算子 | 理解算術運算子的使用，並利用其進行計算 |
| 2 | 9/7 | 6 | if 判斷式 | 學習 `if` 判斷式的條件控制，並編寫程式判斷輸入數字的正負或零 |
| 3 | 9/14 | 5 | for 迴圈、while 迴圈 | 學習如何使用迴圈來重複執行函式與運算 |
| 3 | 9/14 | 6 | 陣列 | 學習陣列的宣告，並利用迴圈計算陣列數字的總和 |
| 4 | 9/28 | 5 | 巢狀迴圈 | 理解巢狀迴圈的思考方式，並學習如何分解複雜的巢狀迴圈 |
| 4 | 9/28 | 6 | 巢狀迴圈綜合練習 | 綜合練習巢狀迴圈的應用 |
| 5 | 10/5 | 5 | 二維陣列 | 理解二維陣列的使用方法，以及適用的資料存儲類型 |
| 5 | 10/5 | 6 | 二維陣列綜合練習 | 綜合練習二維陣列的應用 |
| 6 | 10/19 | 5 | 準備 CodeWar 比賽與 APCS | 利用 ZeroJudge 練習歷屆 APCS 題目 |
| 6 | 10/19 | 6 | 準備 CodeWar 比賽與 APCS | 利用 Kattis 練習題目，並練習 CodeWar 歷屆題目 |
## 學習動機
**因為對程式語言有興趣，並且在未來想就讀資工相關科系，故選擇最多學習資源與最容易入門的C++做自主學習內容**
## 預期成果
**希望學完基礎語法後能輕鬆的撰寫程式，理解基礎演算法，在往後幫助我參加APCS檢測與相關競技程式比賽，也可以提早入門程式語言**
# 競程介紹
>**這是額外補充**
## 競程用語
* **競程:程式競賽**
* **OJ : Oline Judge(用來執行程式判斷程式碼是否正確)**
---
* **<font color=#008000>AC : Accepted 正確答案</font>**
* **<font color=#FF0000>WA : Wrong Answer 錯誤答案</font>**
* **<font color=#FFD700>CE : Compile Error 編譯錯誤</font>**
* **<font color=#0000FF>TLE : Time Limit Exceed 超時</font>**
## 競程介紹
### 簡介
* **拿程式來打比賽**
* **用程式實作出演算法**
* **主要分為 IOI 賽制與 ICPC 賽制**
### IOI 賽制
* **高中競程主流賽制**
* **依照答對某個子任務拿到對應的分數**
* **不會有任何懲罰**
### ICPC 賽制
* **大學競程主流賽制**
* **會有罰時**
* **若兩隊答對數量相同，則比較誰的罰時短**
### 共通點
* **都可以使用C C++**
---
# 基礎程式
```cpp=
#include <iostream>
using namespace std;
int main(){
//輸出Hello, world
cout << "Hello, world\n";
return 0;
}
```
## **標頭檔**
```cpp=
#include <iostream>
```
* **利用 #include 引入`<iostream>`程式標頭檔**
## 命名空間
```cpp=
uisng namespace std;
```
* **使用namespace命名空間來儲存std(standard)**
* **通常用來讓cout cin等程式碼運作順利**
## 函式int main()
* **int是指回傳的值是int類型的值**
* **main()用來存放主要的函式**
## 註解
* **用//來註解文字**
* **或是用**
```cpp=
/*
hello world
*/
```
* **來註解一段文字**
## 輸出Hello, world
```cpp=
//輸出Hello, world
cout << "Hello, world\n";
return 0;
```
* **cout是用來輸出的函式**
* **<<是運算子符號**
* **想輸出的文字需要用 "" 或 '' 來圍住**
* **\n或endl都可以用來換行(在競程中通常使用\n來減少程式碼執行速度)**
* **;用來結尾，一行分號結尾的程式就是一個陳述，陳述是程式執行的單位， C++ 程式是一行陳述執行完畢，才接著下一行陳述繼續執行。**
# 變數
## 變數基本概念
* **在程式中需要用變數來儲存運算結果**
* **變數有許多基本型態**
## 宣告
* **在C++程式中建立變數**
```cpp=
int a ; //一般宣告
int a,b,c,d; //多個宣告
int a = 0; //宣告變數的值
```
* **變數在宣告後才可以使用**
## 變數宣告規則
* **不能以數字為開頭**
* **不能用符號和空格(底線除外)**
* **不能用保留字(int include)**
* **建議使用英文命名**
## 常用資料型態
### **int 整數(Integer)**
* **用來儲存整數值，可以區分為 short、int、long 與 long long（C++ 11），可容納的大小各不相同，int 至少會跟 short 一樣大，long 至少會跟 int 一樣大，long long 至少 64 個位元(通常用在需要龐大運算的變數)。**
* **在初學最常使用 int**
```cpp=
int n = 0;
```
### **float 浮點數**
* **也被稱為小數，用來儲存小數值，可以區分為 float、double 與 long double，越後面的型態使用的記憶體空間越大，精度也就越高。**
* **在初學最常使用double**
```cpp=
double = 3.14;
```
### **char 字元**
* **char 的 sizeof(char) 結果要是 1，基本上用來儲存字元資料，但沒有規定什麼是字元資料，也可用來儲存較小範圍的整數。**
```cpp=
char = 'A'
```
### **bool 布林值**
* **用來儲存正確或錯誤(True / Flase)**
```cpp=
bool answer = true;
```
### **string 字串**
* **用來儲存多個字元**
```cpp=
string name = "Yude"
```
## 輸出輸入
* **在C語言中的輸出輸入通常使用printf和scanf**
* **C語言中的函式在C++ 都能使用，但在C++ 中新增了一套新的、更容易使用的輸入輸出庫**
## 標準輸出流 cout
* **cout是ostream類的預定義對象。它與標準輸出設備連接，通常是螢幕**
* **cout與流插入運算符(<<)結合使用，以在控制台上顯示輸出**
#### 範例:輸出Hello, world
```cpp=
#include <iostream>
using namespace std;
int main(){
cout << "Hello, world\n";
return 0;
}
```
### Output
```cpp=
Hello, world
```
## 標準輸入流 cin
* **cin是istream類的預定義對象。它與標準輸入設備連接，標準輸入設備通常是鍵盤。**
* **cin與流提取運算符(>>)結合使用，從控制台讀取輸入。**
### 範例:Hello "Name"
```cpp=
#include <iostream>
using namespace std;
int main(){
string name; cin >> name;
cout << "Hello " << name << '\n';
return 0;
}
```
### Input
```cpp=
Yude
```
### Output
```cpp=
Hello Yude
```
## 算術運算子
* **用來節省大量的運算**
* **介紹五種常用運算子**
### 加法 +
```cpp=
int a = 2;
a = a + 3; //可縮寫成 a += 3
```
### 減法 -
```cpp=
int a = 3;
a = a - 2; //可縮寫成 a -= 2
```
### 乘法 *
* **C++ 跟四則運算一樣需要先乘除後加減**
* **括號裡的數字先算**
* **<font color=#FF0000>不能除以0</font>**
```cpp=
int a = 3;
a = (a+2)*5;
```
### 除法 /
```cpp=
int a = 3;
a = (a+6)/3;
```
### 取餘數 %
* **這個符號叫做 MOD**
* **又名"模運算"**
* **<font color=#FF0000>不能跟0取餘數</font>**
```cpp=
int a = 3;
a = (a+7)%5;
```
### 補充
```cpp=
int i = 3;
i ++; //=4
i --; //=2
```
### 題目練習
### [**我是計算機**](https://codeforces.com/gym/471838/problem/B)
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
//a+b, a−b, a×b, ⌊a/b⌋, amodb, a^2+b^2
cout << a + b << ' ' << a - b << ' ' << a * b << ' ' << a / b << ' ' << a % b << ' '<< a*a + b*b << ' ';
return 0;
}
```
#### Input
```cpp=
1 1
```
#### Ouput
```cpp=
2 0 1 1 0 2
```
---
# If 判斷式
* **在程式中常常會遇到多種狀況**
* **像是判斷值的大小 判斷是否及格**
* **不同的狀況常有不同的處理方式**
* **此時就需要用到if來判斷狀況**
## if-else 條件式
```cpp=
if( 條件 )
{
如果條件成立時做什麼...
}
// 多增加判斷條件可以用else if
else
{
否則做什麼...
}
```
## 範例 判斷成績是否及格
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int grade; cin >> grade;
if(grade >= 60) cout << "Pass";
else cout << "Fail";
}
```
## Input
```cpp=
67
```
## Ouput
```cpp=
Pass
```
## if與算術運算子題目練習
### [**兩光法師占卜術**](https://zerojudge.tw/ShowProblem?problemid=a003)
```cpp=
#include <windows.h>
#include <bits/stdc++.h>
using namespace std;
int main(){
SetConsoleOutputCP(CP_UTF8);
//因輸出中文會出現亂碼，所以使用此指令，不建議在程式碼中使用中文
int m, d;
cin >> m >> d;
int s = (m * 2 + d) % 3;
if(s == 0) cout << "普通";
else if(s == 1) cout << "吉";
else cout << "大吉";
return 0;
}
```
---
# 迴圈
* **在類似的事情需要反覆進行多次的時候**
## while 迴圈
* **用於反覆執行一段程式碼，直到不再需要執行為止**
```cpp=
int n; cin >> n;
while(n!=0){
cout << n <<'\n' ;
n--;
}
```
* **小括號中的條件只要滿足，就會完整執行一輪程式碼**
* **每執行完一輪，會再次檢查條件，決定是否執行下一輪**
* **當執行條件不成立了，表示不需要再繼續執行，此時 while 就結束了**
* **<font color=#0000FF>執行條件只會在每一輪開始前檢查一次，其它時間不會進行檢查</font>**
#### **上述程式碼的意思是:**
#### **輸入n，當n不等於0時，重複執行輸出n然後n-1**
## 題目練習
### [Stuck In A Time Loop](https://open.kattis.com/problems/timeloop)
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main (){
int N; cin >> N;
int i=0;
while(i!=N){
i++;
cout << i <<" Abracadabra\n";
}
return 0;
}
```
## for 迴圈
* **為另一種迴圈的語法，與while沒有太大差別**
* **有些書籍將 for 定義為執行特定次數時使用**
* **但應該定義為for是較有彈性且較方便的**
#### 完成迴圈，通常有四個要素
* **執行前的準備**
* **執行的條件**
* **反覆執行的事情**
* **收尾或下一輪的前置準備**
#### 我們用 while 迴圈來表示
```cpp=
int i=1; //執行前的準備
while(i<=n){ //執行的條件
cout << i << '\n'; //反覆執行的事情
i++; //收尾或下一輪的前置準備
}
```
#### 如果用 for 來表示
```cpp=
for (int i=1;i<=n,i++){
cout << i << '\n';
}
```
## for 迴圈題目練習
### [**Cinema Crowds 2**](https://open.kattis.com/problems/cinema2)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
int main(){
int N,M; cin >> N >> M;
int X[M];
int sum=0;
FOR(i,0,M){
cin >> X[i];
sum += X[i]; //總共的遊客人數。
if (sum == N) {
cout << M-(i+1) << '\n';
break;
}
else if (sum > N) {
cout << M-i << '\n';
break;
}
}
}
```
---
# Array 陣列
* **當我們需要儲存大量資料時，果用多種變數來儲存，勢必會變得非常不方便**
```cpp=
int n, num1, num2 num3 /*........*/;
cin >> n;
cin >> num1;
cin >> num2;
cin >> num3;
//.......
```
* **由於變數的名字無法由變數決定，無法整理成迴圈**
#### 如果num後的數字可以用變數指定，就變成迴圈
```cpp=
for (int i=0;i<n;i++){
cin >> Num[i];
}
```
* **這就是陣列最大的優點，<font color=#FF0000>可用運算式指定編號</font>**
### 陣列宣告
* **X[n]是長度為n的陣列**
* **宣告陣列必須先宣告陣列長度**
```cpp=
int N[5] = {0,7,14,2,3}
```
### 陣列指派
```cpp=
N[2] = 9;
```
### 陣列輸入
```cpp=
cin >>N[5];
```
### 陣列輸出
```cpp=
cout << N[5];
```
### 範例 印出陣列所有內容
```CPP=
#include<iostream>
using namespace std;
int main(){
int N[5]={2,4,5,6,1};
int i=0;
while(i<5){
cout << N[i] << ' ';
i++;
}
return 0;
}
```
### Output
```cpp=
2 4 5 6 1
```
### 陣列結合迴圈題目練習
### [**Reverse**](https://open.kattis.com/submissions/11753318)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rFOR(i,a,b) for(int i=b-1;i>=a;i--) //倒過來做迴圈
int main(){
int n; cin >> n;
int X[n];
FOR(i,0,n){
cin >> X[i];
}
rFOR(j,0,n) cout << X[j] << ' ';
}
```
### Input
```cpp=
5
1 2 3 4 5
```
### Ouput
```cpp=
5 4 3 2 1
```
---
# 巢狀迴圈
* **有些問題不容易用一層迴圈來解決，需要用到更多層**
* **這時我們就要理解巢狀迴圈的用法，以便於解決問題**
## 內外層不相干
* **當我們要輸出一個同邊長(或不同邊長)的矩形，該如何分析問題呢**
### 矩形繪製
#### 輸入一個整數 n，以 # 輸出一個邊長為 n 的矩形。
#### $1 \le n \le 9$
* **我們先把題目拆分成: 輸出n行，每行為n個#**
* **整理成迴圈**
**換行的迴圈**
```cpp=
for(int i=0;i<n;i++)
{
//輸出n個#
cout << '\n';
}
```
**輸出n的迴圈**
```cpp=
for(int j=0;j<n;j++) //使用j是便於閱讀，避免搞混
{
cout << "#";
}
```
**結合在一起就會變成**
```cpp=
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout << "#";
}
cout << '\n';
}
```
**於是原本複雜的「輸出 n 行，每行輸出 n 個 #」被我們拆成：**
* **輸出 n 行，每行怎麼辦不管它**
* **輸出一行 n 個 #，到底要幾行不管它**
**兩個獨立的問題，個別處理後再合併即可。**
## 內外層有關聯
### 三角形繪製
#### 輸入一個整數 n，以 # 輸出一個邊長為 n 的直角三角形
#### $1 \le n \le 9$
* **我們將題目拆分成:輸出n行，依序為等差數列輸出1~n個#**
**因為題目有點複雜，我們先將要輸出幾個#做出來**
```cpp=
for(int i=1;i<n;i++)
{
cout << i << " #";
}
```
**假如n為5，Ouput應該長這樣**
```cpp=
1 #
2 #
3 #
4 #
5 #
```
* **所以我們得知，每一次的i都需要+1，所以不能用i<n**
* **所以我們先做出外層再做內層**
**外層跟剛剛的矩形一樣**
```cpp=
for (int i=0;i<n;i++)
{
//輸出#的程式碼
cout << '\n';
}
```
* **假如要輸出1 2 3 4 5 ...個#，是不是可以利用j<i來輸出**
* **這時，i就要=1，並i<=n，因為一開始是輸出i個#，而輸出n行**
**更改後的外層**
```cpp=
for (int i=1;i<=n;i++)
{
//輸出#的程式碼
cout << '\n';
}
```
**那麼內就能改成**
```cpp=
for(int j=0;j<i,j++)
{
cout << "#";
}
```
**結合在一起就是**
```cpp=
for (int i=1;i<=n;i++)
{
for(int j=0;j<i,j++)
{
cout << "#";
}
cout << '\n';
}
```
## 題目練習
### [**Zamka**](https://open.kattis.com/problems/zamka)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio; cin.tie(0); cout.tie(0)
int main(void){
fast;
int L,D,X; cin >> L >> D >> X;
int N = -1;
int M = -1;
int sum;
int num;
for(int i=L;i<=D;++i)
{
sum = 0;
num = i;
while(num > 0)
{
sum += num % 10;
num /= 10;
}
if (sum == X)
{
N = i;
break;
}
}
for(int i=D;i>=L;--i)
{
sum = 0;
num = i;
while(num > 0)
{
sum += num % 10;
num /= 10;
}
if (sum == X)
{
M = i;
break;
}
}
cout << N << '\n';
cout << M << '\n';
}
```
---
# 二維陣列
* **如果我們要儲存2D的資料，像是迷宮，不能使用一維陣列儲存**
* **這時我們就可以使用二維陣列**
```
o o o o o o o
o o x x x o o
o x x o x x o
o o x o x x o
o x x x o o o
o o o x x x o
o o o o o x o
```
### 列優先（row-major）
* **列優先是一個符合電腦輸出順序的方式**
* **會先寫滿一列，在開始寫下一列**
* **若將原先 7x7 的二維迷宮依此順序儲存，則會變成：**
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 2 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 3 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 4 | 28 | 29 | 30 | 31 | 32 | 33 | 34 |
| 5 | 35 | 36 | 37 | 38 | 39 | 40 | 41 |
| 6 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
* **讓每列的長度固定，就能用乘法和除法做換算**
* **像是座標(3,2)的上面共有 3 列，每列長度 7，可知前面共有 $3$ x $7$ = $21$ 格**
* **左邊共有 2 行，共計 2 格，因此位置會是$3$ x $7$ + $2$**
* **任意座標 $(i,j)$ 可知位置是 $i$ x $n$ + $j$ ($n$ 為列的長度)**
### 二維陣列的宣告與使用
#### 宣告
* **宣告一個由 N 列，每列 M 行，共計 N X M 個 int 變數的陣列：**
```cpp=
int x[N][M];
```
* **先描述有幾列，再描述每列有幾行**
* **存取時也是先描述要哪一列，再描述要該列的第幾個元素**
### 多維陣列 n-dimension array
* **按照相同的邏輯，複數個相同大小的二維陣列，
可以聚集成一個三維陣列；複數個相同大小的三維陣列，
則可以聚集成一個四維陣列，…**
:::success
n 維陣列是「每個元素皆為 n-1 維陣列」的一維陣列
:::
## 題目練習
### [**This Ain't Your Grandpa's Checkerboard**](https://open.kattis.com/problems/thisaintyourgrandpascheckerboard)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio; cin.tie(0); cout.tie(0)
#define FOR(i,n) for(int i = 0; i < n; ++i)
bool correct_grid(vector<string>& x, int n){
FOR(i,n){
int r_B=0, r_W=0, c_B=0, c_W=0;
FOR(j,n){
//檢查同列的黑白數
if (x[i][j] == 'B') r_B++;
else r_W++;
//檢查同行的黑白數
if (x[j][i] == 'B') c_B++;
else c_W++;
// 檢查是否有連續三個或更多同色
if (j < n - 2) {
if (x[i][j] == x[i][j + 1] && x[i][j] == x[i][j + 2])
return false;
if (x[j][i] == x[j + 1][i] && x[j][i] == x[j + 2][i])
return false;
}
}
//檢查黑白數是否相同
if (r_B != r_W || c_B != c_W)
return false;
}
return true;
}
int main(){
fast;
int n; cin>>n;
vector<string> x(n);
FOR(i,n) cin >> x[i];
if(correct_grid(x ,n)) cout << "1\n";
else cout << "0\n";
return 0;
}
```
### 俄羅斯方塊
給一個俄羅斯方塊在放置方塊後、尚未處理消去的盤面，
你必須輸出消去幾排，以及消去後的樣子。
盤面寬度固定為 10，高度由輸入決定。
以 `.` 代表空位，以 `#` 代表非空。
當一橫列 10 格全部為 `#` 時，則此列會被消去，
所有上面的橫列全部往下掉 1 格，最上面空出來的列以 `.` 補滿。
:::info
#### 範例輸入
```
5
...#...###
..#....##.
##########
#####.####
##########
```
#### 範例輸出
```
remove 2 rows.
..........
..........
...#...###
..#....##.
#####.####
```
#### 範例輸入
```
5
..##...###
..#....##.
####..###.
#####.###.
#########.
```
#### 範例輸出
```
remove 0 rows.
..##...###
..#....##.
####..###.
#####.###.
#########.
```
#### 範例輸入
```
5
.###...##.
##########
##########
########.#
##########
```
#### 範例輸出
```
remove 3 rows.
..........
..........
..........
.###...##.
########.#
```
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio; cin.tie(0); cout.tie(0)
#define FOR(i,a,b) for(int i = a; i<b; i++)
int main(){
fast;
int n;
cin >> n;
string X[n];
bool same[n];
int remove = 0;
FOR(i, 0, n) cin >> X[i];
FOR(i,0,n){
bool check = true;
FOR(j,0,10){
if(X[i][j] == '.') {
check = false;
break;
}
}
if(check){
remove++;
same[i] = 1;
}
else same[i] = 0;
}
cout << "remove " << remove << " rows.\n";
FOR(i,0,remove) cout << "..........\n";
FOR(i,0,n){
if(same[i] == 0) cout << X[i] << '\n';
}
return 0;
}
```
# Complexity 複雜度分析
用來分析一個演算法所需的計算量或記憶體空間
1. 時間複雜度：執行一份程式所需的計算量
2. 空間複雜度：執行一份程式所需的記憶體空間
## 時間複雜度
- $O$ (Big-O)：最壞複雜度，上限(Upper bound)
- $Ω$ (Omega)：最佳複雜度，下限(Lower bound)
- $θ$ (Theta)：平均複雜度
通常關注Big-O，因為我們較關心最糟情況程式執行多少次
### 各種常見的時間複雜度
由小到大
| 名稱 | 時間複雜度 |
| -------------- | ------------- |
| 常數時間 | $O(1)$ |
| 對數時間 | $O(\log n)$ |
| 線性時間 | $O(n)$ |
| 線性乘對數時間 | $O(n \log n)$ |
| 平方時間 | $O(n^2)$ |
| 指數時間 | $O(2^n)$ |
| 階乘時間 | $O(n!)$ |
當輸入個數很少的時候 步驟數差異不大
但當輸入個數**逐漸增加**時每個複雜度量級的差距會越來越大
所以我們只想知道在資料量非常大的時候 最糟情況如何
最重要的是**成長速度**
### 時間複雜度計算原則
以計算量(基本操作次數)而定
會受資料量以及演算法影響
只會紀錄**最高次方項**並**忽略所有的係數**
例如一個程式需要執行 $3n^2 + 4n + 5$ 個基本操作
我們會稱它的時間複雜度為 $O(n^2)$
### 舉例分析時間複雜度
- 基本操作 $O(1)$ 常數時間
用公式解求 1 ~ n 加總的程式
不受資料量影響
```cpp=
int n; cin >> n;
n = n * (n-1) / 2
```
- 迴圈 $O(n)$ 線性時間
會受輸入的資料量影響
```cpp=
int n; cin >> n;
for(int i = 1; i <= n; i++){
sum += i;
}
```
- 特定計算 $O(\log n)$ 對數時間
執行 $x$ 次 $i = i * 2$ 之後 $i \ge n$ 退出迴圈
得到$2^x \ge n$，運用對數律可知 $x = \log_2 n$，
```cpp=
int i = 1;
while(i < n) {
i = i * 2;
}
```
- 雙重迴圈與二維陣列 $O(n^2) 平方時間$
```cpp=
int n; cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
t += a[i] * a[j];
}
}
```
一般情況下 電腦每秒大約可以執行 $10^8$ 次基本操作
如果將題目限制以你寫的程式碼方法分析時間複雜度
如果比 $10^8$ 高 可能會 <span style="color:yellow">超時 (TLE)</span>
### 透過輸入範圍估算時間複雜度
| 輸入範圍 | 時間複雜度 |
| --- | --- |
| $n \leq 10^{18}$ | $O(1) or O(\log n)$ |
| $n \leq 10^9$ | $O(\sqrt n)$ |
| $n\leq 10^6$ | $O(n) \ or \ O(n \log n)$ |
| $n \le 5000$ | $O(n^2)$ |
| $n \le 500$ | $O(n^3)$ |
| $n \le 20$ | $O(2^n)$ |
| $n \le 10$ | $O(n!)$ |
# 數學
## 二進位制運算 $Binary$ $addition$
* 利用 and xor 和右移來實作
```cpp=
signed main(void)
{
int x,y; cin >> x >> y;
while(x)
{
int a = x&y, b = x^y;
a<<=1;
x=a,y=b;
//cout << x << " " << y << '\n';
}
cout << y;
}
```
## 快速冪 $Fastpow$
* 將指數部分以二分的方式處理
例:
3^ 22=(3^ 2)^11
=6^ 11=(6^ 2)^5 *6
=36^ 5 *6=(36^ 2)^2 *36 *6
=1296^2 *36 *6=1679616 *36 *6
```cpp=
const int mod = 1e9+7;
long long int fastpow(long long int x,long long int y)
{
//cout << x << " " << y << "\n";
if(y == 0)return 1;
if(y%2)return fastpow(x*x%mod,y/2)*x%mod;
return fastpow(x*x%mod,y/2);
}
```
* [CSES 1095](https://cses.fi/problemset/task/1095)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
const int mod = 1e9+7;
int fp(int x,int y)
{
if(y == 0) return 1;
if(y%2) return fp(x*x%mod,y/2)*x%mod;
return fp(x*x%mod,y/2);
}
signed main(void)
{
IO
read(n);
while(n--)
{
int a,b; cin >> a >> b;
cout << fp(a,b) << endl;
}
}
```
## 模倒數/模逆元/模反元素 $Inversion$ $mod$
* 費馬小定理:a、p互質，a^p=a (mod p)
```cpp=
//i^(mod - 2) % mod
//inv[i]= (mod - (mod / i) * inv[mod % i]) % mod(不推薦使用)
int inv(int x)
{
return fastpow(x,mod-2);
}
```
## 質數篩
* 複雜度為 $O(n$ $log$ $log$ $n)$
```cpp=
bool notprime[10005];
int main()
{
vector<int> prime;
for(int i=2;i<=10000;i++)
{
if(!notprime[i])
{
prime.push_back(i);
for(int j=2;i*j<=10000;j++)notprime[i*j]=1;
cout<<i<<' ';
}
}
}
```
# 遞迴
比迴圈更高級的作法
## 尋找相似子結構
找出原問題的答案與相似子問題的關係
## 同性質子問題
### 例題: 求$f(n) = 1 \times 2 \times 3 .... \times n$
$f(5) =$ <span style="color:lime">$1 \times 2 \times 3 \times$ $4$</span> $\times 5$
$f(4) =$ <span style="color:lime">$1 \times 2 \times 3 \times$ $4$</span>
由上，可發現 f(5)中的部份計算與 f(4) 完全相同
故**f(5)的結果，可由f(4)算出**
$f(5) = f(4) \times 5$
### 一般化
$f( 5 ) = f( 4 ) \times 5$
$f( 4 ) = f( 3 ) \times 4$
可推得
$f( i ) = f( i-1 ) \times i$
## 實作方法
- Top-down : 由原問題需求出發
- Bottom-up : 從已知最小問題出發
### Bottom-up
$f(1) = f(0) \times 1 = 1 \times 1 = 1$
$f(2) = f(1) \times 2 = 1 \times 2 = 2$
$f(3) = f(2) \times 3 = 2 \times 3 = 6$
$f(4) = f(3) \times 4 = 6 \times 4 = 24$
$f(5) = f(4) \times 5 = 24 \times 5 = 120$
```cpp=
f[0] = 1;
for(int i=1;i<=n;i++){
f[i] = f[i-1] * i;
}
```
### Top-down
$f(5)$ 需要 $f(4)$，先求 $f(4)$
$f(4)$ 需要 $f(3)$，先求 $f(3)$
$f(3)$ 需要 $f(2)$，先求 $f(2)$
$f(2)$ 需要 $f(1)$，先求 $f(1)$
$f(1)$ 需要 $f(0)$，先求 $f(0)$
$f(0)$ 已知，回推
```cpp=
int f(int i){
if (i == 0) return 1;
return f(i-1) * i;
}
```
## 例題
### 費氏數列
求存在多少種以 1 和 2 構成的序列
使序列總和恰為 n
例如 n = 5 答案為 8
1. $11111$
2. $1112$
3. $1121$
4. $1211$
5. $2111$
6. $122$
7. $212$
8. $221$
序列最後一個元素依題意必為 1 或者 2
設總和為 5 時
窮舉所有可能的最後元素如下
$$
\left\{
\begin{aligned}
A_1 + A_2 + ... + A_K +1 = 5\\
A_1 + A_2 + ... + A_K +2 = 5\\
\end{aligned}
\right.
$$
整理完可得
$$
\left\{
\begin{aligned}
A_1 + A_2 + ... + A_K = 4\\
A_1 + A_2 + ... + A_K = 3\\
\end{aligned}
\right.
$$
可知任意一組序列總和為 4 時，
末尾補上 1 即可湊出一組總和為 5
同理任意一組序列總和為 3 時，
末尾補上 2 即可湊出一組總和為 5
設序列總和為 4 共 x 組
序列總和為 3 共 y 組
則序列總和為 5 共 $x * 1 + y * 1$ 組
### 問題轉換
原問題：求有多少序列總和為 5
轉變為
- 求有多少序列總和為 4
- 求有多少序列總和為 3
將上述答案加總，即為所求
設 f( n ) = 有多少序列總和為 n
由上述觀察，可列式表達關係為
$f(n) = f(n-1) + f(n-2)$
### 記錄答案避免重算
子問題會重疊，$n=5$只有六項卻呼叫15次
所以把算過的答案存下來減少計算量
```cpp=
int f(int i){
if(used[i]) return rec[i];
used[i] = true;
if(i <= 1) return rec[i] = 1;
return rec[i] = f(i-1) + f(i-2);
}
```
## 快速冪 $Fastpow$
更有效率的計算 $a^b$
### 將指數部分以二分的方式處理
```cpp=
const int mod = 1e9+7;
int fastpow(int x,int y)
{
if(y == 0)return 1;
if(y%2)return fp(x*x%mod,y/2)*x%mod;
return fp(x*x%mod,y/2);
}
```
### 折半
$f(a,6)=a×a×a×a×a×a$
$=(a×a×a)×(a×a×a)$
$=a^3×a^3$
$=f(a,3)×f(a,3)$
奇數無法折剛好
那就別折，套$f(a,b)=f(a,b−1)×a$
若 b 為奇數，則 b-1 為偶數，可折半
可得關係式
$f(a,b)$ = \begin{cases}
f(a, \frac{b}{2})^2, & \text{if } b \text%2 != 0 \\
f(a,b-1) \times a, & \text{else}
\end{cases}
```cpp=
int f(int a, int b){
if(b == 0) return 1;
if(b%2 != 0) return f(a,b-1) * a;
int t = f(a, b/2);
return t * t;
}
```
## 題目
### [Kattis batmanacci](https://open.kattis.com/problems/batmanacci)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mx = 1e18;
ll len[100100];
char f(int n,ll k){
if(n==1) return 'N';
if(n==2) return 'A';
if(k <= len[n-2]) return f(n-2,k);
return f(n-1,k-len[n-2]);
}
signed main(void)
{
int n,k; cin >> n >> k;
len[1] = 1;
len[2] = 1;
for(int i=3;i<n;i++) len[i] = min(mx,len[i-1]+len[i-2]);
char ans = f(n,k);
cout << ans << endl;
}
```
### [AtCoder typical90_bq](https://atcoder.jp/contests/typical90/tasks/typical90_bq)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define int long long
const ll md = 1e9+7;
//n<=1e18 使用fastpow
int fp(int x,int y){
if(y == 0) return 1;
if(y%2) return fp(x*x%md,y/2)*x%md;
return fp(x*x%md,y/2);
}
//第一格k種，第二格k-1種，剩下都是k-2種
//故得出 k * k-1 * (k-2)^(n-2)
signed main(void)
{
IO
int n,k; cin >> n >> k;
int ans=0;
if(n==1) ans = k;
else if(n==2) ans = (k * (k-1)) % md;
else ans = (((k * fp(k-2,n-2)) % md) * (k-1)) % md;
cout << ans << endl;
}
```
# 圖論
## 廣度優先搜索 $BFS$
先選定一個頂點開始走訪，逐一走過此頂點相鄰未被走過的頂點，若相鄰頂點都被走過，再從走訪過的頂點中擇一為新記錄點，逐一走過新記錄點相鄰未被走過的頂點，以此類推。
廣度優先可以利用佇列 $Queue$ 的方式來處理。
* Uav 439
```cpp=
#include<bits/stdc++.h>
using namespace std;
// 使用 pair 存儲座標
queue<pair<int, int>> q;
// 存儲每個格子到目標點的最短距離
int dis[8][8];
// 定義馬的八種可能移動方向
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int main() {
int ax, ay, bx, by;
char c[4];
// 循環讀取輸入，每次讀取四個字符
while (cin >> c[0] >> c[1] >> c[2] >> c[3]) {
// 初始化最短距離數組
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
dis[i][j] = 1e9;
// 讀取起始點和終點的座標
ax = c[0] - 'a', ay = c[1] - '1', bx = c[2] - 'a', by = c[3] - '1';
// 設置起始點的最短距離為0
dis[ax][ay] = 0;
// 將起始點加入隊列
q.push({ax, ay});
// 使用廣度優先搜索計算最短距離
while (!q.empty()) {
auto p = q.front();
q.pop();
// 遍歷馬的八個可能移動方向
for (int i = 0; i < 8; i++) {
if (p.first + dx[i] >= 0 && p.first + dx[i] < 8
&& p.second + dy[i] >= 0 && p.second + dy[i] < 8
&& dis[p.first + dx[i]][p.second + dy[i]] > dis[p.first][p.second] + 1) {
// 更新下一個格子的最短距離，並將該格子加入隊列
q.push({p.first + dx[i], p.second + dy[i]});
dis[p.first + dx[i]][p.second + dy[i]] = dis[p.first][p.second] + 1;
}
}
}
// 輸出最終結果
cout << "To get from " << c[0] << c[1] << " to " << c[2] << c[3] << " takes " << dis[bx][by] << " knight moves.\n";
}
}
```
* Uav 532
```cpp=
#include<bits/stdc++.h>
using namespace std;
// 使用 tuple 存儲三維座標
queue<tuple<int, int, int>> q;
// 存儲每個格子到終點的最短距離
int dis[30][30][30];
// 定義六個可能的移動方向
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
// 存儲迷宮內容
char m[30][30][30];
// 存儲終點座標
tuple<int, int, int> e;
int main() {
cin.tie(0)->sync_with_stdio(0);
int a, b, c;
// 循環讀取輸入，直到 a 為 0 為止
while (cin >> a >> b >> c && a) {
// 初始化最短距離數組
for (int i = 0; i < a; i++)
for (int j = 0; j < b; j++)
for (int k = 0; k < c; k++) {
cin >> m[i][j][k];
dis[i][j][k] = 1e9;
// 將起點加入隊列
if (m[i][j][k] == 'S') {
dis[i][j][k] = 0;
q.push({i, j, k});
} else if (m[i][j][k] == 'E') {
// 記錄終點座標
e = {i, j, k};
}
}
// 使用廣度優先搜索計算最短距離
while (!q.empty()) {
auto [x, y, z] = q.front();
q.pop();
for (int i = 0; i < 6; i++) {
if (x + dx[i] >= 0 && x + dx[i] < a
&& y + dy[i] >= 0 && y + dy[i] < b
&& z + dz[i] >= 0 && z + dz[i] < c
&& m[x + dx[i]][y + dy[i]][z + dz[i]] != '#'
&& dis[x + dx[i]][y + dy[i]][z + dz[i]] > dis[x][y][z] + 1) {
// 更新下一個格子的最短距離，並將該格子加入隊列
dis[x + dx[i]][y + dy[i]][z + dz[i]] = dis[x][y][z] + 1;
q.push({x + dx[i], y + dy[i], z + dz[i]});
}
}
}
// 判斷是否成功逃脫，並輸出結果
if ([](){auto [x, y, z] = e; return dis[x][y][z] == 1e9;}()) {
cout << "Trapped!\n";
} else {
cout << "Escaped in " << [](){auto [x, y, z] = e; return dis[x][y][z];}() << " minute(s).\n";
}
}
}
```
## 深度優先搜索 $DFS$
先選定一個頂點開始走訪，接著從此頂點相鄰未被走過的頂點中，擇一走訪標示為記錄點，以此類推，不斷從新記錄點的相鄰未被走過頂點中尋找。
若新紀錄點的相鄰頂點都被走過，則退回前一個紀錄點，繼續從未被走過頂點中尋找。
深度優先可以利用堆疊 $Stack$ 的方式來處理。
## 回朔 $Backtracking$
* 窮舉每一種可能
```cpp=
int a[10];
bool used[10];
//回朔
void bt(int x){
if(x==4)
{
for(int i=0;i<4;i++)cout<<a[i]<<" \n"[i==3];
return;
}
//123組成4位數
for(int i=1;i<=3;i++)
{
a[x]=i;
bt(x+1);
}
//12345組成四位數(無重複)
for(int i=1;i<=5;i++)
{
if(used[i])continue;
a[x]=i,used[i]=1;
bt(x+1);
used[i]=0;
}
}
int main(){
bt(0);
}
```
* Uva 441
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n, a[15], ans[6];
bool use[15];
// 回溯函數，列舉所有可能的6個元素的組合
void bt(int x, int y) {
// 當已經找到6個元素時，輸出組合並返回
if (x == 6) {
for (int i = 0; i < 6; i++)
cout << ans[i] << " \n"[i == 5];
return;
}
// 從當前位置 y 開始遍歷數組
for (int i = y; i < n; i++) {
// 如果該位置的元素還未被使用
if (!use[i]) {
// 標記該元素為已使用，並將其添加到當前組合中
use[i] = 1;
ans[x] = a[i];
// 遞歸進入下一層，注意遞歸時更新 y 的值
bt(x + 1, i + 1);
// 回溯：取消標記，以便嘗試其他組合
use[i] = 0;
}
}
}
int main() {
// 循環讀取輸入
cin >> n;
while (1) {
// 讀取數組元素
for (int i = 0; i < n; i++)
cin >> a[i];
// 呼叫回溯函數，從位置0開始列舉組合
bt(0, 0);
// 讀取下一組輸入的數組大小
cin >> n;
// 如果 n 不為零，輸出換行，否則跳出循環
if (n)
cout << '\n';
else
break;
}
}
```
# APCS
## $10/22$場次
**這次是我第一次參加$APCS$，這時候程度還是相當不夠
實作的時候太過緊張，又把題目想太難
所以只拿了第一題的子分數和其他題的子分數共$45$分，差點就能$2$級分**
### 成績: 觀念題2級分 實作題1級分
### 第$1$題 機械鼠
[**題目連結**](https://zerojudge.tw/ShowProblem?problemid=m370)
* **題目說明**
有$n$個位置上有食物，另外有一隻老鼠一開始位於位置$x$。
老鼠在開始覓食前要選擇今天要往左邊或往右移動去尋找食物，經過食物時可以停下來吃食物，吃完後可以選擇繼續往相同方向移動，或者是結束今天的覓食。
請問老鼠最多能吃到多少個食物，以及最後停下來吃食物的位置。
* **解題思路**
設一個陣列$f$，來存食物的位置
再設兩個變數$l、r$存左邊比較多還是右邊
利用迴圈來跑每一個食物，看有沒有比$x$大
最後比較$l、r$
$l$大輸出 `f[0]` $r$大輸出`f[n-1]`
* **程式碼**
```cpp=
#include <bits/stdc++.h>
using namespace std;
signed main(void)
{
int x,n;
while(cin >> x >> n)
{
int f[n];
for(int i=0;i<n;i++) cin >> f[i];
sort(f,f+n);
int l=0,r=0;
for(int i=0;i<n;i++)
{
if(f[i]<x) l++;
else r++;
}
if(l > r) cout << l << " " << f[0] << "\n";
else cout << r << " " << f[n-1] << "\n";
}
}
```
## $1/7$場次
**這次是第二次參加，也比較不會緊張了，目前分數還沒出來
觀念出很多函式題和遞迴題，預計$2、3$級分
實作題寫得蠻順利的，第一題卡了一下就寫出來了
第二題是建表加二維陣列題，其實應該能用函式寫得更簡單
但當時怕出錯就直接用判斷式硬爆，後來發現判斷經過字元的種類數寫錯了**
### 成績: 觀念題3級分 實作題3級分
### 第$1$題 遊戲選角
[**題目連結**](https://zerojudge.tw/ShowProblem?problemid=m931)
* **題目說明**
有$n$個角色，每個角色有攻擊力和防禦力。
角色的能力值是攻擊力和防禦力的平方和
輸出能力值第二大的攻擊力和防禦力數值。
保證每個角色的能力值相異。
* **解題思路**
先用$p$存每個角色的能力值
排序完後 再一一對比各個角色的平方和是否為`p[n-2]`(第二大)
符合的話便輸出
* **程式碼**
```cpp=
#include <bits/stdc++.h>
using namespace std;
signed main(void)
{
int n; cin >> n;
int a,d,A[50],D[50],p[50];
for(int i=0;i<n;i++)
{
cin >> a >> d;
A[i] = a;
D[i] = d;
p[i] = a*a + d*d;
}
sort(p,p+n);
for(int i=0;i<n;i++)
{
if(A[i]*A[i] + D[i]*D[i] == p[n-2]) cout << A[i] << " " << D[i] << "\n";
}
}
```
### 第$2$題 蜜蜂觀察
[**題目連結**](https://zerojudge.tw/ShowProblem?problemid=m932)
* **題目說明**
蜜蜂 Bob 在一個大小是 $m$x$n$ 的蜂巢 (見範例說明圖示），並且每個蜂巢格上會有一個代表字母（大小或小寫英文字母）。
Bob 一開始在蜂巢左下角，行走方向定義如圖：0 是往右上; 1 是往右邊; 2 是往右下; 3 是往左下; 4 是往左邊; 5 是往左上。
輸入每步移動的方向，請輸出經過的路徑每格的代表字母，以及經過字元的種類數（大小寫相異），若經過時碰到牆壁該行動會停在原地。
* **解題思路**
先變成正常的陣列
再來建一個表來表示$0$~$5$的$x、y$變化(用陣列來看非數學座標化)
| | ▵$x$ | ▵$y$ |
| --- | ---- | ---- |
| $0$ | 0 | -1 |
| $1$ | 1 | 0 |
| $2$ | 1 | 1 |
| $3$ | 0 | 1 |
| $4$ | -1 | 0 |
| $5$ | -1 | -1 |
然後因為有牆壁，只要撞到就會停下來
所以我們寫一個`in_range()`函式來判斷做變化後是否會超出邊界(撞牆)
```cpp=
bool in_range(int pre_x, int pre_y)
{
return ((pre_x < n && pre_x >= 0) && (pre_y < m && pre_y >= 0));
}
```
然後因為最後需要判斷經過字元的種類數
所以我們用set來包不一樣的字元
`set<char>s`
每一次移動的時候動態增加字元
`s.insert(b[pre_y][pre_x]);`
最後種類數直接 `s.size()`
* **程式碼**
```cpp=
#include <bits/stdc++.h>
using namespace std;
char b[50][50];
int step_x[6] = {0,1,1,0,-1,-1};
int step_y[6] = {-1,0,1,1,0,-1};
string ans;
set<char> s;
int pre_x,pre_y,m,n;
bool in_range(int pre_x, int pre_y)
{
return ((pre_x < n && pre_x >= 0) && (pre_y < m && pre_y >= 0));
}
signed main(void)
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int k; cin >> m >> n >> k;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin >> b[i][j];
}
}
pre_x = 0,pre_y = m-1;
int dir;
for(int i=0;i<k;i++)
{
cin >> dir;
if(!(in_range(pre_x + step_x[dir],pre_y + step_y[dir])))
{
ans += b[pre_y][pre_x];
s.insert(b[pre_y][pre_x]);
}
else
{
pre_y += step_y[dir];
pre_x += step_x[dir];
ans += b[pre_y][pre_x];
s.insert(b[pre_y][pre_x]);
}
}
cout << ans << "\n" << s.size()<< "\n";
}
```
Sign in with Wallet
Connect another wallet