Codeforces 1682 D Circular Spanning Tree

• 2022 年 10 月 23 日
• 筆記
• 思維題專輯

題意

1-n排列，構成一個圓；1-n每個點有個值0或者1，0代表點的度為偶數，1代表點的度為計數；詢問能否構成一棵樹，樹的連邊在圓內不會相交，在圓邊上可以相交，可以則輸出方案。

提示

1. 首先考慮什麼時候無解，顯然，奇數點個數是偶數，並且>=2
2. 由奇數點個數為偶數可以發現，它們可以連到同一個偶數點上（並非直接連）
3. 剩下的偶數點可以直接順時針串聯，直到連到最近的一個奇數點上
4. 相當於每個奇數點後面有一條偶數鏈，或者沒有偶數鏈只有一個奇點（這都是一樣的，因為鏈最後一個點都只剩下一個需要連的點），直接把鏈的最後一個點連在一起就好了

程式碼

#include<bits/stdc++.h>

using namespace std;
char s[200005];

void run() {
    int n;
    cin >> n;
    cin >> s;
    int ans = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        ans += s[i] - '0';
    }
    if (ans % 2 || ans == 0) {
        puts("NO");
        return;
    } else {
        puts("YES");
    }
    int cnt = n - ans;
    if (cnt == 0) {
        for (int i = 2; i <= n; i++) {
            cout << 1 << ' ' << i << '\n';
        }
        return;
    }
    vector<vector<int>> vec;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '1') {
            vector<int> res;
            res.emplace_back(i);
            for (int j = i + 1; j <= n; j++) {
                if (s[j - 1] == '0')res.emplace_back(j);
                else {
                    i = j - 1;
                    break;
                }
            }
            vec.emplace_back(res);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '0') {
            vec.back().emplace_back(i);
        } else
            break;
    }
    int root = 1;
    for (auto k: vec) {

        for (int i = 1; i < k.size(); i++) {
            cout << k[i-1] << ' ' << k[i] << '\n';
        }
    }
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i].size() > 1) {
            root = i;
        }
    }
    for (int i = 0; i < vec.size(); i++) {
        if (i == root)continue;
        cout << vec[root].back() << ' ' << vec[i].back() << '\n';
    }


}

int main() {
    int t;
    cin >> t;
    while (t--)
        run();

    return 0;
}