競程班第三堂社課-APCS
===
如果你還沒加discord:
觀念題
---
### 題型
* 程式設計基本觀念
* 程式運行
* 程式填空
* 程式除錯
### C語言基本語法
#### if else
#### switch
#### 布林/位元運算
#### 二/多維陣列
二維陣列即陣列的陣列，可以想成是一個表格。
宣告:
```cpp=
int a[2][3]={{1, 9, 10}, {4, 0, -6}};
bool b[100][3][4]; //三維陣列
```
基本上和一維一樣。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin>>n>>m;
int a[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}
}
```
#### 引用
可以理解為變數的別名，在創建時就必須聲明是哪一個變數的別名，並且不得為空，而且不可更換所代指的變數
```cpp=
int i = 1;
int &r = i;
r=2;
cout << i;//output:2
i=3;
cout << r;//output:3
```
#### 作用域
在c/c++中一個大括號所括起來的區域是一個作用域，它的局部變數無法在作用域外被使用，並且在作用域中局部變數的優先級最高
```cpp=
#include <iostream>
using namespace std;
// 全局變量聲明
int x = 20;
int main ()
{
// 局部變量聲明
int x = 10;
cout << x;
//output:10
return 0;
}
```
```cpp=
#include <iostream>
using namespace std;
// 全局變量聲明
int x = 20;
int main ()
{
// 局部變量聲明
{
int x = 10;
}
cout << x;
//output:20
return 0;
}
```
#### 函數
C++ 中的函式定義的一般形式如下：
```cpp=
return_type function_name( type x , type y ... )
{
body of the function;
}
```
在 C++ 中，函數由一個函數頭和一個函數主體組成。 下面列出一個函數的所有組成部分：
回傳類型(return_type)： 函數回傳的值的資料型別。如果不需要傳回任何值，return_type 的關鍵字是 void。
函數名稱（function_name)：函數的名稱。
參數（type x,type y...)：當函數被呼叫時，你可以向函數傳遞一個或多個值，參數清單包括函數參數的類型、名稱、順序，並且函數可以不包含參數。
函數主體：函數主體包含函數所要執行的代碼
#### 函數的宣告
```cpp=
return_type function_name( type , type ... );//只需包含回傳類型，函數名稱，和參數型別
```
#### 函數的呼叫
```cpp=
int main(){
int i,j;
function_name(i,j);//只需函數名稱和所要傳入的參數
return 0;
}
```
:::info
:warning: 當參數為引用時傳入的變數會和函數內的參數連動
:::
#### 遞迴
當函數自己呼叫自己時，這種行為名為遞迴
而遞迴的主要使用場景是當大問題可以被反覆分解為為多個小問題時
```cpp=
return_type function_name( type x , type y ... )
{
...
function_name(i,j...) ;
...
}
```
***
### 排序法
#### 穩定排序
可以保證排序完後有相同數值的元素的相對位置與原先相同
#### 氣泡排序
思路:重複n次，從第一項開始把小的向上換
複雜度$O(n^2)$(優化方式是在一次循環中只要沒有成功更換任何一個就停止循環)
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int A[n];
for(int i=0;i<=n-1;i++)
{
cin >> A[i];
}
for (int i = n-1; i > 0; i--)
{
for (int j = 0; j <= i-1; j++)
{
if( A[j] > A[j+1])
{
int tmp = A[j];
A[j] = A[j+1];
A[j+1] = tmp;
}
}
}
for(int i=0;i<=n-1;i++)
{
cout << A[i]<<' ';
}
return 0;
}
```
:::
#### 插入排序
思路:每次把選取的數插入進已完成排序的陣列
:::spoiler code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int num[100];
int N;
int i, j, tmp;
//[input]
cin >> N;
for( i=0 ; i<N ; i=i+1 )
{
cin >> num[i];
}
//[sort]
for (int i = 1; i < n; ++i) {
int key = num[i];//因前i-1個已經排好因此選擇第i個來排序
int j = i - 1;//因原本有i個數已經排好，因此插入一個數後最多有i個數字比它大，因重零開始所以i要減1次
while (j >= 0 && num[j] > key) {//把後面的數往後移，挪出插入的位置
num[j + 1] = num[j];
j--;
}
num[j + 1] = key;//插入
}
//[output]
for( i=0 ; i<N ; i=i+1 )
{
cout << num[i] << " ";
}
cout << endl;
return 0;
}
```
:::
複雜度一樣$O(n^2)$
#### merge排序
思路:把陣列往下拆成兩半，一直拆下去直到只有一個，然後慢慢合併，每次合併的時候排序，所以在合併完兩個排序好的陣列，可以在O(n)的時間複雜度，得到一個排序後的陣列，最後合完的就排好了
:::spoiler code:
```cpp=
int a[200000];
void mergesort(int l, int r){
if (l == r - 1){
return;
}
int mid = (l + r) / 2;
mergesort(l, mid);
mergesort(mid, r);
int ans[r-l];
int i = l, j = mid, k = 0;
for (; i<mid && j<r; k++){
if (a[i] < a[j]){
ans[k] = a[i];
i++;
}else{
ans[k] = a[j];
j++;
}
}
for (; i<mid; i++, k++){
ans[k] = a[i];
}
for (; j<r; j++, k++){
ans[k] = a[j];
}
k = 0;
for (; k<r-l; k++){
a[l+k] = ans[k];
}
}
```
:::
複雜度$O(n\log n)$(因為每次往下拆兩半，所以是以二為底的log)
#### 不穩定排序
不可以保證排序完後有相同數值的元素的相對位置與原先相同
#### 選擇排序
思路:每次循環中選取未排序序列中找到最小/大元素，然後放到已排序序列的尾端
:::spoiler code:
```cpp=
void selection_sort(int a[], int len)
{
int i,j,temp;
for (i = 0 ; i < len - 1 ; i++)
{
int min = i;
for (j = i + 1; j < len; j++) //走訪未排序的元素
{
if (a[j] < a[min]) //找到目前最小值
{
min = j; //紀錄最小值
}
}
if(min != i)
{
temp=a[min]; //交換兩個變數
a[min]=a[i];
a[i]=temp;
}
}
}
```
:::
***
### 手算遞迴/迴圈
***
### 二分搜
搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
**陣列必須滿足單調性才能使用**
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,tar;
cin >> n >> tar;
int a[n];
for(int i=0;i<=n-1;i++) cin >> a[i];
int r=n-1,l=0;
while(l!=r-1)
{
int mid=(l+r)/2;
if(a[mid]==tar){cout << "Yes" << endl ;return 0;}
else if(a[mid]>tar){
r=mid;
}
else{
l=mid;
}
}
//如果都找完了就代表沒有
cout << "No" << endl;
}
```
:::
***
### 數學
#### 費氏數列
$f_0=0$
$f_1=1$
$f_n=f_{n-1}+f_{n-2}$
#### gcd/lcm
利用輾轉相除法
```cpp=
int gcd(int a, int b)
{
if (a < b)
swap(a, b);
if (b == 0)
return a;
return gcd(b, a % b);
}
lcm的算法是a*b/gcd(a,b)
```
#### 帕斯卡三角形(?)
***
### C字串
在c語言中字元是藉由ascii碼來儲存的
而字串則是由字元組成的陣列，因此
它無法伸縮與合併，如果想要進行進些操作則必須要使用對應函數
```cpp=
char c='c';//' '用來儲存單一字元
char s[6]="hello";//c語言的字串必須使用" "包括，並且c語言為了表達字串的結尾會在尾部多儲存一個'\0'字元，因此陣列至少要比字串大1格
```
***
### 複雜度
**時間複雜度(稱作big O)
通常用來估計程式運行效率
寫法$O()$**
Eg.
```cpp=
for (int i=0; i<n; i++)
```
的複雜度為$O(n)$，即執行步驟數跟n成正比
Eg.
```cpp=
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
```
複雜度為$O(n^{2})$，即執行步驟數跟n成平方關係
p.s.複雜度只取多項式最高冪次
Eg.$O(n^{2}-n-1000)$ 取為$O(n^{2})$
**估計複雜度用途:檢驗程式是否能夠在限制時間內運行完成
**Eg.因為一般電腦每秒執行步驟數為1e9(理論上)，保險起見通常用1e8估計複雜度;
若題目要求一秒內執行完且$$n<=2e5$$
那複雜度為$O(n^{2})$的步驟數預計為4e10次，大於要求，則無法通過
若複雜度為$O(n\log{n})$則預計步驟數為18*2e5，符合要求
***
### 資料結構
#### stack
**就像把書疊起來
最後放進去的會最先出來**
#### queue
可以想成一堆東西在排隊
先排進去的會先出來
***
實作題
---
### 第一題
>APCS的前兩題都不會有時間複雜度的問題(除非用了太扯的方法)--吳邦一教授
* 算術運算
* map
* 邏輯運算
* 字元/字串排序
* 迴圈、條件判斷
* 陣列
***
### 第二題
* set
* 迴圈
* 函數呼叫
* 找規律
* 遞迴
* 枚舉
### 模擬
注意陣列溢位
仔細想好每個步驟
太複雜可以利用紙張畫圖
[例題](https://zerojudge.tw/ShowProblem?problemid=j123)
### 字串 string
把他想成裝 char 的 vector 就好
可以直接 cin, cout**
```cpp=
#include <string>
string str;//聲明
cin >> str;//輸入
cout << str << endl;//輸出
string a, b, c;
cin >> a >> b >> c;
str = a + b + c;//會將abc三個字串相連
cout << str[0] << endl;//輸出字串的第一個元素
cout << str.substr(6, 5) << '\n';//輸出包含字串第六個字元到第十個字元的字串
cout << str.substr(6) << '\n';//輸出字串第六個字元到字串最後的字串
cout<<str.size()<<'\n';//輸出字串的長度
```
### 並查集
集合的程式表達方式
初始化陣列 ```fa[i] = i```，表示指向自己。
合併（Union）：合併兩個元素所屬集合（合併對應的樹）
```cpp=
void unite(int x, int y) { fa[find(x)] = find(y); }
```
查詢（Find）：查詢某個元素所屬集合（查詢對應的樹的根節點），這可以用來判斷兩個元素是否屬於同一集合
```cpp=
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
```
***
### 第三/四題
* 遞迴
* 模擬
### sort函式(複雜度$O(n\log n)$
寫法
```cpp=
#include <iostream>
#include <algorithm>//記得標頭檔，bits/stdc++.h的話也可
using namespace std;
int main()
{
int n;
cin >> n;
int a[n];
for(int i=0;i<=n-1;i++) cin >> a[i];
sort(a,a+n);//預設由小排到大
for(int i=0;i<=n-1;i++) cout << a[i];
}
```
### set
集合，內部的元素會自動排序好，但不會有重複的元素
操作都是 $O(\log n)$
```cpp=
#include <set>
set<int> s;
s.insert(2); //{2}
s.insert(-5); //{-5, 2}
s.insert(20); //{-5, 2, 20}
s.insert(2); //{-5, 2, 20}
s.erase(2); //{-5, 20}
s.count(20); // 1
if (s.count(20) == 1)
{
cout << "20 is included in s" << endl;
}
else
{
cout << "20 is not included in s" << endl;
}
```
:::info
:warning:
**二分搜請使用 set.lower_bound(x); 複雜度$O(logn)$
請勿使用 lower_bound(set.begin(),set.end(),x); 複雜度$O(n)$
map和upper_bound()同上**
:::
### map
**宣告:**
```cpp=
map<int, int> mymap;
```
前面那個 int 稱為 key ，後面的稱為 value
key 不能重複，內部元素會按照 key 排序
複雜度 $O(\log n)$，但常數偏大
```cpp=
map<int, int> m;
int a, b;
m[a] += b;
m[a]++;
m[1000000] = 10;
m[-100] += 5;
```
```cpp=
map<char, int> m;
m['a'] = 1;
m['b'] = 7;
cout << m['a'] << endl; // 1
```
```cpp=
map<string, string> m;
m["apple"] = "banana";
cout << m["apple"] << endl; // banana
```
### priority queue
**可以 $O(1)$ 取最大/最小值**
**複雜度 $O(\log n)$**
```cpp=
priority_queue<int> pq; //大到小
priority_queue<int, vector<int>, greater<int>> pq2; //小到大
pq.push(2);
pq.push(10);
pq.push(-5);
cout << pq.top() << endl; //輸出10
pq.pop();
cout << pq.top() << endl; //輸出2
```
### stack
**就像把書疊起來
最後放進去的會最先出來**
```cpp=
#include <stack>
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
```
### queue
**可以想成一堆東西在排隊
先排進去的會先出來**
```cpp=
#include <queue>
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << endl;
q.pop();
cout << q.front() << endl;
cout << q.back() << endl;
```
### deque (double ended queue)
**還是 queue
但可以從前面 push 和 pop
還可以當陣列來用**
```cpp=
#include <deque>
deque<int> dq;
dq.push_back(10);
dq.push_front(20);
cout << dq[1] << endl;
dq.pop_front();
dp.pop_back();
```
***
### 位元運算子
**AND: &
OR: |
XOR: ^
NOT: !**
| & | 0 | 1 | | \| | 0 | 1 || ^ | 0 | 1 || ! | |
| - | - | - |-| - | - | - |-| - | - | - |-| - | - |
| **0** | 0 | 0 | | **0** | 0 | 1 || **0** | 0 | 1 || **0** | 1 |
| **1** | 0 | 1 | | **1** | 1 | 1 || **1** | 1 | 0 || **1** | 0 |
```cpp=
int a = 12, b = 9;
cout << (a & b) << " " << (a | b) << " " << (a ^ b) << endl;
```
***
### 前綴和
前綴和是一個預先處理的陣列，陣列的第i個元素的值為$a_0+a_1...+a_i$
所以我們可以先定義一個數列$P$，其中$P_k =\displaystyle\sum_{i=1}^{k}a_i$
**那如果query是問$a_l+a_{l+1}+...+a_r$，答案就是$P_r-P_{l-1}$
(要求的是$l$到$r$，所以不能減到第$l$項)**
**詢問的區間為藍色
藍色=黃色-綠色=10-4=6**
**所以現在問題變成怎麼做出數列$P$ ? (在小於$O(n^2)$的複雜度)**
由於每個線段都只差一項
因此只要把前一個線段+這項就完成了
**令$P_0=0$
$P_i=P_{i-1}+a_i$
這樣就能在$O(n)$的時間處理好
加上每次query的時間為O(1)(一次減法)
總時間複雜度為$O(n\ +\ q)$**
:::warning
:warning:注意編號!! 小心不要戳出陣列
:::
### 差分
把前後兩項的差算出來就是差分，差分和前綴和互為逆運算
差分數列利用差分來表示前後兩數的關係，因此如果要在$[l, r]$都加上$k$
我們就在$D_l$加上$k$，在$D_{r+1}$加上$-k$
最後再做一次前綴和還原成原陣列就好了
**對"原陣列"做"前綴和" $\rightarrow$ 獲得"前綴和數列"
對"原陣列"做"差分" $\rightarrow$ 獲得"差分數列"
對"差分數列"作"前綴和" $\rightarrow$ 獲得"原陣列"
對"前綴和數列"作"差分" $\rightarrow$ 獲得"原陣列"**
***
### 雙指針
雙指針顧名思義，就是同時使用兩個指針，在序列、鍊錶結構上指向的是位置，在樹、圖結構中指向的是節點，通過或同向移動，或相向移動來維護、統計信息
***
### 分治
字面上的解釋是「分而治之」，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併 。
流程:
分治演算法的核心思想就是「分而治之」。
大概的流程可以分成三個步驟：分解 -> 解決 -> 合併。
分解原問題為結構相同的子問題。
分解到某個容易求解的邊界之後，進行遞迴求解。
將子問題的解合併成原問題的解。
分治法能解決的問題一般有以下特徵：
該問題的規模縮小到一定的程度就可以輕鬆解決。
這個問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質，利用該問題分解出的子問題的解可以合併為該問題的解。
這個問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。
**實例可參見merge sort**
***
### 貪心算法
每一步行動總是按某種指標選取最優的操作
例題:
經典的硬幣問題，要求用最少的硬幣來付錢
貪心策略:每次都取所能取的最大幣值
當幣值為20,10,5,1時
如圖示可以用貪心解決的
但如果幣值換成1,5,11這種特殊幣值時，就會發現用這種方法，並不是所有的數值都可以用最少的硬幣來付錢，這是因為貪心只有在局部時是最優，並沒有考慮到全局情況
***
### 圖
有兩種做法可以用來紀錄一張圖：
鄰接矩陣 ：紀錄所有頂點兩兩之間的關係，但當頂點數目很多，邊卻很少的情形，會浪費很多記憶體空間。
鄰接串列 ：只紀錄每個頂點的所連接的點。
| 1 | 2 | 3 | 4 | 5 | 6 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 1,2,5 | 1,2,3 | 2,4 | 3,5,6 | 1,2,4 | 3,5,6 |
### 樹
特點:
1. 每個節點都只有有限個子節點或無子節點；
2. 沒有父節點的節點稱為根節點；
3. 每一個非根節點有且只有一個父節點；
4. 除了根節點外，每個子節點可以分為多個不相交的子樹；
5. 樹裡面沒有環
### DFS
DFS中文名稱是深度優先搜索，是一種用於遍歷或搜尋樹或圖的演算法。所謂深度優先，就是說每次都嘗試往更深的節點走
```cpp=
void dfs(int n) {
vis[n] = 1;
for (int i = 0; i<g[n].size(); ++i) {
if (!vis[g[n][i]]) {
dfs(g[n][i]);
}
}
}
```
### BFS
BFS中文名稱是廣度優先搜尋。所謂廣度優先。就是每次都嘗試存取同一層的節點。如果同一層都存取完了，再訪問下一層。這樣做的結果是，BFS 演算法找到的路徑是從起點開始的最短合法路徑。換言之，這條路徑所包含的邊數最小。在 BFS 結束時，每個節點都是透過從起點到該點的最短路徑來存取的。演算法過程可以看做是圖上火苗傳播的過程：最開始只有起點著火了，在每一時刻，有火的節點都向它相鄰的所有節點傳播火苗。
```cpp=
void bfs(int n) {
while (!q.empty()) q.pop();
q.push(n);
vis[n] = 1;
d[n] = 0;
p[n] = -1;
while (!q.empty()) {
n = q.front();
q.pop();
for (int i = 0; i<g[n].size(); ++i) {
if (!vis[g[n][i]]) {
q.push(g[n][i]);
vis[g[n][i]] = 1;
d[g[n][i]] = d[n] + 1;
p[g[n][i]] = n;
}
}
}
}
```
:::info
:warning: 當不是在圖上dfs/bfs時，要記得排除已計算過的點
:::
### 拓撲排序
許多工作間會有「相依關係」，也就是需要先完成前項才能完成後項
拓撲排序就是已知各工作間的相依關係，是否能夠找到一組合法順序，讓工作可以依序順利執行
此圖有許多可行的拓樸排序，包括：
5, 7, 3, 11, 8, 2, 9, 10（視覺由左至右，由上至下）
3, 5, 7, 8, 11, 2, 9, 10（編號最小的可用頂點在前）
3, 5, 7, 8, 11, 2, 10, 9（依傳入鄰居的字典順序排列）
5, 7, 3, 8, 11, 2, 10, 9（最少的邊在前）
7, 5, 11, 3, 10, 8, 9, 2（編號最大的可用頂點在前）
5、7、11、2、3、8、9、10（嘗試由上至下、由左至右）
3、7、8、5、11、10、2、9（任意）
作法: 類似BFS，紀錄每個點的入度，當有一個點入度=0就把它推進queue中然後就可以在這個過程算一些東西
```cpp=
int n, m;
vector<int> G[MAXN];
int in[MAXN]; // 存储每个结点的入度
bool toposort() {
vector<int> L;
queue<int> S;
for (int i = 1; i <= n; i++)
if (in[i] == 0) S.push(i);
while (!S.empty()) {
int u = S.front();
S.pop();
L.push_back(u);
for (auto v : G[u]) {
if (--in[v] == 0) {
S.push(v);
}
}
}
if (L.size() == n) {
for (auto i : L) cout << i << ' ';
return true;
} else {
return false;
}
}
```
***
### 二分答案
解題的時候往往會考慮枚舉答案然後檢驗枚舉的值是否正確。若滿足單調性，則滿足使用二分法的條件。把這裡的枚舉換成二分，就變成了「二分答案」
```cpp=
bool check(){
//檢查函數
}
int find() {
int l = 1, r = 1e9 + 1; // 因為是左閉右開的，所以 10^9 要加 1
while (l + 1 < r) { // 若兩點不相鄰
int mid = (l + r) / 2; // 取中間值
if (check(mid)) // 如果可行
l = mid; //捨棄左半邊
else
r = mid;
}
return l; // 傳回左邊值
}
```
***
### DP
施工中
[本次APCS第四題](https://zerojudge.tw/ShowProblem?problemid=m373)
***
## 其他資源
[AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m)
[題庫](https://judge.tcirc.tw/Problems?tabid=AP325#tab03)