---
# System prepended metadata

title: 12/21~1/9 備戰APCS與心得

---

# 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>

