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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61