题解：P14351 [JOISC 2019] 矿物 / Minerals

这个题的思路比较简单，特殊性质给的提示很明显。

首先对于任意初始情况，你都可以在最开始询问

2n

次，把种类有变化的和没变化的分成两类，然后就相当于做特殊性质。

考虑插入第一类中一半的矿石，然后依次插入第二类。对于插入的第二类矿石

i

，如果种类无变化就说明它的匹配点在你插入的一半中，否则匹配点就在另一半中。这样划分成两个子问题，递归处理即可。

显然这样做的询问次数为

O(n\log n)

。

但是要卡点常：

你只需要保证第一类矿石的状态一样就行，其它矿石的状态不管怎样都足以判断。所以不需要回滚操作，或者一直保持所有矿石状态一样。
依次插入第二类矿石的过程中，如果某一半第一类矿石的匹配点已经满了，就可以不继续问了。
看别人代码发现：mid=(l+r)*0.4 会少问几万次。
shuffle 一下矿石，防止被卡，实测没用。

最多问了

982911

次。

CPP

#include<bits/stdc++.h>
using namespace std;
void Answer(int a, int b);
int Query(int x);
random_device R;
mt19937 G(R());
int bj[100050];
void solve(vector<int>x,vector<int>y,int ty1){
	if(x.size()==1){
		Answer(x[0],y[0]);
		return;
	}
	int len=max(1,(int)(x.size()*0.4));
	vector<int>l1,r1,l2,r2;
	int o=0;
	for(int j=0;j<len;j++)o=Query(x[j]),l1.push_back(x[j]);
	for(int j=len;j<x.size();j++)l2.push_back(x[j]);
	shuffle(y.begin(),y.end(),G);
	for(int j=0;j<y.size();j++){
		int v=y[j],cnt=Query(v);
		if(cnt==o){
			if(ty1==1&&bj[v]==1)r1.push_back(v);
			else if(ty1==1&&bj[v]==0)r1.push_back(v);
			else r2.push_back(v);
		}else {
			if(ty1==0&&bj[v]==0)r1.push_back(v);
			else if(ty1==0&&bj[v]==1)r1.push_back(v);
			else r2.push_back(v);				
		}
		bj[v]^=1;
		if(r1.size()==l1.size()){
			for(int k=j+1;k<y.size();k++)r2.push_back(y[k]);
			solve(l1,r1,ty1^1),solve(l2,r2,ty1); 		
			return ;
		}
		if(r2.size()==l2.size()){
			for(int k=j+1;k<y.size();k++)r1.push_back(y[k]);
			solve(l1,r1,ty1^1),solve(l2,r2,ty1); 
			return ;
		}	
		o=cnt;
	}
}
void Solve(int n){
	vector<int>x,y;
	int o=0; 
	for(int i=1;i<=2*n;i++){
		int cnt=Query(i);
		if(cnt==o)y.push_back(i);
		else x.push_back(i);
		o=cnt;
	}
	solve(x,y,0);
}

题解：P14351 [JOISC 2019] 矿物 / Minerals

文章操作

相关推荐

评论

题解：P14351 [JOISC 2019] 矿物 / Minerals