題意
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/519058.html
標籤：其他