CF1854D 题解

First Post:

Last Update:

非常好题目。其实我之前已经想到了二分环长除以常数次的做法，但因为不会问出整个环而只有一个 的做法，非常可惜。

首先题中的序列相当于一个内向基环树森林，最后的答案就是 所在的那个联通块的所有点。

从 出发走 次只会到达一个点，我们可以用 次询问二分出这个点的编号，下文把这个点记作 。

考虑 所在的联通块对应的环，如果我们能找到这个环的点集 ，那么，如果一个点属于答案，那么其走 步一定能到达 中的点，我们可以用 次询问判断。

设环长为 。朴素做法是先问出 ，因为其一定在环上。然后用 次询问找到 ，进而找到整个环。

因为 距离询问上界并不多，考虑在环上卡常，即只问出 除以常数个点，这里令这个常数为 。

首先，我们问出所有的 ，将其作为初始的 。

对于剩下的点，如果其在环上，那么只要走 步就一定能走到 中的点。

可以二进制分解为 ，那么接下来的做法也就清楚了：

  1. 对于还不在 中的每个点，问其走 步能否到达 中的点，若是则加入 。
  2. 对于还不在 中的每个点，问其走 步能否到达 中的点，若是则加入 。

虽然上述过程可能加入一些在 的连通块中但不在环上的点，但这些点对答案判断是没有影响的。

询问次数分析：第一步会使用 次询问，对于在环上的点，接下来两步会用 和 次询问。对于不在环上的点，整个过程会用 次询问。加起来一共是 ，甚至还有 次询问的空余时间。

但是上文的分析基于我们知道环长 ，否则第一步我们就会问到很多重复的点，导致询问次数超出预期。考虑用剩下 次询问问出环长 。不过，我们并不需要知道这个 的精确值，只需知道一个估计值。那考虑使用 BSGS 的思想。我们先问出点集 ，然后询问 走 步能否到达 中的点，如果是，就将 作为环长的近似值，这样误差是 的，询问次数上界是 ，不超过 ，满足题目限制。

再补充作者原来想到的做法：设定阈值 ，问出环上长度为 的一小段，然后判断答案时，如果一个点在 的联通块中，那么其走 次一定能到达这一段中的点，枚举这个 即可，询问次数是 ，取 ，即可得到前文提到的 复杂度。虽然 ，但因为带了个 的常数所以无法通过。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5;
typedef vector<int> vint;
int n;
void Reduce(vector<int> &S) { 
	sort(S.begin(),S.end());
	S.erase(unique(S.begin(),S.end()),S.end());
}

bool Ask(int u,int k,const vector<int> &S)
{
	printf("? %d %d %d ",u,k,(int)S.size());
	for(auto i : S) printf("%d ",i);
	printf("\n");
	fflush(stdout);
	int res;
	cin >> res;
	return res;
}
bool Ask(int u,int k,int l,int r)
{
	vector<int> S;
	for(int i = l;i <= r;i++) S.push_back(i);
	return Ask(u,k,S);
}
inline int Getnxt(int u,int k)
{
	if(k == 0) return u;
	int lef = 1,rig = n;
	while(lef < rig)
	{
		int mid = lef + rig >> 1;
		if(Ask(u,k,1,mid)) rig = mid;
		else lef = mid + 1;
	}
	return lef;
}
inline int GetLen(int st)
{
	vector<int> st8;
	for(int i = 0;i <= 7;i++)
		st8.push_back(Getnxt(st,i));
	Reduce(st8);
	for(int i = 1;i * 8 <= n;i++)
		if(Ask(st,i * 8,st8)) return i * 8;
	return n;
}
vector<int> C;
bool inc[N];
void addc(int x) { if(inc[x]) return;inc[x] = true;C.push_back(x);}
int main()
{
	cin >> n;
	int st = Getnxt(1,n + 1);
	int len = GetLen(st);
	for(int i = 0;i * 4 <= len + 4;i++)
		addc(Getnxt(st,i * 4));
	for(int i = 1;i <= n;i++)
		if(!inc[i] && Ask(i,2,C)) addc(i);
	for(int i = 1;i <= n;i++)
		if(!inc[i] && Ask(i,1,C)) addc(i);
	vector<int> Ans;
	for(int i = 1;i <= n;i++)
		if(inc[i]) Ans.push_back(i);
		else if(Ask(i,n + 1,C)) Ans.push_back(i);
	printf("! %d ",(int)Ans.size());
	for(auto i : Ans) printf("%d ",i);
	printf("\n");
	fflush(stdout);
	return 0;
}
≡