「CF1854D」Michael and Hotel 题解

逆天交互题、、、我只能说阈值分治赛高！！！

Description

有一个有 \(n\) 个点的内向基环树森林，zlsim 位于 \(1\) 号节点，请你通过以下操作求出哪些节点（包括 ）可以通过从这两点开始沿边行走若干步汇至一点。

• 给出两个参数 \(u,k\) 和点集 \(S\)，询问是否能够通过从 \(u\) 出发走 \(k\) 步达到任意 \(S\) 中的节点。
  你最多可以询问 \(2000\) 次。

Solution

十分严谨的推导过程：

• 一个节点走足够多步一定可以走到环；
• 只要走到的环是 \(1\) 号节点所属，就满足条件。
  据此，问题转化为了求 \(1\) 号节点最后到达的环有哪些节点（不关注次序）。
  我们再理一下我们可以使用的操作组（不一定全）：

1. 使用 \(\log n\) 次询问找到 \(u\) 出发走 \(k\) 步到达的节点；
2. 使用 \(n\) 次查询找到环上连续 \(k\) 个点的前面 \(k\) 个点。
   容易发现，操作组 \(2\) 是一个倍增的形式，但倍增的前几次操作损耗太大，可以使用操作 \(1\) 来解决，形成一个阈值分治的形式。由于最后我们还要询问 \(n\) 次，令进行操作组 \(1\) \(k\) 次，有询问次数 \(k\log n+n\log \frac{n}{k}+n\)。易知当 \(k\log k=n\) 时，原式存在最小值 \(n+2k\log n\)。当 \(n=500,k=80\) 时，大概为 \(1935\)。可以通过此题。

Code

#include <bits/stdc++.h>
using namespace std;

using ci = const int;

using u32 = uint32_t;
using i64 =  int64_t;
using u64 = uint64_t;

template<class T> inline void Max(T &x, const T &y) { if (x < y) x = y; }
template<class T> inline void Min(T &x, const T &y) { if (y < x) x = y; }

const int N = 505;
const int K = 80;

int n, circle_begin;
set<int> circle;

int get_val() {
	bool val;
	cin >> val;
	return val;
}

bool ask1(int u, int k, int l, int r) {
	cout << "? " << u << " " << k << " " << r - l + 1 << " ";
	for (int i = l; i <= r; ++i) cout << i << " ";
	cout << endl;
	return get_val();
}

bool ask2(int u, int k) {
	cout << "? " << u << " " << k << " " << circle.size() << " ";
	for (int i : circle) cout << i << " ";
	cout << endl;
	return get_val();
}

int u_k(int u, int k) {
	int l = 1, r = n, mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (ask1(u, k, l, mid)) r = mid;
		else l = mid + 1;
	}
	return l;
}

void output() {
	vector<int> ans;
	for (int i = 1; i <= n; ++i) {
		if (circle.count(i) or ask2(i, n)) ans.push_back(i);
	}
	cout << "! " << ans.size() << " ";
	for (int i : ans) cout << i << " ";
	cout << endl;
	exit(0);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	int p = circle_begin = u_k(1, n);

	circle.insert(p);

	for (int i = 2; i <= K; ++i) {
		p = u_k(p, 1);
		if (p == circle_begin) output();
		circle.insert(p);
	}

	int now_k = K;
	while (1) {
		vector<int> ls;
		for (int i = 1; i <= n; ++i) {
			if (!circle.count(i) and ask2(i, now_k)) ls.push_back(i);
		}
		for (int i : ls) circle.insert(i);
		if (ls.size() < now_k) output();
		now_k <<= 1;
	}

	return 0;
}