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

_Eriri_ · 2025-11-03 15:22:26 · 题解

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

首先对于任意初始情况，你都可以在最开始询问 2n 次，把种类有变化的和没变化的分成两类，然后就相当于做特殊性质。

考虑插入第一类中一半的矿石，然后依次插入第二类。对于插入的第二类矿石 i，如果种类无变化就说明它的匹配点在你插入的一半中，否则匹配点就在另一半中。这样划分成两个子问题，递归处理即可。

显然这样做的询问次数为 O(n\log n) 。

但是要卡点常：

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

最多问了 982911 次。

#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);
}