# 演算法筆記
## **目錄**
### 1.[STL](https://hackmd.io/L3i-dTqRTq-o0vZzCxd1XQ?both#STL)
### 2.圖論
### 3.Sparse table
### 4.字串相關
### 5.指標
## 題單參考
[yui huang 的演算法筆記](https://yuihuang.com/oj-level-4/)
[資讀題單](https://docs.google.com/spreadsheets/d/1pETbGRvHBhybv--MRj4N_khKetZDGWcsiRs70WNi_0A/edit#gid=589172402)
## **STL**
### (1)STACK
* 從最頂端存取、刪除、新增資料
* 後進先出
#### 程式碼
```cpp=
stack <int> stk;
stk.top(); //回傳stack頂端的值
stk.pop(); //刪除stack頂端的資料
stk.push(); // 將新值加入stack
stk.size(); // 輸出stack的大小
```
### 補充：前序/中序/後序運算法
**前序** +35
**中序** 3+5
**後序** 35+
那要如何轉換呢?
**例題：後序運算法**
我們平常使用的是中序運算法，但是對電腦而言，使用後序運算法是較為方便的
如果要用程式來進行中序轉後序，則必須使用堆疊，演算法很簡單，直接敘述的話就是使用迴圈，取出中序式的字元，遇運算元直接輸出；堆疊運算子與左括號； 堆疊中運算子優先順序大於讀入的運算子優先順序的話，直接輸出堆疊中的運算子，再將讀入的運算子置入堆疊；遇右括號輸出堆疊中的運算子至左括號。
### (2)QUEUE
* 先進先出
* 從最前端存取、刪除資料，從最後端新增資料
``` cpp=
queue <int> q;
q.front(); //回傳 queue 最前端的值
q.pop(); //刪除 queue 最前端的資料
q.push(); //將一個新的值加入 queue 的最後端
q.size(); //回傳 queue 的大小
```
### (1) + (2) = deque! (雙向佇列)
對了，deque可以用insert
```cpp=
#include <deque>
deque <int> dq;
dq.empty(); //測試 deque 是否為空。(回傳布林值)
dq.size(); //查詢目前 deque 中有幾個元素。
dq.push_front();//在 deque 的前端加入一個元素。
dq.push_back(); //在 deque 的後端加入一個元素。
dq.pop_front(); //移除目前 deque 中最前端元素。
dq.pop_back(); //移除目前 deque 中最後端元素。
dq.front(); //取得目前 deque 中最前端元素。
dq.back(); //取得目前 deque 中最後端元素。
dq.insert(iterator, n, val); //插入位置/次數/值
```
### (3)Heap (priority_queue)
* 存取、刪除 heap 最頂端的資料 (為預設的極值)
* 維持極值
:::success
預設為由大至小排列，但可以再進行更改
```cpp=
priority_queue <int> pq; //由大至小
priority_queue <T, vector<T>, greater<T> > pq; //由小至大
priority_queue<T, vector<T>, cmp> pq; //自行定義 cmp 排序
```
:::
```cpp=
pq.push(); //輸入
pq.top(); //存取最大權重值
pq.pop(); //刪除最大權重值
pq.size(); //回傳 pioraity_queue 的大小
```
### (4)Set
* 用於插入/刪除/選取資料
* 會自動進行排序/不會選到重覆的
```cpp=
set <int> s;
s.insert(); //新增
s.erase(); //刪除
s.find(); //查詢 (與iterator有關)
s.count(); //查詢是否存在於集合中
s.lower_bound(val); //找出大於或等於val的最小值的位置
for (auto it = s.begin(); it != s.end(); it++) // set的遍歷
cout << *it << endl;
```
### 補充：lower_bound and upper_bound (二分搜)
排序過的vector也可以用!
```cpp=
auto it = lower_bound(v.begin(), v.end(), val);
//用二分搜找出 "大於或等於" x的最小值的 "位置"
auto it = upper_bound(v.begin(), v.end(), val);
//用二分搜找出 "大於" x的最小值的 "位置"
```
還不太熟練，來幾道習題吧!
[APCS-圓環出口](https://zerojudge.tw/ShowProblem?problemid=f581) [APCS-牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084) [APCS-飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608) [APCS-雷射測試](https://zerojudge.tw/ShowProblem?problemid=i401) [紀念品分組](https://zerojudge.tw/ShowProblem?problemid=b159)
### (5)Map
* 使用**關鍵字Key**去索引該**關鍵字的值value**
* 為一對一的功能
* 可以修改value, 不能修改Key
* 包含插入、修改、刪除、尋找
```cpp=
map <string, int> mp; //宣告一個 key為string, value為int 的map
//插入的方法
mp[key] = value; //也可進行更改
mp.insert(pair<string, int>(Hi, 1) );
//查詢
mp.find(); //返回資料所在位置，若無則返回與end()函數相同
mp.count();
mp.erase(); //刪除
mp.clear(); //清空
```
### (6)Vector
* 可改變容量的陣列
```cpp=
vector <int> adj;
adj.push_back(); //新增尾部元素
adj.pop_back(); //刪除尾部元素
```
### (7)Pair
* 包含兩個數值 前面的稱為first, 後面的稱為second
* 兩個數值可以為不同種類的數據類型
```c++=
#include <utility>
pair <T1, T2> p1 // 宣告
make_pair (v1, v2) //直接使用v1 / v2來創建這個pair
//pair的操作
p1.first = 1;
p1.second = 2;
```
### (8)struct
常常在排序時用到!
```c++=
struct A // 結構名稱
{
結構變數;
int age;
int weight;
bool female; //之類的
}; //這裡要有分號，別忘記了!
struct A a;
a.age = 16; //以此改變
```
### [補充：指標(還是搞不太懂= =)](https://hackmd.io/L3i-dTqRTq-o0vZzCxd1XQ?view#%E6%8C%87%E6%A8%99)
### (9) Linked list
可支援插入以及刪除某個元素，但能夠存取的節點只有開頭
```cpp=
struct Node
{
int val;
Node *_next ;
Node *_before ;
Node()
{
_next = NULL;
_before = NULL;
}
};
```
### (10) bitset
```cpp=
bitset<N> b(a); // 宣告一個大小為N的bitset, 後面的a是初始化
b.count() //回傳有幾個位元是1
b.set() //將所有位元設為1
b.reset() //將所右位元設為0
```
## 二分搜
1. 左閉右閉
```cpp=
int binary_search(int l, int r)
{
while(l < r)
{
int m = (l+r)/2;
if ( f(m) == 1 ) r = m;
else l = m+1;
}
return l;
}
```
## 二元樹
例子： [洛谷 P5076](https://www.luogu.com.cn/problem/P5076)
模板，其實跟線段樹有點像?
但傳上去只有86分，可能有bug!
```cpp=
初始建構
struct Node
{
int val, cnt=1, siz=1;
struct Node *l=NULL;
struct Node *r=NULL;
};
void add(Node *now, int x)
{
now -> siz++;
if (x < now -> val)
{
if (now -> l != NULL)
add(now -> l, x);
else
{
Node *son = new Node;
son -> val = x;
now -> l = son;
}
}
else if (x > now -> val)
{
if (now -> r != NULL)
add(now -> r, x);
else
{
Node *son = new Node;
son -> val = x;
now -> r = son;
}
}
else now -> cnt++;
}
//查詢x的排名
int query_x( Node *now, int x)
{
if (now == NULL) return 0;
if (now -> val == x)
{
if (now -> l != NULL) return now -> l -> siz;
return 0;
}
if (now -> val > x)
return query_x( now -> l, x);
else
{
if (now -> l != NULL)
return now -> l -> siz + now -> cnt + query_x( now-> r, x);
else return now -> cnt + query_x(now -> r, x);
}
}
//查詢排名第x
int query_num(Node *now, int rank)
{
if (now == NULL) return 2147483647;
int lsiz;
if (now -> l == NULL) lsiz = 0;
else lsiz = now -> l -> siz;
if (lsiz >= rank)
return query_num( now->l, rank);
if (lsiz + now -> cnt >= rank)
return now -> val;
else
return query_num( now -> r, rank - lsiz - now->cnt);
}
//求x前面的數 (小於x且最大的數)
int query_front( Node *now, int x, int ans) //找較小值
{
if (now->val >= x) //比目前大就找左子樹
{
if (now -> l != NULL) //有更小的就往左找
return query_front(now -> l, x, ans);
else return ans; // 沒更小的了
}
else
{
if (now -> r == NULL) //看有沒有比目前更大的，沒有輸出目前
return now -> val;
else
{
//有就往右子樹找，先把目前可能答案紀錄
return query_front(now -> r, x, max(ans, now -> val));
}
}
}
//求x後面的數 (大於x且最小的數)
int query_next(Node *now, int x, int ans)
{
if (now -> val <= x)
{
if ( now -> r != NULL)
return query_next(now -> r, x, ans);
else return ans;
}
else
{
if (now -> l == NULL) return now -> val;
else
return query_next(now-> l, x, min(ans, now-> val));
}
}
```
## 圖論
### 圖的儲存方式
可分為**鄰接矩陣**與**鄰接陣列**
* **鄰接矩陣**
在鄰接矩陣中，建立一個二維陣列A
若(u, v)之間有連通，則使A[u][v] = 1, 否則A[u][v] = 0
在無向圖中記得A[v][u]也要設定
```c++=
bool A[M][M] = 0;
int u, v;
cin >> u >> v;
A[u][v] = 1;
A[v][u] = 1;
```
* **鄰接陣列**
對於每一個點儲存一個vector, 記錄他連到的所有點
```cpp=
vector <int> adj[M];
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
```
### 圖的遍歷
分為**BFS(廣度優先搜尋法)** 以及 **DFS(深度優先搜尋法)**
* **BFS**
使用**queue**存下可以走到但尚未走過的點
然後將走過的點pop, 繼續走與他相鄰的點
* <font color="red">**可以用來記錄每個點與原點的距離!** </font>
假設每一點的權重均為1
```cpp=
vector <int> adj[M];
bool vis [M] = {0}; //紀錄是否走過
int d[M] = {-1}; //紀錄距離
queue <int> que;
d[1] = 0;
que.push(1);
while (que.size())
{
int now = que.front();
que.pop();
vis[now] = 1;
for (int v:adj[now]) //對於adj[now]中的每一個點都跑一遍
{
if (!vis[v])
{
que.push(v); // 還沒跑過就加入que
d[v] = d[now] + 1;
vis[v] = 1 //並紀錄已經跑過
}
}
}
```
* **DFS**
走目前能走的位置，一樣記錄每個點是否走過
```cpp=
vector <int>adj[M];
bool vis[M] = {0};
DFS(1);
void DFS(int n)
{
vis[n] = 1;
for (int v:adj[n])
{
if (!vis[v])
DFS(v);
}
}
```
### 拓撲排序
當事情有**先後順序**的時候，輸出做事情的順序
思路：能做的就先做完!
將事情的先後順序看成**有向圖**，當做過該事件後刪除此點
```cpp=
vector <int> adj[M];
int deg[M] = {0}; //紀錄每個點從哪裡來的! 0即為前面沒有要先做的
int main()
{
for (int i=0; i<m; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
queue <int> que;
for (int i=1; i<=n; i++)
if (deg[i]==0) //若事情前面沒有要先做的事就先跑
que.push(i);
while (que.size())
{
int now = que.front();
que.pop();
for (int v:adj[now])
{
deg[v]--;
if (deg[v] == 0)
que.push(v);
}
}
}
```
### 樹
有n個點，n-1條邊的連通圖
除了**根節點**以外，每個點都有**父節點**
* 在樹上進行**DFS**!
可以不用紀錄visited
:::success
對於考到樹的題目，可以嘗試往整個子樹去想，不要只考慮單一節點之間的關係
ex: TOI2022 共享自行車 2020 建設人工島
:::
```cpp=
void dfs(int n, int par)
{
for (int v:adj[n])
if (v != par)
dfs(v, n);
}
```
* 記錄節點的**深度**!
```cpp=
int d[M];
d[1] = 0; //此處先假設根節點為1, 要將其換成根節點喔!
void dfs(int n, int par)
{
for (int v:adj[n])
if (v != par)
{
d[v] = d[n] +1;
dfs(v, n);
}
}
```
或者這樣也可以!
```cpp=
int dep[M];
void dfs(int n, int par, int d)
{
dep[n] = d;
for (int v:adj[n])
if (v != par)
{
dep[v] = dep[n] +1;
dfs(v, n, d+1);
}
}
```
* **樹直徑**
先隨機找一點A, 找出距離其最遠的點B, 再找出距離點B最遠的點C, 點B和點C的距離即為答案!
```cpp=
int dep[M];
vector <int> adj[M];
int dfs(int, int, int);
int main()
{
for (int i=0; i<m; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int u = dfs (1, 0, 0);
int v = dfs(u, 0, 0);
cout << dep[v];
}
int dfs(int n, int par, int d)
{
dep[n] = d;
int far = n; //紀錄距離最遠的點
for (int v:adj[n])
{
if (v!= par)
{
int tmp = dfs(v, n, d+1);
if (dep[tmp] > dep[far]) //若有更遠的就更新
far = tmp;
}
}
return far;
}
```
相關題目：[CSES tree diameter](https://cses.fi/problemset/task/1131)
#### 稍微進階的樹直徑
[CSES Tree distance](https://cses.fi/problemset/task/1132)
對每個點先找他的下面的距離
然後找那個點的parent, if(d[往下走的] + 1 > d[parent]) 答案就會是d[往下走的]
#### **子樹大小**
#### **樹重心**
### LCA(樹的共同祖先)
有兩點a, b, 其中a**深度**較深
* 將a點走至與b點深度相同
* 若此時a = b, a即是答案
* 當深度兩者相同時，搜尋他們的祖先，記錄從何時不同
* 何時不同的上一個祖先就是答案
```cpp=
vector <int> adj[M];
int anc[18][M]; //記錄他們的祖先 前面紀錄為第幾層祖先
int dfs (int n, int par, int d)
{
anc[0][n] = par;
dep[n] = d;
for (int v:adj[n])
if (v != par)
dfs (v, n, d+1);
}
int lca(int a, int b)
{
if (dep[a] < dep[b]) swap(a, b); //從深度較深的開始計算
for (int i=17; i>0; i--)
{
if (dep[anc[i][a]] >= dep[b] )
a = anc[i][a]; //此時a的深度必定大於或等於b, 而當小於b時就不會再更新
}
if (a == b)
return a;
for (int i=17; i>=0; i---)
{
if (anc[i][b] != anc[i][a]) //紀錄何時不同
a = anc[i][a];
}
return anc[0][a]; //何時不同的祖先即為答案
}
int main()
{
for (int i=1; i<18; i++) //紀錄祖先的祖先
{
for (int j=1; j<node; j++)
{
anc[i][j] = anc[i-1][anc[i-1][j]];
}
}
cout << lca(a, b); //開始lca!
}
```
相關題目：[CSES company queries 2](https://cses.fi/problemset/task/1688)
### 並查集 (DSU)
用以處理**不交集**的**合併**和**查詢**問題
可以查詢兩點是否相通
透過不斷尋找**源頭**進行
```cpp=
p[M] = {-1}; //先將陣列進行初始化
int find_root (int x) //找尋源頭
{
if (par[x] != x) //若x的源頭不等於x代表還有源頭，繼續找
return find_root(par[x]);
return x;
}
```
當想讓兩者合併時
先將兩者的源頭都找出來，將其中一個源頭的源頭改為另一個源頭
```cpp=
void union(int x, int y)
{
int rx = find_root(x);
int ry = find_root(y);
par[rx] = ry;
}
```
相關題目：[畢業旅行](https://zerojudge.tw/ShowProblem?problemid=d831) [我的朋友很少](https://zerojudge.tw/ShowProblem?problemid=a445)
### 最短路
#### (1) Dijkstra演算法
適用於**沒有負邊**的情況下
想成帶有權重的BFS, 將權重和接收點用pair表示!
1. 維護一個priority_queue , 裡面存放該點的最小距離以及該點 (dis, now)
2. 取出**距離最小**的該點，若該點未被處理過，則dis即為此點的最小距離 (直接到步驟3)
3. 對now的相鄰點進行鬆弛(此時你要確定now已經不能再被鬆弛)
```cpp=
priority_queue<pii, vector<pii>, greater<pii>> pq;
dis[1] = 0;
pq.push({0, 1});
while(pq.size())
{
ll d = pq.top().f;
int now = pq.top().s;
pq.pop();
if (d != dis[now]) continue; // 如果不等於代表這一點已經被鬆弛過了
for (pii p: adj[now])
{
int v = p.f, w = p.s;
if (dis[v] > d+w)
{
dis[v] = d+w;
pq.push({dis[v], v});
}
}
}
```
#### (2) Bellman-Ford演算法
與先前的Dijkstra略有不同，可以運用在**有負邊**的情況，也可以檢查是否有<font color="#f00">負環</font>!
複雜度為 O($nm$) 這一點要注意!已經因為這樣好幾次TLE了= =
```cpp=
const ll inf = 1LL << 60;
queue<ll> q;
q.push(1);
while(q.size())
{
int now = q.top();
q.pop();
for (pll p: adj[now])
{
ll v= p.f, w = p.s;
if (dis[v] > dis[i]+w)
{
dis[v] = dis[i]+w;
q.push(v);
}
}
}
```
### 二分圖
1. 用DSU做
當有n個點時開2*n個區域，若點a與點a+n在一起就表示不是二分圖
### MST (最小生成樹)
1. Krusal algorithm
將邊依照權重從小到大排序，檢驗目前的點是否已經在此集合裡(用並查集檢查)
複雜度為 **O($mlogm$)**
```cpp=
struct side
{
ll x, y, w;
} sd[M];
bool cmp(sd a, sd b)
{
return a.w < b.w;
}
for (int i=0; i<m; i++)
cin >> sd[i].x >> sd[i].y >> sd[i].w;
sort(sd, sd+m, cmp);
ll sum = 0;
for (int i=0; i<m; i++)
{
if (find(sd[i].x) == sd[i].y) continue;
Union(sd[i].x, sd[i].y);
sum+=sd[i].w;
}
cout << sum << endl;
```
2. Prim's algorithm
隨便選一個點當開頭，找**目前與已連接的點所連接的最小邊**，做法類似dijkstra
(下面程式碼尚未完成)
複雜度為 **O($n^2$)** 或 **O($m logm$)**
```cpp=
vector<pii> adj[M];
for (int i=0; i<m; i++)
{
int a, b, w;
cin >> a >> b >> w;
adj[a].push_back(w, b);
adj[b].push_back(w, a);
}
for (int i=0; i<n; i++)
sort(adj[i].begin(), adj[i].end);
int sum = 0;
priority_queue<pii>pq;
```
## 區間問題
整理在這個[簡報](https://slides.com/yujuan/desk)裡了!
題目敘述:給你一個長度為N的數列，接下來有q筆詢問
詢問的類型有:
(1)將[l, r]之間的數字全部加上x
(2)輸出[l, r]這個區間的最大值
### 前綴和
當問 [l, r]之間的和時
先記錄從第 1 項到第 i 項的和
那第 l 項到 第 r 項的和就是 (1-r) - (1-l)
### 差分序列
當我們有 [ a1, a2, a3, a4.. an]的序列時
紀錄 ( a2 - a1 ) , ( a3 - a2 ) ,
### Sparse table
有概念了，但不太清楚，先放個別人的[參考程式碼](https://hackmd.io/@alanlai/HkZ5NqyDt)
#### 概念：
將其先一開始每個均為一塊，然後將其不停**合併** (不同塊之間可重疊!)
以$s[i][j]$表示從 $i$ 開始， 長度為$2^j$的範圍 (也就是終點為 $i + 2^j -1$!)
例如$s[i][0]$表示從$i$開始，長度為$2^0 = 1$的範圍，也就是只有$i$自己!
$s[i][1] 會等於 s[i][0] + s[$
所以當我們要求長度為$n$的最大值時，需要 **$j = [\log_2n$]**
然後用DP更新
```cpp=
int N;
int s[1005][1005];
int log2[1005]; //紀錄那個數字log2是多少
int num[1005];
for (int i=0; i<N; i++)
{
cin >> num[i];
s[i][0] = num[i];
}
//2的j次方為 1 << j 或 pow(2,j)
//建n以內log2的表
log2[1] = 0;
for (int i=2; i<N; i++)
log2[i] = log[i/2] +1; //做無條件進位
for (int j=1; j<log2[N]; j++)
{
for (int i=0; i+pow(2,j) - 1<N; i++)
s[i][j] = max(s[i][j-1], s[i+pow(2,j)][j-1] ) ;
}
```
## 字串
### 處理字串的方式
### Stringstream的用法
可以用來將字串進行分割，或將其與Int進行轉換，首先引入標頭
```cpp=
#include <sstream>
```
**(1)將int轉換成stream**
stringsteam提供 **<<** 和 **>>** 來進行**讀取**以及**輸入**
```cpp=
#include <sstream>
int main()
{
stringstream s1;
int number 1234;
string output; // 要進行轉換的string容器
s1 << number; //將number的值輸入至s1中
s1 >> output;
cout << output; //如此一來得到的就會是1234啦!
}
```
相反的，也可以將stream轉換成int!
**(2)字串分割**
先進先出，會以空白鍵作為分界
```cpp=
stringstream ss;
string a = " I am a girl";
ss << a;
string output;
ss >> output ;
cout << output ; // 這樣就會得到I!
ss >> output;
cout << output; //此時就會得到am囉
```
### 小數點後幾位
https://it-easy.tw/cout-float/
運用 setprecision
```cpp=
cout << fixed << setprecision (2) << 1.235 << endl;
//這樣輸出結果就會是1.23!
```
### 對齊我的輸出~
運用setw();
```cpp=
cout << setw(4) << 123456;
//這樣輸出結果就是1234!
```
### Substr
顧名思義就是子字串
用法為 string (開頭位置，後面幾個), 若無結束位置就到底
```cpp=
string a = "abcdefg";
cout << a.substr(2, 5); // cdefg
```
### replace
取代字串
```cpp=
string.replace(n1, k, string2); //將s1中從n1開始後k個用s2取代
```
### to_string(待查)
### next_permutation
### getline
```cpp=
getline(cin, str, '結束字元'):
example:
str = 123456;
cout << getline(cin, str, '5'); //answer = 12345
```
## 台大資管會用到的函式(字串
### cin.getline(跟樓上的很像)
only for char string! (char 資料型態的string)
```cpp=
cin.getline(str, len);
```
### 大小寫
```cpp=
toupper(char) //變大寫
tolower(char) //變小寫
isupper(char) //判斷是否是大寫
islower(char) //判斷是否是小寫
```
### strchr
```cpp=
```
### strstr
### ispunct
## DP
排列
```cpp=
```
組合
n 為可能幣值 , x為總和
```cpp=
for (int i=1; i<=n; i++)
for (int j=0; j<=x; j++)
if (i-coin[j] >= 0)
{
combination[j] = combination[j-coin[i]] + combination[j];
}
```
範例：
現有 (1, 3, 5)共3種幣值，要湊5元，可能的組合為?
當只有1元組合時，有 1 種
當有1、3元組合時，可以在 1有兩個的時候出來一個分支，所以有1+1 = 2種
組合與排列回圈內外順序相反，畫成不一樣的樹
### backstracking (窮舉) (回溯)
例題：[zerojudge229 括號匹配問題](https://zerojudge.tw/ShowProblem?problemid=a229)
```cpp=
vector<vector<int>> result;
void backtrack_helper (路徑, 下一步選擇清單)
{
if ( 終止條件 )
result.add (路徑);
return;
for 下一步 in 選擇清單
做選擇
backtrack_helper (路徑, 下一步選擇清單)
撤銷選擇
}
```
## 指標
指標相關
| | * | & |
| -------- | -------- | -------- |
| **宣告時** | 宣告指標 | 宣告參考變數(幾乎跟原本一模一樣的變數)
|**非宣告時** | 取值符號 (取得指標變數指向的值) | 取址符號 (變數的記憶體位置) |
**對參考變數的改變也會改到原本的變數喔！**
```cpp=
* //為宣告指標用
e.g. int *ptr //這代表這是一個指向int的指標
& //為取址運算子
e.g. int *ptr = &a //a必須要是int
struct p a;
a.b
->表示指向的結構變數的內容
(*times1).p //與下者相等
times1->p
->
```
struct 裡的function (函式直接寫在struct內部)
範例：
```cpp=
struct p
{
double h;
double w;
double BMI()
{
return this-> w/ (this->h * this->h);
//this為物件本身的指標 但this也可以省略
}
};
```
## 快速冪
計算$a^n$
將n改為二進位，如果此時是1，就相乘
```cpp=
int power(int a, int n)
{
int ans = 1;
for (; n; n/=2)
{
if (n&1) ans = ans*a;
a = a*a;
}
}
```
## Greedy
### 排程問題
只有一個->按照**結束時間**從早開始排
pf 參考2023資訊之芽手寫作業4
多個->結束時間+製作時間從小到大排序
## 數學
### 找質數
歐拉篩
```cpp=
bool isPrime[M];
vector<int> prime;
fill(isPrime, isPrime+M+1, 1);
for (int i=2; i<M; i++)
{
if (isPrime[i]) prime.push_back(i);
for (int j: prime)
{
if (j*i > M) break;
isPrime[i*j] = 0;
if (i % j == 0) break; // 直到此質數是自己的因數，當跑到i/j時就會跑過了
}
}
```
### 找同餘? 模擬元
## 酷酷待查的東東
### enum
### next_premutation
Sign in with Wallet
Connect another wallet