競賽程式進階技巧

所有範例程式非唯一正解
有任何錯誤歡迎糾正
這份講義包含

$STL\mathrm{和}sort-searching$
對初學者來說很硬，要背很多東西，但一旦會了就非常方便

題庫

先給你們一隻水豚，小心品嚐 :>

• $\mathrm{一}\mathrm{維}vector$
• $\mathrm{一}\mathrm{維}vector(2)$
• $\mathrm{二}\mathrm{維}vector$
• $set$
• $set2$
• $map1$
• $map2$

---

vector

vector介紹

vector算是從基礎語法晉升到競賽程式最明顯的指標了，所以特別的重要，vector是可以動態改變大小的陣列，不像傳統陣列開了就不能再修改

vector建立

vector<type> v(size, value);
• type:資料型態 e.g:int&char
• size:陣列的初始大小
• value:陣列的初始值

$e.g.$

//以下語法都是合法的
vector<int> v1; // v1 = {} 空 的 陣 列
vector<char> v2; // v2 = {} 空 的 陣 列
vector<int> v3(5); // v3 = {0, 0, 0, 0, 0}
vector<int> v4(3, 17); // v4 = {17, 17, 17}
vector<int> v5 = {4, 8, 7};

vector常用語法

vector<int> name;
• name.push_back(val):將 val 加進陣列的最後  //O(1)
• name.pop_back():將陣列最後的元素刪除  //O(1)
• name.size():回傳陣列的大小(無號整數)  //O(1)
• name.empty():回傳陣列是否為空  //O(1)
• name.clear():將陣列清空  //O(size)
• name.resize(size, value):
將陣列的大小設為 size,多出來的部分設為 val //O(Δsize)

$e.g.$

vector<int> v; // v = {}
v.push_back(5); // v = {5}
v.push_back(2); // v = {5, 2}
/***********************************/
v.resize(5, 3); // v = {5, 2, 3, 3, 3}
v.size(); // 5
v.empty(); // false
/***********************************/
v.pop_back(); // v = {5, 2, 3, 3}
v.clear(); // v = {}

二維vector

二維vector常常被使用來做linked-list或圖，完全沒有空間被浪費

$e.g.$

vector<vector<int>> v1; // v1 = {} 空 的 矩 陣

vector<vector<int>> v2(3);
// v2 = { {}, {}, {} } 矩 陣 內 有 三 個 空 的 陣 列

vector<vector<int>> v3(3, vector <int>(2));
// v3 = { {0, 0}, {0, 0}, {0, 0} }

vector<vector<int>> v4(3, vector <int>(2, 5));
// v4 = { {5, 5}, {5, 5}, {5, 5} 

//如果您使用的是devc++則改成這樣，否則會報錯
//                |這裡原本沒空格
vector<vector<int> > v1;
/**************************/
vector<vector<int>> v(3); // v = { {}, {}, {} }
v[1].push_back(1); // v = { {}, {1}, {} }

$STL$

註: string也算

$STL$

迭代器

大部分都能這樣用所以可以背起來

vector<int> v = {1, 3, 6, 7, 8}
//function(L, R, arg),作用於 [L, R) ; L, R可以用v.begin()和v.end()
• min_element(L, R):陣列最小元素的 iterator  //O(n)
• max_element(L, R):陣列最大元素的 iterator  //O(n)
//以下使用二分搜
• binary_search(L, R, val): 
要先排序,回傳是否有找到 val  //O(log n)    
• lower_bound(L, R, val):
要先排序,陣列數值大於等於 val 的 iterator  //O(log n)
• upper_bound(L, R, val):
要先排序,陣列數值大於 val 的 iterator  //O(log n)

$e.g.$

vector<int> v1={1, 3, 5, 8};
auto it = lower_bound(v.begin(), v.end(), 3);  //使用auto讓it等於搜索出來的迭代器
*it = 7;  //透過指標，直接指向it在記憶體中的位置，就可以改變或使用了

$sort$

可以將STL排序，大部分用在vector

$e.g.$

sort(L, R) 以及 vector<int> v={4, 8, 7, 6, 3} 當例子。
• sort(L, R); //將陣列的 [L, R) 由小到大排序
• sort(v.begin(), v.end()); //[3, 4, 6, 7, 8]
• sort(v.begin(), v.begin()+3); //[4, 7, 8, 6, 3]
• sort(v.begin()+3, v.begin());  //RE

• sort的*arg
*arg是排序方式，傳入一個布林函式，作為比較函式，做到自定義排序，會以這個形式呈現sort(v.begin(), v.end(), *arg);
  
  $e.g.$

//由大到小排序
bool mycmp(int infront, int back){
    return infront > back;
}
sort(v.begin(), v.end(), greater<int>()); //將陣列從大到小排序
sort(v.begin(), v.end(), mycmp); //使用自訂義排序
sort(v.rbegin(), v.rend()); //special

greater<int>是讓sort由大到小排列，可以學看看

• 以下很重要
  mycmp回傳的布林值是兩個相鄰的資料的關係，讓sort函式內部知道要怎麼排序，infront>back是告訴sort函式，前面的數字要大於後面的數字，於是sort函式就會由大到小排序了

包裝容器pair

用法

pair<type1, type2> name
• type:元素型別(可以不同)
------------------------
• name.first:取得前面的元素
• name.second:取得後面的元素

$e.g.$

pair<int, int> p1; // p1 = { , } 空 的 pair
pair<int, int> p2(4, 8); // p2 = {4, 8}
pair<int, int> p3 = {4, 8};
p3.first; // 4
p3.second; // 8

pair<pair<int, int>, int> p4 = {{4, 8}, 7};
p4.first; // {4, 8}
p4.first.first; // 4
p4.second; // 7
vector<pair<int, int>> v1(100, {1, 2});
cin>>v1[0].first;
vector<pair<int, int>> v2;
v2.push_back(make_pair(1, 2));

如果要對vector<pair<int, int>>進行排序，會先排序前項，如果前項相同再排列後項，如果要進行其他方式，那可能要使用自定義排序

線性容器

• 線性容器通用函式

1. name.size()
2. name.empty()
   不支援所有迭代器{name.begin(), name.end()}

queue&stack

可以吧queue想像成一個水管，只能右進左出，只能訪問最前面跟最後面
而stack則是像一個桶子，後進先出，只能訪問最上面

• 函式

//以下都合法
stack<int> s;
• s.push(val):將 val 加進 stack 的最上面,O(1)
• s.pop():將 stack 最上面的元素刪除,O(1)
• s.top():取得 stack 最上面的元素,O(1)
queue<int> q;
• q.push(val):將 val 加進 queue 的最後面,O(1)
• q.pop():將 queue 最前面的元素刪除,O(1)
• q.front():取得 queue 最前面的元素,O(1)
• q.back():取得 queue 最後面的元素,O(1)

priority_queue

將最重要的元素放在最頂端，只能訪問最前項，預設是將最大當作最重要

$e.g.$

priority_queue<int> pq
• pq.push(val):將 val 加進 pq 裡面,O(log n)
• pq.pop():將 pq 最上面的元素刪除,O(log n)
• pq.top():取得 pq 最上面的元素,O(1)

• 註 : pq的時間常數比set還要低
• 進階語法

樹狀容器

set&multiset

set主要的功能有排序與去重：
把資料送入set時，若set內已有該數值就會被刪除，若沒有就會被排序
即所有相同資料在set中只能存在一個

set<int> s;
int val=1;
s.empty();  //回傳布林值：s是否為空
s.size();  //回傳整數：s的大小
s.begin();  //回傳迭代器：s最前面的位置
s.end();  //回傳迭代器：s最後位置的下一個位置
s.insert(val);  //插入數值val到s中 回傳pair<iterator,bool>插入位置和是否成功 O(log n)
s.count(val);  //查看s中val數值的數量（set中必為1或0）O(log n)
s.erase(val);  //刪除s中的val元素 回傳iterator刪除元素的下一個位置O(log n)
s.erase(iterator);  //刪除iterator迭代器位置的數值 回傳bool是否刪除成功 O(1)
s.find(val);  //查找val數值的位置 回傳iterator O(logn)

multiset是允許多個相同數值存在的set
使用方法和set大致相同

multiset<int> ms;
int val=1;
ms.empty();  //回傳布林值：s是否為空
ms.size();  //回傳整數：s的大小
ms.begin();  //回傳迭代器：s最前面的位置
ms.end();  //回傳迭代器：s最後位置的下一個位置
ms.insert(val);  //插入數值val到s中 回傳iterator插入位置（必定插入成功） O(log n)
ms.count(val);  //查看s中val數值的數量 O(K+log n)
ms.erase(val);  //刪除s中的所有val元素 回傳整數被刪除的元素數量 O(K+log n)
ms.erase(iterator); //刪除iterator迭代器位置的數值 回傳iterator刪除元素的下一個位置 O(1)
ms.find(val);  //查找val數值的位置 若有多個數值 回傳最前面的那個 O(logn)

map

用於儲存離散化的資料，像是一個陣列，但陣列索引可能是任何資料型態，特別是當需要開一個很大的陣列的時候可以考慮使用它，通常都以map<int, int>來做

//map<key_type,value_type> mp;  這是宣告方式
map<char,int> mp;  //預設每一項都是0
mp['A'];  //在mp中宣告一個引索為A的數
mp['A']=1;
mp['A']+=5;
cout<<mp['A'];  //6
mp.erase(iterator);
mp.erase(key);  //刪除該索引的
mp.find(key);  //回傳該索引的位置 找不到則回傳mp.end()

其實還有一些很厲害的

$STL$ ，但我很懶，就放在這邊等你們探索吧

• deque
• unordered map
• bitset
• gp_hash_table

二分搜尋

• 非常非常非常重要的演算法
• 非常非常非常重要的演算法
• 非常非常非常重要的演算法

很重要，所以要說三遍

可以在極短的時間內找到需要的值
但只能在排序好的資料中使用

傳統的二分搜過程是：

1. 選擇資料中的中位數
2. 若所要的資料大於中位數則丟棄所有小於較小的資料
3. 再對大於的資料中繼續找中位數並丟棄不需要的資料
4. 直到找到所需的資料

由於二分搜不需要檢查每個資料，只需要折半再折半，因此對比線性搜尋的

$O(N)$時間，時間複雜度為

$O(\log N)$的二分搜非常 　星爆 　快

---

傳統二分搜範例寫法

要注意維護左閉右開或左開右閉

• 遞迴版本

int a[10] = {1, 3, 4, 5, 6, 7, 8, 10, 11, 12};  //已排序好的陣列
int binerySearch(int l, int r, int val) {       //左;右;要尋找的值
    if(l+1 == r) return l;                      //找到剩最後一項,回傳答案
    int mid = (l + r)/2;
    if(a[mid] > val) {                          //小於找左邊
        return binerySearch(l, mid, val);
    }
    else {                                      //大於找右邊
        return binerySearch(mid, r, val);
    }
}

• 迴圈版本

int a[10]={1, 3, 4, 5, 6, 7, 8, 10, 11, 12};  //要搜尋的陣列
int ans, val=5, l=0, r=9;  //所求在陣列的值，所求，左邊界，右邊界
while(true){
    if(l+1 == r){  //刪到只剩下一個值（即答案）
        ans=l;
        break;
    }
    int mid = (l + r)/2;
    if(a[mid] > val) r=mid;//小於所求找左邊
    else l = mid;          //大於所求找右邊
}

重點是先找到中間點，如果要找的值大於中點，則找中點的右邊，否則則找中點的左邊，若區間只有一個值，那就是答案了

但是要左邊右邊找找去好麻煩
還要管左閉右開之類的問題

所以這邊提供一個比較好的二分搜寫法我平常也用這個，我稱為跳跳二分搜

跳跳二分搜

int a[10]={1, 3, 4, 5, 6, 7, 8, 10, 11, 12};
int ans=0;
int val=5;
for(int j=10;j>0;j>>=1){
    while(ans+j<10&&a[ans+j]<=val){
        ans+=j;
    }
}

跟上面的傳統二分搜比起來簡單很多吧!只需要判斷能不能往前跳，如果不能要跳小格一點，等到一次跳的距離變成0格，答案就出來了，時間複雜度也一樣是

$O(logN)$ 可是二分搜只能在排序好的陣列中使用欸! 要怎麼做出排序好的陣列？

---

排序

排序演算法有很多
e.g.泡沫排序,選擇排序,快速排序,合併排序,希爾排序…非常非常多種，最常使用的是快速排序和合併排序，因為時間複雜度低，只需要

$O(NlogN)$，但原理不好理解，如果之後有時間再解釋

• 在
  $STL$的部分就有說到
  $sort$了，這裡就不再重複