# 中正競程期中手札
```cpp
string last_update = "2023.11.7";
```
[toc]
## 如何讀題本
對於一道題目，最重要的地方有三個 `Input 格式`, `Output 格式`, `技術規格或測資範圍`，而 **題目敘述** 則是可能會包含一些題目要求的細節，**範例測資** 則是用來幫助你了解題意用的，通過範例測試資料不代表你能通過該道題目，但是輸出入格式決定了你要怎麼撰寫程式，而技術規格會讓你可以知道要使用何種變數型態以及何種方法來完成這道題目。
### 題本範例解說
我們舉複數運算題本為例子來解釋如何識讀題本。
#### 題目敘述
你學到了酷酷的 $\text{struct}$，於是你想練習，所以讓我們用 $\text{struct}$ 來實作複數的加減法以及乘法吧!
#### 輸入格式
輸入的第一行為一個正整數 $n$，代表有 $n$ 組運算要進行，每一組運算會有三行輸入。
第一行為兩個整數 $a_1, b_1$ 分別代表第一個複數的實部與虛部，
第二行為一個字元，可能為 $+, -, *$ 其中之一，代表要進行何種運算，
第三行為兩個整數 $a_2, b_2$ 分別代表第二個複數的實部與虛部。
#### 輸出格式
輸出共有 $n$ 行，對於每一組運算各輸出一行，包含兩個以空白隔開的整數分別代表輸入的兩個複數進行運算過後得到的實部與虛部。
#### 技術規格
* $1 \leq n \leq 10^5$
* $-100 \leq a_1, b_1, a_2, b_2 \leq 100$
#### 範例測資
| 範例輸入 | 範例輸出 |
| -------- | -------- |
|`1`<br>`4 5`<br>`*`<br>`2 7`| `-27 38`<br><br><br><br>|
#### 如何讀題
首先，題目敘述提到了我們這題要進行複數的加減以及乘法，所以在做這題前你就知道你需要具備這些知識，接下來看到 `輸入格式` ，裡面提到每筆測資會有 $n$ 組運算要進行，你就會想到應該要使用迴圈來幫助我們完成重複且固定次數的操作。
```cpp=
int n;
cin >> n;
for(int i = 0; i < n; ++i)
{
// do something
}
```
接下來你就會讀取四個整數跟一個字元，用那個字元來判斷你要做何種運算，那運算時要用何種變數型態來存取就需要看一下 `技術規格`，估計最極端的結果會不會沒辦法存在你要用的資料型態內。
做完運算後你需要輸出結果，而題目的 `輸出要求` 提到輸出共有 $n$ 行，對於每一組運算各輸出一行，所以在輸出結果後都要輸出一個換行字元。
```cpp=
for(int i = 0; i < n; ++i)
{
// calculate
cout << ans << '\n';
}
```
## 常見錯誤
### 輸出忘記換行
有些題目通常只會給你單行的範例輸出會讓你誤以為不用換行，記得仔細檢查題目是否有多組輸入，那輸出時當然也要記得換行啦。
### 變數數值在運算時發生 **overflow**
先給大家一些常見的變數型態大概的範圍估計
$\text{int: }$ $-2 \times 10^9 \sim 2 \times 10^9$
$\text{long long int: }$ $-9 \times 10^{18} \sim 9 \times 10^{18}$
假設有一道題目要你輸出 $x \cdot y^2 + 5$，$1 \leq x \leq 10^3, 1\leq y \leq 10^4$
當你 $x, y$ 都很小時使用 $int$ 當然沒問題，那最極端的情況呢?
$x = 10^3, y = 10^4$, $x \cdot y^2$ 是不是已經超過 $\text{int}$ 最大可存範圍了?
這種情況就會發生所謂的溢位，至於溢位會產生的結果跟電腦如何存取一個數字有關，不太好敘述，簡單來說你可以視為他的結果會跟你預期的不一樣，應該要使用 $\text{long long int}$ 來存。
### **struct** 宣告定義時語法錯誤
宣告 struct 記得加分號
```cpp=
struct psg
{
int member_count;
string members[10];
};
```
### 使用 char array 要多開幾格預留空間
眾所皆知 char array 在字串結尾會有一個結尾字元 `\0`，當題目跟你說字串長度最長 $n$ 時，應該開至少 $n + 5$ 格左右的陣列，防止出現不可預期的輸出。
### 陣列大小開錯
很多人不習慣使用 vector，輸入 $n$ 之後再開，通常喜歡寫成以下形式:
```cpp=1
int arr[1000005];
```
這時候拜託看清楚 $0$ 有幾個。
## 如何除錯(Debug)
### 手生測資
範例測資是用來幫助你了解題目，沒有通過範測一定過不了題目，但通過了不代表會通過完整的所有測試資料。舉例來說，複數運算範例測資只有給你乘法的情況，你應該要去想一些加法和減法的測資來驗證你的程式，同時也應該生一個多筆運算的測資來檢查換行，還有會不會讓前面留下來的結果影響後面的輸出。
### 輸出變數結果
如果你發現程式輸出的結果與預期不符，你可以把運算過程的變數輸出，來看你的過程有沒有問題，像是排序就可以把每一次交換的情況印出來看看。
```cpp=
for(int i = 0; i < n - 1; ++i)
{
for(int j = 0; j < n - i - 1; ++j)
{
if(arr[j] > arr[j + 1])
{
cout << arr[j] << ' ' << arr[j + 1] << '\n';
swap(arr[j], arr[j + 1]);
}
}
}
```
## 如何估算一個算法的時間複雜度
我們會用兩種方法來判斷一個程式是否有效率:
1. 程式運行的時間長短
2. 程式使用的記憶體大小
在此我們先介紹如何預估一個程式的運行效率，第一種方法是直接跑跑看，但是這種方法會受到硬體不同和執行環境不同造成差異，因此我們引入時間複雜度的概念來評估效率。
首先，讓我們來觀察這個程式他會運行幾次運算
```cpp=1
int num = 10000, divisor = 2;
for(int i = 2; i < num; ++i)
if(num % i == 0)
divisor++;
```
我們可以經過簡單的計算發現這個迴圈會跑 ||$num - 2$|| 次，我們在 $num$ 很大的情況下，會發現 $-2$是可以被忽略的，這也就是我們的 `Big O Notation`，`Big-Ο`代表演算法時間函式的上限(Upper bound)，而在最壞的狀況下，演算法的執行時間不會超過 `Big-Ο`，因此我們可以利用這個東西來評估一個程式的時間複雜度。
對於計算一個程式的 `Big-O`，會有以下三種基本原則:
1. 常數可忽略不計
2. 取最大次方
3. Log底數可忽略不計
所以剛才那個程式的時間複雜度就是 $\mathcal{O}(num)$，
那這個程式的時間複雜度呢?
```cpp=
for(int i = 0; i < n - 1; ++i)
{
for(int j = 0; j < n - i - 1; ++j)
{
if(arr[j] > arr[j + 1])
{
cout << arr[j] << ' ' << arr[j + 1] << '\n';
swap(arr[j], arr[j + 1]);
}
}
}
```
答案是 ||$\mathcal{O}(n^2)$||
而在C++的程式中，我們會保守估計一秒大概可以運行約 $10^8$ 次運算，
所以這個程式碼的 $n$ 最多只能到約 $10^4$ ，不然執行時間就會超過 $1$ 秒，如果你沒有依據數據範圍好好地評估要使用時間複雜度多好的方法來寫程式，很容易得到一個 `TLE`，下面附上幾個常見的時間複雜度。
| Big-O | 時間複雜度別名 | 常見情況 |
| -------- | -------- | -------- |
| $\mathcal{O}(1)$ | 常數 | 陣列取值 |
| $\mathcal{O}(n)$ | 線性 | 陣列走訪、線性搜尋法 |
| $\mathcal{O}(\log n)$ | 對數 | 二分搜尋法 |
| $\mathcal{O}(\sqrt{n})$ | 根號 | 找因數 |
| $\mathcal{O}(n \log n)$ | $Null$ | 合併排序、快速排序 |
| $\mathcal{O}(n^2)$ | 平方 | 泡沫排序法 |
| $\mathcal{O}(2^n)$ | 指數 | 遞迴求費氏數列 |
| $\mathcal{O}(n!)$ | 階層 | 算一個字串的所有排列 |
Sign in with Wallet
Connect another wallet