P14538 题解

依赖交互库非自适应

2.5n

做法。

首先想一个显然的方向：分治。每次查询一个位置集合包含的人的集合大小。如果等于位置集合大小

-1

那么很显然是这一些位置里的人的问题，递归下去。否则虽然我们知道是外面位置的问题，但是不知道是哪些人。先把已经在目前查询的位置集合里投票的人拉出来问一下，如果也在外面位置出现了那么就返回，否则我们成功确定了哪些人，递归即可。

分析一下发现这玩意是

3n

的。

你会发现一个人不在一个位置集合是一件好事，而他在一个位置集合的话对于该位置集合的补集，我们不知道他在没在里面投票。

我们刚在做法的问题在于我们不知道是哪些人，那我们肯定是希望无论我们知道问题出现在目前位置集合还是目前位置集合的补集，需要查询的额外人数都尽可能少，换句话说尽可能均等。

考虑随一半的人问目前位置集合，另一半问补集。你会发现这样就是期望

2.5n

的了。

数据看似很烂，

\max

也就

250

次询问。

CPP

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(35172);
bool chiedi(vector<int> S, int x);
int delibera(int N) {
	vector<int> psbm,psbp;
	for(int i=0;i<N;i++) psbm.push_back(i);
	for(int i=0;i<=N;i++) psbp.push_back(i);
	while(psbp.size()>1){
		shuffle(psbm.begin(),psbm.end(),rng);
		shuffle(psbp.begin(),psbp.end(),rng);
		int midm=psbm.size()>>1,midp=psbp.size()>>1;
		vector<int> L,R;
		int cntl=midp,cntr=psbp.size()-midm;
		vector<int> l1,r1,iL,iR;
		for(int i=0;i<midp;i++) L.push_back(psbp[i]);
		for(int i=midp;i<psbp.size();i++) R.push_back(psbp[i]);
		for(int i=0;i<midm;i++) if(chiedi(L,psbm[i])) cntl--,l1.push_back(psbm[i]),iL.push_back(psbm[i]); else cntr--,iR.push_back(psbm[i]);
		for(int i=midm;i<psbm.size();i++) if(chiedi(R,psbm[i])) cntr--,r1.push_back(psbm[i]),iR.push_back(psbm[i]); else cntl--,iL.push_back(psbm[i]);;
		if(cntl){
			for(auto v:r1) if(chiedi(L,v)) return v;
			psbm=iL,psbp=L;
		}
		else{
			for(auto v:l1) if(chiedi(R,v)) return v;
			psbm=iR,psbp=R;
		}
	}
    return psbp[0];
}

文章操作

相关推荐

评论

P14538 题解