【LOJ3161】「NOI2019」I 君的探险

【题目链接】

• 点击打开链接

【思路要点】

• 以下是笔者在考场上的做法，与标准解法存在一定区别。
• 首先我们可以先讨论一下 A , B A,B A,B 两类数据的做法。
• 对于 A A A 类数据，对每个洞穴以 1 2 \frac{1}{2} 21​ 的概率进行操作，此后观察一遍所有的洞穴，将同色的洞穴归为一类，递归处理每一类即可。
• 对于 B B B 类数据，我们本质上需要计算每个节点 i i i 的父节点的位置。点亮一个前缀，通过观察节点 i i i 是否变色我们可以判断其父亲是否在某个前缀中，整体二分即可。
• 对于剩余数据，考虑模仿 A A A 类数据的做法，对每个洞穴以 1 2 \frac{1}{2} 21​ 的概率进行操作，记该集合为 S S S 。此后观察一遍所有的洞穴，对于变色的洞穴 i i i ，我们可以确定 i i i 与 S S S 中奇数个点之间有边，因此 i i i 与 S S S 中的至少一个点之间有边，记所有 i i i 组成的集合为 T T T 。
• 对 S S S 中的所有元素以 1 2 \frac{1}{2} 21​ 的概率进行操作，可以将 S S S 分为已操作和未操作两个集合，类似于 B B B 类数据的整体二分解法，通过询问其是否变色，可以确定 T T T 中每一个元素和某一个集合中的至少一个点存在一条边。
• 并且，每当我们找到一条边，我们均可以删除新出现的孤点，以避免其出现在后续的计算中。
• 期望时间复杂度 O ( M L o g M ) O(MLogM) O(MLogM) ，期望使用操作次数 O ( M L o g M ) O(MLogM) O(MLogM) 。

【代码】

#include "explore.h"
#include<bits/stdc++.h>
using namespace std;
int n, m;
namespace subtask1 {
	const int MAXN = 505;
	bool state[MAXN];
	void work() {
		for (int i = 0; i <= n - 1; i++)
			state[i] = false;
		for (int i = 0; i <= n - 2; i++) {
			modify(i);
			for (int j = i + 1; j <= n - 1; j++) {
				if (query(j) != state[j]) {
					report(i, j);
					state[j] ^= true;
				}
			}
		}
	}
}
namespace subtaskA {
	const int MAXN = 2e5 + 5;
	int a[MAXN], tmp[MAXN];
	bool cmp(int x, int y) {
		return tmp[x] < tmp[y];
	}
	void work(int l, int r) {
		if (l + 1 == r) report(a[l], a[r]);
		if (r - l + 1 <= 2) return;
		random_shuffle(a + l, a + r + 1);
		for (int i = l; i <= r; i++)
			if (rand() & 1) modify(a[i]);
		for (int i = l; i <= r; i++)
			tmp[a[i]] = query(a[i]);
		sort(a + l, a + r + 1, cmp);
		int mid = l - 1;
		for (int i = l; i <= r; i++)
			if (tmp[a[i]] == 0) mid = i;
		work(l, mid);
		work(mid + 1, r);
	}
	void work() {
		srand('X' + 'Y' + 'X');
		for (int i = 0; i <= n - 1; i++)
			a[i] = i;
		work(0, n - 1);
	}
}
namespace subtaskB {
	const int MAXN = 2e5 + 5;
	int a[MAXN], tmp[MAXN], cur;
	bool cmp(int x, int y) {
		return tmp[x] < tmp[y];
	}
	void work(int l, int r, int ql, int qr) {
		if (ql > qr) return;
		if (l == r) {
			for (int i = ql; i <= qr; i++)
				report(a[i], l);
			return;
		}
		int mid = (l + r) / 2;
		while (cur < mid) modify(++cur);
		while (cur > mid) modify(cur--);
		for (int i = ql; i <= qr; i++)
			if (a[i] <= mid || query(a[i])) tmp[a[i]] = false;
			else tmp[a[i]] = true;
		sort(a + ql, a + qr + 1, cmp);
		int qmid = ql - 1;
		for (int i = ql; i <= qr; i++)
			if (tmp[a[i]] == false) qmid = i;
		work(l, mid, ql, qmid);
		work(mid + 1, r, qmid + 1, qr);
	}
	void work() {
		for (int i = 1; i <= n - 1; i++)
			a[i] = i;
		cur = -1, work(0, n - 1, 1, n - 1);
	}
}
namespace subtaskF {
	const int MAXN = 2e5 + 5;
	bool done[MAXN], state[MAXN];
	int cm, cq, fm, a[MAXN], b[MAXN];
	bool va[MAXN], vb[MAXN];
	vector <int> e[MAXN];
	set <pair <int, int> > st;
	vector <pair <int, int> > pend;
	void found(int x, int y) {
		if (x > y) swap(x, y);
		if (st.count(make_pair(x, y))) return;
		st.insert(make_pair(x, y));
		fm++, report(x, y);
		pend.push_back(make_pair(x, y));
		done[x] = check(x);
		done[y] = check(y);
	}
	void mod(int x) {
		cm++, state[x] ^= true;
		for (unsigned i = 0; i < e[x].size(); i++)
			state[e[x][i]] ^= true;
		modify(x);
	}
	int qry(int x) {
		cq++;
		return query(x);
	}
	bool cmpa(int x, int y) {
		return va[x] > va[y];
	}
	bool cmpb(int x, int y) {
		return vb[x] > vb[y];
	}
	void sortA(int l, int r) {
		while (l <= r) {
			if (va[a[l]]) l++;
			else if (!va[a[r]]) r--;
			else swap(a[l], a[r]);
		}
	}
	void sortB(int l, int r) {
		while (l <= r) {
			if (vb[b[l]]) l++;
			else if (!vb[b[r]]) r--;
			else swap(b[l], b[r]);
		}
	}
	void workmod(int la, int ra, int lb, int rb) {
		if (lb > rb) return;
		if (la == ra) {
			for (int i = lb; i <= rb; i++)
				found(a[la], b[i]);
			return;
		}
		random_shuffle(a + la, a + ra + 1);
		random_shuffle(b + lb, b + rb + 1);
		for (int i = la; i <= ra; i++)
			if (rand() & 1) mod(a[i]), va[a[i]] = true;
			else va[a[i]] = false;
		sortA(la, ra);
		for (int i = lb; i <= rb; i++)
			if (qry(b[i]) != state[b[i]]) vb[b[i]] = true;
			else vb[b[i]] = false;
		sortB(lb, rb);
		int mida = la - 1, midb = lb - 1;
		for (int i = la; i <= ra; i++)
			if (va[a[i]]) mida = i, mod(a[i]);
		for (int i = lb; i <= rb; i++)
			if (vb[b[i]]) midb = i;
		workmod(la, mida, lb, midb);
		workmod(mida + 1, ra, midb + 1, rb);
	}
	void workqry(int la, int ra, int lb, int rb) {
		if (lb > rb) return;
		if (la == ra) {
			for (int i = lb; i <= rb; i++)
				found(a[la], b[i]);
			return;
		}
		for (int i = lb; i <= rb; i++)
			state[b[i]] = qry(b[i]);
		random_shuffle(a + la, a + ra + 1);
		random_shuffle(b + lb, b + rb + 1);
		for (int i = la; i <= ra; i++)
			if (rand() & 1) mod(a[i]), va[a[i]] = true;
			else va[a[i]] = false;
		sortA(la, ra);
		for (int i = lb; i <= rb; i++)
			if (qry(b[i]) != state[b[i]]) vb[b[i]] = true;
			else vb[b[i]] = false;
		sortB(lb, rb);
		int mida = la - 1, midb = lb - 1;
		for (int i = la; i <= ra; i++)
			if (va[a[i]]) mida = i;
		for (int i = lb; i <= rb; i++)
			if (vb[b[i]]) midb = i;
		workqry(la, mida, lb, midb);
		workqry(mida + 1, ra, midb + 1, rb);
	}
	void work() {
		srand('X' + 'Y' + 'X');
		while (fm < m) {
			for (unsigned i = 0; i < pend.size(); i++) {
				int x = pend[i].first, y = pend[i].second;
				e[x].push_back(y);
				e[y].push_back(x);
			}
			pend.clear();
			if (cm <= cq) {
				int la = 0, lb = 0;
				for (int i = 0; i <= n - 1; i++)
					if (!done[i] && rand() % 2) a[++la] = i, mod(i);
				for (int i = 0; i <= n - 1; i++)
					if (!done[i] && qry(i) != state[i]) b[++lb] = i;
				for (int i = 1; i <= la; i++)
					mod(a[i]);
				workmod(1, la, 1, lb);
			} else {
				int la = 0, lb = 0;
				for (int i = 0; i <= n - 1; i++)
					if (!done[i] && rand() % 2) a[++la] = i, mod(i);
				for (int i = 0; i <= n - 1; i++)
					if (!done[i] && qry(i) != state[i]) b[++lb] = i;
				workqry(1, la, 1, lb);
				for (int i = 0; i <= n - 1; i++)
					if (!done[i]) state[i] = qry(i);
			}
		}
	}
}
void explore(int N, int M) {
	n = N, m = M;
	if (n <= 500) {
		subtask1 :: work();
		return;
	} else if (N % 10 == 8) {
		subtaskA :: work();
		return;
	} else if (N % 10 == 7) {
		subtaskB :: work();
		return;
	} else {
		subtaskF :: work();
		return;
	}
}