# 12/21~1/9 備戰APCS與心得
終於要考第二次APCS了，但老實說跟十一月那次間隔有點短，再加上大部分時間都在寫網頁，這次能學得新觀念不是太多，但既然我在高一下之後就沒在紀錄競賽程式，這邊就做個暑假到高二上學的統整跟考後心得
## Linked list
Linked list，又稱鏈結串列，是個有點特別的資料結構，每一節點，都包含自身的資料跟指向下/前一個的指標，我喜歡把它想成地點與告示牌，像是你走進公園裡，第一個地點是長凳，上面有個牌子寫著溜滑梯，你就知道下一個景點是溜滑梯，走過去又發現一個寫著翹翹板的牌子，你就能繼續走下去
話說我每篇學習歷程都有前一篇跟下一篇的連結，應該也算一種linked list(〜￣▽￣)〜
### 基本架構
最基本的一個節點長這樣
```cpp=
struct node {
int val;
struct node *prev, *next; //告示牌 往前或往後
};
```
但老實說我在實作的時候更常用陣列做linked list，不是刻節點，只是這樣就不能做記憶體的釋放
```cpp=
struct node {
int val;
struct node *next;
};
node first;
void traversal() {
node *current = first;
while (current != NULL) {
// do something
current = current-> next;
}
}
void deleteNode(int x) {
node *current = first,
*prevNode = NULL;
while (current != NULL && current -> val != x) {
previous = current;
current = current -> next;
}
if (current == NULL) {
return;
} else if (current == first) {
first = current -> next;
delete current;
} else {
prevNode -> next = current -> next;
delete current;
}
}
void reverse() {
node *current = first,
*prevNode = NULL,
*nextNode = currentNode -> next;
while(nextNode != NULL) {
currentNode -> next = prevNode;
prevNode = currentNode;
currentNode = nextNode;
nextNode = nextNode -> next;
}
current -> next = prevNode;
first = current;
}
```
### 遍歷與查找
就是順著pointer走
```cpp=
```
陣列版我習慣用for寫
```cpp=
node arr[105];
```
然而這也是linked list的弱點，因為只能不斷循著pointer走，所以查找複雜度不佳，是O(n)
### 編輯節點
而Linked list的優點是刪除或插入中間項十分快速，以刪除舉例，只要把自己前一項的pointer指向自己的下一項，就能輕鬆越過自己了，時間複雜度O(1)
```cpp=
//假設欲刪除一叫做currentNode的節點
node *currentNode,
*prevNode = currentNode -> prev,
*nextNode = currentNode -> next;
prevNode -> next = currentNode -> next;
nextNode -> prev = currentNode -> prev;
```
陣列版操作比較簡單
```cpp=
//假設刪除arr[i]
node arr[105];
arr[arr[i].prev].next = arr[i].next;
arr[arr[i].next].prev = arr[i].prev;
```
這是linked list最厲害的一點，但在打競賽時，其實不到非常常用，因為有set，刪除跟插入O(logn)還不錯，查找O(logn)也比linked list快，使得linked list在競賽中變得不太主流，少數題型才會用到
### 倒轉linked list
這在競賽裡面似乎不怎麼實用，但好像是企業面試的經典題，所以還是學了
重點就是要把當下的節點、前一個、下一個都存起來，把當下的節點的pointer轉向(前轉後，後轉前)，再把三個節點通通往後移，重複做直到linked list尾端，並更新linked list的頭
```cpp=
node *currentNode = first,
*prevNode = NULL,
*nextNode = currentNode -> next;
while(nextNode != NULL) {
currentNode -> next = prevNode;
currentNode -> prev = nextNode;
prevNode = currentNode;
currentNode = nextNode;
nextNode = nextNode -> next;
}
first = current;
```
Linked list大概就先這樣，底下放幾題解題心得
## 合併排序
## Tree
樹則是更特殊資料結構，算是圖中的一種特殊狀況(突然想起來一年級的時候學習歷程只有打DFS跟BFS，忘了講圖論@@)
## 單調隊列
## 奇怪的資結
### 差分序列
### BIT
```cpp=
int n, BIT[MAXN];
int lowbit(int x) {
return x & -x;
}
int modify(int x) {
for(int i = x; i <= n; i += lowbit(i)) {
// modify BIT[i]
}
}
int query(int x) {
int ret = 0;
for(int i = x; i > 0; i -= lowbit(i)) {
ret += BIT[i];
}
return ret;
}
```
### 線段樹
```cpp=
int ST[MAXN];
void pull(int x) {
//相加or比大小來合併左節點與右節點
}
int query(int x, int l, int r, int ql, int qr) {
//[ql, qr]: 查詢區間
if (ql <= l && qr >= r) {
return ST[x];
}
int ret = 0;
int mid = (l + r) >> 1;
// 此為區間和作法，若是RMQ就跟query比大小
if (ql <= mid) {
ret += query(x << 1, l, mid, ql, qr);
}
if (qr > mid) {
ret += query(x << 1 | 1, mid + 1, r, ql, qr);
}
return ret;
}
void update(int x, int l, int r, int pos){
if (l == r) {
//更新ST[x]
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(x << 1, l, mid, pos);
else update(x << 1 | 1, mid + 1, r, pos);
pull(x);
}
```
## 並查集
```cpp=
int root[MAXN], unionRank[MAXN]; // 上司跟集合大小
int findParent(ll x) {
// 若上司是自己，代表你就是該集合的老大，若不是，遞迴的同時把上司改成老大
return root[x] == x ? x : root[x] = findParent(root[x]);
}
void unionByRank(int x, int y) {
int rootX = findParent(x), rootY = findParent(y);
// 老大相同不合併
if (rootX == rootY) {
return;
}
// 用集合大小來決定誰併到誰理
if (unionRank[rootX] > unionRank[rootY]) {
root[rootY] = rootX;
unionRank[rootX] += unionRank[rootY];
} else {
root[rootX] = rootY;
unionRank[rootY] += unionRank[rootX];
}
}
```
## 拓樸排序
```cpp=
int n, in[MAXN] = {}; // 點數, 入度
queue<int> root, ans; // 當下入度=0的點, 拓排解答
vector<vector<int>> graph;
void topoSorting() {
// 初始化入度為0的點
for (int i = 1; i <= n; i++) {
if (in[i] == 0) {
root.push(i);
}
}
while (!root.empty()) {
int head = root.front();
root.pop();
ans.push(head);
for (auto i: graph[head]) {
in[i]--;
if (in[i] == 0) {
root.push(i);
}
}
}
}
```
## Connected Component
```cpp=
int low[MAXN] = {}, DFN[MAXN] = {}, currentDFN = 0, SCC[MAXN] = {};
bool inStack[MAXN] = {false}; // 還沒形成SCC的點
vector<vector<int>> edges;
stack<int> st;
void Tarjan(int v) {
low[v] = DFN[v] = ++currentDFN;
st.push(v);
inStack[v] = true;
for (int &i : edges[v]) {
if (!DFN[i]) {
Tarjan(i);
low[v] = min(low[v], low[i]);
} else if (inStack[i]) {
// 還在stack中則SCC必尚未形成，排除掉連到已完成SCC的交錯邊
// 之所以是跟DFN[i]比大小不是跟low[i]是因為
// 這條邊可能是回邊或交錯邊(接回的子孫有回邊接到v祖先)
// 不管怎樣，都至少已經有一回邊，而low的定義是只走一回邊
// 故只能用DFN[i]更新low[v]
low[v] = min(low[v], DFN[i]);
}
}
if (low[v] == DFN[v]) {
int top;
do {
top = st.top();
st.pop();
SCC[top] = v;
inStack[top] = false;
} while (top != v); // v之後的都在此SCC中
}
}
```
## Fast Power
```cpp=
int fastPow(int a, int n) {
int ret = 1;
while (n > 0) {
if (n & 1) ret = ret * a;
a = a * a;
n >>= 1;
}
return ret;
}
```
## APCS心得
在講一月的APCS之前，先前情提要一下十一月那場
## 最後的最後
---
<ul style ="display: flex; flex-direction: row; width: 100%; justify-content: space-between;margin: 0; padding: 0;">
<li style="list-style: none;"><a href = "https://hackmd.io/@WeberChang/Bysh-oH5K" >上一篇</a></li>
<li style="list-style: none;"><a href = "https://hackmd.io/@WeberChang/rJBpwRsut">主頁</a></li>
<li style="list-style: none;"><a href = "https://hackmd.io/@WeberChang/B1P1d5rpY">下一篇</a> </li>
</ul>
Sign in with Wallet
Connect another wallet