Introduction

Involution is a common transformation in mathematical contests. However, it can be difficult to visualize. Unlike the transformations typically taught in high school, an involution can produce an image that looks completely different from the original—without any apparent similarity.

To some extent, you can imagine involution as follows: First, place a ball at the center of the transformation. Then, project the original image onto the north pole of the ball. Next, position a new plane parallel to the original image at the north pole and project the image back through the south pole of the ball.

In the following program, I use the spng library to decode a PNG image, scale it up, apply the involution transformation, and then encode it back into a PNG file.

Introduction

堆積是一種特殊的樹狀資料結構，滿足以下性質，以下用最大堆積為例

1. Parent Node 的值總是大於等於 Child Nodes 的值。
2. Binary Heap 為一個完全二元樹，即除了最底層，其他層都是滿的，且最底層的節點都靠左對齊。

至於什麼是二元樹？二元樹是一種樹狀結構，其每個節點最多只能有兩個 Children。

Heap operations

堆積有以下幾種操作

1. Build Heap: 將一個陣列轉換成堆積
2. Insert: 插入一個新元素到堆積中
3. Extract Max: 移除並回傳堆積中最大的元素

Build Heap (Heapify)

將一個陣列轉換成堆積的方法稱為 Heapify。

常見的方法是從最後一個 Parent Node 開始，將每個 Parent Node 與其 Children 比較，若 Parent Node 小於 Children，則交換兩者的值，並繼續往下比較，直到該 Parent Node 大於等於所有他的新 Children。

Introduction

這週我們要來學習如何使用串列來解決一些問題。

Sliding Window

Concept

有時候我們會遇到這樣的問題，問題希望你找出所有長度為 \(k\) 的連續區間的最大最小值。
這時候，我們可以使用滑動窗口的技巧完成這樣的問題。

滑動窗口主要關注元素的進出，以最大值為例，我們可以維護一個雙向佇列 (deque)。
這個 deque 裡面存放由大到小的元素位址。

以下表為例，假設 \(k=4\)。

則區間 \(1-4\) 的最大值為 \(5\)。
區間 \(2-5\) 則為 \(4\)，依此類推。

我們可以藉由對 doubly link list 的操作，處理每一個區間的最大值。

Introduction

雖然動態陣列相當好用，某些時候也可以代替鏈結串列，然而，我們用動態陣列還是有許多無法完成的工作，例如我們要刪除中間的某一個節點，或是你的動態陣列要存的單一節點資料非常多，導致每次開兩倍依舊不是一個好的選項時。除此之外，鏈結串列還可以把兩個不同的串列用非常快的速度連接起來 (\(O(1)\)) ，也因此即使過了40年以上，他依舊是我們資料結構與演算法中必修的一部分。

鏈結串列主要分為兩種，一個是單向的，另一個則是雙向的。兩者各有優缺。

Pointer

在談到鏈結串列之前，我們先來談談指標。指標是一個變數，他存的是一個記憶體位置。在C++中，我們可以用*來宣告一個指標，例如

1
2

int a = 10;
int *p = &a;

這樣我們就宣告了一個指標p，他指向了變數a。如果我們想要取得a的值，我們可以透過*p來取得。如果我們想要改變a的值，我們可以透過*p來改變。

1
2

*p = 20;
std::cout << a << "\n"; // 20

對於一個結構，我們也可以宣告一個指標，例如

1
2
3
4
5
6
7
8
9
10
11

struct Node {
    int data;
    Node *next;
};

Node *node = new Node;
node->data = 10;
node->next = nullptr;

std::cout << node->data << "\n"; // 20
delete node;

Introduction

有了動態陣列之後，堆疊與佇列就可以被實作出來了。堆疊的基本概念是先進去的後出來，就像疊好的盤子。佇列則相反，先進去的會先出來，就像一群在排隊的人。

Queue

接著我們來實作佇列，你會發現，這次我們要利用resize。如果佇列沒有內容物而要求輸出front()，請輸出-1。如果佇列內沒有任何元素，請跳過指令。因為想要有效的利用空間，所以我們會使用環形陣列的方式儲存資料。

Template for your program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

// push back, pop front, and get front
#include <iostream>
#include <vector>
// [l, r)
struct Queue {
    Queue(): sz(0), l(0), r(0), capacity(0) {}
    std::vector<int> values;
    int l, r, sz, capacity;
    void set_capacity(int new_capacity);
    Queue& push(int val);
    Queue& pop();
    int front();
    int size() { return sz; }
};

void Queue::set_capacity(int new_capacity) {
    // Your code below
    
    // Your code above
}

Queue& Queue::push(int val) {
    // Your code below
    
    // Your code above
    return *this;
}

Queue& Queue::pop() {
    // Your code below
    
    // Your code above
    return *this;
}

int Queue::front() {
    // Your code below

    // Your code above
}

const int PUSH{1};
const int POP{2};
const int FRONT{3};

int main(void) {
    std::ios::sync_with_stdio(0);std::cin.tie(0);
    int operation_num;
    std::cin >> operation_num;

    Queue st;
    for (int i{0}; i < operation_num; ++i) {
        int op, value;
        std::cin >> op;
        switch (op) {
        case PUSH:
            std::cin >> value;
            st.push(value);
            std::cout << st.size() << "\n";
            break;
        case POP:
            st.pop();
            break;
        case FRONT:
            std::cout << st.front() << "\n";
            break;
        }
    }
}

Usage of Queue

BFS(CSES)

你有一個迷宮的地圖，任務是找到從起點到終點的路徑。你可以向左、向右、向上、或向下移動。

Input

Introduction

有了動態陣列之後，堆疊與佇列就可以被實作出來了。堆疊的基本概念是先進去的後出來，就像疊好的盤子。佇列則相反，先進去的會先出來，就像一群在排隊的人。

Stack

首先我們先來實作堆疊，你會發現，只要利用上次的push_back以及pop_back就可以很方便的做出堆疊的結構。

Template for your program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <vector>

struct Stack {
    std::vector<int> values;
    Stack& push(int value);
    Stack& pop();
    int top();
    int size();
};

Stack& Stack::push(int value) {
    // your code below

    // your code above
    return *this;
}

Stack& Stack::pop() {
    // your code below

    // your code above
    return *this;
}

int Stack::top() {
    // your code below

    // your code above
    return -1;
}

int Stack::size() {
    return values.size();
}

const int PUSH{1};
const int POP{2};
const int TOP{3};

int main(void) {
    int operation_num;
    std::cin >> operation_num;

    Stack st;
    for (int i{0}; i < operation_num; ++i) {
        int op, value;
        std::cin >> op;
        switch (op) {
        case PUSH:
            std::cin >> value;
            st.push(value);
            std::cout << st.size() << "\n";
            break;
        case POP:
            st.pop();
            break;
        case TOP:
            std::cout << st.top() << "\n";
            break;
        }
    }
}

Usage of Stack

Evaluation of Arithmetic expression

https://zerojudge.tw/ShowProblem?problemid=a017

My answer written in C.

Introduction

陣列的大小往往都是固定的，如果你需要一個可以增減的陣列，你可能會想到std::vector。然而，既然官方的函式庫裡面有這樣的東西，就表示我們可以做一個出來。

Vector

核心概念：倍增法

當空間不足時，新增一倍的空間。也可以當作是空間\(\times 2\)。

P1 Vector

Vector.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

struct Vector {
    Vector(int _sz = 0) : sz(_sz), capacity(_sz) {
        if (sz != 0) value = new int[sz];
        else value = nullptr;
    }
    ~Vector() {
        if (value != nullptr) delete [] value;
    }
    Vector& resize(int new_size);
    Vector& push_back(int val);
    Vector& pop_back();
    int& operator[](int index) { return value[index];}
    int *value;
    int sz, capacity;
};

請完成Vector.cpp的實作。

編譯

前言

當初我同學有在架設我們學校的線上評測系統，而一開始我們的系統非常不穩定，因此，他想到可以寫離線的程式答題系統緩解我們上課的需求。而我看到這個系統，我覺得這是一個不錯的想法，並依此加以改良，新增 TLE 判定和超時時會強制停止，並且可以跨平台使用。

使用(解題者)

一題會是一個資料夾，裡面會有隱藏檔案和非隱藏檔案。

README.txt 內文

以下說明檔案功能及用法

1. 編譯並執行 Run.cpp 可以獲得評測結果
2. 程式碼請寫在 Solve.cpp 裡面
3. 題目敘述在 Description 裡面，一般應該是 .txt，.md 或 .pdf
4. 標準輸入輸出用 cin 和 cout 就可以了

以下說明答題結果

1. AC 作答正確
2. WA 輸出結果錯誤，或不符合題目要求
3. TLE 執行時間過長
4. 程式跳掉 一般來說都是 RE(runtime error)

源起 & 說明

起心動念編纂這本「講義」的時候，正值我準備 APCS 考試期間，當時也正在就讀高中，考量到時間上的不足，我邀請 3 個人一起參與，所以，作者總共有 4 個人，而本篇貼文所摘錄的是我所創作的部分。

作者序

演算法與資料結構一直以來都是程式設計中最重要的部分。然而許多的書籍在介紹時，出於篇幅考量，字句精簡，以致晦澀難懂。本書旨在對於演算法及資料結構進行詳細的介紹，避免初學者遇到與我相同的困境，因而花費許多時間。雖說是競賽入門，然我仍有計畫放一些進階的資料結構與演算法。

後續我盡可能會將所有題目放在 ZeroJudge 的課程裡，方便大家測試自己的程式碼，也方便除錯。
(參加課程方式。從使用者選單->「參加課程」->課程代碼：a7HcCs)

這本書作為我程式設計學習的其中一個指標，也是我自主學習計畫的內容。希望能幫助到一些在資料結構與演算法的學習與運用上不知如何進展的人。

作者：李尚哲、余光磊、戴偉璿與李卓岳。

本教材歡迎分享使用，僅須註明出處，惟不得作營利用途。

樹狀樹組-BIT

快速求取區間和的助手

題目連結

https://codeforces.com/problemset/problem/1741/D

題目概要

給你一個 \(1; 2 …m\) 但沒有排序的數列，其中 \(m=2^n, n \in N\)。 這些數字要被放在一個完全二元樹的樹葉(葉節點)中。 定義此完全二元樹是 “\(beautiful\)” 的若且唯若葉節點的數值剛好由左而右遞增。 我們可以做的操作是對任一節點，將他的左右子樹互換。 請問最少幾次操作可以讓樹變成 “\(beautiful\)” 的，如果做不到輸出 -1。

提示 1

判斷做不做得到與怎麼做可以分開。

提示 2

怎麼做可以快速分辨是否成功。想想線段樹。

想法