---
# System prepended metadata

title: 【C++】競程筆記（枚舉）
tags: [程式設計, C++, 競程, 演算法, CP]

---

【C++】競程筆記（枚舉）
===

[TOC]

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

---

枚舉就是窮舉法，把所有東西都列出來。

字典序（Lexicographic order）
---

字典序，就是依照字典中出現的先後順序進行排序。

主要是用來比較和已排序序列（特別是字串）的規則，按照類似於字典中單字排列的方式進行運算。

字典序是一種排序方法，其核心思想是透過比較兩個序列的元素，從第一個元素開始，逐步向後，直到找到第一個不同的元素，然後根據這個元素的順序決定兩個序列的先後。

如果一個序列是另一個序列的前綴，則較短的序列排在前面。這種排序方式與我們在字典中查找單字的順序類似，因此被稱為「字典序」。

1. 比較開頭字元

像是 "apple" 和 "banana"：

第一個字元：'a' vs 'b'

'a' 在字母表中排在 'b' 之前，因此 "apple" < "banana"。

2. 若前面字元都相同，則遍歷找兩字串中字元不同處去比較

像是 "apple" 和 "apricot"：

前兩個字元相同：'a' = 'a', 'p' = 'p'

第三個字元：'p' vs 'r'

'p' 在 'r' 之前，因此 "apple" < "apricot"。

3. 一字串較短，另一字串較長

像是 "app" 和 "apple"：

前三個字符相同：'a' = 'a', 'p' = 'p', 'p' = 'p'

"app" 到此結束，而 "apple" 還有後續字元，因此 "app" < "apple"。

### 字典序的比較規則
---

1. 兩字串首元素開始比較
2. 逐個元素比較：如果目前的元素相同，則繼續比較下一個元素。
3. 遇到不同元素時決定順序：如果在某個位置上，兩個元素不同，則較小元素所在的序列排在前面（「較小」取決於元素的順序，例如字母表順序或數值大小）。
4. 處理前綴情況：如果一個序列是另一個序列的前綴（即較短序列的所有元素與較長序列的前綴完全相同），則較短的序列排在前面。

next_permutation()
---

用已排序（由小到大）的資料，產生下一組排列。

語法：`std::next_permutation(first, last);`

> Returns true if the container could be rearranged to the to the lexicographical larger permutation.

From : [GeeksForGeeks](https://www.geeksforgeeks.org/stdnext_permutation-prev_permutation-c/)

若容器可重新排列為按字典序更大的排列，則回傳 true。

```cpp=
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3};
    do {
        for (int n : vec) cout << n << " ";
        cout << endl;
    } while (next_permutation(vec.begin(), vec.end()));

    return 0;
}
```

輸出結果：

```
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1
```

`3! = 1*2*3 = 6`，所以有六種情形，與輸出相符。

prev_permutation()
---

對已降冪排序（由大到小）的資料，產生上一組排序。

語法：`std::prev_permutataion(first, last)`

> Returns true if the container could be rearranged to the to the lexicographical smaller permutation.

From : [GeeksForGeeks](https://www.geeksforgeeks.org/stdnext_permutation-prev_permutation-c/)

若容器可重新排列為字典序較小的排列，則回傳 true。

```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {2, 1, 3};
  
    do {
        for (auto i: v) cout << i << " ";
        cout << endl;
    } while (prev_permutation(v.begin(), v.end()));

    return 0;
}
```

輸出結果：

```
2 1 3 
1 3 2 
1 2 3
```

例題：彈珠配置
---

Source：https://zerojudge.tw/ShowProblem?problemid=d913

暴力窮舉法

```cpp=
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_solution(const vector<int>& perm, const vector<vector<int>>& guesses, const vector<int>& counts) {
    for (int i = 0; i < 6; i++) {
        int match_count = 0;
        for (int j = 0; j < 6; j++) {
            if (perm[j] == guesses[i][j]) {
                match_count++;
            }
        }
        if (match_count != counts[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    vector<vector<int>> guesses(6, vector<int>(6));
    vector<int> counts(6);

    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> guesses[i][j];
        }
        cin >> counts[i];
    }

    // 從最小排列 {1,2,3,4,5,6} 開始
    vector<int> perm = {1, 2, 3, 4, 5, 6};

    do {
        // 若經函數處理過後發現是正確排列, 則輸出
        if (is_solution(perm, guesses, counts)) {
            for (int num : perm) {
                cout << num << " ";
            }
            return 0;
        }
    } while (next_permutation(perm.begin(), perm.end()));
    
    return 0;
}
```

這個題目很像最近很紅的 minecraft 猜方塊遊戲。老闆心中會秘密選定一個特定的排序，然後叫你去猜排序，而老闆只會告訴你有幾個正確的位置，但不會告訴你是哪一個位置正確。

假設先猜 1 2 3 4 5 6，而正確答案為 4 3 2 1 5 6，老闆會告訴你兩個數字對了。

有關題目敘述，輸入部分前六個數字是 1 2 3 4 5 6 的排列，第七個數字為彈珠在正確位置的個數。

然後輸出部分，則為字典序最小的排列。

再來因為 6! 排列，可能性只有 720 種，所以可以直接暴力解。

有關以上程式，`is_solution` 函數中的參數解釋如下：

* perm：目前測試的排列。
* guesses：前六次猜測的排列。
* counts：每一個猜測的正確位置數。

裡面用了雙層迴圈，主要用 perm 與 guesses 的六次猜測排列做比較，如果 `perm[j]` 跟 `guesses[i][j]` 的位置相同，則 `match_count ++`，然後經過一輪測試過後，發現 `match_count != count`（當前測試排列的正確位置數與彈珠的正確位置數不相等），就直接 false，換下一組排列，依此類推。

集合（Set）
---

若要列舉 $\{0, 1, \cdots, N - 1\}$ 的一個子集合，只需列舉 $0$ 到 $2^{N-1}$ 的所有整數。

C++ STL 中的 `<set>` 為一個關聯式容器，`<set>` 容器中儲存的元素型態必須符合以下條件： 

1. 元素型態必須可以比較大小。 
2. 元素型態必須可以被複製和指定。

:::info
在 C++ STL 中，關聯式容器（associative containers）是一類特殊的容器，透過鍵（key）、值（value）的關聯方式來儲存和管理元素。與序列式容器（如 vector、list）按照元素插入的順序來存儲元素不同，關聯式容器中的元素是根據 key 自動排序的，使得查找、插入和刪除操作能在時間複雜度 $O(log n)$ 內完成。
:::

特性：

* 唯一性：set 中的元素是唯一的，重複的元素將被忽略。
* 自動排序：元素會依照特定的排序準則（預設為升序）自動排列。
* 不可修改：一旦元素插入 set，其值不可直接修改，如需更改，需先刪除舊元素，再插入新元素。

語法：

```cpp
#include <set>
```

```cpp
set<T, comp> s;
```

T：集合中元素的資料型態。

s：集合的名稱。

comp：為 binary predicate function（二元謂詞函數：有兩個參數並回傳 bool 的函數或函數物件），告訴 set 如何比較兩個元素。這東西是 optional 的，如果沒有提供，則集合按升序排序。

```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    
    // 建立空集合
    // Creating an empty set
    set<int> s1;
    
    // 建立一個來自初始化列表的集合
    // Creating a set from an initializer list
    set<int> s2 = {5, 1, 3, 2, 4};

    for (auto i : s2) 
        cout << i << " ";
    return 0;
}
```

output：

```
1 2 3 4 5 
```

E.g. Source：https://www.geeksforgeeks.org/set-in-cpp-stl/

常用運算：

假設集合名字叫 set1。

* set1.insert(element)：插入某元素。
* set1.erase(element)：刪除某元素。
* set1.find(element)：查找某元素。
* set1.size()：回傳容器 set1 的長度（意即總元素數量）。
* set1.empty()：檢查容器 set1 是否為空。

參考資料
===

[枚舉 - NTUCPC Guide](https://guide.ntucpc.org/BasicAlgorithm/enumerate/)

[C++ 容器类 <set> | 菜鸟教程](https://www.runoob.com/cplusplus/cpp-libs-set.html)
    
[Set in C++ STL - GeeksforGeeks](https://www.geeksforgeeks.org/set-in-cpp-stl/)