1. 首頁 > 生活百科 > >

Codeforces 1682 D Circular Spanning Tree

生活百科

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

Codeforces 1682 D Circular Spanning Tree

文章插圖
提示1. 首先考慮什么時候無解，顯然，奇數點個數是偶數，并且>=22. 由奇數點個數為偶數可以發現，它們可以連到同一個偶數點上（并非直接連）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);} elsebreak;}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;}【Codeforces 1682 D Circular Spanning Tree】

    推薦閱讀