NOI 2019 I 君的探险 题解

First Post:

Last Update:

很神的题，很有教育意义。

先想想自己能问什么，再想想自己该怎么问。

首先观察操作，一次 modify 只能改变与其相邻的点的状态，那么假如我们对集合 中的点都进行一次 modify，我们就能对于 ，知道其连向 中的边数的奇偶性。

那么一个性质一个性质地看，对于性质 ，可以将点分为两部分，然后维护左部点集 和 的邻域 ，然后在 中选出一半点求出这一半点的邻域，然后分治下去。

这个做法很好，但是没啥前途。一个更巧妙地获取邻域信息的做法是：枚举二进制位 ，对第 位为 的点 modify，对每个点记录一个值 ，如果某个点在第 位改变了状态就将 。那么最后， 中存储的就是 的所有邻居的异或和！

这个其实不仅能做 A 性质，C 性质和 D 性质也都能做了。对于一个点，我们可以用两次 modify 和一次 query 来检查 和 之间有没有连边。那么我们可以用 ”剥叶子“ 的思想，维护一个队列存放当前所有叶子，如果如果有就将 与 的边记录，然后更新 。如果此时 的邻边都做完了，那就直接将 加入队列。如此往复即可做完。

但这个做法做不了 B 性质，出题人希望我们有更好的做法。B 性质是一棵存在拓扑序 的树，即 。那么我们可以直接利用先前对集合 进行 modify 的结论，对每个 二分一个 ，将 的点 modify，这样就知道 是否在 中。直接这样二分显然没前途，对所有 整体二分即可。

正解比较神奇。重复如下过程：将当前还未孤立的点随机排列，那么设当前有 个点，则期望有 个点有奇数条向排在它前面的点连的边。而对于这种有奇数条边连向前面的点，套用 B 性质的整体二分算法可以找到它的至少一条出边，所以直接跑这个算法。跑完后把新产生的孤立点删掉，再重复之前过程即可。

询问次数当然在 级别。这个 不知道从哪来的，官方题解也没说。

不管怎么样，还是有教育意义的一道题，性质 ABCD 都是很有价值的。想要做出这些性质乃至这道题，都必须要对题中的操作及提供的信息 有深刻地理解。这题再次让我们看到二进制的奇妙运用，当然还看到了比较常规的对于一个集合进行考虑，来得到一些可二分做法的思路。这大概是交互的魅力所在。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
#include "explore.h"
using namespace std;
typedef pair<int,int> pii;
#define FI first
#define SE second
#define mkp make_pair
const int N = 2e5 + 5,M = 3e5 + 5;
mt19937 Rnd(1919810);
inline int randint(int l,int r) { return Rnd() % (r - l + 1) + l;}
int n,m,mcnt;
vector<int> G[N];
bool die[N];
set<pair<int,int> > reped;
inline void addedge(int x,int y) {
	if(x > y) swap(x,y);
	if(x == y || reped.count(mkp(x,y))) return;
	// cerr << x << ' ' << y << endl;
	reped.insert(mkp(x,y));
	report(x,y);++mcnt;
	G[x].push_back(y);G[y].push_back(x);
	die[x] = check(x);die[y] = check(y);
}

namespace Brute {
	int col[N];
	inline void explore(int N,int M) {
		n = N;m = M;
		for(int i = 0;i < n - 1;i++) {
			modify(i);col[i] ^= 1;
			for(int j = i + 1;j < n;j++)
				if(query(j) != col[j])
					col[j] ^= 1,report(i,j);
		}
	}
}
namespace A {
	int nxor[N],col[N];
	inline void explore(int N,int M) {
		for(int i = 0;i <= __lg(n);i++) {
			for(int j = 0;j < n;j++)
				if((j >> i) & 1) modify(j);
			for(int j = 0;j < n;j++)
				if(col[j] != query(j))
					nxor[j] |= (1 << i),col[j] ^= 1;
		}
		for(int i = 0;i < n;i++) nxor[i] ^= i;
		for(int i = 0;i < n;i++)
			if(i < nxor[i]) report(i,nxor[i]);
	}
}
namespace TreeB {
	int a[N];
	void erfen(int l,int r,int ql,int qr) {
		if(l == r) { for(int i = ql;i <= qr;i++) report(l,a[i]);return;}
		int mid = l + r >> 1;
		for(int i = l;i <= mid;i++) modify(i);
		static int a1[N],a2[N];
		int c1 = 0,c2 = 0;
		for(int i = ql;i <= qr;i++)
			if(a[i] <= mid || query(a[i])) a1[++c1] = a[i];
			else a2[++c2] = a[i];
		for(int i = l;i <= mid;i++) modify(i);
		for(int i = 1;i <= c1;i++) a[ql + i - 1] = a1[i];
		for(int i = 1;i <= c2;i++) a[ql + c1 + i - 1] = a2[i];
		erfen(l,mid,ql,ql + c1 - 1);
		erfen(mid + 1,r,ql + c1,qr);
	}
	void explore(int n,int m) {
		for(int i = 0;i < n;i++) a[i] = i;
		erfen(0,n - 1,1,n - 1);
	}
}
namespace Chain {
	int nxor[N],col[N];
	inline void explore(int N,int M) {
		for(int i = 0;i < n;i++) modify(i);
		int p0;
		for(int i = 0;i < n;i++) if(query(i)) col[i] = 1;
		for(int i = 0;i < n;i++) if(!col[i]) p0 = i;
		for(int i = 0;i <= __lg(n);i++) {
			for(int j = 0;j < n;j++)
				if((j >> i) & 1) modify(j);
			for(int j = 0;j < n;j++)
				if(col[j] != query(j))
					nxor[j] |= (1 << i),col[j] ^= 1;
		}
		for(int i = 0;i < n;i++) nxor[i] ^= i;
		int las = 0,nxt;
		for(int _ = 1;_ < n;_++) {
			nxt = nxor[p0] ^ las;
			report(p0,nxt);las = p0;p0 = nxt;
		}
	}
}
namespace Sol {
	int S[N],tot,col[N];
	bool usd[N];
	inline void modify2(int x) {
		col[x] ^= 1;
		for(auto y : G[x]) col[y] ^= 1;
		modify(x);
	} // 比较 col 和 query 的结果可以看出在“未报告”的边中连了奇数/偶数条
	int a[N],b[N];
	void erfen(int l,int r,int ql,int qr) {
		if(l == r) { for(int i = ql;i <= qr;i++) addedge(b[i],a[l]);return;}
		int mid = l + r >> 1;
		for(int i = l;i <= mid;i++) if(!die[a[i]]) modify2(a[i]),usd[a[i]] = true;
		static int a1[N],a2[N];
		int c1 = 0,c2 = 0;
		for(int i = ql;i <= qr;i++)
			if(usd[b[i]] || query(b[i]) != col[b[i]]) a1[++c1] = b[i];
			else a2[++c2] = b[i];
		for(int i = l;i <= mid;i++) if(!die[a[i]]) modify2(a[i]),usd[a[i]] = false;
		for(int i = 1;i <= c1;i++) b[ql + i - 1] = a1[i];
		for(int i = 1;i <= c2;i++) b[ql + c1 + i - 1] = a2[i];
		erfen(l,mid,ql,ql + c1 - 1);
		erfen(mid + 1,r,ql + c1,qr);
	}
	inline void explore(int N,int M) {
		n = N;m = M;
		while(mcnt < m) {
			tot = 0;
			for(int i = 0;i < n;i++) if(!die[i]) a[++tot] = i;
			shuffle(a + 1,a + tot + 1,Rnd);
			for(int i = 1;i <= tot;i++) b[i] = a[i];
			erfen(1,tot,2,tot);
		}
	}
}

void explore(int N,int M) {
	n = N;m = M;
	if(n <= 500) return Brute::explore(n,m);
	if(n % 10 == 8) return A::explore(n,m);
	if(n % 10 == 7) return TreeB::explore(n,m);
	if(n % 10 == 6) return Chain::explore(n,m);
	Sol::explore(n,m);
}
// start: 2023.12.15 11:10
≡