[TOC]
<div style="page-break-after: always;"></div>
# <font color = "blue">**第零單元：AA 競程 Level 0 課程導覽**</font>
## 一、課程定位
* Level 0 為 AA 競程的入門課程，目標是建立「寫程式解題」的底層功力。
* 適合對象：
1. 完全零基礎、想進入競程領域者。
2. 準備台灣的 [APCS 程式檢定](https://apcs.csie.ntnu.edu.tw/) 者。
3. 想補強 C/C++ 語法與電腦科學思維的自學者。
* Level 0 課程分為兩期
| 期別 | 主軸 | 對應講義單元 |
| -------- | -------- | -------- |
| 語法班 | 對 C/C++ 語法及程式邏輯有基本的觀念 | 1-7 |
| 競程入門班 | 擁有進階的語法知識如浮點數的觀念、簡易 STL | 8-17 |
## 二、學完 Level 0 後你能做到什麼？
1. **電腦科學思維**：知道電腦能「快且準」地重複計算，並能拆解問題成演算法步驟。
2. **C 語言地基＋C++ 基礎**：資料型態、流程控制、陣列、字串、函式、指標、簡易 STL 容器。
3. **APCS 觀念＋實作**：[APCS(大學程式先修檢測)](https://apcs.csie.ntnu.edu.tw/) 實作可穩定達 三級分(涵蓋程式實作初級與中級的內容)，觀念題覆蓋一半以上內容。
4. **競程初級實力**：能解 [zero judge](https://zerojudge.tw/) 基礎題庫、[AtCoder Beginner Contest](https://atcoder.jp/contests/archive?ratedType=1&category=0) 大多數 A、B 題。
5. **為進階打底**：準備好進入 Level 1 學習基礎資料結構與演算法。
## 三、Level 0 課程不會學到的東西
1. AI／大數據／機器學習等專門領域（需先具備程式與演算法基礎，AA 競程的課程暫不涉獵這些領域）。
2. 進階資料結構與演算法（Level 1 起介紹）。
3. 遞迴（recursion）、基礎資料結構（basic data structures）、基礎演算法（basic algorithms）等 [APCS 程式試讀](https://apcs.csie.ntnu.edu.tw/index.php/questionstypes2025/) 中的進階主題（同樣於 Level 1 之後介紹）。
## 四、什麼是競程
* 競程是競技程式的縮寫，又稱為 [演算法競賽](https://zh.wikipedia.org/zh-tw/%E6%BC%94%E7%AE%97%E6%B3%95%E7%AB%B6%E8%B3%BD)，在台灣國中至大學都有相關的競賽，比較重要的競賽條列如下：
| 年紀 | 競賽名稱 | 舉辦時間 |
| -------- | -------- | -------- |
| 升國一 ～ 升大學 | [YTP 少年圖靈計劃](https://www.tw-ytp.org/) | 每年暑假 |
| 高三以下 | [資訊奧林匹亞](https://tpmso.org/toi/) | 每年 3 月~ 4 月 |
| 高中生 | 資訊學科能力競賽 | 每年的上學期 |
| 高三以下 | [美國資訊奧林匹亞](https://usaco.org/) | 每年 12 月 ~ 3 月 |
* 多數與軟體相關的行業會使用競程類型的題目來篩選面試者。
* 競程的比賽內容簡單來說就是<font color="red">利用電腦解數學問題</font>，這些問題都有明確的評斷好壞的方式！
* 有些比賽會讓大家做出一個 app 或產品，讓評審評判哪個好哪個壞，這樣的事情絕不會出現在競程。
* 以加法問題為例：
* 若是數學問題，會這樣問：「請計算 $3+5$ 的值。」
* 競程問題的例子： [TIOJ1002. A+B Problem](https://tioj.ck.tp.edu.tw/problems/1002)
這麼簡單的問題，為何需要用電腦來算？
實際上，所有寫程式能解出來的問題，人類用手算也一定能解的出來，主要差別在於<font color ="red">計算速度</font>，例如說，若上述加法問題改成要你一次解一億個加法運算，你要花多久時間才能算完呢？電腦的優勢是非常快的速度加快以及不需要睡眠，人類一生都算不完的計算量電腦一秒內就能計算完成！
那麼，競程的就只是把人類做的事寫成程式碼而已嗎？
No！就算解同樣的問題，也有好方法和壞方法之分。以下舉兩個問題為例。
---
1. 質數判定問題：「給你一個正整數 $x$，請判斷 $x$ 是否為質數。」
我們可以利用質數的定義：「質數必須大於 $1$，且除了 $1$ 和自己本身外，無法被其他自然數整除的數」，直接從 $2$ 枚舉到 $x-1$，看看是否每個數都不能整除 $x$ 來判定 $x$ 是否為質數。這是個能夠解決問題的方法，但是總共要枚舉 $x - 2$ 個數。
實際上我們可以用一些數學方法證明出只需要從 $2$ 枚舉到 $\sqrt{x}$ 就行了，如此一來要枚舉的數就少了非常多，明顯後者就是比前者好的方法。
---
2. 比較輕重問題：「給你 4 個重量不同的物品，你每次只能比較兩個物品的重量哪個輕哪個重，請問若想要知道哪個物品最輕，以及哪個物品最重，共要比較幾次？」
一個可能比較直覺的方法是，各花 $3$ 次比較分別求出最輕和最重的物品，總共需要 $6$ 次，但實際上有更好的方法可以更少次！這裡就留給大家自己思考。(在 Codeforces 這個競程練習平台上也能找到一模一樣的題目：[CF 730 B. Minimum and Maximum](https://codeforces.com/problemset/problem/730/B))
---
如上面所舉的兩個例子，大部分競程題目是在考驗大家能否設計出比較好的解決問題方法，**解決問題的方法** 就是「**演算法**」，這也就是為什麼這些比賽也被稱為「演算法競賽」。但設計出演算法後，我們還得把這些演算法用程式碼寫出來，才能在比賽中確實得分。把演算法用程式碼寫出來的能力就是「實作能力」，若沒有實作能力，設計出再好的演算法也沒有用。實作能力則和對程式語言的理解以及邏輯思維能力有關，所以 AA 競程的 Level 0 課程會先幫大家加強對程式語言的熟悉度以及基本的邏輯思維能力，如此一來之後學習演算法的路程才會更通順。
## 五、學前需求
### 5.1 電腦技能
1. 要有足夠快的打字速度，至少要練到寫程式碼時不需要花心思去思考要打的字在鍵盤上的位置。可在 [SpeedCoder Race](https://www.speedcoder.net/race/) 網站上練習。
2. 熟悉電腦各種快速鍵的使用如：複製、貼上、全選、尋找、截屏等功能。
3. 會使用搜尋引擎尋找資料，例如能夠查詢第一次接觸到的工具如何使用。
### 5.2 數學基礎
我們預期 Level 0 的學員擁有台灣國中二年級以下(包含二年級)的數學知識，以下列一些比較重要的數學概念：
#### 1. 負數的加減乘運算
* 能計算以下算式的結果：
$(-2) \times (-3) - 5 \times (-6+3)$
#### 2. 餘數的概念
* 能夠計算 $25$ 除以 $7$ 的餘數。
#### 3. 小數與分數的加減乘除運算
* 能計算 $1.1 \times 1.1$。
* 能計算 $\frac{3}{4} + \frac{4}{5}$
* 能計算 $\frac{3}{2} \div \frac{5}{-7}$。
* 能把 $\frac{18}{30}$ 變成最簡分數。
#### 4. 數學符號
* 絕對值：知道 |-5| 是什麼意思。
* 指數：會計算 $3^4$。
* 根號：知道 $\sqrt{121} = 11$。
* 向下取整、向上取整：會計算 $\lceil -3.5\rceil$、$\lfloor -2\rfloor$、$\lfloor \sqrt{5} \rfloor$。
#### 5. 數線及區間
* 懂的把數值標在數線上。
* 知道什麼是閉區間、開區間，知道 $[2,3)$ 的意思。
#### 6. 平面座標
* 能夠畫出 $x, y$ 軸，並把座標 $(-4,3)$ 標出來。
#### 7. 函數的概念
* 看得懂 $f(x,y) = |x-3| + (y-x)^2$ 這樣的函數，並能計算 $f(2, 3)$ 的值。
* 給一個函數 $f(x) = 2x+1$ 甚至是 $g(x) = \lfloor{\frac{x}{10}}\rfloor$，能把此函數在平面上描繪出來。
#### 8. 質數的概念
* 知道質數的定義。
* 知道 20 以內的質數有哪些。
#### 9. 數列
* 有數列的概念，知道什麼是下標、上標。
#### 10. 等差級數
* 會計算 $1+2+3+\ldots+100$、$7+10+13+\ldots+40$ 等。
#### 11. 因數與倍數
* 知道什麼是最大公因數和最小公倍數
#### 12. 集合、聯集、交集的概念
* 知道集合的定義
* 知道交集、聯集的定義，會計算 ${a, b, c}$ 和 ${b, c, d}$ 的聯集與交集
#### 13. 邏輯
* 邏輯推理能力，如：
* 能結合 $a < b$ 與 $b < c$ 推論出 $a < c$
* 能根據 $a < b$ 推論出 $2a < 2b$
* 能根據 $a < b$ 推論出 $-2a > 2b$
* 能結合 $a < b$ 與 $b < c$ 推論出 $a \le c$ (很多人會以為只能推論出 $a < c$)
* $A, B$ 是兩個事件，知道在若 $A$ 則 $B$ 的條件是成立時，非 $A$ 和 $B$ 也可能同時成立
## 六、學習時應有的心態
在開始進入正式教學內容前，有以下幾點要提醒大家：
1. **先入境隨俗，暫忘其他語言**
如果你已經寫過 Python、JavaScript…請先把那些語法規則放一邊。不同語言在整數除法、索引習慣、型別系統等處大相逕庭；硬把舊習慣套到 C/C++ 只會 Debug 到天荒地老。
> 例：Python 的 -3 // 2 會得到 -2，而 C++ 的 -3/2 結果是 -1，差一就可能讓你除錯除到天荒地老。
2. **多源學習，主動查證**
本講義只是導覽，不是百科全書。當你搞不清 `'\n'` 與 endl 有什麼差別時，就搜尋「C++ 換行 endl 與 '\n'」或翻閱 cppreference。至少看兩篇不同作者的說明，交叉比對、驗證真偽；仍有疑惑就把整理好的問題帶來和老師討論。
3. **語法班聚焦「競程中常見語法」**
語法班只會教程式解題及了解基礎程式邏輯概念的必要的語法，但也存在很多上課中沒提過的語法規則，這部分就讓有興趣的人以後自己研究了。
4. **競程是馬拉松，不是百米衝刺**
資訊奧林匹亞等競程比賽涵蓋的演算法博大精深，遠超教科書篇幅。按照學校數學課節奏，三年都講不完，更別說實戰。要有大量刷題與反思的心理準備：持續練習，才能追求卓越。
## 七、網路上競程相關的 C/C++ 語法教材
* [從零到一：那些演算法競賽會用到的基礎語法](https://emanlaicepsa.github.io/2020/10/21/0-index/)
* [2023 資訊之芽 C 語法班](https://sprout.tw/c2023/#!slides.md)
<div style="page-break-after: always;"></div>
# <font color = "blue">**第一單元：輸入輸出與算數運算**</font>
## 一、與編寫程式有關的檔案
從撰寫程式碼到產生出執行結果的過程中，牽扯到許多不同功能的檔案，包括：
1. 程式碼的編輯器：能讓大家編寫程式的「程式」。例如 [Code::Blocks](https://www.codeblocks.org/)，Code::Blocks 同時也是台灣 APCS 所提供的編輯器之一。現在也有許多網站提供編寫程式和執行程式的服務，例如 [OnlineGDB](https://www.onlinegdb.com/)。
2. 原始碼檔：也就是保存你寫的程式碼的檔案。
3. 編譯器：可以把你寫的程式碼轉換成執行檔的程式。
4. 執行檔：也就是你寫的程式碼轉換出來讓電腦真正在執行的程式！
以下列出相關表格並補充一些資訊。
| 名稱 | 作用 | 常見工具 |
| --------------------- | ----------------- | ------------------------------------------------------------------------- |
| **Editor**（程式碼編輯器） | 程式碼撰寫、上色、語法提示 | VS Code、Code::Blocks、線上 IDE（[OnlineGDB](https://www.onlinegdb.com/)、[replit](replit.it)） |
| **Source File**（原始碼檔） | 純文字檔，副檔名多為 `.cpp` | — |
| **Compiler**（編譯器） | 把原始碼轉成機器可執行的檔案 | `g++`, `clang++` |
| **Executable**（執行檔） | 真正跑在 CPU 上的程式 | Windows `.exe`、Linux 無副檔名 |
## 二、兩個 C/C++ 線上語法參考手冊
[cplusplus](cplusplus.com) 和 [cppreference](cppreference.com) 是學習 C/C++ 語法時，能參考的兩個網站。
以下表格做簡單的比較：
| 面向 | **cplusplus.com** | **cppreference.com** |
| -------------- | ---------- | ------------- |
| **維護者** | 個人維運為主。 | 維護方式類似維基百科，活躍貢獻者眾多。 |
| **核心定位** | 對初學者友善的教學手冊：<br>著重可讀性、生活化範例；條目較短。 | 按照 C++ 標準來介紹。 |
| **涵蓋 C++ 標準版本** | 版本比較舊，大多為 C++11 以前。 | 涵蓋比較新的語法，至 C++26 都有。 |
| **錯誤率** | 會有少數一些範例、說明出錯。 | 錯誤率極低，有人回報錯誤後會快速更新。 |
#### 給初學者的小建議
1. **先看 cplusplus**：建立「這工具能做什麼」的輪廓。
2. **再查 cppreference**：確認語法細節、版本限制、陷阱。
3. 發現兩邊描述不同 → 以 **cppreference** 為準，並實機測試。
## 三、兩個範例程式
**範例 1：輸出 Hello World**
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << "Hello, AACPSCHOOL!" << endl;
return 0;
}
```
**範例 2：讀入兩數，輸出兩數相加**
```cpp=
#include<iostream>
using namespace std;
int main() {
int A, B; // 宣告兩個整數
cin >> A >> B; // 依序讀入 A 和 B 兩個整數
cout << A + B << endl; // 輸出 A + B 的值
return 0;
}
```
## 四、範例程式共通部分介紹
1. `#include<iostream>`：[iostream](https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a00911_source.html) 是一個程式碼的檔案名稱。``#include<iostream>`` 簡單來說就是我現在寫的程式也要使用 [iostream](https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a00911_source.html) 這個檔案裡的程式碼。
2. `using namespace std;`：namespace 的中文翻譯是「命名空間」，我們可以看到 [iostream](https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a00911_source.html) 這個程式碼裡的大部分內容是使用 `namespace std ... {}` 包起來的，這代表著我們若要使用此命名空間(namespace)裡的東西，就必須先寫下`using namespace std;`這段文字。若沒寫這些文字的話，在使用此命名空間裡的物件或函式時，都必須在其前面加上``std::``，以下是第一個範例程式碼不使用 `using namespace std;` 的寫法：
```cpp=
#include<iostream>
int main() { // 程式會從 main 函式裡的第一行開始執行
std::cout << "Hello, AACPSCHOOL!" << std::endl; // 輸出 "Hello, AACPSCHOOL!"
return 0; // 結束主函式並回報程式正常結束
}
```
可看到在 cout 和 endl 前都加上了 ``std::``。當程式碼很長時，會有一堆地方都要加上 ``std::``。在競賽中為了加快解題速度，一般會直接加上 ``using namespace std;`` 以避免使用大量的 ``std::`` 來節省打字時間。
:::warning
**重要提醒**
在程式解題中，我們會為了減少程式碼長度而使用一些方便的語法，如 ``using namespace std;``，但實際上在多人合作開法程式，或者是寫比較龐大的專案時使用這種寫法是不妥的。
例如以下程式碼會編譯錯誤：
```cpp=
#include<iostream>
using namespace std;
int size = 4;
int main() {
cout << size << endl;
return 0;
}
```
編譯錯誤的提示可能為：``error: reference to 'size' is ambiguous``
這是因為 std 這個命名空間裡已經有 size 這個東西，而你又在宣告一個名為 size 的變數，就會導致編譯器無法辨別第 5 行的 size 到底是指什麼。
若無論如何都想要在 main 函式外面宣告一個名為 size 的變數，然後再 main 裡面輸出 size 的值，那應該要這樣寫：
```cpp=
#include<iostream>
int size = 4;
int main() {
std::cout << size << std::endl;
}
```
:::
3. `int main() { ... }`：在中文被稱為「主函式」(英文是 main function)。關於「函式」這個詞的解釋以後會再說明，現在只需要知道，電腦會在程式碼裡找到主函式，並從主函式大括號裡的程式碼一行一行依序執行。
4. `return 0;`：請先理解為此指令代表要離開它所在的函式，而當`return 0;` 是位於主函式裡，執行到此值令就代表程式要結束了，直接略過在此指令之後與函式所在的右大括弧之前的所有指令。教到函式後才會有更詳細的介紹。可嘗試執行以下程式碼，可發現 `Hello, AACPSCHOOL!` 只被印出兩次。
```cpp=
#include<iostream>
using namespace std;
int main() { // 程式會從 main 函式裡的第一行開始執行
cout << "Hello, AACPSCHOOL!" << endl;
cout << "Hello, AACPSCHOOL!" << endl;
return 0;
cout << "Hello, AACPSCHOOL!" << endl;
}
```
:::info
**補充資訊**
在 [cppreference 裡 Main function](https://en.cppreference.com/w/cpp/language/main_function) 的介紹是這樣寫的 The body of the main function does not need to contain the return statement: if control reaches the end of main without encountering a return statement, the effect is that of executing `return 0;`
翻譯成中文就是：主函式裡的 `return 0;` 可以省略，省略的效果相當於主函式最後有放 `return 0;`，所以有時候會看到有些示範程式碼不包含此指令。
:::
## 五、token
> token 有「詞語單元」、「令牌」、「標記」等各種中文翻譯，但此書之後提到時不翻譯，直接使用 token 稱之。
token 是 C++ 程式碼裡最小可辨識單位，類似於英文裡「單字」的概念，類型包括：
1. **關鍵字 (Keywords)**\
或稱「保留字」。已被規定有特殊意義的單字，如 `int`、`return`、`namespace` 等，完整的列表請參考 [此連結](https://en.cppreference.com/w/cpp/keyword)。
2. **識別碼 (Identifiers)**\
使用者自己取名的單字，如 ``A``,``B``,``endl``,``std`` 都是識別碼。
3. **字面常數 (Literals)**\
程式碼裡直接可識別是什麼意思的值，例如 ``1``、``"Hello, AACPSCHOOL!"``。
4. **運算子 (Operators)**\
``+``、``<<``、``>>`` 就是運算子，也就是我們數學上的運算符號的概念。
5. **特殊符號 (Special Symbols)**\
如 ``;``、``,``、``(``、``)`` 以及夾住 iostream 的 ``<`` 和 ``>`` 都屬這類。
**token 間的排版規則為：**
1. 相鄰的兩個「關鍵字 / 識別碼 / 字面常數」之間 **必須** 以至少一個空白或是換行分隔。
2. 「運算子」與「特殊符號」前後的空白可有可無。
:::warning
**重要提醒**
雖然以下程式碼也是個能正常運行的程式碼：
```cpp=
#include <iostream>
using namespace
std;
int main(){int a,b;cin>>a>>b;cout<<a+b<<"\n";return 0;}
```
但是考慮到程式碼的可讀性及容易維護程度，**請不要寫出下面這樣的程式碼**。初學時請按照老師給的範例程式碼的格式來撰寫程式碼，當對 C++ 語法了解更深後，可自行參考 [Google C++ Style Guide](https://google.github.io/styleguide/cppguide.html) 學習大家公認比較好的程式碼風格 (coding style)。
:::
:::info
**補充資訊**
網路上有很多網站都提供幫你把程式碼變得漂亮的服務如：[formatter.org
](https://formatter.org/cpp-formatter)。
若你是 IDE 的使用者，也可以查查看你使用的 IDE 是否有自動幫你排版、美化程式碼的功能或外掛。
:::
## 六、statement
> statement 有「語句」、「敘述」、「陳述式」等各種中文翻譯，此書採用「陳述式」這個翻譯。
以下方程式為例，第 $4$ 至第 $7$ 行的每一行都是一個 [statement](https://en.cppreference.com/w/cpp/language/statements)，都是以**分號**做結尾，忘記加分號就會發生編譯錯誤。
statement 有非常多種類型，目前的範例程式碼裡只出現 declaration statements(宣告陳述式，第 $4$ 行)、expression statements(運算陳述式，第 $5$、$6$ 行) 和 jump statements(跳躍陳述式，第 $7$ 行)。
```cpp=
#include<iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B;
cout << A + B << endl;
return 0;
}
```
## 七、註解
有時我們會想要用文字輔助別人或未來的自己看得懂自己當下寫的程式碼，但這些文字又必須不影響到程式的執行，此時可以使用註解。C++ 的註解有兩種形式：
#### 1. **單行註解**
當任何地方出現連續兩個斜線，也就是`//` 後，斜線本身以及斜線後面的文字都不會影響到程式碼。所以我們的代碼可以寫成如下：
```cpp
#include<iostream>
using namespace std;
int main() {
// 輸出英文的「我愛 AA 競程的課程」
cout << "I love lessons of AACpSchool." << endl;
return 0;
}
```
#### 2. **多行註解**
可以用 `/*` 和 `*/` 把不要電腦執行的地方包住，例如：
```cpp
#include<iostream>
using namespace std;
int main() {
/* 這
是
測
試
*/
cout /*這是測試 2*/ << "I love lessons of AACpSchool." << endl;
return 0;
}
```
:::info
**補充資訊**
以上關於註解的描述有例外情況：
* 註解放在字元或字串的字面常數裡並沒有特殊意義
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << "/* Hello */ World!\n" << endl;
}
```
此程式會輸出：
```txt=
/* Hello */World!
```
另外，多行註解並非巢狀結構，在第一個 `/*` 之後遇到第一個 `*/` 之間夾住的地方就是註解的內容，不會因為多夾住了一個 `/*` 導致多行註解要到第二個 ``*/`` 才結束，請看以下例子：
```cpp=
#include<iostream>
using namespace std;
int main() {
/* "/* */ cout << " */ Hello!" << endl;
}
```
此程式會輸出：
```txt
*/ Hello!
```
:::
## 八、記憶體與記憶體的計量單位
記憶體是電腦用來儲存資料的硬體設備。
記憶體有以下這些單位：
1. **位元(bit)**
**位元** 是記憶體的最小單位，只能表示兩種值：$0$ 和 $1$。
2. **位元組(byte)**
**位元組** 是記憶體用來儲存資料的最小單位，在一般情況 $1$ 位元組等於 $8$ 位元。
3. **KB, MB, GB, TB**
* $1$ KB = $1024$ ($2^{10}$) bytes
* $1$ MB = $1024$ KB
* $1$ GB = $1024$ MB
* $1$ TB = $1024$ GB
## 九、資料型態
1. **什麼是資料型態**
請大家先回答一個看似無關緊要的問題：以下紅框框裡的符號是什麼？
可能有人會回答：「大寫英文字母 T」，也可能會有人回答：「注音符號ㄒ」，不過實際上，這張圖是從維基百科上截下來的希臘字母中的第 19 個字母。
也就是說，就算是同一個符號，若沒有好好解釋它是那一種類的符號，還是無法知道該符號是什麼意思。而儲存在記憶體裡的資料也是這樣，若沒說明清楚他是那一種類型的資料，那就無法好好解讀儲存在記憶體裡的內容。
而在 C++ 裡，就要求程式碼裡若使用到任何資料，都一定要指定清楚該資料是那種類型，也就是指定該資料是哪種「資料型態」。
2. **基本資料型態(Fundamental types)**
> Fundamental types 有 「內建類型」、「基本資料型態」、「基礎資料型態」等稱呼，此書稱之為「基本資料型態」
基本資料型態是在不需要引入任何函式庫的情況下，C++ 原本就提供給你使用的資料型態，如果想要使用更複雜的型態就得自己創造或引用函式庫了(如何自己創造會在以後的單元介紹)，按照常見使用情境可分成以下四組：
(1) Integer (整數)：用來儲存整數，下個小節會介紹。
(2) Floating Number (浮點數)：用來儲存實數的資料型態，但通常無法精確儲存數值，存下來的值會是近似值。包含`float`, `double`, `long dobule` 三種，在競程中只推薦使用 `double` 和 `long double`。在第九單元會有更詳細的介紹。
(3) Boolean (布林)：單指 `bool` 這個資料型態，在第二單元會介紹。
(4) Character (字元)：在競程中主要會用到的是 `char`，我們平常見到的英文字母、數字、英文標點符號，甚至是空白、換行都是字元的一種。此單元第十一小節會介紹。
*註：以上分類是參考 [cplusplus: Fundamental data types](https://cplusplus.com/doc/tutorial/variables/) 中的介紹，
在 cppreference 上分類方式並不一樣。*
:::warning
**重要提醒**
C++ 的基本資料型態並不包含「字串」，若想要用單一變數儲存字串，在 AA 競程語法書下冊會提到 string 這個容器(可把「容器」這個詞理解成是比較複雜、高級的資料型態)可以儲存字串。
:::
## 十、整數資料型態
C++ 提供非常多種類型的整數資料型態，並且同一種資料型態可能有多個別名。C++ 並沒有規定整數資料型態中，每個資料型態的位元數的精確數值，而是規定它們「**至少**」要有多少位元。例如說，對於最常被大家使用的 **int** 來說，其實 C++ 標準只規定它至少要有 16 位元，但一般在解題我們都直接把它當作有 32 位元來使用。
**以下表格只列出在程式解題時，各種整數資料型態的位元組數及數值範圍**。C++ 標準的規定及各種資料型態的別名請參考：https://en.cppreference.com/w/cpp/language/types
| 資料型態名稱 | 在競程環境下位元組數量 | 在競程環境下數值範圍 |
| -------- | ------ | ------- |
| short | 2 | −32768 to 32767 |
| int | 4 | −2,147,483,648 to 2,147,483,647 |
| long | 4 或 8 | −2,147,483,648 to 2,147,483,647 或 −9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 |
| long long | 8 | −9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 |
整數資料型態又分為 signed (有號) 和 unsigned (無號) 兩種，上方表格列的都是有號的整數型態，無號的整數資料型態範圍會是從 $0$ 開始，不包含負數，請見以下表格：
| 資料型態名稱 | 對應的有號型態名稱 | 在競程環境下數值範圍 |
| -------- | ------ | ------- |
| unsigned short | short | 0 to 65535 |
| unsigned int | int | 0 to 4,294,967,295 |
| unsigned long | long | 0 to 4,294,967,295 或 0 to 18,446,744,073,709,551,615 |
| unsigned long long | long long | 0 to 18,446,744,073,709,551,615 |
:::danger
**新手常犯錯誤警告**
在競程比賽時請大家不要使用 long，因為 long 在不同競賽平台上佔的位元數不一樣，容易搞混而出錯。
例如，在 Codeforces long 只佔 32 位元，但在 Atcoder 上佔 64 位元。
有很多程式新手會因為誤以為在 Codeforces 上 long 也是佔 64 位元而出錯。
:::
:::success
**重要資訊**
可使用 cout << sizeof(資料型態) << endl; 來輸出一個資料型態佔幾個位元。
例如：``cout << sizeof(int) << endl;``
:::
## 十一、字元資料型態與跳脫字元
字元是用來儲存英文字母、數字、英文標點符號等的資料型態，每種符號都會對應到一個數字，可參照 [ASCII 表](https://en.cppreference.com/w/cpp/language/ascii)。
在競程中有機會用到的此類資料型態為 `char`。
:::info
**補充資訊**
字元的資料型態除了 char 以外，還有 unsigned char、signed char，這 $3$ 種資料型態都只能儲存 ASCII 表裡的符號。
若要儲存中文等其他語言的文字，要使用 char16_t、chart32_t 等，此書不會介紹
根據 [cppreference: Character types](https://en.cppreference.com/w/cpp/language/types.html#Character_types) 中所描述：char 並不一定是 unsigned char 或 signed char。
不過這通常不影響競程使用到的程式。
:::
在程式碼裡我們要表示一個字元常數時，必須把字元用單引號括起來如下：
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << 'A' << endl; // 輸出一個字元 A
}
```
若我們要輸出 `'` 這個字元，就得這樣寫：
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << '\'' << endl; // 輸出一個字元 '
}
```
這樣的寫法被稱為「跳脫字元」(Escape character)，是由 `\` 和另一個字元組成，讓我們有辦法在程式碼裡表示具有特殊意義的字元，除了 `'` 外，還有反斜線 `'\\'`、單引號`'\''`、雙引號`'\"'`。
甚至換行也能用跳脫字元來表示，寫作`'\n'`。
跳脫字元的詳細列表及更進階用法請見：https://en.cppreference.com/w/cpp/language/escape
其餘關於字元的知識我們會在第八單元介紹。
## 十二、變數
### 1. 變數與記憶體
記憶體是電腦用來儲存資料的硬體設備，記憶體裡的位置會用數字編號。當我們宣告一個變數時，電腦就會為我們分配位置來儲存我們宣告的變數，此後我們使用或修改此變數，實際上就是在使用或修改該變數被分配到的記憶體位置裡儲存的資料。
:::info
**補充資訊**
可使用以下方式來查看宣告的變數所使用的記憶體位置
```cpp=
int x, y;
cout << (long long)&x << endl;
cout << (long long)&y << endl;
```
也就是輸出時，在變數前面加上 `(long long)&`，以後會再介紹這是什麼意思
:::
### 2. 變數的宣告方式
宣告變數的語法為：``資料型態名稱 變數名稱; ``
例如：``int A;``
也可以同時宣告很多個同一種資料型態的變數，只要在相鄰兩個變數名稱間恰加一個逗號即可，語法為 ``資料型態名稱 變數名稱1, 變數名稱2, 變數名稱3, ..., 變數名稱n;``
例如：``int A, B, C;``
### 3. 變數的命名規則
變數名稱必須是識別碼 (Identifiers)，而識別碼的規則如下：
(1) 變數名稱由 **底線、半形大小寫英文字母、數字** 所組合而成的。
(2) 變數名稱第一個字母不可以是數字。
(3) 變數大小寫是有區分的。例如說，變數 `a` 和 `A` 是不一樣的。
(4) 不能使用 [C++ 的關鍵字(C++ Keywords)](https://en.cppreference.com/w/cpp/keyword) 當作變數名稱。「關鍵字」是指在 C++ 裡面已經有特殊意義的單詞，例如：int、bool、if、for 等等已有其他用途的單詞都不能當作變數名稱。
:::info
**補充資訊**
要在 cppreference 查變數命名規則，要到識別碼的介紹頁面：
https://en.cppreference.com/w/cpp/language/identifiers
:::
### 4. 全域變數 (Global variable) 與局部變數 (Local variable)
當變數是宣告在函式外面時，就是全域變數，否則就是局部變數。
```cpp=
#include<iostream>
using namespace std;
int x; // 宣告在這裡是全域變數
int main() {
int y; // 宣告在這裡是局部變數
cin >> x >> y;
cout << x + y << endl;
return 0;
}
```
### 5. 變數的初始化
我們可以在宣告變數的時候，就給變數一個初值，例如：
```cpp
int a = 5, b = 10;
```
，如此一來我們就宣告了兩個變數 $a$ 和 $b$ 且他們的值分別是 $5$ 和 $10$。
若在宣告時沒有給定初值，分兩種情況：
(1) 如果該變數是全域變數，初值就是一定是 $0$。
(2) 如果該變數是局部變數，初值可能是任意的值。
:::danger
**常犯錯誤警告**
普遍人類在競程上常犯的錯誤之一就是誤把沒初始化的整數局部變數他的初值也當作 $0$，這是有好幾年經驗的競程老手也會犯的錯誤
:::
:::danger
**新手常犯錯誤警告**
這裡有兩個相關的程式新手常犯的編譯錯誤：
1. 使用一個變數之前沒有宣告它
2. 宣告變數的位置在使用它的位置之後
**也就是說，在使用任何一個變數時，一定要先宣吿它，而且宣告的值令必須為在使用的指令之前。**
:::
## 十三、cin 和 cout 的使用方式
cin 可以用來讀入程式使用者輸入的參數，語法為 `cin >> 變數名稱;`，實際的例子為：`cin >> x;`，也可以一個輸入多個變數，每個變數前面都要有個 `>>` 符號，例如： `cin >> x >> y >> z;`，輸入的變數可以是任何基本資料型態，輸入時會自動忽略空白及換行(也就是 Enter 鍵)。
cout 則用來輸出變數到螢幕，語法為 `cout << 變數名稱;`，例如：
```cpp
int x = 2;
cout << x << endl;
```
這樣就會把變數的值輸出到螢幕上，後面的 ``endl`` 是換行的意思。
若只是要輸出一個字元，則是用單引號把要輸出字元夾住，例如：
```cpp
cout << 'A' << endl;
```
若要輸出字串則是：`cout << "here is the text content";`，例如：
```cpp
cout << "Hello, aacpschool\n";
```
，雙引號裡的文字也可使用跳脫字元，例如 `\n` 就是換行的跳脫字元。
和 cin 相同，也可以一個 cout 輸出很多東西，每個輸出的東西前都要有 `<<` 符號，如： `cout << x << " " << y << "\n";`
:::danger
**新手常犯錯誤警告**
1. cin 是用 >>，cout 是用 <<，新手很容易搞反，此錯誤是編譯錯誤
2. 要輸入和輸出兩個以上的東西時，東西是用 << 或 >> 隔開，新手很容易寫成逗號(`,`)，此錯誤仍然可以編譯成功，但會出現編譯器警告
:::
## 十四、字面常數(literal)
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << 321 << endl;
cout << 'A' << endl;
cout << "Hello!" << endl;
};
```
執行以上程式碼，會輸出 $3$ 行如下：
```txt=
321
A
Hello!
```
可發現在程式碼裡面我們打了什麼，就輸出了什麼。像 `321`、`'A'`、`"Hello!"` 這樣子的 token 被稱為「字面常數」，它們分別是整數、字元、字串的字面常數。以下對它們做介紹：
1. **整數的字面常數：**\
整數的字面常數最一般的寫法是一個整數數字再加上一些字母構成的後綴 (Suffix) 如 `123ULL`，常用到的後綴有：`U`、`LL`、`ULL`。`U` 代表這個數字是無號整數，LL 代表這個數字的資料型態是 long long。U 和 LL 寫成小寫也 ok，且 U 和 LL 的順序也可以對調。例如，`123U`、`654Ull`、`-789LL` 都是正確的整數字面常數寫法。\
\
我們能根據字面常數的寫法來判斷它是什麼資料型態，就算沒有加上 `LL`，也仍可能是 long long 的資料型態。
整數字面常數的資料型態是如何被決定的可參考 cppreference 在 [Integer literal](https://en.cppreference.com/w/cpp/language/integer_literal) 附的表格。\
首先，先根據該整數字面常數的字母後綴來找到表格中對應的欄位，例如當沒有任何後綴時，對應的欄位裡(也就是 no suffix)依序寫著三種資料型態：`int`、`long int`、`long long int` 編譯器會由上往下找到第一個能儲存此數字的資料型態，所以，`100` 會是 int，而 `1000000000000000000 ` 是 `long int` 或 `long long int` (如果 long int 是 64 位元，就會是 `long int`，否則若 `long int` 只有 32 位元，就會是 `long long int`)。也就是說，若要強制一個常數的資料型態是 `long long`，就要在他的後綴加上 `LL`, 或`ll`。
2. **字元的字面常數：**\
用兩單引號(`'`) 夾起來的東西就是字元的字面常數，例如 `'a'`、`'\n'`。單引號裡只能有恰一個字元或恰一個由反斜線開頭的跳多字元。
3. **字串的字面常數：**\
用兩個雙引號(`"`) 夾起來的若干個字元就是字串的字面常數，例如 `"Hello!"`，甚至可以是零個字元如：`""`，代表空的字串。
## 十五、運算式 (Expressions)
「運算式」的概念和數學上列的式子很像，都是由運算子和運算元組成，例如運算式 `1+2*3` 中，`+` 和 `*` 就是運算子，而數字就是運算元。
根據功能可把運算子分為一些類別如：算術運算子、指派運算子等(完整分類可參考 [cppreference: Expressions](https://en.cppreference.com/w/cpp/language/expressions.html))，此單元我們就只先介紹算術運算子中最基礎的五個運算子：`+`(加)、`-`(減)、`*`(乘)、`/`(除)、`%`(取餘)，並且只先介紹運算元是整數資料型態時的運作原理。
以下用條列的方式介紹運算式與運算子的規則。
1. 加、減、乘和數學上的運作方式一模一樣，例如 `cout << -3 * 5 << endl;` 會輸出 `-14`，而`cout << -3+5 << endl;` 會輸出 `-1`。
2. 「除」與「取餘」運算對應到數學課裡所教的除法中，「商」與「餘數」的概念，例如 $7$ 除以 $3$ 的商是 $2$，餘數是 $1$，那 `7 / 3` 運算結果就是 `2`，`7 % 3` 的運算結果就是 `1`。可用以下程式碼測試：
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << 7 / 3 << endl; // 輸出 2
cout << 7 % 3 << endl; // 輸出 1
return 0;
}
```
但若運算元有負數時，運算規則是什麼呢？請先實驗以下程式碼：
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << 7 / 3 << endl; // 輸出 2
cout << -7 / 3 << endl; // 輸出 -2
cout << 7 / -3 << endl; // 輸出 -2
cout << -7 / -3 << endl; // 輸出 2
cout << 7 % 3 << endl; // 輸出 1
cout << -7 % 3 << endl; // 輸出 -1
cout << 7 % -3 << endl; // 輸出 1
cout << -7 % -3 << endl; // 輸出 -1
return 0;
}
```
可發現在被除是的絕對值是 $7$，除數的絕對值是 $3$ 的情況下，除法的運算結果的絕對值都是 $2$，這是因為 C++ 的除法的運算規則叫做「向零取整」，這意思是，若把真實的結果算出來寫成小數後，直接把小數點後面的位數都捨棄，例如 $\frac{-7}{3}=-2.3333...$，把小數點的位數捨棄後就剩下 $2$。
而取餘運算的結果必須滿足 `(a / b) * b + a % b == a`，就結論而言，在算取餘時，可以先忽略正負號來做取餘運算，並若被除數是負號，結果就要再加上負號。
3. 和數學上的運算子一樣有優先級的概念，「乘」、「除」、「取餘」的優先級一樣，「加」、減的優先級一樣，若優先級相同，則左邊的先算。例如：`7-5%3*2` 會先計算 `5%3`，得到 `2`，再計算 `2*2`，得到 `4`，最後再計算 `7-4`，得到 `3`。
4. 和數學上的運算式類似，可增加括號來改變運算順序。但要注意，數學課上的括號有小、中、大括號之分，但在 C++ 裡不管是第幾層的括號，一率使用小括號。例如：`((2+3)*2-1)/5` 是正確的表達是寫法，但不能寫成 `[(2+3)*2-1]/5`。
:::success
**重要資訊**
運算子的優先級可在以下連結查看：
https://en.cppreference.com/w/cpp/language/operator_precedence \
Precedence 越小的運算子，優先級越高
:::
:::warning
**重要提醒**
在不同程式語言中，整數除法與取餘的定義可能不一樣，例如在 Python 中，整數除法的規則是向下取整，而不是向零取整。
:::
## 十六、指派運算子
`=` 符號被稱為[指派運算子](https://en.cppreference.com/w/cpp/language/operator_assignment)。它也可以和其他 **算術運算子** 做結合，如`+=`、`-=`、`*=` 等。
1. `變數 = 運算式;` 是程式中要把某個變數的值變動的語法格式。例如 `a = 2 + x;` 就是把 `a` 的值改成 `2 + x` 的意思。**<font color="red">左邊的變數也可以出現在右邊的運算式裡</font>**，例如 `a = (a * 2) % 5 ;`。
2. 可以在一個指令內把多個變數指派為同一個值如：`a = b = c = 4;` 代表 $a, b, c$ 的值更改為 $4$。
3. `a *= a + 1;` 是 `a = a * (a + 1);` 的縮寫。而 `b -= x + y;` 是 `b = b - (x + y);` 的縮寫，也就是說，`變數 *= 運算式;` 相當於在執行 `變數 = 變數 * (運算式);`，乘號可改為任意算術運算子。
:::danger
**新手常犯錯誤警告**
指派運算子的左側只能是單一一個變數，不能是多個運算元組成的表達式，舉例來說，以下程式碼是不符合 C++ 語法規則，會發生編譯錯誤
```cpp=
a + b = c;
```
:::
## 十七、[未定義行為 (undefined behavior)](https://en.cppreference.com/w/cpp/language/ub)
在 C++ 中有些程式碼雖然可以順利地編譯，但某些狀況是編譯器不預期會發生的事，但若真的發生時，編譯器可以隨自己喜好處理，這樣的事情被稱為「**未定義行為**」，英文為 **undefined behavior**，縮寫為 **UB**。在此單元可能遇到的未定義行為有：
1. 「局部變數未初始化」是一種未定義行為，所以未初始化的局部變數什麼值都有可能出現。
2. 進行整數除法或取餘運算時，若除數是 $0$ 是一種未定義行為，通常處理方式是直接報錯並中斷程式執行。
3. 「整數溢位」也是一個常見的未定義行為，下一小節會介紹。
:::danger
**常犯錯誤警告**
由於「未定義行為」會造成同一份程式碼在不同環境下的執行結果不同，於是有可能發生以下情境：
> 在自己電腦上測試能通過範例測資，但傳到 OJ 上卻連範例測試資料都無法通過
當遇到這種情況時，常見的原因之一就是程式碼裡含有未定義行為。
:::
:::info
**補充資訊**
除了未定義行為，還有兩個相似的概念：未指定行為(unspecified behavior) 和 實作定義行為(implementation-defined behavior)。
「未指定行為」代表 C++ 標準預期你會寫出來這樣的程式，並給出一些可能的執行結果，編譯器會確保執行結果是指定的可能結果之一，但不需要說明是哪一種，且每次邊溢出來的程式執行結果可能不同。
「實作定義行為」代表雖然在不同環境下執行結果可能不同，但編譯器必須明確說明到底會發生什麼事，每次執行的結果也都一樣。
:::
## 十八、整數溢位
請先實驗以下程式碼：
```cpp=
#include<iostream>
using namespace std;
int main() {
int x = 100000;
cout << "the square of x is "<< x * x << endl;
}
```
執行此程式碼會輸出：
```txt
the square of x is 1410065408
```
看到這大家應該會覺得很奇怪， $x$ 的平方不應該是 $10000000000$ (也就是 $10^{10}$) 嗎?為什麼會跑出奇怪的數字呢？
這是因為 $x$ 的資料型態是 `int`，而 C++ 預期兩個 `int` 運算的結果也是 `int` 的資料型態，但 $10^{10}$ 超過 `int` 的範圍，所以沒辦法用 int 表示正確答案，就會算出一個奇怪的結果。
「兩個 `int` 的值運算的結果並無法用 `int` 表示」這類的事情被稱作「整數溢位」，英文是 [Integer overflow](https://en.wikipedia.org/wiki/Integer_overflow)。C++ 把有號整數的「整數溢位」視為「未定義行為」，這代表正常的程式裡不應該發生這樣的行為，若真的發生，雖然編譯能通過，但執行結果什麼都有可能發生。
那麼在前面的例子，我們要怎麼正確求出 $100000$ 的平方呢？相當多人會這樣想：「既然平方後的結果雖然不能用 int 儲存，但可以用 long long 儲存，那我們就先宣告一個 long long 的變數把結果存下來再輸出即可」，於是就寫出以下程式碼：
```cpp=
#include<iostream>
using namespace std;
int main() {
int x = 100000;
long long result = x * x;
cout << "the square of x is " << result << endl;
return 0;
}
```
但執行後可發現輸出仍不符合預期。這是因為「運算子」是按照某種順序一個一個被執行的，在以上程式碼的第 $3$ 行中，乘法運算子會先被執行，在執行時並不會去預先判斷運算結果會被指派給一個 `long long` 的變數，所以運算結果仍然會先用 `int` 儲存，此時就已經發生「整數溢位」，運算完後再把此錯誤的結果指派給 result 這個變數，result 得到的值當然還是錯的。
要解決這個問題最簡單且粗暴的方法就是把 x 改為用 `long long` 型態宣告。所以當大家在寫這個單元的習題時，若發現運算結果會超過 int 範圍，就直接把所有變數都用 `long long` 宣告吧！下個單元我們會再教更合理的防止整數溢位的程式碼寫法。
:::info
**補充資訊**
無號的整數資料型態發生「整數溢位」並不是「未定義行為」，因為 C++ 有規定，若一個無號整數的資料型態是 $n$ 個位元，那麼兩個此無號整數型態的變數運算結果就是數學的的運算結果除以 $2^n$ 的餘數。
cppreference 裡關於有號整數和無號整數的「整數溢位」的說明可在以下連結的 Overflows 欄位找到。\
https://en.cppreference.com/w/cpp/language/operator_arithmetic.html
:::
## 十九、編譯錯誤訊息
當程式碼有語法錯誤時，編譯時編譯器會回報錯誤訊息，例如以下程式碼編譯時會回報類似於 `program.cpp:4:12: error: 'x' was not declared in this scope` 這樣的訊息。這個訊息提醒我們 x 並未被宣告。
```cpp
#include<iostream>
using namespace std;
int main() {
cin >> x >> y;
cout << x + y << endl;
return 0;
}
```
現在我們把程式碼改為：
```cpp
#include<iostream>
using namespace std;
int main() {
int x, y
cin >> x >> y;
cout << x + y << endl;
return 0;
}
```
它的錯誤訊息變為 `program.cpp:5:5: error: expected initializer before 'cin'` ，但是依我們目前擁有的知識，是看不懂它在說什麼。但沒關係，這種時候我們可以把錯誤訊息拿去搜尋引擎搜尋，多看幾個回答，就會發現有不少回答有提到類似`You forgot a semicolon` 這樣的句子(如[這個回答](https://cplusplus.com/forum/beginner/8607/))，我們就可以知道很有可能是因為我們忘記在某個地方加分號。
同時我們也看到，在這個例子中雖然錯誤訊息裡是寫著錯誤發生在第五行，但真正寫錯的地方是第四行，這是因為編譯器要執行到第五行時才會發現這個錯誤，這種「錯誤訊息指出的錯誤行數和你實際寫錯的行數並不相同」的情況是常常有的。所以以後請注意，有些時候錯誤是因為更前面的行數寫錯而造成，但由於編譯器在更後面的地方才能判斷出你程式碼真的有寫錯，所以提示你的錯誤行數可能會比較後面。
最後總結三個重點：
1. 我們可以根據錯誤訊息來尋找程式碼哪裡語法錯誤。
2. 有時候會發生看不懂錯誤訊息，或是編譯器誤會程式碼想要做的事情，這時可以藉由搜尋引擎來尋找錯誤原因，因為一般而言，**<font color="red">你犯的錯誤早就有千千萬萬個人犯過且問過了</font>**。
3. 錯誤訊息提示的行數偶爾會和你寫錯的位置對不上。
<div style="page-break-after: always;"></div>
# <font color = "blue">**第二單元：線上評測系統介紹**</font>
## 一、線上評測系統
在「寫程式」這項工作已非常盛行的這個時代，有非常多讓新手練習寫程式的網站，這些網站被稱作「Online Judge」(這裡把它翻譯為線上評測系統，維基百科則稱它為「[線上解題系統](https://zh.wikipedia.org/zh-tw/%E5%9C%A8%E7%BA%BF%E8%AF%84%E6%B5%8B%E7%B3%BB%E7%BB%9F)」)，通常被簡稱為「OJ」，在 OJ 裡，你只要提交程式碼，系統就會自動幫你判斷你的程式是否正確解出某道題目。
為了使做題更順利，你必須清楚了解線上評測系統是如何判斷你的程式是否正確的，也必須知道你上傳的程式出錯時，網站回饋給你的資訊代表什麼意義。
## 二、各大 OJ 介紹
雖然語法營的階段會讓大家在 AA 競程架設的 OJ 上練習，不過在競程入門班之後，大家會漸漸接觸到更多知名 OJ，這裡先列出介紹一下。
1. [Codeforces](https://codeforces.com/)\
這是世界上最多人使用的 OJ，題目都比較新穎，平均每個禮拜都會辦個 2 場以上的比賽，一場比賽的參賽人數可高達 3 萬人。
2. [Atcoder](https://atcoder.jp/)\
這是日本最大的 OJ，每週也都會固定辦比賽，特別推薦 AA 競程 Level 1 以上程度的人參加其中叫做 Atcoder Beginner Contest 的系列比賽。要配合 [kenkoooo Atcoder Problems](https://kenkoooo.com/atcoder) 這個網站使用，比較容易找到過去比賽的題目。
3. [CSES Problem Set](https://cses.fi/)\
這是一個知名的競程題庫，目前有 $400$ 題，涵蓋競程多數經典題，有配合題庫的電子書 [Competitive Programmer’s Handbook](https://cses.fi/book/book.pdf) 可以學習，適合已具備 C++ 語法知識的人練習，題目程度大多是 AA 競程 Level 1 以上。
4. [NCOJ](https://oj.ntucpc.org/)\
這是台大程式解題社架的網站，包含過去台大舉辦的 APCS Camp、IOI Camp 的題目，也能找到 YTP 少年圖靈計劃的考古題。
5. [TIOJ](https://tioj.ck.tp.edu.tw/)\
這是建中傳承已久的 OJ，早期全台灣不少學校都會在此平台辦比賽，但後來幾乎只會新增建中資訊能力競賽校內賽的題目以及一些全國性比賽的考古題。
## 三、OJ 如何判斷你的程式是否正確?
OJ 在判定你程式碼是否正確的方式如下：\
系統裡有很多事先產生好的隱藏測試資料(通常不會超過 $200$ 組)，看看你的程式碼是否能把在所有隱藏的測試資料都回答正確。
以 TIOJ 裡的一道題目 [TIOJ 1002. A + B Problem](https://tioj.ck.tp.edu.tw/problems/1002) 為例，以下把此題的必要元素都列出來：
> **Problem Name**：A+B Problem
>
> **Description**\
> 請計算 $a + b$。
>
> **Input Format**\
> 一行包含兩個正整數 $a, b$ ($0 \le a, b \le 10$)。
>
> **Output Format**\
> 輸出一行包含一個數字，代表 $a+b$ 的結果。
>
> **Sample Input 1**\
> 1 2
>
> **Sample Output 1**\
> 3
>
> **Time Limit (ms)**\
> 500
>
> **Memory Limit (KiB)**\
> 65536
這道題其實就是第一單元範例程式 $2$ 在解的問題，系統裡會放有此題的一些隱藏測試資料，例如可能是 `10 0`、`8 9`、`0 5` 等，但不可能是 `1 3 2`，因為輸入只有兩個數字，也不可能是 `-5 3`，因為在 Input Format 裡有用括號註明隱藏測試資料裡的 $a, b$ 範圍必須大於等於 $0$ 且小於等於 $10$。
有些 OJ 能看到共有幾組隱藏測試資料，且可能可知道你的程式碼在每個隱藏測試資料是否答對，例如此題其實只有兩筆隱藏測試資料。
通常出現在題目裡的範例輸入(Sample Input) 也都會被放在隱藏測試資料，這題(應該)也不例外，所以若你若用以下程式碼直接輸出 $3$ 就能答對第一個子題。
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << '3' << endl;
return 0;
}
```
OJ 並不會管你的程式碼在輸出時，究竟輸出的東西是什麼資料型態，所以無論是輸出數字 $3$ 還是輸出字元 `'3'`，只要輸出的結果和標準答案一樣，都同樣能答對。
:::danger
**新手常犯錯誤**
有很多人會誤以為自己的程式碼只要在 OJ 上能答對就是正確的了，但還是有可能該份程式碼只是剛剛好在 OJ 給定的隱藏測試資料都答對了，卻在沒出現在隱藏測試資料某些測試資料上會答錯。而且這樣的事情發生頻率其實是非常高的，依筆者經驗，對於初學者，這種情況發生頻率高達 5% 以上。
:::
## 四、競程題目的組成
#### 1. 題目名稱 (Problem Name)
每道競程題目就像國文課文一樣，都會有一個標題，請大家不要小看標題，有些時候，出題者會把提示藏在標題裡(或者反過來用標題擾亂作答者)。
#### 2. 題目描述 (Problem Description)
此區塊目的為提供問題的背景、目標和具體任務，但不一定會把所有細節都寫在此區塊。
#### 3. 輸入格式 (Input Format)
此區塊會提供測試資料的精確格式，以 [TIOJ 1002. A + B Problem](https://tioj.ck.tp.edu.tw/problems/1002) 為例，題目敘述只告訴你會給你兩個整數，但不會告訴你這兩個整數是各自佔一行，還是會放在同一行裡，就算題目描述一樣，輸入格式不同會影響程式碼該如何實作。
#### 4. 範圍限制 (Constraints)
範圍限制指的是會告訴你所有隱藏測試資料的每個參數會落在哪個範圍裡面。
有些題目會把範圍限制直接放在輸入格式裡，當輸入格式裡提到一個變數時，就一同介紹此變數的範圍。也有些題目會把這部分從輸入格式中獨立出來(如 Atcoder 的題目都屬於這類)。
#### 5. 輸出格式 (Output Format)
指定程式如何呈現輸出。例如題目若有道題是輸出兩個數字作為答案，那到底是誰先誰後，以及兩個數字是否要換行等都是在此區塊裡描述。\
<font color = "red">註：有些 OJ 其實不管你輸出的兩個東西間究竟是空白還是換行，只要輸出的東西正確，都算你對，但有些 OJ 就要求一定要完全按照輸出格式裡的描述輸出。</font>
#### 6. 範例輸入與輸出 (Sample Input and Output)
提供合法的可能輸入範例及其對應的正確輸出。幫助做題者驗證自己理解的題目要求是否真的符合出題者的描述。
有些題目甚至會有額外的區塊用文字解釋在給定的範例輸入下，範例輸出是如何被計算出來的。
#### 7. 記憶體限制與執行時間限制 (Memory and Time Limits)
競程題目不僅要求你的程式輸出正確答案，還要在限定的時間和記憶體資源內解決一筆測試資料。
這個資訊常常會是解題的重要關鍵，不可忽視。
#### 8. 給分方式 (Scoring Method)
並非所有題作答時都只有對或錯兩種結果，有些題會有部份分，這樣的題就會有一個區塊告訴你怎樣的情況下能拿到部份分。
---
深入了解這些元素對於在程式競賽中成功解題至關重要。每個部分都有其特定角色，對解題方法和程式設計有著直接影響。掌握這些知識，你將能更有效地進行程式競賽的題目解答。
## 五、競程解題網站上傳結果說明
當你在競程解題網站（如 Codeforces ）上傳一份程式碼後，可能得到的結果如下(只列出比較常見的幾個)：
### 程式競賽結果狀態詳解
大多數 OJ 上都會有個頁面展示你上傳題目後，系統回傳你的結果代表什麼意思，以下列出幾個 OJ 的回傳結果解說頁面連結：
1. [Atcoder 的回傳結果解說頁面](https://atcoder.jp/contests/abc358/glossary)
2. [TIOJ 的回傳結果解說頁面](https://tioj.ck.tp.edu.tw/about/verdicts)
3. [Codeforces 的回傳結果解說頁面](https://codeforces.com/blog/entry/4088)
仔細看後可發現每個 OJ 回傳結果分類都不太一樣，甚至同一種錯誤有可能會有不一樣的回傳結果。清楚的了解一個 OJ 的回傳結果可能是哪些問題造成的對解題來說是很有幫助的。
以下列出一些大多數 OJ 共通會有的回傳結果解釋。
- 🟢 **Accepted (AC)**
- 代表你的解答完全正確。
- 🟠 **Wrong Answer (WA)**
- 程式的輸出結果與預期答案不符。
- 🟡 **Runtime Error (RE 或 RTE)**
- 程式執行時遇到錯誤，如除以零、訪問非法記憶體等。
- 🔴 **Compilation Error (CE)**
- 你的程式碼語法不正確或不遵循編程語言的規則。
- 🔵 **Time Limit Exceeded (TLE)**
- 程式在規定時間內未能完成執行。
- 🟣 **Memory Limit Exceeded (MLE)**
- 程式使用的記憶體量超出題目的限制。
<div style="page-break-after: always;"></div>
# <font color = "blue">**第三單元：條件陳述式與型別轉換**</font>
## 一、布林型態介紹
布林是許多程式語言會有的資料型態之一，英文是 boolean，在 C++ 中對應的關鍵字是 bool。
布林資料型態的可能值只有 true 和 false 兩種，true 和 false 的意思就是「真」和「假」。`true` 和 `false` 同時也是布林資料型態唯二的字面常數。
```cpp
bool true_value = true; // 把變數 true_value 的值初始化為 true
bool false_value = false; // 把變數 false_value 的值初始化為 false
```
若直接用 cout 輸出一個布林變數如下：
```cpp
bool true_value = true;
cout << true_value << endl; // 輸出 1
bool false_value = false;
cout << false_value << endl; // 輸出 0
```
值為 true 的布林值輸出的結果是 `1`，值為 false 的布林值輸出結果會是 `0`，若希望輸出的結果是英文的 `true` 和 `false`，可使用以下方式來輸出，也就是輸出變數前再加上 `<< boolalpha`，且只要曾經加過之後輸出的布林值也都是以英文單字的形式輸出。
```cpp
bool v = true;
bool u = false;
cout << boolalpha << v << endl; // 輸出 true
cout << u << endl; // 輸出 false
```
:::info
**參考資料**
https://en.cppreference.com/w/cpp/io/manip/boolalpha
:::
## 二、比較運算子與邏輯運算子
1. **比較運算子**包含 `==`,` !=`,` >`,` <`, `>=`, `<=` 這六種，依序代表「等於」、「不等於」、「大於」、「小於」、「大於等於」以及「小於等於」。這些運算子的規則都是 `運算式1 比較運算子 運算式2`，運算後的結果以 bool 型態表示，也就是 true 或 false。
```cpp
bool v1 = 1 + 1 < 3; // 初始化 v1 為 true
bool v2 = 2 > 2; // 初始化 v2 為 false
```
2. **邏輯運算子**包含 `!`, `&&`, `||`，依序代表「取反」、「且」以及「或」，對應到數學符號的話則依序是`¬`,`∧`,`∨`。其中 `!x` 當 x 是 true 是會得到 false；而 x 是 false 時會得到 true。 `&&`, `||` 和數學上的「且」、「或」意思一樣。
```cpp
bool v1 = !false; // 初始化 v1 為 true
bool v2 = v1 && false; // 初始化 v2 為 false
bool v3 = v1 || v2; // 初始化 v3 為 true
```
對於邏輯運算子來說，左右能放的參數有限，所以可以直接把所有可能的參數和結果畫成表格，被稱為 [真值表](https://zh.wikipedia.org/zh-tw/%E7%9C%9F%E5%80%BC%E8%A1%A8)，`&&` 和 `||` 的真值表如下：
| A | B | A && B | A \|\| B |
| -------- | -------- | -------- | -------- |
| true | true | true | true |
| true | false | false | true |
| false | true | false | true |
| false | false | false | false |
`!` 的真值表如下：
| A | !A |
| -------- | -------- |
| true | false |
| false | true |
3. **比較運算子** 及 **邏輯運算子** 都和 **算術運算子** 都是「運算子」(Operator) 的一種，因為它們都是把兩個數值結合後變成一個新的數值 (`!`是少數的例外，是直接把一個數值變成另一個數值)。
這三種運算子主要差異在於它們結合的運算元的資料型態及運算結果的資料型態的組合不一樣。
(1) **算術運算子** 是結合兩個「數值」的運算元變成一個新的「數值」；
(2) **比較運算子** 則是結合兩個「數值」變成一個新的「布林值」；
(3) **邏輯運算子** 是結合兩個「布林值」變成一個新的「布林值」。
(註：數值可以是整數或浮點數。)
:::danger
**新手常犯錯誤警告**
在數學課中以及 python 中， a 小於 b 且 b 小於 c 可寫成 $a < b < c$，但在 C++ 中，一定要寫成 $a < b\ \&\&\ b < c$。同理 a 等於 b 且 b 等於 c 在 c++ 中要寫成：$a == b\ \&\&\ b == c$。
:::
:::danger
**新手常犯錯誤警告**
`==` 和 `=` 是不同的， `=` 是指派運算子，`==` 是比較運算子，很多新手在比較兩個變數是否相等時，會不小心寫成 `=`，且可怕的是，有時候把 `==` 寫成 `=` 也能編譯通過，例如以下判斷 a 和 b 是否相等的程式碼：
```cpp!
#include<iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
if(a = b) {
cout << "same\n";
} else{
cout << "not same\n";
}
return 0;
}
```
:::
## 三、運算子的優先順序
c++ 的標準定義了每種運算子的優先級如下連結：
https://en.cppreference.com/w/cpp/language/operator_precedence
可發現每種運算子都有一個數字表示它的優先級，在同一個運算式裡，優先級數值越小的運算子要先做運算，若有好多個優先級相同的運算子，則要參考表格中 Associativity 的欄位，它告訴了我們相同優先級要從左算到右還是又算到左。：
若要使用非預設的運算順序 c++ 定義的運算子優先順序，可像數學課上學的運算式一樣，使用括號把要優先算的。
以下有幾個常用的順序，請背起來：
1. 目前已介紹的運算子中 `!` 是優先級最高的。
```cpp
bool v = !true || true; // v 的初始值為 true。因為 !true 會先運算。
bool v2 = !(true || true); // v2 的初始值為 false。因為 true || true 會先運算。
```
2. `*`、`/`、`%` 的順序相同，`+`、`-` 的順序相同，「乘、除、取餘」高於「加、減」，若相同時，由左到右依序計算。
3. 所有算術運算子的優先級都高於 `!` 以外的比較運算子以及邏輯運算子。
4. 比較運算子的優先級高於 `!` 以外的邏輯運算子。
5. `&&` 的優先級高於 `||`。
<font color="red">**特別叮嚀：若沒有熟記運算子的優先順序，最好都加上小括號才不會出錯。**</font>
## 四、if 條件式
### (1) if 條件式結構解說
以下是 if 條件式的結構：
````cpp
if(式子1) {
區塊 1
}
else if(式子2) {
區塊 2
}
else if(式子3) {
區塊 3
}
....
else if(式子n) {
區塊 n
}
else {
最終區塊
}
````
電腦會依序檢查 `式子1`、`式子2`、... 直到某個 `式子i` 的值是 true 時，就會執行對應的 `區塊 i`，`區塊 i` 以外的其他區塊都會略過。若所有式子都不吻合，就會執行`最終區塊`。
`else if` 可以不存在，也可以有任意多個，`else` 也可以不存在，但若存在的話只能有一個。
區塊裡也可以宣告變數，但離開區塊後在區塊裡宣告的變數就不能再使用了。更詳細的解釋在後續會解釋。
### (2) 例題示範
以下是 [票種判斷](https://codeforces.com/group/E2QZG7dbgT/contest/485557/problem/D) 這題的參考解答，請參考此程式碼如何和題目敘述對應。
```cpp
#include<iostream>
using namespace std;
int main() {
int x;
cin >> x;
if(x >= 65) {
cout << "senior discount ticket\n";
} else if(x < 12 && x > 3) {
cout << "children ticket\n";
} else if(x <= 3) {
cout << "infant ticket\n";
} else {
cout << "regular ticket\n";
}
return 0;
}
```
以下程式碼調換了兒童票和嬰兒票的判斷順序，就可以把兒童票判斷式中的 `x > 3` 給省去，這是因為我們程式執行到第三個判斷時，已經不可能會有 `x <= 3` 的情況了。
```cpp=
#include<iostream>
using namespace std;
int main() {
int x;
cin >> x;
if(x >= 65) {
cout << "senior discount ticket\n";
} else if(x <= 3) {
cout << "infant ticket\n";
} else if(x < 12) {
cout << "children ticket\n";
} else {
cout << "regular ticket\n";
}
return 0;
}
```
但要注意，若此時又把兒童票和嬰兒票的判斷順序調換，變為如下：
```cpp=
// 此為錯誤的程式碼
#include<iostream>
using namespace std;
int main() {
int x;
cin >> x;
if(x >= 65) {
cout << "senior discount ticket\n";
} else if(x < 12) {
cout << "children ticket\n";
} else if(x <= 3) {
cout << "infant ticket\n";
}else {
cout << "regular ticket\n";
}
return 0;
}
```
那麽就是錯誤的邏輯了，所以 if 條件式的判斷順序不一定能任意調換。
### (3) 巢狀 if 條件式
if 條件式的區塊裡也能有 if 條件式，可稱為**巢狀 if 條件式**。下面程式碼是 [票種判斷](https://codeforces.com/group/E2QZG7dbgT/contest/485557/problem/D) 使用巢狀 if 條件式的範例程式碼：
```cpp=
#include<iostream>
using namespace std;
int main() {
int x;
cin >> x;
if(x < 12) {
if(x <= 3) {
cout << "infant ticket\n";
} else{
cout << "children ticket\n";
}
} else {
if(x >= 65) {
cout << "senior discount ticket\n";
} else {
cout << "regular ticket\n";
}
}
return 0;
}
```
### (4) if 條件式中大括號的省略
若區塊裡只包含僅有一個陳述句(statement)，那麼我們可以把該區塊的大括號省略。但大多時候都不建議省略，因為省略時很容易寫出錯誤的程式碼，很多大公司如 [Google 的程式碼規範](https://tw-google-styleguide.readthedocs.io/en/latest/google-cpp-styleguide/formatting.html#id7) 裡都是這樣規定的。
:::danger
**很難檢查到的錯誤**
請預測以下程式碼會輸出什麼？並執行看看和自己預測的是否一樣。
看到這個例子後，相信大家就知道為什麼會建議大家在寫含有 else 的 if 條件式時，不要省略大括號。
```cpp!
#include<iostream>
using namespacae std;
int main() {
int x = -50;
int ans = 0;
if(x >= 0)
if(x > 100)
ans += 100;
else
ans += 50;
cout << ans << '\n';
return 0;
}
```
:::
## 五、型態轉換及其規則
1. 「型態轉換」 的意思：
在 C++ 中，當一個變數被宣告後，它的型態就已經確定了，不能再更動。但是在做運算的時候，我們可以把一個運算式(expression)的值在運算前先轉變為其他型態的值再做運算，或者有些時候編譯器會自動幫你把變數的值做型態轉換後再做計算。例如，當把運算結果資料型態為 typeA 的運算式指派給資料型態為 typeB 的變數，那麼編譯器就會自動幫你把 typeA 的值轉型為 typeB 的值。
2. 型態轉換的規則：
(1) `bool` 轉 `int`：
若把 `bool` 的型態的運算式和 `int` 型態做運算時，`true` 會變成 $1$；`false` 會變成 $0$。
```cpp
int x = true; // x 初始化為 1
int y = false; // y 初始化為 0
```
(2) `int` 轉 `bool`：
若強制把 `int` 型態的運算式的結果轉為 `bool` 型態，非 $0$ 的值會變為 `true`；$0$ 會變為 `false`。
```cpp
bool x = -3; // x 初始化為 true
bool y = 10; // y 初始化為 true
bool z = 0; // z 初始化為 false
```
(3) `char` 轉 `int` 和 `int` 轉 `char`：
根據 [ASCII](https://zh.wikipedia.org/wiki/ASCII) 轉換，更多資訊會在第七章介紹。
(4) 浮點數轉整數 和 整數轉浮點數：
會在第八章介紹。
3. [隱性轉型(Implicit conversions)](https://en.cppreference.com/w/cpp/language/implicit_conversion) 與 [顯性轉型(Explicit type conversion)](https://en.cppreference.com/w/cpp/language/explicit_cast) ：
所謂的「顯性轉型」就是型態轉換這件事是由你自己用指定語法告訴編譯器在計算時要把某個數值轉型。而「隱性轉型」則是在某些狀況下編譯器會自動幫你把數值做型態轉換。
4. [隱性轉型(Implicit conversions)](https://en.cppreference.com/w/cpp/language/implicit_conversion) 的規則：
(1) 開頭時已說過，把一個運算式結果指派給一個變數時，若兩者資料型態不同，就會發生隱性轉型。
(2) 在 if 條件式裡的判斷式，若運算的結果不是 `bool`，會被強制轉型為 `bool`。
(3) `bool`, `char`, `unsgined char` 這些位元數量比 `int` 小的數，在做算術運算時會自動被轉型成 `int`。
範例程式片段：
```cpp
bool flag1 = true, flag2 = true;
int result = flag1 + flag2; // result 初始化為 2
```
(4) 所有非布林型態在做邏輯運算時都會被**隱性轉型**成布林型態。
```cpp
int v = !!5; // v 初始化為 1。這是因為 ! 是邏輯運算，會先把 5 轉為 true，
// 再取反兩次後仍是 true，最後再轉型為 int，於是變為 1
```
(5) 在一般情況下用 cout 輸出布林值會隱性轉型成整數型態。
綜合 (3)、(4) 之範例程式片段：
```cpp
int x = 4;
cout << (bool)x << endl; // 輸出 1
```
(6) 整數和浮點數運算時，整數會被轉成浮點數。
```cpp
int x = 5, y = 2;
double v1 = x / y; // v1 初始化為 2
double v2 = x * 1.0 / y; // v2 初始化為 2.5
```
(7) 階級相同的有號型態和無號型態做運算時，會把有號的變成無號的。
```cpp
unsigned int x = 0;
int y = 1;
bool v = (x - y) > 10; // v 會被初始化為 true。因為根據第一課「整數溢位」這個要點裡提到的規則，
// unsigned 的 0 減 unsigned 的 1 會得到一個很大的正整數。
```
5. [顯性轉型(Explicit type conversion)](https://en.cppreference.com/w/cpp/language/explicit_cast) 的語法：
我們可以用 `(變數型態) 運算式` 來把一個運算式的運算結果強制轉成小括號裡的變數型態。請看以下兩種常見使用情境：
(1) 希望把兩個整數在做運算時被當成浮點數來運算
```cpp
int x = 5, y = 2;
double v1 = x / y; // 普通的做除法運算會是整數除法，v1 結果為 2。
double v2 = (double)x / y; // 首先 x 的值先被轉型成浮點數再和 y 做運算， y 的值也會因為隱性轉型的規則變為浮點數，
// 於是運算結果為 2.5。
cout << "the value of v1 is " << v1 << " and the value of v2 is " << v2 << endl;
```
(2) 希望兩個 int 在做運算式被當作 long long 來避免 overflow
```cpp
int x = 50000, y = 60000;
long long v1 = x * y;
long long v2 = (long long)x * y;
cout << "the value of v1 is " << v1 << " and the value of v2 is " << v2 << endl;
```
## 六、[變數範圍(Scope)](https://omegaup.com/docs/cpp/en/cpp/language/scope.html)
所謂的 Scope，代表著程式碼內可以使用變數的位置區段。若此變數為全域變數，宣告結束後的每一行都可以使用。反之，若此變數為局部變數，只有在宣告結束後的同一個區塊(Block)內都可使用。
* Block 的例子：
1. `if` 和 `else` 後面接的每組大括號夾住的範圍就是一個 Block。
```cpp
int v = 3;
if(v != 3) {
int x = 3;
cout << x << endl;
} else {
cout << x << endl; // 這行會發生錯誤，因為已經離開 x 的變數範圍了。
}
```
3. 我們可以在任意陳述句之間插入一組左右大括號來形成一個 Block。
```cpp
#include<iostream>
using namespace std;
int main(){
int x = 3;
{
int y = 4;
}
int z = y; // 這行會發生錯誤，因為已經離開 y 的變數範圍了。
return 0;
}
```
* 同名的變數
1. 在同一個 block 裡一個變數名稱只能被一個變數擁有
```cpp
int main() {
int x = 1;
double x = 2.0; // 發生錯誤
return 0;
}
```
2. 在不同層級的 block 可以有相同的變數名稱，但在使用一個變數時，它所代表的變數會是宣告的變數離它層級最近的那個，這種情形叫做變數覆蓋(shadow)。
(註：當大括號裡還有另一個大括號時，兩個大括號的範圍就是不同層級。)
```cpp
int main() {
int x = 1;
{
int x = 2; // 也可以宣告為 double x = 2;不同層級的 block 可以使用不同的變數型態
x += 1;
cout << x << endl; // 會印出 3
}
cout << x << endl; // 會印出 1
return 0;
}
```
<font color ="red">**雖然 C++ 允許在不同層級宣告一個相同名字的變數，但這麼做很容易寫出錯誤的程式碼，所以請盡量不要重複宣告同樣的變數名稱**</font>
<div style="page-break-after: always;"></div>
# <font color = "blue">**第四單元：while 迴圈**</font>
## 一、迴圈的用途
雖然電腦能用比我們快幾十億倍的速度做事情，但是電腦做事情仍是按照一個指令一個指令運作，難道我們非得事先寫出十億個指令才能讓電腦幫我們執行十億個操作嗎？並不！只要借助「迴圈」我們就可以把**重複的**事情寫成短短幾行。
考慮以下題目：
:::success
**細菌繁殖**
已知在第 $0$ 天的時候，培養皿裡面共有 $A$ 隻細菌，並且每隔一天，每隻細菌都會分裂成 $B$ 隻細菌，請問，至少要到第幾天，培養皿裡才會有 $C$ 隻以上的細菌？同時也要回答在達到 $C$ 隻以上細菌時，培養皿裡共有幾隻細菌？(假設細菌都不會被消滅，且培養皿裡可以裝得下任意多隻細菌)
測試資料範圍：
* $1 \le A, C \le 10^9$
* $2 \le B \le 10^9$
:::
在只有第二單元以前的知識時，其實還是能通過這題的，因為可以證明在此題的測試資料範圍限制下，細菌無論如何都在 $30$ 天以內達到 $C$ 隻以上，所以我們就只要使用以下程式碼(只列出此前 25 行)，即可通過。
```cpp=
#include<iostream>
using namespace std;
int main() {
long long A, B, C;
cin >> A >> B >> C;
if(A >= C) {
cout << "0 " << A << '\n';
return 0;
}
A *= B;
if(A >= C) {
cout << "1 " << A << '\n';
return 0;
}
A *= B;
if(A >= C) {
cout << "2 " << A << '\n';
return 0;
}
A *= B;
if(A >= C) {
cout << "3 " << A << '\n';
return 0;
}
A *= B;
// 還剩 27 個 if 條件式...
```
雖然這個程式碼能通過此題，但在寫此份程式碼時會發現有一個明顯的缺點：就算我們有複製貼上可以用，但把第 $6$ 至第 $9$ 行重複貼上 $30$ 次後，我們還是得逐一把 if 條件式裡印出的第一個數字改正。
但可發現相鄰兩個 if 條件式裡要印出的數字只差 $1$，所以我們若用一個變數儲存要印出的第一個數字，並讓此變數每經過一個 if 條件式就增加 $1$，那我們就可以寫出一個複製後完全不需要修改的程式碼了！修改後的程式碼如下：
```cpp=
#include<iostream>
using namespace std;
int main() {
long long A, B, C;
cin >> A >> B >> C;
int day = 0;
if(A >= C) {
cout << day << " " << A << '\n';
return 0;
}
A *= B;
day += 1;
if(A >= C) {
cout << day << " " << A << '\n';
return 0;
}
A *= B;
day += 1;
if(A >= C) {
cout << day << " " << A << '\n';
return 0;
}
A *= B;
day += 1;
// 還要再複製 28 次
}
```
而迴圈的功能就是讓我們能一再重複的執行同一組指令，只要用 `while(true) {/* 要一直重複執行的程式碼 */}` 這樣的語法
就可以把程式碼簡化為如下：
```cpp
#include<iostream>
using namespace std;
int main() {
long long A, B, C;
cin >> A >> B >> C;
int day = 0;
while(true) {
if(A >= C) {
cout << day << " " << A << '\n';
return 0;
}
A *= B;
day += 1;
}
return 0;
}
```
雖然目前我們尚不知道 while 迴圈的語法規則，但已經能感受到他的厲害了吧！接下來，我們來仔細講解 while 迴圈的語法規則，並更自然地使用它。
## 二、while 迴圈
**while** 迴圈的結構可以分解如下：
```cpp
while(條件式 A) {
程式碼區塊 B
}
```
**while** 迴圈執行的流程圖如下：
```flow
st=>start: whlie 開始
A=>condition: 條件式 A
B=>subroutine: 程式區塊B
e=>end: while 結束
st->A
A(true)->B->A
A(false)->e
```
以下用文字詳細說明：
`條件 A` 裡要填入的是一個運算式，而`區塊 B` 則可以包含任意多個指令。在執行 while 迴圈時，會先檢查 `條件 A` 裡的運算結果轉型成布林值後是否為 true，如果是的話，就會執行`區塊 B`，執行完後又會再檢查一次`條件 A` 裡的運算式，若仍為真，繼續執行`區塊 B`，如此反覆下去，直到`條件 A` 的運算式運算結果變為 false 為止。
再了解 while 迴圈規則後，我們能幫「細菌繁殖」這題寫出更自然的程式碼如下：
```cpp
#include<iostream>
using namespace std;
int main() {
int A, B, C;
cin >> A >> B >> C;
int day = 0; // 現在是第幾天
long long num = A; // 現在有的細菌數量
// 只要細菌數量還少於 C，就把細菌數量乘以 B，並且天數加 1
while(num < C) {
num *= B;
day += 1;
}
cout << day << " " << num << '\n';
return 0;
}
```
因為 while 迴圈的作用就是讓我們重複做某件事情，直到某個條件不再被滿足為止。
## 三、**break** 陳述式 和 **continue** 陳述式
**continue** 陳述式的寫法如下：
```cpp=
continue;
```
也就是關鍵字 continue 再加上分號。
用法範例如下：
```cpp
// 印出不超過 10 的正整數中所有的奇數。
#include<iostream>
using namespace std;
int main() {
int i = 1;
while(i <= 10) {
if(i % 2 == 0) {
i += 1;
continue;
}
cout << i << endl;
i += 1;
}
return 0;
}
```
在迴圈裡一遇到 **continue** 陳述式就會跳過它以後的指令，直接進入迴圈的小括號裡的區塊。通常 **continue** 陳述式都會配合 if 條件式使用。
而 **break** 陳述式的用法範例如下：
```cpp
// 印出 1 至 10
#include<iostream>
using namespace std;
int main() {
int i = 1;
while(1) {
if(i > 10) {
break;
}
cout << i << endl;
i += 1;
}
return 0;
}
```
在迴圈裡一遇到 **break** 陳述式就會結束該迴圈。
:::danger
**新手常犯錯誤警告**
請注意，執行到 **break** 陳述式會強制離開最近的一層迴圈，不會受它和迴圈之間有多少層 if 陳述式影響。
:::
## 四、Do-while 迴圈
還有一個與 while 類似的語法為 ``do{ 程式碼區塊 A }while(陳述式 B);``，它會先執行一次 `區塊 A` 後，再去檢查 `條件 B` 是否為 true，只要仍是 true，就再回去執行一次 `區塊 B` 。流程圖如下：
```flow
st=>start: do while 開始
B=>subroutine: 程式區塊 B
A=>condition: 條件判斷式 A
ed=>end: do while 結束
st->B
B->A
A(yes)->B
A(no)->ed
```
以下是用 `do while` 寫的計算由 $n$ 加到 $1$ 的結果的程式碼：
```cpp
#include<iostream>
int main() {
int n;
cin >> n;
int answer = 0;
do{
answer += n;
n -= 1;
} while(n > 0);
return 0;
}
```
## 五、特別的運算子：``i++``, ``++i``, ``i--``, ``--i``
若一個語句單獨出現 `i++` 或 `++i`，其實就是 `i += 1` 的意思，`--` 也是同樣道理。但如果混在其他地方出現如：`int x = i++;`那它是`int x = i; i+=1;` 的意思；而`int x = ++i; `則是 `i += 1; int x = i;` 的意思。在使用時請不要用在太複雜的場景上，會造成自己難以理解自己在寫什麼，甚至寫出含有 UB（未定義行為） 的程式碼。例如：`int x = i + ++i;` 就是個 UB。
## 六、Time Limit Exceed 與程式執行時間估計
電腦雖然計算速度是人類的幾十億倍，但仍然是需要花時間，並不是什麼事情都能瞬間解決，所以有時我們會需要去估計一個程式的執行時間。尤其是在競程中，每個題目都會告訴你時間限制，所以我們要學會估計自己寫的程式需要跑多久。
1. 電腦在執行程式時花時間的事情包括：運算、讀入、輸出等等，在 Level 0 裡我們先著重在運算的次數即可。加減乘的運算速度比較快，例如一秒內完成 $10^9$ 次加法運算在現今多數 OJ 上都是沒問題的。但有些運算子的運算速度如除法、取餘就比較慢，保守估計的話，一個程式碼在最糟情況至多只會執行 $10^8$ 次的運算一定沒問題。我們現在就來嘗試估計以下程式碼的運算次數。
```cpp
#include<iostream>
int main() {
int n;
cin >> n;
int answer = 0;
do{
answer += n;
n--;
} while(n > 0);
cout << answer << endl;
return 0;
}
```
do while 的大括號裡面共進行兩次運算，小括號裡的條件判斷也算是一次運算，總共會循環 $n$ 次，所以總共會有 $3 \times n$ 次運算，
如果 $n$ 的值不會超過 $10^7$ 的話，最多就只會有 $3 \times 10^7$ 左右個運算。這樣子的運算次數現代電腦肯定能在 $1$ 秒內執行完。
2. 這裡簡單列一下一些操作所花的時間比較：`加減、邏輯運算` $<$ `乘` $<$ `除,取餘` $\ll$ `讀入,輸出`
## 七、EOF 的介紹
EOF 的意思就是 End of File，翻譯成中文就是「檔案的結尾」，例如當有人說：「程式這次的讀入遇到 EOF 了」時，意思就是「當程式想要再讀入資料時，卻發現已經沒有資料可讀、整個檔案都已經讀完了」的意思。
在 C++ 中，我們可以用以下方式判斷是否已讀入到資料的檔案結尾：
```cpp=
/* 此程式目的是每讀入一個數字就把該數字輸出，
* 直到遇到檔案結尾為止。
*/
#include<iostream>
using namespace std;
int main() {
while(true) {
int n;
cin >> n;
if(cin.eof())break; // 若曾經執行 cin >> n 時遇到檔案結尾，cin.eof() 就會回傳 true，否則回傳 false
cout << "n = " << n << '\n';
}
}
```
不過在解題時，以下是更方便的寫法：
```cpp=
/* 此程式目的是每讀入一個數字就把該數字輸出，
* 直到遇到檔案結尾為止。
*/
#include<iostream>
using namespace std;
int main() {
int n;
// 若 cin >> n 嘗試讀入一個整數失敗時，運算結果轉型成布林值時就會變成 false，於是就會結束迴圈
// 不過遇到 EOF 只是沒有成功讀入一個整數的其中一種可能，諸如遇到的是一個字串也算是失敗
while(cin >> n) {
cout << "n = " << n << '\n';
}
}
```
EOF 在 C 語言有其他用法，相關介紹可參考 [競程小撇步 Trick 1.6 - eof](https://tmt514.gitbooks.io/the-code-tactics-book/content/1.6/eof.html) (但裡面提到的一些知識和專有名詞 AA 競程的競程入門班才會介紹)。
## 八、常見的競程題目輸入輸出方式
在競程中，除了我們至今看到的題目都是最普通的方式，一些比較不一樣的輸入輸出方式請見一下例題。
1. [ABC288 A - Many A+B Problems](https://atcoder.jp/contests/abc288/tasks/abc288_a)。會先給你一個正整數代表一個輸入有多少組詢問。
2. [小月的袋子](https://codeforces.com/group/E2QZG7dbgT/contest/486969/problem/N)。會告訴你，當你讀到符合某個條件的輸入時就結束。以這題來說，當讀到一個 $0$ 時就算結束。
3. [平均分數](https://codeforces.com/group/E2QZG7dbgT/contest/486969/problem/O)。這種情形敘述裡可能會有多種描述方式如：「請讀到檔案結尾」、「讀到沒有資料為止」、「當讀到 EOF 時結束」。
以現在國際競賽的命題趨勢來說，除了最普通的方式外，只剩下上面第 1 種輸入輸出方式，但是台灣的比賽及測驗可能還是會出現 2, 3 這兩種情形。
<div style="page-break-after: always;"></div>
# <font color = "blue">**第五單元：for 迴圈**</font>
## 一、 **for** 迴圈
在使用 while 迴圈時，可能會發現，很多時候我們想做的事情會有一個步驟是「初始化某些值」，以及某個步驟是「在每次循環的最後要進入到下次循環前要做的事」，例如前面在介紹 while 迴圈時所舉例的計算一個數字的位數和，「初時化某些值」做的事情就是 `int now = x;`，每次循環最後做的事情是 `now /= 10;`，這樣我們就可以把它寫成如下 **for** 迴圈：
```cpp
#include<iostream>
using namespace std;
int main() {
int x;
cin >> x;
int answer = 0;
for(int now = x; now != 0; now /= 10) {
answer += now % 10;
}
cout << answer << endl;
return 0;
}
```
我們把 **for** 的結構分解如下：
```cpp
for(初始化陳述式 A; 條件式 B; 運算式 D) {
程式碼區塊 C
}
```
**for** 迴圈執行的流程圖如下：
```flow
st=>start: for 開始
A=>operation: 初始化陳述式 A
B=>condition: 條件式 B
C=>operation: 運算式 D
D=>operation: 程式碼區塊 C
ed=>end: for 結束
st->A
B(no)->ed
A->B
B(yes)->D
D(right)->C
C->B
```
以下用文字詳細說明 for 迴圈的執行步驟：
1. for 迴圈首先會執行 `初始化陳述式 A` **一次**，`初始化陳述式 A` 有以下 3 整形式：
(1) 可以在此宣告同一種資料型態的一些變數如：`for(int x=1,y=2;條件式 B;運算式 C)`
(2) 可以是一個運算式如： `for(x += 2,z--;條件式 B;運算式 C)`
(3) 可以是空的如： `for(;條件式 B;運算式 C)`
再次強調，`初始化陳述式 A` 只會在 for 迴圈最剛開始時執行一次，且且若有宣告變數，離開迴圈後宣告的變數的生命週期就結束了。
2. 接著會執行 `條件式 B`，`條件式 B` 是個條件運算式，也就是說，就算運算式的運算結果不是布林值，也會被隱性轉型成布林值(和 if 條件式一樣)，若運算結果為 true，會繼續執行`程式碼區塊 C`，否則結束此 **for** 迴圈。
3. 若步驟 2 的 `條件式 B` 成立，會接著執行 `程式碼區塊 C`，`程式碼區塊 C` 可包含多個指令，也可為空，此步驟會依序執行 `程式碼區塊 C` 的所有指令，可想像成是 **for** 迴圈的主體，。
4. `程式碼區塊 C` 執行完後就會執行 `運算式 D`，可以是任何運算式，也可以為空。執行完後，就會回到步驟 2。
更詳細的 for 的規則可參考：https://en.cppreference.com/w/cpp/language/for
## 二、巢狀迴圈
迴圈裡面還可以有迴圈，甚至想要有幾層就可以有幾層，例如，以下是一份能印出九九乘法表的程式碼：
```cpp
#include<iostream>
using namespace std;
int main() {
for(int i = 1; i <= 9; i++) {
for(int j = 1; j <= 9; j++) {
cout << i << " x " << j << " = " << i * j << endl;
}
}
return 0;
}
```
再次強調之前「第二單元 邏輯運算與 if 判斷式」提過的 scope 的概念：變數可以宣告在迴圈裡面，但是一離開宣告時所在的迴圈，該變數就不能再用了，若再使用該變數，就會發生編譯錯誤。例如以下程式碼會發生編譯錯誤：
```cpp
for(int i = 1; i <= 9; i++) {
for(int j = 1; j <= 9; j++) {
int tmp = 0;
}
tmp++; // 這一行使用了不能再使用的變數名稱，所以會發生編譯錯誤
}
```
<div style="page-break-after: always;"></div>
# <font color = "blue">**第六單元：陣列**</font>
## 零、 目前的困境
考慮以下題目：
:::success
**[陣列的介紹](https://aatoi.com/problem/arrayintro)**
給你一個長度為 $N$ 的數列 $a_1, a_2, \ldots, a_N$，你要回答 $Q$ 個問題，第 $i$ 個問題會給你一個參數 $k_i$，請回答數列 $a$ 的第 $k_i$ 個數字是什麼。
#### 輸入格式
輸入的第 $1$ 行包含一個正整數 $N$ ($1 \le N \le 10^5$)。
輸入的第 $2$ 行包含 $N$ 個正整數 $a_1, a_2, \ldots, a_N$ ($1 \le a_i \le 10^9$)。
輸入的第 $3$ 行包含一個正整數 $Q$ ($1 \le Q \le 10^5$)。
接著還有 $Q$ 行，當中的第 $i$ 行包含一個正整數 $k_i$ ($1 \le k_i \le N$)，代表第 $i$ 個詢問給定的參數。
#### 輸出格式
共輸出 $Q$ 行，第 $i$ 行包含一個正整數代表第 $i$ 個詢問的答案。
:::
這意的題在只使用上個單元以前的知識幾乎是不可能解出來的，如果 $N$ 的上限只有 $3$ 那可能我們還能用以下寫法：
```cpp=
#include<iostream>
using namespace std;
int main() {
int N;
cin >> N;
int a1, a2, a3;
if(N == 1) {
cin >> a1;
} else if(N == 2) {
cin >> a1 >> a2;
} else if(N == 3) {
cin >> a1 >> a2 >> a3;
}
int Q;
cin >> Q;
while(Q--) {
int k;
cin >> k;
if(k == 1) {
cout << a1 << '\n';
} else if(k == 2) {
cout << a2 << '\n';
} else if(k == 3) {
cout << a3 << '\n';
}
}
}
```
但這題 $N$ 的上限可是 $10^5$ 耶！用類似的寫法的話，我們豈不是要宣告 $10^5$ 個變數，並且寫 $10^5$ 個 if、else if 才能完成嗎？就算你真的寫出來好了，大部分的 OJ 還是會因為你的程式碼檔案大小太大而不讓你上傳，那這樣的題該怎麼解決呢？
這時，就是用到「**陣列**」的時候啦！
## 一、陣列的介紹
為了解出 **[陣列的介紹](https://aatoi.com/problem/arrayintro)** 這道題，你可能會這樣想：「C++ 是否存在能讓我們一口氣宣告非常多個變數的功能呢？而且這些變數最好能用數字編號，就像數學上的數列一樣，而且要讓我們能夠直接在程式碼中，能根據一個變數 $i$，取得數列裡第 $i$ 個數」
實際上，這就是 C++ 裡「陣列」所提供的功能唷！
陣列可類比於數學上的數列，並且和變數一樣，要先宣告後才能使用，宣告時也要指定數列的長度，以下條列陣列的語法規則：
* 陣列的宣告的格式為：``資料型態 陣列名稱[陣列儲存的數字數量];``，例如 `int a[5];` 代表宣告一個名字為 `a` 且能儲存 $5$ 個 **int** 資料型態的值的陣列
* 陣列名稱的命名規則和單一變數的命名規則一樣。
* 大小必須是常數如整數的字面常數，不能使用變數。
* 宣告了陣列 `a[5]` 後，我們就有 $5$ 個變數 $a[0]、a[1]、a[2]、a[3]、a[4]$ 可以使用，中括號裡的數字被稱為「索引值(index)」。<font color="red">**請注意，索引值的編號是從 $0$ 開始！ a[5] 是不合法的**</font>。
* 要使用陣列 `a` 裡的某個數時，可用 `a[運算式]`，如此一來我們就可以根據表達式的結果取得 `a` 裡索引值是該運算式運算結果的數。
請看以下程式碼範例：
```cpp=
#include<iostream>
using namespace std;
int main() {
int a[5];
// 以下用亂序一個一個指派數字給陣列裡的每個數，索引值 $i$ 的數被指派為 i + 1
a[3] = 4;
a[0] = 1;
a[2] = 3;
a[4] = 5;
a[1] = 2;
cout << a[2] << '\n'; // 輸出 3
cout << a[2 * 2 - 1] << '\n'; // 輸出 a[3] 的值，也就是 4
cout << a[a[0]] << '\n'; // a[0] 的值是 1，於是 a[a[0]] 的值就是 a[1] 的值，也就是 2，故輸出 2
}
```
有了以上知識後，可以用以下程式碼解出 [陣列的介紹](https://aatoi.com/problem/arrayintro)：
```cpp=
#include <iostream>
using namespace std;
int main() {
long long a[100001];
int N;
cin >> N; // 讀入數列 a 的長度
for(int i = 1; i <= N; i++) {
cin >> a[i]; // 把 a 第 i 個數儲存在陣列索引值為 i 的位置
}
int Q;
cin >> Q; // 讀入詢問數量
while(Q--) {
// 每進入一次，就處理一個詢問
int k;
cin >> k; // 讀入要輸出數列第幾個數
cout << a[k] << '\n'; // 直接把 k 當作 a 的索引值來輸出答案
}
}
```
了解此份程式碼後，請嘗試解出 [比賽得分計算](https://aatoi.com/problem/contestscore) 這題，驗證自己是否真的明白了。
## 二、陣列的初始化
1. 和一般的變數一樣，陣列宣告時有多種方法能指定陣列裡的數的初始值，這裡只介紹最常用的一種方式：把所有初值用大括號包住，並以逗號隔開。\
例如： ``int a[10] = {0, 1, 2, 3};`` ，第一個數就是 `a[0]` 的初始值，第二個數是 `a[1]` 的初始值，依此類推。陣列後面沒給值的數初始值都會是 $0$。甚至如果你想要讓陣列裡所有值得初值都是 $0$，可以使用 ``a[10] = {};``。更多的陣列初始化方式請參考：https://en.cppreference.com/w/c/language/array_initialization
2. 和一般的變數一樣，若沒有給定初始值，且若是宣告在全域，陣列裡所有值的初值都是 $0$，否則若宣告在函式內，初始值是未知的。
3. 若不想在宣告時給初值，可以宣告完後再一個一個位置指定或用迴圈來指定初值，如：
```cpp
int a[20];
for(int i = 0; i < 20; i++) {
a[i] = i + 1;
}
```
**請注意，若宣告的陣列很大時（例如幾千幾萬個變數以上），請不要給陣列初值，否則在某些環境上編譯器會編譯出很檔案大小非常大的執行檔，某些 OJ 會因此把你的程式碼當作編譯錯誤。**
* 有給定初始值時可以不寫陣列大小。例如：我們可以寫 int ``a[] = {1, 2, 3, 4};`` 編譯器會自動幫我們判斷這個陣列的大小為 $4$。
## 三、關鍵字 const
在宣告變數時，我們可以在資料型態名稱前面再加上關鍵字 `const`，代表這個變數在宣告給定值以後，都不會再改變變數裡的值，並且若使用這個關鍵字，宣告時一定要給定初值，否則如下面這段程式碼就會無法編譯通過。
```cpp
#include<iostream>
using namespace std;
int main() {
const int x;
return 0;
}
```
const 的常見用途至少有以下兩點：
1. 當我們使用一個很常出現在程式碼裡的固定數字時，例如陣列大小，或是取模運算的固定模數，可以使用 const 變數取代，這樣對編譯器來說他的效果和常數一樣。我們用以下程式碼示範：
```cpp
#include<iostream>
const int N_MAX = 1000000;
int a[N_MAX];
int b[N_MAX];
int c[N_MAX];
int main() {
int n;
cin >> n;
for(int i = 0 ; i < n; i++) {
cin >> a[i] >> b[i];
c[i] = a[i] + b[i];
}
for(int i = 0; i < n; i++) {
cout << c[i];
}
return 0;
}
```
這麼做至少有兩個好處：(1) 這個數字不再只是數字，我們從名字上可以看出這個數字的意義，且我們可以用這個 const 變數合法的用來宣告陣列大小。 (2) 若我們後來發現此數值有誤，需要修改，那就只要改動程式碼的一個地方就行了。
2. 在呼叫函式時，雖然一個變數是 pass by reference，但我們可以在這個 pass by referene 的參數前面再加上 const 關鍵字，代表我們不允許這個函式裡面改動這個參數的值，這樣其他人在使用這個函式時，看函式的宣告方式就知道自己的傳進去的值是否會被修改到了。也可以防止自己在撰寫函式時，不小心修改到不能修改的變數值。
## 四、 Memory Limit Exceed 與程式使用的記憶體量估計
有了陣列的存在，我們就能夠在短短幾行程式碼內就使用非常大量的記憶體來儲存資料，但電腦的記憶體用量並不是無限的，所以我們並不能濫用記憶體。在競程中，當記憶體用量超過限制時，OJ 就會判定你的程式錯誤，並告訴你上傳的結果是 **MLE**，因此估計記憶體用量也是競程中重要的一環。
我們用下列問題作為估計記憶體使用量會不會超過限制的範例：
> 請計算 256 MB 能夠開多大的 **int** 型態的陣列。
由於 $256$ MB $= 256 \times 2^{20}$ bytes，而一個 **int** 佔 $4$ bytes，所以 256 MB 只能夠儲存 $256 \times 2^{20} \div 4 = 64 \times 2^{20} \approx 6.4 \times 10^7$ 個 **int**。也就是說，如果在記憶體限制只有 $256$ MB 時我們卻宣告了一個大小為 $7 \times 10^7$ 的 **int** 陣列就會造成 MLE。
## 五、多維陣列
首先我們來看看 [二維陣列練習題](https://codeforces.com/group/DKK9MEEHUh/contest/326567/problem/A) 這道題目。這道題要你讀入一個大小為 $R \times C$ 的矩陣。這時就是二維陣列出場的時候了！前面教的陣列被稱為一維陣列，在一維陣列中，我們只使用一個索引值來表示一個數所儲存的位置。而使用二維陣列則可以用兩個索引值來表示一個數的位置！例如，我們寫下 `int a[50][60];` 就代表我們宣告了一個大小為 $50 \times 60$ 的陣列，第一個索引值可以填的數為 $0 \sim 49$，第二個索引值能填的數為 $0 \sim 59$。
實際上，不僅有二維陣列，也可以有三維、四維甚至更高維的陣列。宣告多維陣列的語法和宣告一維陣列很像，都是 `資料型態 陣列名稱[第一個維度的大小][第二個維度的大小]...[最後一個維度的大小];`。
有了此知識後，我們就可以用以下程式碼讀入 [二維陣列練習題](https://codeforces.com/group/DKK9MEEHUh/contest/326567/problem/A) 這道題的輸入：
```cpp
#include<iostream>
using namespace std;
int a[51][51];
int main() {
cin >> R >> C >> k >> m;
for(int i = 1; i <= R; i++) {
for(int j = 1; j <= C; j++) {
cin >> a[i][j];
}
}
return 0;
}
```
<div style="page-break-after: always;"></div>
# <font color = "blue">**第七單元：函式**</font>
## 一、函式
函式就好像個丟進去一些東西後會吐一個東西出來的機器，定義函式時，必須指定你要丟進去多少參數以及每個參數的資料型態，也要指定此函式會回傳(吐出來)什麼樣資料型態的變數。
C++ 程式在宣告函式的格式為：`回傳的資料型態 函式名稱(傳入的參數1, 傳入的參數 2, ...){ 函式內容 }`。`傳入的參數`的格式則是 `資料型態 變數名稱`，而在函式內容裡若執行到長相為 `retrurn 表達式;` 的「return 陳述式」，就會回傳此表達式的運算結果。例如以下是個求兩個整數的和的函式：
```cpp
int sum(int x, int y) {
return x + y;
}
```
而以下是求兩個函式中比較大的那個值的函式：
```cpp
int max(int x, int y) {
if(x > y) {
return x;
}
return y;
}
```
有了這兩個函式以後我們可以嘗試以下的程式碼：
```cpp
#include<iostream>
using namespace std;
int sum(int x, int y) {
...
}
int max(int x, int y) {
...
}
int main() {
int x = 3;
int y = 4;
int v1 = sum(x, y); // v1 初始化為 7
int v2 = max(x, y); // v2 初始化為 4
cout << v1 << " " << v2 << endl;
return 0;
}
```
除此之外還有幾點要注意：
1. 函式名稱的命名規則和變數一樣，但可能存在相同名稱的函式，例如以下程式碼是可以編譯通過的。
```cpp
int max(int x, int y) {
if(x < y) { return y; }
return x;
}
long long max(int x, long long y) {
if(x < y) { return y; }
return x;
}
long long max(long long x, int y) {
if(x < y) { return y; }
return x;
}
int max(int x, int y, int z) {
if(x > y && x > z) { return x; }
if(y > z) { return y; }
return z;
}
int max(double x, double y) {
if(x < y) { return y; }
return x;
}
```
這意思是，就算函式名稱一樣，只要傳入的參數數量及型態無法一一對應就是合法的。相對地，若有兩個名稱一樣且傳入的參數個數及型態也一樣的函式就不行了，例如以下程式碼會編譯錯誤：
```cpp
#include<iostream>
int f(){
return 1;
}
double f(){
return 1;
}
int main() {
return 0;
}
```
2. 函式的宣告必須在最外側，也就是函式裡面無法再宣告其它函式，例如以下就是不合法的程式片段。
```cpp
int main() {
int sum(int x, int y) {
return x + y;
}
return 0;
}
```
必須寫成：
```cpp
int sum(int x, int y) {
return x + y;
}
int main() {
return 0;
}
```
3. 函式的內容都是一行一行執行，且當執行到 retrun 後，就不會再繼續執行之後的指令了。
```cpp
int sum(int x, int y) {
return x + y;
return y; // 這行的存在沒有意義，因為一定不會執行到。
}
```
4. 要使用自己定義的函式時，可以在該函式宣告之後的任何函式裡執行，在宣告前的函式裡使用則會發生編譯錯誤。
5. 若發生函式執行完函式的內容後都沒有執行到 return 陳述式，這是未定義行為，什麼事都有可能發生，甚至還常常會不小心通過範例測是資料，但上傳到 OJ 後卻出錯。這是熟悉函式的語法後，程式老手也仍然會寫出的 bug，不過此錯誤編譯器會警告，請大家不要忽略任何編譯器提出的警告。
例如以下程式碼會出現 `warning: non-void function does not return a value [-Wreturn-type]` 這樣的警告。
```cpp=
#include<iostream>
using namespace std;
int add(int x, int y) {
int val = x + y;
}
int main() {
int x, y;
cin >> x >> y;
cout << add(x, y) << '\n';
return 0;
}
```
6. 當使用函式時，我們傳了一些變數給函式並不代表函式裡對這些變數做修改後會影響傳進去的變數，因為實際上電腦做的事情是「讓函式複製一份我們傳給他的變數後再做處理」。會在介紹「Pass by value 以及 Pass by reference」再做更進一步的解釋。
## 二、void 函式
函式其實是可以不回傳任何變數。這種函式要在原本寫回傳的資料型態的位置寫上 c/c++ 的關鍵字 `void`。
例如以下是一個不回傳任何東西，僅僅只是印出傳入函式的 int 值的函式。這種函式就不需要回傳任何東西，只要直接在 `return`後面加個分號就行了，若 `return` 的位置是在最後面時也可以省略，並非未定行為。
```cpp
void print(int x) {
cout << "the input value is " << x << endl;
return; // 此行可省略
}
```
## 三、Pass by value 以及 Pass by reference
在「函式」所提到的「傳變數進去函式做的事情其實是把此變數複製一份」被稱為 Pass by value。除了 Pass by value 的傳值方式以外，還有一種傳值方式叫做 Pass by Reference，用這種方式我們就可以在函式裡面修改到純進去函式的變數值。只要在傳入參數時的資料型態名稱與變數名稱之間加上 `&` 符號即可。請看執行下列程式碼來看看兩者的差別。
```cpp
#include<iostream>
using namespace std;
void pass_by_value(int x) {
x = 1;
}
void pass_by_reference(int &x) {
x = 2;
}
int main() {
int v = 0;
pass_by_value(v);
cout << v << endl; // 輸出 0
pass_by_reference(v);
cout << v << endl; // 輸出 2
return 0;
}
```
## 四、內建函式
C++ 的原本就提供我們很多好用的函式，稱之為「內建函式」。要使用內建函式時，就必須「引用」此內建函式所存在的檔案名稱。例如說，其實 C++ 也有提供剛才我們自己撰寫的 max 函式，它是撰寫於 algorithm 這個檔案裡，所以我們要使用內建的 `max` 函式，就必須在使用之前執行 `#include<algorithm>`。
在競賽中大部分好用的內建函式都存在於 algorithm 這個檔案裡面，可以在 https://en.cppreference.com/w/cpp/algorithm 這個網址中查詢 algorithm 你有哪些好用的函式，以及怎麼使用它們。另外有一些和數學有關的內建函式則是存在於 `cmath` 這個檔案裡面。
這堂課我們只介紹四個很常用的函式。
1. `swap`，此函式位在 `algorithm` 函式庫裡。$swap(a, b)$ 能交換變數 $a$ 和變數 $b$ 的值，變數 $a$ 和 $b$ 的資料型態必須一樣，且傳的參數只能是變數，不能是一個運算式，也不能是字面常數。
2. `max` 和 `min`，它們位在 `algorithm` 函式庫裡。$max(a, b)$ 會回傳 a 和 b 中比較大的那個數的值，若要得到多個數的最大值，可使用大括號把所有數包起來，例如：$max(\{1,3,5,9,7\})$ 就會回傳 $9$；`min` 則相反，會回傳最小的那個值。
3. `abs`，它位在 `cmath` 函式庫裡。這個函式會回傳一個數的絕對值，例如：`int a = abs(-5);` ，a 宣告完後的值就會是 $5$。更多的 cmath 裡的函式我們會在教浮點數的時候提到。
4. `gcd` 和 `lcm`，它們位在 `numeric` 函式庫裡，是 C++17 以後才出現在標準裡的函式，顧名思義， $gcd(x, y)$ 會回傳 $x$ 和 $y$ 的最大公因數，而 $lcm(x, y)$ 會回傳 $x$ 和 $y$ 的最小公倍數。
:::danger
**新手常犯錯誤警告**
以上除了 abs 以外需傳兩個參數以上的函式，傳入的所有參數必須是相同資料型態，否則會造成編譯錯誤，例如以下程式碼：
```cpp=
int x = 5;
long long y = 6;
cout << max(x, y) << endl;
```
編譯後產生的可能錯誤訊息如下：
> d6cd9c43db1f.cc:8:11: error: no matching function for call to 'max'
cout << max(x, y) << endl;
最容易犯錯的情況是把一個 long long 資料型態的變數和一個整數字面常數取 max，尤其是那些只要不加 LL 這個後綴就不會是 long long 資料型態的平台上，最容易犯這種錯誤，請拿以下程式碼分別在 Codeforces 和 Atcoder 上測試看看，並思考為什麼會有不同的編譯結果。
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
long long x;
cin >> x;
cout << max(1000000000000000, x) << '\n';
}
```
:::
## 五、把陣列當作函式參數
### 1. 傳入一維陣列
我們要傳入一個名為 `a` 的 `int` 陣列時，可以這樣寫：`void f(int a[])`，**並且，當我們在函式裡修改陣列 `a` 裡的數值時，函式外傳被傳進去的陣列裡的數也會被修改。** 這點和傳入基本資料型態時的行為是不一樣的，可以使用以下程式碼來測試其中的差異。
```cpp
#include<iostream>
using namespace std;
void int_test(int x) {
x = 1;
}
void array_test(int a[]) {
a[0] = 2;
}
int main() {
int v = 0;
int_test(v);
cout << v << endl; // 輸出 0
int a[3] = {0, 1, 2};
array_test(a);
cout << a[0] << endl; // 輸出 2
return 0;
}
```
如果傳進函式時在中括號裡打上陣列的大小(例如使用 `f(int a[3])`)是沒有意義的事情，中括號裡的數值會被編譯器忽略。
### 2. 傳入多維陣列
若要傳入多維陣列，必需告知函式第二個以後的維度的大小，例如若我要傳的陣列是 `int a[3][4][5]`，那麼函式就得這樣寫：
`void f(int a[][4][5])`。同樣的，若在函式裡修改多維陣列裡的值，傳進去的陣列也會被修改。
## 六、關鍵字 static
以下程式碼展示了 static 的一種用法：
```cpp
#include<iostream>
using namespace std;
void static_varaible_test() {
static int x = 1;
x++;
cout << x << endl;
}
void normal_varaible_test() {
int x = 1;
x++;
cout << x << endl;
}
int main() {
static_varaible_test(); // 輸出 2
static_varaible_test(); // 輸出 3
static_varaible_test(); // 輸出 4
normal_varaible_test(); // 輸出 2
normal_varaible_test(); // 輸出 2
return 0;
}
```
一般情況在函式裡宣告變數時，每一次呼叫函式，函式裡宣告的變數都是新的東西，例如上面程式碼裡 normal_varaible_test() 函式裡的變數 x，每次呼叫函式時總是會印出 $2$。但我們若在變數型態名稱前面加上關鍵字 `static`，此變數每次的修改都會保留，所以三次傳入分別會輸 $2, 3, 4$。也就是說，若加上 static 這個關鍵字，這個變數就會至始至終都是使用同一塊記憶體。
## 七、函式的預設參數
函式的參數可以有預設的值(default parameters)，範例如下：
```cpp
#include<iostream>
using namespace std;
/* 預設的值直接寫在參數後，用等號連接，有預設的值的參數一定得是最後的連續一些參數
*
*/
int add(int x = 2, int y = 1) {
return x + y;
}
int sub(int x, int y = 1) {
return x - y;
}
/* 此函式會編譯錯誤，因為有預設的值的參數不是最後的連續一些參數
int add(int x, int y = 3, int z) {
return x + y + z;
}
*/
int main() {
cout << add() << endl; // 輸出 3
cout << add(5) << endl; // 輸出 6
cout << add(5, 6) << endl; // 輸出 11
cout << sub(5) << endl; // 輸出 4
cout << add(5, 6) << endl; // 輸出 -1
return 0;
}
```
# 第八單元以後
[請見 Part 2](/@aacp/library2)
Sign in with Wallet
Connect another wallet