Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

2019 Week 4: Data Structures & Searching

本週延續前兩週，將繼續介紹資料結構以及 STL 的使用
並且接下來將使用這些基本資料結構構造(解釋)一些演算法

底下的術語挺多的，各位不須馬上就得記起來，等到未來碰到再回來多複習幾遍

Graph

圖 (Graph)，是一個由邊 (Edge) 集合與點 (Vertex) 集合所組成的資料結構。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Graph 的術語：

點 (vertex)：組成圖的最基本的元素
邊 (edge)：點與點的關係
$u$ 的鄰點 (neighbors)：
$u$ 透過一個邊連到的所有點
有向圖 (directed graph)：邊帶有方向性
無向圖 (undirected graph)：每條邊都是雙向的
道路 (walk^[1])：點邊相間的序列， e.g.
$v_{0} e_{1} v_{1} e_{2} v_{2} . . e_{n} v_{n}$
路徑 (path)： 點不重複的道路^[2]
環 (cycle)：路徑的起點與終點連接後形成環
入度 (in-degree)：連到該點的邊數量 (方向性)
出度 (out-degree)：該點往外連的邊數量 (方向性)
走訪/遍歷 (traversal/search)：走完全部的點或邊

在討論圖的邊，常會有

u

是邊起點與

v

是邊終點的慣例用符

上面這就是一種有向圖

通常 graph 用鄰接表 (adjacency list) 或鄰接矩陣 (adjacency matrix) 儲存資料

鄰接表

struct edge { int u, v, w; }; //兩個相鄰點與邊權重

vector<edge> graph;

int main() {
    :
    .
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &u, &v, &w);
    graph.push_back({u, v, w});
  }
}

為每個點紀錄其鄰點

鄰接矩陣

int graph[MAXN][MAXN];

int main() {
    :
    .
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &u, &v, &w);
    graph[u][v] = w;
  }
}

為每對點紀錄邊的關係

使用鄰接矩陣要注意空間成本

Tree

樹 (Tree)，這個資料結構在圖像化看起來像顆倒掛的樹，根在上，而葉子在下。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Tree 的術語及特點：

Tree 是個有向無環連通圖
節點 (node)：樹上的點不使用圖的術語 vertex
父 (parent)：節點能反向拜訪的第一個節點
子 (child)：節點能正向拜訪的第一個節點
祖先 (ancestor)：節點能反向拜訪的所有節點
孫子 (descendant)：節點能正向拜訪的所有節點
根 (root)：沒有父節點的節點
葉 (leaf)：沒有子節點的節點
深度 (depth)：節點的深度為從根到該節點所經過的邊數
森林 (forest)：一個集合包含所有不相交的 Tree
每個非根節點只有一個父節點

Union-Find Forest (併查森林)

考慮設計一個結構，
它要能存放一些集合，且這些集合之間沒有相同元素
這樣的集合族稱作 Disjoint sets

Disjoint sets 通常應用在"分類"問題中

直觀的想法是將每個集合有哪些元素，用陣列或連結串列紀錄起來
而常見的集合操作有，新增、刪除、(取)聯集、取交集(?)、取集合大小

可以思考一下這些操作的複雜度要多少

但併查森林則是將紀錄方式從 "集合有哪些元素" 改為 "元素屬於哪個集合"

Initialization

for (int v = 1; v <= N; v++) group[v] = v;

Find

Find 會尋找某個元素屬於哪個集合

int Find(int v) {
  if (v == group[v]) return v;
  return Find(group[v]);
}

假設有元素

1

5

，其中

1, 2

一組，

3, 4, 5

一組。

下 Find(5) 指令，那麼他要回傳給我

3

Path Compression

稍微想像一下可發現，若樹長這樣：

那麼明顯 Find(i) 的複雜度為

O (N)

直覺的，如果樹不是長得這麼長，而是一個個節點都直接接在

3

底下
那麼 Find(i) 的複雜度似乎就能下降了。
所以每當回溯時就順便把最上層 group 的標號^[3](也就是

3

) 給所有拜訪完的節點

i

也就是改寫為：

int Find(int v) {
  if (v == group[v]) return v;
  return group[v] = Find(group[v]); // Path Compression
}

於是原本的森林下 Find(5) 指令

森林會變成：

Union

Union 會將兩個集合合併起來 (再次提醒：此集合族是 disjoint 的)

void Union(int u, int v)
  { group[Find(u)] = Find(v); }

若對下圖這樣的情況，做 Union(4, 2); 也就是將

4

的 root

3

合併到

2

的 root

1

則上圖會變為下圖這樣：

還有種方式稱作 Union by rank/size，將 rank/size 小的樹合併到 rank/size 大的樹下，可以加快許多。

範例 UVa OJ 879 Circuit Net：

cin.ignore(); // for getline
while (getline(cin, pins)) {
  if (pins.empty()) break; // for getline

  stringstream sin(pins);
  while (sin >> a >> b) Union(a, b);
}

int cnt = 0;
for (int i = 1; i <= N; i++) if (group[i] == i) cnt++;

std::stringstream 是很方便的東西，不過據說效率不夠優。

練習：

UVa OJ 10583 Ubiquitous Religions
UVa OJ 11987 Almost Union-Find
CODEFORCES 1253D Harmonious Graph
TIOJ 1192 鑰匙設計

搜尋

有了圖，有了樹，可以開始討論這回事了

不彷將搜尋所能觸及到的可能性/目標稱為狀態
每當狀態改變後，前個狀態到下個狀態的過程稱狀態轉移。
若把狀態看作點，而狀態轉移看作邊，包含這些點與邊的圖稱作狀態空間

回憶一下上面曾介紹的術語：

走訪/遍歷 (traversal/search)：走完全部的點或邊

遍歷也是種搜尋，但"走完"可能得付出龐大的時間成本，或是空間成本
根據狀態空間規模，須用一些手段使得能更快速的找到所想要的東西。

本章使用的圖論符號慣例：

$E$ (Edge) 表邊集合，通常起點用
$u$ 、終點用
$v$ 作為節點符號
$V$ (Vertex) 表節點集合，表達單一節點常用
$u$ ,
$v$

DFS

深度優先搜尋 (Depth-first Search/DFS)：走訪為每拜訪一節點就往其一鄰點拜訪下去。
這裡的走訪為走遍所有點(而非邊)，若中途碰到曾走過的點不往下繼續走。^[4]

按照上圖，走訪順序為

1

依照自然數列開始走訪到

15

。

DFS 走過的道路為樹，稱此樹為 DFS 樹：

(圖上節點左上角的數字代表深度)

void dfs(int u, int dep) { // dep := depth
  for (auto& v: E[u]) {
    if (vis[v]) continue;
    vis[v] = true;
    dfs(v, dep+1);
  }
}

這裡 for 迴圈採用 Range-based 寫法

其中 vis[i]^[5] 為 true 代表此節點已拜訪過，下次不考慮此節點為更深的子孫節點。
所以在開始進行走訪前，將起點設為已拜訪：

vis[root] = true; // root 代表走訪此圖的起點
dfs(root, 0);

DFS 除了能夠以上述遞迴方式呈現，也可以採用 stack 來實作：

stack<tuple<int, int, int> > S;
S.emplace(root, 0, 0);
vis[root] = true;

while (!S.empty()) {
  int u, cur, dep; // cur := current index
  tie(u, cur, dep) = S.top(); S.pop();

  for (int i = cur; i < E[u].size(); i++) {
    int v = E[u][i];
    if (vis[v]) continue;

    vis[v] = true;
    S.emplace(u, i, dep);
    S.emplace(v, 0, dep+1);
    break;
  }
}

狀態空間搜尋^[6]

搜尋某個狀態，可以利用函式與參數表示，例如會把 f(1, 2, 3) 和 f(3, 4, 5) 這樣的函式呼叫，當作不同的狀態去接觸(求解)它。

範例 UVa OJ 572 Oil Deposits：

題目要求一個區域中有幾個連通圖
所謂的連通，就是圖中任意兩點間至少有一條路徑

當接觸到 dfs(r, c) 這個狀態時，代表這裡有塊包含座標

(r, c)

的 oil deposit (前提是 plot[r][c] 為 '@')
而 DFS 走訪時，只需確保不再重複走到走過的點，所以走過就設 '*'

void dfs(int r, int c) {
  if (plot[r][c] == '*') return;
  plot[r][c] = '*';

  for (int dr = -1; dr <= 1; dr++)
    for (int dc = -1; dc <= 1; dc++) //雙重迴圈讓八個方位都走
      if (r+dr >= 0 && r+dr < m && c+dc >= 0 && c+dc < n)
        dfs(r+dr, c+dc);
}

只要是連通圖，DFS 都能把此圖走訪完
這裡簡單算走進幾次連通圖就好

int count = 0;
for (int i = 0; i < m; i++)
  for (int j = 0; j < n; j++)
    if (plot[i][j] == '@') { dfs(i, j); count++; }

BFS

廣度優先搜尋 (Breadth-first Search/BFS)：走訪為每拜訪一節點就將其全部鄰點拜訪過。

按照上圖，走訪順序為

1

依照自然數列開始走訪到

15

。

當然，與 DFS 同樣，因為走訪中途碰到曾走過的點不往下繼續走，所以 BFS 走完後也會有個 BFS 樹：

最短步數

搜索地圖起點到任意點的最短步數，
例如地圖上 * 代表牆(不能走)，$ 代表路，% 是起點，@是終點
且每一步只走上下左右一格：

*  *  *  *  *  *  *  *  *  *  
*  *  *  *  $  %  $  $  *  *  
*  $  $  $  $  *  *  $  *  *  
*  $  *  $  *  *  *  $  *  *  
*  $  *  $  $  $  *  $  *  *  
*  $  *  $  *  $  $  $  *  *  
*  $  $  *  *  $  *  $  $  *  
*  *  $  $  $  *  *  *  $  *  
*  @  *  *  $  *  $  $  $  *  
*  $  *  *  $  *  $  *  $  *  
*  $  $  $  $  $  $  *  *  *  
*  *  *  *  *  *  *  *  *  *

BFS 可以應用在這^[7]：

*  *  *  *  *  *  *  *  *  *  
*  *  *  *  1  0  1  2  *  *  
*  5  4  3  2  *  *  3  *  *  
*  6  *  4  *  *  *  4  *  *  
*  7  *  5  6  7  *  5  *  *  
*  8  *  6  *  8  7  6  *  *  
*  9  10 *  *  9  *  7  8  *  
*  *  11 12 13 *  *  *  9  *  
*  21 *  *  14 *  12 11 10 *  
*  20 *  *  15 *  13 *  11 *  
*  19 18 17 16 15 14 *  *  *  
*  *  *  *  *  *  *  *  *  *

其中上面數字代表深度。
這個走法就跟粘菌走迷宮同樣

下方給出實作程式碼，可以配合上面例子來理解：

queue<int> Q;
Q.push(root); //root 代表走訪此圖的起點
vis[root] = true;

while (!Q.empty()) {
  int u = Q.front(); Q.pop();
  
  for (auto& v: E[u]) {
    if (vis[v]) continue;
    vis[v] = true;
    Q.push(v);
  }
}

根據條件應將不合法的走法濾掉，在 Q.push() 之前可判斷一下。

BFS 跟 DFS 結構只差在 stack 和 queue，除此之外兩者是非常相似的

範例 UVa OJ 11624 Fire!：

一開始先將 Joe 與各火點放進 queue 中，以便讓 BFS 以此為起點走訪：

for (int r = 0; r < R; r++) {
  scanf("%s", input);
  for (int c = 0; c < C; c++) {
    if (input[c] == '#') maze[r][c] = 0;
    if (input[c] == '.') maze[r][c] = INF;
    if (input[c] == 'J') J.push({r, c, 0}), maze[r][c] = INF, vis[r][c] = true;
    if (input[c] == 'F') F.push({r, c, 0}), maze[r][c] = 0;
  }
}

(其中 INF^[5:1] 為一個非常大的數字，例如 int 的上限)

Joe 不能被火燒到，所以 Joe 一定要走得比火快
由此，算出各點何時火會燒過來就能判斷 Joe 是否能比火先到

搜尋火到各點的最短路：

while (!F.empty()) {
  point f = F.front(); F.pop();

  for (int d = 0; d < 4; d++) {
    int nr = f.r+dr[d], nc = f.c+dc[d];
    if (nr == R || nc == C || nr < 0 || nc < 0 || maze[nr][nc] != INF || maze[nr][nc] == 0) continue;
    
    maze[nr][nc] = f.t + 1;
    F.push({nr, nc, f.t+1});
  }
}

其中 point 結構三個變數為 row, column 與 time (火抵達的時間)
並利用 dr 與 dc 以當前所在點走遍四個方向：

              /* 左, 右, 下, 上 */
int const dr[] = {0, 0, -1, 1};
int const dc[] = {-1, 1, 0, 0};

現在 maze (也就是地圖) 上有紀錄火到的時間了。
接下來讓 Joe 去尋找最短路：

int escape = -1;
while (!J.empty()) {
  point j = J.front(); J.pop();
  if ((j.r == R-1 || j.c == C-1) || (j.r == 0 || j.c == 0)) {
    escape = j.t + 1;
    break;
  }

  for (int d = 0; d < 4; d++) {
    int nr = j.r+dr[d], nc = j.c+dc[d];
    if (vis[nr][nc] || j.t + 1 >= maze[nr][nc]) continue;
    
    vis[nr][nc] = true;
    J.push({nr, nc, j.t+1});
  }
}

j.t + 1 >= maze[nr][nc] 就能看 Joe 走這點是不是會被火燒
最後判斷走到邊界，就成功逃脫了！

練習：

UVa OJ 532 Dungeon Master
STEP5 0127 攻略妹妹
 UVa OJ 11234 Expressions
UVa OJ 1599 Ideal Path

Backtracking

利用各種可得的限制來做搜尋目標中的偷吃步

八皇后問題^[8]：西洋棋盤上任意擺放八個皇后彼此都不互攻的情況有幾種？

如下圖是其中一種合法的擺法

^[8:1]

若想著把每一種任意擺放可能性列出來，再來挑選可行的盤面，
將有

(\binom{64}{8}) = 4426165368

^[9] 種盤面要產，明顯的程式會跑很久

而兩個皇后放在同個 row 或 column 上一定會互攻，所以只需在每個 row 或 column 擺放一個皇后就好：

int dfs(int row) {
  if (row == 8) return 1;
  
  int sum = 0;
  for (int col = 0; col < 8; col++)
    if (check(row, col)) {
      board[row] = col; // 在 (row, col) 放置一個皇后
      sum += dfs(row + 1);
    }
  
  return sum;
}

這邊的 check(r, c) 就是本節的主題了，
在轉移狀態(盤面)前，若能預感(?)這狀態不是想要的，就中斷轉移，然後 backtrack 到原狀態，繼續進行別的狀態轉移

用 check(r, c) 檢查將皇后放置在

(r, c)

後是否能繼續再放置其他皇后。

有點幾何知識的話，會發現 check() 只需要

O (N = 8)

就能做到：

bool check(r2, c2) {
  for (int r1 = 0; r1 < r2; r1++) {
    int c1 = board[r1];
    if (c1 == c2 || c1-c2 == r1-r2 || c1-c2 == r2-r1) return false;
  }
  
  return true;
}

枚舉的盤面會少於

N!

很多，因為 check() 剪掉了許多不必再繼續遞迴下去的 DFS 樹枝。

^[10]

練習：

UVa OJ 524 Prime Ring Problem
UVa OJ 211 The Domino Effect

Basic STL 介紹

STL 全名 Standard Template Library
由容器 (containers)、迭代器 (Iterators)、演算法 (Algorithms)、函式 (Functions) 4 種元件組成。

延續第三週，我們將再介紹幾個常用的 STL 裡的容器
絕大部分 STL 的東西只要涉及區間的操作，區間表示一律為左閉右開

推薦的參考網站： cplusplus.com、C++ reference

inserter

介紹 std::set 之前，得先介紹一些集合操作
inserter 顧名思義，就是把一些東西插入到某個地方

#include <iostream>     // std::cout
#include <iterator>     // std::inserter
#include <list>         // std::list
#include <algorithm>    // std::copy
using namespace std;

int main () {
  list<int> foo, bar;
  for (int i = 1; i <= 5; i++)
    foo.push_back(i), bar.push_back(i*10);

  list<int>::iterator it = foo.begin();
  advance(it, 3);

  copy(bar.begin(), bar.end(), inserter(foo, it));

  for (auto it : foo) cout << it << ' ';

  return 0;
}

< 1 2 3 10 20 30 40 50 4 5

set_union

union 就是將兩個集合取聯集

#include <iostream>     // std::cout
#include <algorithm>    // std::set_union, std::sort
#include <vector>       // std::vector
using namespace std;

int main () {
  int first[] = { 5, 10, 15, 20, 25 };
  int second[] = { 50, 40, 30, 20, 10 };
  vector<int> V(10);                      // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort(first, first+5);     //  5 10 15 20 25
  sort(second, second+5);   // 10 20 30 40 50

  it = set_union(first, first+5, second, second+5, V.begin());
                                               // 5 10 15 20 25 30 40 50  0  0
  V.resize(it - V.begin());                    // 5 10 15 20 25 30 40 50

  for (auto it : V) cout << it << ' ';

  return 0;
}

< 5 10 15 20 25 30 40 50

set_intersection

取交集

#include <iostream>     // std::cout
#include <algorithm>    // std::set_intersection, std::sort
#include <vector>       // std::vector
using namespace std;

int main () {
  int first[] = { 5, 10, 15, 20, 25 };
  int second[] = { 50, 40, 30, 20, 10 };
  vector<int> V(10);                      // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort(first, first+5);     //  5 10 15 20 25
  sort(second, second+5);   // 10 20 30 40 50

  it = set_intersection(first, first+5, second, second+5, V.begin());
                                               // 10 20 0  0  0  0  0  0  0  0
  V.resize(it - V.begin());                    // 10 20

  for (auto it : V) cout << it << ' ';

  return 0;
}

< 10 20

set_difference

差集

#include <iostream>     // std::cout
#include <algorithm>    // std::set_difference, std::sort
#include <vector>       // std::vector
using namespace std;

int main () {
  int first[] = { 5, 10, 15, 20, 25 };
  int second[] = { 50, 40, 30, 20, 10 };
  vector<int> V(10);                      // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort(first, first+5);     //  5 10 15 20 25
  sort(second, second+5);   // 10 20 30 40 50

  it = set_difference(first, first+5, second, second+5, V.begin());
                                               //  5 15 25  0  0  0  0  0  0  0
  V.resize(it - V.begin());                    //  5 15 25

  for (auto it : V) cout << it << ' ';

  return 0;
}

< 5 15 25

set

集合(set) 是非常基礎的數學結構，對於資料結構也一樣基礎
特別注意：集合中的元素不會重複

`std::set`

std::set 是使用紅黑樹實作的，插入、刪除、查詢都為

O (\log_{2} N)

，其中元素也不會重複。
且元素們在 set 容器中保持排序的

也就是說迭代器位置會優先從元素值小的排到大的

#include <set>
using std::set;

宣告：

set<T> S: 一個空的集合

函式：

S.insert(T a): 插入元素 a
S.erase(iterator l, iterator r): 把

[l, r)

位置上的元素移除
S.erase(T a): 移除元素 a
S.find(T a): 指向元素 a 的迭代器；若 a 不存在，則回傳 s.end()
S.count(T a): 元素 a 是否存在

key-value pair (KVP)

鍵(key)值(value)對(pair) 是非常實用的資料結構

例如想表達每個人

p_{i}

的身高

h_{i}

可以寫：

('john', 167), ('aria', 145), ('bob', 170)

又或是表達有理數

\frac{220}{440}

的分子分母：

(220, 440), (22, 44), (2, 4), (1, 2)

`std::map`

std::map 的插入、刪除或查詢為

O (\log_{2} N)

map 的每個元素結構為 std::pair<T1, T2> 構成的 KVP：

#include <map>
using std::map;

宣告：

map<T1, T2> M: 空的

函式：

M[k] = a: 修改鍵值 k 對應的值為 a
M[k]: 存取鍵值 k 對應的值
M.insert(pair<T1, T2> P): 插入一個鍵值對 P

範例 CODEFORCES 1133C Balanced Team：

每次將 skill 為

a_{i}

student 附近相差

5

以內的 skill 都記錄下來就行

例如有 skill

1

、

6

及

4

的 student 存在
那麼首先記錄

1

：

skill: 1 2 3 4 5 6 7 8 9 10 11
count: 1 1 1 1 1 1 0 0 0  0  0

接著

4

skill: 1 2 3 4 5 6 7 8 9 10 11
count: 1 1 1 2 2 2 1 1 1  0  0

然後

6

skill: 1 2 3 4 5 6 7 8 9 10 11
count: 1 1 1 2 2 3 2 2 2  1  1

所以每次對於 skill

a_{i}

：

for(int i = 0; i < n; i++) {
  scanf("%d", &a[i]);
  for(int k = 0; k <= 5; k++) cnt[a[i]+k]++;
}

接著找出哪個區間記錄值最大：

int best = 1;
for(int i = 0; i < n; i++) best = max(best, cnt[a[i]]);

且慢！
注意到一個限制：

1 \leq a_{i} \leq 10^{9}

若把 cnt 陣列的空間開得這麼大，明顯的會 Runtime error^[11]

回憶一下第一場比賽

所以把陣列改成 map<int, int>，就能避免空間上的龐大需求

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

練習：

UVa OJ 11991 Easy Problem from Rujia Liu?

Priority queue

優先隊列 (priority queue) 是隊列 (queue) 的一個變種

dequeue 會先選容器中優先度最大的元素
front 也先選容器中優先度最大的元素

`std::priority_queue`

每次進出的時間複雜度都為

O (\log_{2} N)

對於數值型態的元素，數值越大優先度越大

#include <queue>
using std::priority_queue;

對於未定義順序關係的元素(型態)，要先定義小於運算子，例如：

struct XXX {
  int code, weight;
  bool operator<(const XXX &lhs) const
    { return weight < lhs.weight; }
};

priority_queue<XXX> PQ; // []

PQ.push({2, 2147483647}) // [{2, 2147483647}]
PQ.push({3, -1}) // [{2, 2147483647}, {3, -1}]
PQ.push({2, 0}) // [{2, 2147483647}, {2, 0}, {3, -1}]

PQ.top(); // {2, 2147483647}

PQ.pop(); // [{2, 0}, {3, -1}]

puts(PQ.empty()? "yes" : "no"); // no

< no

priority_queue 也能定義比較函數，可以自行實驗

範例 GCJ Kickstart Round E 2018 B Milk Tea：

樸素的，將所有 binary string (preferences) 都產出來，並把 string 對應的抱怨 (complaint) 算出來
接著找出最小抱怨並且不屬於 forbidden types 的 binary string 就好。

span 保存將產出的 binary string：

priority_queue<pair<int, string> > span;
span.emplace(0, "");

以 seed 作為基礎，再將 string 加上 "0" 或 "1"
並每次將當前的抱怨值算出後保存：

for (int i = 0; i < P; i++) {
  priority_queue<pair<int, string> > seed;
  swap(seed, span);

  while (!seed.empty()) {
    int cp; // complaints
    string bin; // binary string
    tie(cp, bin) = seed.top(); seed.pop();

    span.emplace(cp+one[i],  bin+"0");
    span.emplace(cp+zero[i], bin+"1");
  }
}

其中 one[i] 與 zero[i] 為 Shakti 的朋友們對於第

i

個 option 的加總 (選項只有

0

和

1

)
但光是產出所有 binary string 就足夠讓複雜度導致 TLE。

在上述過程中，若把某些 string 去除掉，就能使效率增加不少
合理的，答案只要最小抱怨值的 binary string，那在過程中移除抱怨值較大的那些 string 就行了：

while (span.size() > M+1) span.pop();

因為共有

M

個 forbidden type，所以至少要保存

M + 1

個 binary string

最後把 string 為 forbidden type (ban) 的濾掉，留下抱怨值最小的就好：

int ans;
while (!span.empty()) {
  tie(cp, bin) = span.top(); span.pop();
  if (!ban.count(bin)) ans = cp;
}

練習：

ICPC 3135 Argus
UVa OJ 11997 K Smallest Sums

看英文 walk 這字，帶有一種隨意的感覺，是種無限制的路 ↩︎
很多人無法很好的區分道路與路徑，甚至行跡，通常得仔細讀上下文 ↩︎
這邊容易誤會，因為 disjoint sets tree 的"根"，是我們進行遞迴下探走到的"葉"。 ↩︎
注意，這裡的圖剛好是連通的。 ↩︎
這個變數將成為以後的慣例 ↩︎ ↩︎
State space search ↩︎
有時間可以玩玩看 pipes，裡頭有附上 source code ↩︎
Wikipedia/ Eight queens puzzle ↩︎ ↩︎
就是組合
$C$
$64$ 取
$8$ 的意思 ↩︎
Mathworks/ The Eight Queens Problem ↩︎
不過實驗證明，提交上 Codeforces 會拿到 Compilation error ↩︎

2019 Week 4: Data Structures & Searching

Graph

Tree

Union-Find Forest (併查森林)

Initialization

Find

Path Compression

Union

範例 UVa OJ 879 Circuit Net：

練習：

搜尋

DFS

狀態空間搜尋[6]

範例 UVa OJ 572 Oil Deposits：

BFS

最短步數

範例 UVa OJ 11624 Fire!：

練習：

Backtracking

練習：

Basic STL 介紹

inserter

set_union

set_intersection

set_difference

set

std::set

宣告：

函式：

key-value pair (KVP)

std::map

宣告：

函式：

範例 CODEFORCES 1133C Balanced Team：

練習：

Priority queue

std::priority_queue

範例 GCJ Kickstart Round E 2018 B Milk Tea：

練習：

Read more

Week 15: Number theory & Calculation

Week 14: Number theory

Week 13: Graph 2

Week 11: Graph

狀態空間搜尋^[6]

`std::set`

`std::map`

`std::priority_queue`