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

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

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

字典序（Lexicographic order）

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

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

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

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

比較開頭字元

像是 “apple” 和 “banana”：

第一個字元：’a’ vs ‘b’

‘a’ 在字母表中排在 ‘b’ 之前，因此 “apple” < “banana”。

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

像是 “apple” 和 “apricot”：

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

第三個字元：’p’ vs ‘r’

‘p’ 在 ‘r’ 之前，因此 “apple” < “apricot”。

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

像是 “app” 和 “apple”：

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

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

字典序的比較規則

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

next_permutation()

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

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

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

From : GeeksForGeeks

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

#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;
}

輸出結果：

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

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

#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;
}

輸出結果：

1
2
3

2 1 3 
1 3 2 
1 2 3

例題：彈珠配置

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

暴力窮舉法

#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> 容器中儲存的元素型態必須符合以下條件：

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

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

特性：

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

語法：

1	#include <set>

1	set<T, comp> s;

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

s：集合的名稱。

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

#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;
}