# APCS準備用講義
主講者：國立北港高級中學 二年忠班 1號 吳成昊
預期課程結束後的成果：APCS達到實作3級分以上
建議練習時間：每週5-8小時
:::info
要注意的是聽完每節課之後都應該把提到的題目自己在做一遍，並自己尋找類似的題目來做，多加練習才能熟悉程式並在APCS中得到好成績
:::
## 0. 競程基礎知識
### 競程是什麼？
競程，或叫做演算法比賽(Algorithm Competition)是一個資訊領域中十分大型與多樣的比賽，除了考驗參賽者的程式能力，更加注重思考以及邏輯等等的能力。競程內容大致為：給參賽者多個或多組題目，並要求參賽者以程式，在特定條件限制下使用更加合適的演算法解出題目。
常見的競程比賽（以高中來說）有：
==IOI==、==APCS==、==少年圖靈計畫==、==全國數理暨資訊學科能力競賽==等等...
其中雖然APCS稱為檢定，但因其考試形式與競程相同，故列入上述列表。
### 相關詞語
**執行結果:**
:::success
AC:
> Accepted的簡寫，你最想要看到的結果
:::
:::warning
WA:
> Wrong Answer的縮寫，你一定有哪裡寫錯了（只有在少之又少的狀況下可能為測資怪怪的）
:::
:::danger
TLE:
> Time Limit Exceeded 超時執行，每個題目都有他自己的時間限制，超過這個時間就會把執行中斷，並告訴你這個訊息
:::
:::danger
MLE:
> Memory Limit Exceeded 超出記憶體限制量，很少發生的狀況，除非你幹了一些不該幹的事，請改用空間複雜度較低的方法
:::
:::danger
CE:
> Compile Error的意思，你有加好分號嗎？還是有哪裡的括號沒有閉合？總之，編譯錯誤！
:::
:::danger
RE:
> Runtime Error的狀態，也就是程式執行時有地方出問題導致無法正常結束，例如無限迴圈啦、你做了除以0的除法啦之類的，給我回去好好檢查自己的程式碼！
:::
### 時空複雜度：
**時間複雜度：**
用於表示一個==演算法的效能好壞==，以Big-O Notion表示，要注意的是它並不是輸入資料多少的所需時間函數，而是==隨著資料量增加，計算時間的增加曲線函數關係==。什麼意思呢？舉例來說，這裡有一個變數$n$代表資料的數量，而有兩個函數分別為$y=n$與$y=n^2$，在資料量低的時候，兩者的差異並不明顯，但$y=n^2$的==成長速率==要明顯比$y=n$還要快，這個成長速率的概念便是時間複雜度的簡化版。
**常見時間複雜度有以下幾種：**
$O(1)、O(\log_{2}n)、O(n\log_{2}n)、O(n)、O(n^2)$
再往上的$O(n!)$等等通常是一個非常不好的方法，在此不多贅述
## 1. C++基本語法
### 標頭檔：
各位在學習C++過程中很常看到以下程式碼吧
```cpp=
#include<iostream>
```
這串程式碼其實叫做標頭檔，就是告訴電腦我這個程式需要哪些額外套件，就像吃炸雞要配可樂一樣叫電腦把要的東西拉進來，競程上通常只用一個萬用標頭檔：
```cpp=
#include<bits/stdc++.h>
```
這串標頭檔包含了競程上所有常用的功能，十分好用啊！
---
### 輸入與輸出：
**標準輸入：cin >> (要用來儲存資料的變數)**
cin讀取規則會==斷在任何不可見的字符==，如以下例子
輸入
```cpp=
1 2 3 4
5
```
程式碼
```cpp=
cin >> a >> b >> c >> d >> e;
cout << a << b << c << d << e;
```
輸出
```cpp=
12345
```
這樣子會依序讀入資料到a、b、c、d、e，可以一直延伸。
**標準輸出：cout << (要輸出的東西)**
### 資料流(>>或<<)可以==一直延伸==，但應保持==一行做一件事的原則==
**換行字符: \n**
使用endl亦有相同作用，但endl同時會將緩存flush掉
又因為flush是==十分耗時==的動作可能會讓你差點TLE的程式真的TLE
所以競程實作上請多加利用"\n"這個換行字符，少用endl
##### 以輸出10000次HelloWorld為例
```cpp=
#include<iostream>
using namespace std;
int i = 0;
int main()
{
while(i < 10000){
cout << "HelloWorld" << endl;
i++;
}
}
```
以上程式碼耗時平均60ms
```cpp=
#include<iostream>
using namespace std;
int i = 0;
int main()
{
while(i < 10000){
cout << "HelloWorld" << "\n";
i++;
}
}
```
以上程式碼平均耗時50ms
:::warning
不要以為只有10ms很少，後面時間複雜度（後面會講）更高的程式可能1ms就會是TLE與沒有TLE的差距，務必注意！
:::
**簡單優化：**
一個程式中除了演算法耗時外，另一個耗時的就是==IO處理==!
IO處理是什麼，簡單來說就是==所有的輸入輸出==都跟他有關！也就是說他是無法避免的時間損耗。
所以！我們要主動做一些IO優化，以下是兩個最基本的優化，把他們放在main函數裡的最前面即可！
```cpp=
cin.tie(0);
ios_base::sync_with_stdio(false);
```
這兩個優化的功能可以見這裡->[Wiwiho的競程筆記](https://cp.wiwiho.me/io-optimize/)
在此僅說加了優化後不可以跟c的輸入輸出(scanf、printf)混用，其餘不多做贅述。
**整行輸入: getline(cin,(要用來儲存資料的變數))**
取得整行換行字符前的東西，要注意的是，若你在getline前先做了一次cin有可能會導致以下結果：
```cpp=
#include<iostream>
using namespace std;
int i;
string s;
int main()
{
cin >> i;
getline(cin,s);
cout << i << "\n";
cout << s << "\n";
}
```
輸入：
```cpp=
1
Hello World!
```
輸出：
```cpp=
1
```
### 各位有沒有發現輸出的s不見了！
:::warning
輸入時 1 後面其實有一個換行字符，而cin輸入時會停在那裡，因此導致getline一進來就直接吃到換行而停止輸入！
:::
解法也很簡單，只要在cin後面加上以下的程式碼就可以了
```cpp=
cin.ignore(1000000,"\n");
```
第一個參數可以填任意值，代表可忽略字元的上限（建議超大）
第二個則代表這個字串以前以及他本身會被忽略。
---
### 資料型態
在C++中有各式各樣的資料型態，以下程式碼舉例：
```cpp=
#include <iostream>
using namespace std;
int main(){
int a; //32位整數資料，範圍：-2,147,483,648 to 2,147,483,647
bool b;//布林值，只能儲存"是"或"否"兩種數值
char c;//字元，一個"半形"的字
float f;//浮點數，總之就是可以保存小數點
double d;//雙精浮點數，總之就是可以保留比較多位的小數點
long long l;//64位長整數，真的超大，範圍：-9,223,372,036,854,775,808 至 9,223,372,036,854,775,807
}
```
以上幾種有沒有看的頭昏眼花，以下做~~人話版~~簡化版解釋：
1. int，整數，顧名思義是存==整數==進去的，如果你硬要把一個小數點塞進去的話...小數點後的數字就會不見。==（無條件捨去）==
2. bool，布林值，可以存==true==或==false==兩種數值，意思就是"對"或"不對"，或者"是"或"不是"之類的概念。
3. char，字元，我們的字是由一堆字元所組成的，像是APPLE這個單字，是由'A' 'P' 'P' 'L' 'E'這幾個字元所組成的，如果用英文來比喻就是字母的意思。（標點符號也算字元！）
4. float，浮點數，看到一個點字不難想像他就是可以用來存==帶小數點的數字==用的，但因為有double這個資料類型，在競程實務上很少用他。（都跑去用double了）
5. double，雙精浮點數，看到雙精，不知道各位有沒有想到“精準度“這個詞，這個東西也是存==小數點==用的，但是可以存比float更加後面好幾位的小數點。**舉例來說，如果你只能以量筒最小刻度為單位去裝水，double就像把量筒從1ml一個刻度變成0.1ml一個刻度的概念。**
6. long long，==長整數==，這東西簡單來說就是超大，真的很大。
**要注意的事情：**
- 如果你往任何資料型別塞入一個==超過他儲存範圍的數字==，那他就會==爆掉變成奇怪的東西==，舉例來說：我在int中存入1,000,000,000,000，他這時候已經超過範圍了，就會發生神奇的事情導致結果壞掉，在競程上要特別注意，==int存不下去就用long long==
- long long的運算遠比int還要慢
- 在C++中要表示long long要==在字尾加一個L==
- 在C++中要表示float要在==字尾加一個f==
快速練習：[TIOJ 1001. Hello World](https://tioj.ck.tp.edu.tw/problems/1001)
---
### 資料結構
我真的不習慣中文名稱，所以用英文XD
**Stack:**
這東西可以想像成一堆書，你不能從底下抽書出來，一定要先拿出上面的書本，而且==最後放上去的書本會先被拿起來==，Stack就是這樣的概念
**Queue:**
想像成一個隊伍，==只能從隊尾進去，隊首出來==，Queue就是這種東西
**Array:**
想像成一個箱子，而且這個箱子是有==分格子==的，==一格只能放一個東西==
---
### 算術運算
可能有同學覺得為甚麼要特別講算術運算，不就是簡單的加減乘除嗎？
**的確如此**，但是！有些神奇的運算規則是各位需要特別注意的！
**算術運算子：**
| 符號 | 意涵 | 注意事項 |
| -------- | -------- | -------- |
| `a + b` | 加(plus) |單純的加法|
| `a - b` | 減(minus) |單純的減法|
| `a * b` | 乘以(times) |單純的乘法|
| `a / b` | 除以(divide) |除法，要注意如果整數除以整數便會無條件捨去後面的小數點，如果要有小數點請用float或double去除！|
| `a % b` | 取模(取餘數) |這個運算子是我們比較少見到的東西，他的用途就是會計算a除b的餘數，在競程上十分常用到這個概念，務必熟悉！|
快速練習：[TIOJ 1002. A+B Problem](https://tioj.ck.tp.edu.tw/problems/1002)
---
### 邏輯運算
**邏輯運算子:**
|符號|意涵|注意事項|
|--------|--------|--------|
|`!`|not|會把true變成false反之亦然|
|`==`|equal|要注意是==不是=跟數學不一樣|
|`!=`|not equal|若左邊不等於右邊則成立，等於便不成立|
|`&&`|and|必須要兩個或多個條件都成立才會是true否則為false|
| `\|\|` |or|只要其中有一個條件成立便會輸出true，全部不成立才會輸出false|
所以你可以透過一連串的組合來達到神奇的效果，以下有個題目可以快速練一下（實務上鮮少有以下情形，這題目只是用來檢測你熟不熟邏輯運算）
```cpp=
#include<iostream>
using namespace std;
int main()
{
int a = 10, b = 10, c = 5, d = 2;
bool result = true;
result = !(0 != (a == b && (c*d) == b && b == c));
cout << result;
}
```
請問以上程式碼執行後的result應為何者？
(A) result == 1
(B) result == 0
\(C\) Compile Error
:::spoiler 詳解
答案為(A)
解析：
首先括號內先做，a == b為true，c*d == b為true，b == c為false，又因為這三個是以&&連接起來，只要有一個不成立就會輸出false，因此括號內的結果是false。
再來看0 != (...)就會是0 != false，0就是false的意思，false != false顯然不成立，所以輸出false。
最後，外面有一個!，所以將裡面的結果翻轉，輸出true結束。
:::
---
### 位元運算
位元運算就是利用二進制的0跟1去做運算，有很多神奇的用途，屬於基本語法，實務上非常常見於競程的題目中，但是在理解上很容易會卡關，可以多加練習補強。
**位元運算子**
| 名稱 | 符號（舉例） |說明
| -------- | -------- | -------- |
| AND | `a&b` |所有位元都是1時便輸出1，其他狀況會輸出0|
| NOT | `~a` |將1輸出成0，0輸出成1|
| OR | `a\|b` |只要位元中有一個是1便輸出1，兩個都是0才會輸出0|
| XOR | `a^b^c^d` |若有奇數個1則輸出0，若有偶數個1則輸出1|
| 左移 | `a << n` |將所有位元向左移$n$位，並在右邊補一個0|
| 右移 | `a >> n` |將所有位元向右移$n$位，並在最右邊補一個原本的最高位數字|
### 光聽這些是不是很模糊呢? 我們來舉實際的例子!
首先，我們要將一個數字轉換為二進位要怎麼轉呢?
用以下數字為例:
$17 = 1\times2^4 + 0\times2^3 + 0\times2^2 + 0\times2^1 + 1\times2^0$ 因此可記作==1 0 0 0 1==
$21 = 1\times2^4 + 0\times2^3 + 1\times2^2 + 0\times2^1 + 1\times2^0$因此可記作==1 0 1 0 1==
$80 = 1\times2^6 + 0\times2^5 + 1\times2^4 + 0\times2^3 + 0\times2^2+0\times2^1 + 0\times2^0$因此可記作==1 0 1 0 0 0 0==
各位會發現，只要是==偶數==，二進位的==最後一格就會是0==，==奇數則為1==，是==很重要==的特性
以上是用手計算的過程，但實際上要怎麼用程式轉換呢?
以下是將501轉換為二進位的程式碼，各位可以自己看看原理是什麼!
```cpp=
#include<iostream>
using namespace std;
int main()
{
int i = 501;
string binary;
while(i != 0)
{
binary += (i % 2 == 0)? "0":"1";
i = i/2;
}
cout << binary;
}
```
:::spoiler 原理解說
首先，while迴圈會在==i = 0的時候終止==，因為迴圈中用的是==整數除法會無條件捨去==，因此到了最後一定會剩下0
我將二進位的結果存成一個字串，並且在第9行的時候我去算當下的數字對二取餘數是否等於0，如果是，就代表當前最高位$k$是有數字的，記作$1\times2^k$，沒有就代表當前最高位是0，記作$0\times2^k$
最後將原本的i除以2，進到下一位的數字(即$2^{k-1}$的計算)，如此循環往復便可以逐一將每個位的結果計算出來。
:::
**XOR異或運算:**
這個概念是十分難懂的東西，我們在此說明，我們知道每個數字都可以用二進位來表示，而異或運算是對於數字間每一位分別進行運算，什麼意思呢？
如果我有兩個數字，分別為 21 跟 17，我們已經知道這兩個數字可以分別用二進位表示成10001跟10101，用表格記錄一下得到：
|位數|5|4|3|2|1|
|-|-|-|-|-|-|
|17|1|0|0|0|1|
|20|1|0|1|0|1|
如果我們對這兩個數字進行XOR會發生什麼呢？
> 1. 從第五位開始，有==偶數==個1，進行XOR之後得出1
> 2. 第四位==0對0 XOR還是0==
> 3. 第三位有==奇數==個1輸出0
> 4. 第二位==0 XOR 0還是0==
> 5. 第一位有==偶數==個1輸出1
最後得到10001=17
各位有沒有發現我把特定幾串字畫起來，這些其實就是XOR的運算規則！
在==同一位中==，全部數字排列下來有==奇數個1則輸出0==，有==偶數個1則輸出1==，==0跟0還是0==
為什麼說全部數字呢？因為XOR可以==一直延伸==，只要把所有數字都用表格攤開就可以運算了
**如果有位數不足一律==往最高位數補0==直到對齊！**
這裡有一題給各位快速練習 $\rightarrow$ [ZJ c461. apcs 邏輯運算子 (Logic Operators)](https://zerojudge.tw/ShowProblem?problemid=c461)
:::spoiler 解析
:::
Sign in with Wallet
Connect another wallet