CF2133C The Nether 题解

交互题，如果把

n\le 500

的限制改成

n\le 5000

是不是会更好一点？

我们记

l_i

表示以

i

开头的最长链。

首先我们能用

n

次交得到

l_i

，并且找到其中一个最长链的第一个元素

x

，发现最大的

l_i

必然是一个最长链的首端。

证明：如果

i

不是这个最长链的第一个元素，那么假设

j

连向

i

，则

l_j=l_i+1

，那么

l_i

就不是最大值，矛盾。

然后我们就选择一个链，先找到它的首端。

接下来的问题是：我们如何找到一个点

v

，满足点

u

直接连向点

v

？

这个应该是好交互的。我们枚举

v

，然后直接交互即可，具体操作见代码。

时间复杂度

O(n^2)

。后面找点是有

O(n\log n)

的实现的，读者可以尝试着去对我的代码进行优化。瓶颈在于输出。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int n;
int a[N];
int id[N];
bool cmp(int x,int y){
	return a[x]>a[y];
}
void solve(){
	cin>>n;
	int l=0;
	for(int i=1;i<=n;i++){
		// ? i n 1 2 3 ... n 即以 i 为开头，可以在全图跑的最长链
		cout<<"? ";
		cout<<i<<" "<<n<<" ";
		for(int j=1;j<=n;j++)cout<<j<<" ";//真正的瓶颈在于这里 :(
		cout<<"\n";
		fflush(stdout);
		cin>>a[i];
		l=max(l,a[i]);
		id[i]=i;
	}
	sort(id+1,id+n+1,cmp);//提示
	vector<int>ans;
	int idd=1;
	for(int i=1;i<=n;i=idd){
		ans.push_back(id[i]);
		if(a[id[i]]==1)break;
		for(int j=1;j<=n;j++){//这里完全可以优化至 O(n\log n)，感兴趣的读者可以思考一下，有前后两个提示
			if(a[id[i]]-a[id[j]]==1){//提示
				//id[i] 2 id[i] id[j]，即以 id[i] 为开头，可以跑 id[i] 和 id[j] 的最长路 这是可以判定 id[i] 是否连向 id[j] 的
				cout<<"? "<<id[i]<<" 2 "<<id[i]<<" "<<id[j]<<"\n";
				fflush(stdout);
				int x;
				cin>>x;
				if(x==2){
					idd=j;
					break;
				}
			}
		}
	}
	cout<<"! "<<ans.size()<<" ";
	for(auto x:ans)cout<<x<<" ";
	cout<<"\n";
	fflush(stdout);
	return;
}
signed main(){
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	int T=1;
	cin>>T;
	while(T--)solve();
	return 0;
}
/*

*/

CF2133C The Nether 题解

文章操作

相关推荐

评论

CF2133C The Nether 题解