用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:contest:cf_global_13

这是本文档旧的修订版!


Codeforces Global Round 13

F. Magnets

题意

给定 $n$ 个磁体,编号 $1\sim n$。磁体有三种类型 $S,N,-$,其中 $-$ 代表无磁性。允许 $n+\lfloor \log n\rfloor$ 次询问。

每次询问选择若干磁体,分成两组,然后用装置测量两组磁体之间的受力。

其中,设第 $i$ 组有 $s_i$ 个 $S$ 型磁体,$n_i$ 个 $N$ 型磁体,则受力为 $s_1s_2+n_1n_2-s_1n_2-s_2n_1$,若受力超过 $n$ 则测量装置损坏。

要求在不损坏装置的前提下在允许询问次数内找到所有无磁性磁体。

数据保证至少有两个有磁性的磁体和一个无磁性的磁体。

题解

每次询问 $1\sim i-1$ 和 $i$ 号磁体两组之间的受力,当受力不为 $0$ 时 $i$ 号磁体一定有磁性,$1\sim i-1$ 中一定恰有一个有磁性磁体。

考虑二分找到 $1\sim i-1$ 中的有磁性磁体,然后用第 $i$ 号磁体检验 $i+1\sim n$ 磁体的磁性。查询次数 $n-1+\lceil \log n\rceil$。

查看代码

查看代码

int query(int a,int b){
	puts("? 1 1");
	enter(a);
	enter(b);
	fflush(stdout);
	int t;scanf("%d",&t);
	return t;
}
int query(int pos,int lef,int rig){
	printf("? 1 %d\n",rig-lef+1);
	enter(pos);
	_rep(i,lef,rig)space(i);
	puts("");
	fflush(stdout);
	int t;scanf("%d",&t);
	return t;
}
int solve(int pos,int lef,int rig){
	int mid=lef+rig>>1;
	if(lef==rig)return mid;
	int t=query(pos,lef,mid);
	if(t)return solve(pos,lef,mid);
	else
	return solve(pos,mid+1,rig);
}
int main()
{
	int T=read_int();
	while(T--){
		int n;scanf("%d",&n);
		vector<int> ans;
		int pos=2;
		while((query(pos,1,pos-1))==0)pos++;
		int t=solve(pos,1,pos-1);
		_for(i,1,pos){
			if(i!=t)
			ans.push_back(i);
		}
		_rep(i,pos+1,n){
			if(query(pos,i)==0)
			ans.push_back(i);
		}
		printf("! %d ",ans.size());
		_for(i,0,ans.size())space(ans[i]);
		puts("");
		fflush(stdout);
	}
	return 0;
}
2020-2021/teams/legal_string/jxm2001/contest/cf_global_13.1614581792.txt.gz · 最后更改: 2021/03/01 14:56 由 jxm2001