【题解】CF1854D Michael and Hotel

交互题。

考虑题意即为找到 \(1\) 所在内向基环树上的所有点。

我们考虑我们怎么找到环上的点，我们考虑我们可以 \(O(\log n)\) 询问到一个环上的点，方法即为将 \(k\) 定为一个大数，然后二分点集。然后我们便可以在 \(O(n\log n)\) 的时间复杂度内找到所有环上的点（我们一会儿再讲怎样优化）。

我们找到环上的点了之后，我们再将 \(S\) 设为环上的点，\(k\) 设为一个极大数，\(u\) 从 \(1\sim n\) 遍历，如果返回 \(1\) 即为可以到达，否则不能到达，这样我们就可以在 \(O(n)\) 的时间内找到所有链上的点。

我们显然现在需要将找环上的点的操作再精简一下。

我们考虑我们找链上的点时的方法十分地高效，我们可以略作修改来找环。

我们考虑假设我们找到了环上的长度为 \(len\) 的链，那么我们可以将 \(S\) 设为已经找到的环上的点，\(k = len\)，\(u\) 从 \(1\sim n\) 遍历。返回 \(1\) 便将点加入环，这样，我们每次的环长就可以倍增了，停止条件就是环长没有倍增（即绕了一圈回来了）。

上面的方法显然可能将环外的点也加进来，但是显然没有任何印象。

我们便可以将两种找环上点的方法结合起来，先每次 \(\log n\) 询问环上的单点0，然后每次 \(O(n)\) 倍增环上的点。由下图可知，一开始询问出长度为 \(56\) 链是最优的，当然上下浮动一点点也无伤大雅。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 5e2 + 8;

int n,tot,rt = 1;

bool check(int tim,int l,int r){
	printf("? %d %d %d ",rt,tim,r - l + 1);
	for(int i = l; i <= r; ++i) printf("%d ",i);
	puts("");fflush(stdout);
	
	int op;scanf("%d",&op);
	return op;
}

set<int> Nodes;
bool vis[NN];

void Get_Part_Of_Ring(){
	int l = 1,r = n;
	while(l < r){
		int mid = (l + r) / 2;
		if(check(1000,l,mid)) r = mid;
		else l = mid + 1;
	}
	Nodes.insert(l);
	rt = l;
	for(int i = 1; i <= 62; ++i){
		l = 1; r = n;
		while(l < r){
			int mid = (l + r) / 2;
			if(check(1,l,mid)) r = mid;
			else l = mid + 1;
		}
		if(vis[l]) break;
		vis[l] = 1;
		Nodes.insert(l);
		rt = l;
	}
}
void Get_Ring(){//事实上应该包括了一部分的链 
	if(Nodes.size() != 63) return;//环找完了，在上一个函数里面  
    int sz = Nodes.size(); 
    while(1){
        tot = 0;
        for(int i = 1; i <= n; ++i) if(!vis[i]){
        	printf("? %d %d %d ",i,sz,Nodes.size());
            for(auto j : Nodes) printf("%d ",j);
            puts("");fflush(stdout);
            
            int op;scanf("%d",&op);
            if(op) vis[i] = 1,Nodes.insert(i);
        }//将环扩倍，当然也会有环外面链的部分被包含进来，但是无伤大雅 
        sz *= 2;
        if(sz > Nodes.size()) break;//有一部分重复了,环长没有扩倍，说明环找完了 
    }
}
void Get_Link(){
	for(int i = 1;i <= n;i++)if(!vis[i]){
        printf("? %d %d %d ",i,1000,Nodes.size());;
        for(auto j : Nodes) printf("%d ",j);
        puts("");fflush(stdout);
        
        int op;scanf("%d",&op);
        if(op == 1) Nodes.insert(i);
    }
}
void print(){
	printf("! %d ",Nodes.size());
	for(auto i : Nodes) printf("%d ",i);
    puts("");fflush(stdout);
}
int main(){
	scanf("%d",&n);
	Get_Part_Of_Ring();
	Get_Ring();
    Get_Link();
    print();
    return 0;
}