Codeforces link

Luogu link

題解 CF1682D

Part 0. 無解情況

首先考慮無解情況。

首先，若 $s$ 中 $\text{1}$ 的個數是奇數，肯定無解。

其次，樹肯定是有葉子的，而葉子的度數肯定是 $1$，所以若 $s$ 中沒有任何一個 $\text{1}$，也無解。

其余情況都有解。

---

Part 1. 含有偶數度數節點的情況

我們可以把序列拆分成若干個 $[\text{0},\text{0},...,\text{0},\text{1}]$ 的子序列（單獨的 $\text{1}$ 也可以作為一個子序列）。注意這是個環，所以序列首尾相接。然后任意挑出一個位于某個子序列首的 $\text{0}$ 作為根。接下來：

• 每個序列連成一條鏈；
• 每個序列的第一個元素接上根節點。

因為 $\text{1}$ 有偶數個，所以鏈也有偶數條，從而根節點的度數也是偶數，符合題意。

---

Part 2. 不含有偶數度數節點的情況

任意挑一個節點為根，構造菊花圖即可。

//CF1682D #include <cstdio>const int N = 2e5 + 10; int t, n; char s[N];int main(){scanf("%d", &t);while(t--){scanf("%d%s", &n, s+1);int cnt = 0;for(int i = 1; i <= n; ++ i){if(s[i] == '1'){++ cnt;}}if(cnt == 0 || cnt & 1){puts("NO");continue;}puts("YES");if(cnt == n){for(int i = 2; i <= n; ++ i){printf("1 %d\n", i);}continue;}int st = 0;if(s[n] == '1' && s[1] == '0'){st = 1;} else {for(int i = 1; i <= n; ++ i){if(!st && s[i] == '0' && s[i-1] == '1'){st = i;}}}#define pre(i) (i==1 ? n : i-1)#define nxt(i) (i==n ? 1 : i+1)bool flg = true;for(int i = st+1; flg || i < st; ++ i){if(i == n+1){i = 1;if(st == 1) break;flg = false;}if(pre(i) == st || s[pre(i)] == '1'){printf("%d %d\n", i, st);}if(s[i] == '0'){printf("%d %d\n", i, nxt(i));}}}return 0; }

總結

以上是生活随笔為你收集整理的题解 [CF1682D] Circular Spanning Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。