競程筆記
===
# 前言
這本講義只是我在閒暇時間將自己打競程時所學到的的知識和技巧隨手記錄下來的筆記，因此嚴謹性和完整性皆嚴重不足，還請求知慾較強的人自行google啦。

# 小技巧

#include<bits/stdc++.h> //在GNU環境下加入此標頭檔，相當於include所有library。

int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);//在main中加入這兩行能讓IO變快，但加了後就只能使用cin和cout。
    
    //使用endl，IO會變慢。
    cout<<"Hello World!!"<<endl; //bad (╬☉д⊙) 
    cout<<"Hello World!!"<<'\n'; //good (^_^) 
}

# 時間複雜度
時間複雜度(Time Complexity)說穿了就是一種【粗略估算】程式效率的手段。舉個例子:

int main()
{
    int n;
    cin>>n;
    vector<int> arr(n); //建立大小為n的一維動態陣列
    
    for(int i = 0 ; i < n ; i++)
    {
        int temp;
        cin>>temp;
        arr[i] = temp;
    }
    
    for(int i = 0 ; i < n ; i++)
        for(int k = 0 ; k < n ; k++)
            cout<<arr[i]*arr[k]<<'\n';
}

程式一共要執行1(int n)+1(cin>>n)+n(創建長度為n的陣列)+n(第一個for迴圈)+$n^2$(雙層for迴圈) = $n^2+2n+2$條指令。因為只有開頭輸入的n能影響程式的指令數，所以我們可以創造出一個函數
$$
f(n) =n^2+2n+2
$$
來描述此程式的運行指令數。

可是如果每次都要這樣一行一行計算指令數很麻煩，所以數學家們發明出了【複雜度符號】來更方便的估算程式效率。

一般來說競程大都使用Big-O $O()$ 符號來表示複雜度。

## 複雜度兩大規則
1. 只留最高次項:只要n夠大，只有最高次向能對程式效率造成決定性的影響。比方說對上面的程式來說，當n=100時$f(100)=10202$ 和 $O(f(n)) = n^2=10000$對電腦來說其實是差不多的(電腦平均可是能執行$10^9$條指令/sec)。

2. 捨去最高次項係數:基於同樣理由，n足夠大時係數對最高次項的影響不大，故捨去。

舉幾個例子:
$f(n) = 100n^3+43n$ , $O(f(n))=n^3$
$f(n)=123$ , $O(f(n))=1$

# 基礎資料結構與STL
## 什麼是資料結構?
資料結構(Date Structuer , DS)就是讓資料在電腦中組織、儲存的方式。

不同的資料結構有各自的優點，像是array用$O(1)$時間來存取特定位置的資料，鏈結串列(Linked list)能在$O(1)$時間插入/刪除資料，紅黑樹(Red–black tree)能在$O(\log_2n)$尋找樹上是否有某元素等等..。

選用合適的資料結構，能大大提升程式效率!
## 什麼是STL?
STL(Standard Template Library)，中譯標準模板庫，裡面有C++內建的、預先幫你寫好的演算法(Algorithm)和資料結構。這樣一來比賽時就不用自己寫，不只省時還大幅減少Bug，對於新手，STL也能讓一些較難實作的演算法和資料結構維持黑箱狀態，就算不懂原理也能使用(只不過行有餘力還是了解一下原理比較好)。

這也是為何打競程經常使用C++的一大主因。
## 模板(Template)
想知道如何使用STL，就必須先了解模板。

假設我們要創建一個容器(ex.stack)來儲存資料，在沒有模板前，如果要儲存N種資料型態就必須寫N種容器，很麻煩。所以人們就發明出了模板。

一個容器的宣告方式如下:

int main()
{
    cotainer<T> name;
}

cotainter是容器名稱，T是要放入容器的資料型別，name是使用者賦予的容器名稱。

比方說今天我要使用stack，那麼我可以這麼寫:

int main()
{
    stack<int> stack1;    //宣告一個存著int的stack
    stack<char> stack2;   //宣告一個存著char的stack
    stack<stack<float>> stack3;    //模板中也能放模板喔!
}

## vector(動態陣列)
能任意變換大小，伸縮自如的陣列。其餘和普通陣列幾乎沒有差別。

int main()
{
    //宣告方式
    vector<T> v1(a , b);    //宣告大小為a預設值為b的T型別vector。
    vector<int> v2(4 , 100);    //宣告大小為4預設值為100的整數vector，v2 = {100,100,100,100}
    vector<vector<char>> v3;    //宣告二維字元陣列
    
    //基本method
    v[index];    //存取位址為index的資料。
    v.resize(int size , T value) //將vector大小設為size。如果原來大小大於size則捨去多餘元素，反之則補上value。複雜度O(size)。
    v.push_back(T data);    //在vector尾端加入以一個data。複雜度O(1)。
    v.pop_back();     //刪除尾端資料。複雜度O(1)。
    v.size(); //查看vector內元素量，O(n)。
}

### vector例題
[The Blocks Problem](https://onlinejudge.org/external/1/101.pdf)

## Stack(堆疊)
可以把堆疊想成一疊盤子，只能從頂部放入或取走盤子，越晚放到盤子堆上的會優先被拿走，這就是Stack的特性，叫做***LIFO(Last In Fitst Out)***。Stack有push(在頂部加入資料)和pop(從頂部取出資料)兩種基本操作。

int main()
{
    stack<T> name;
    st.pop();  //彈出頂部資料，O(1)。
    st.push(T data); //壓入資料，O(1)。
    st.top() :  //讀取頂部資料，要注意使用此method時stack不為空，O(1)。
    st.size(); //查看stack內元素量，O(n)。
}

### stack例題
[Parentheses Balance](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=614)(經典stack應用，很推薦做做看)
## queue
施工中...
## deque
施工中...
## set
施工中...
## map
施工中...
## priority queue
施工中...
## disjoin set
施工中...