JOISC2019 l 鉱物 (Minerals)
fangzichang
·
·
题解
最后的优化稍微不太一样。
题意
交互库有一个球的集合 $S$，一开始为空。每次交互操作时，选手程序向交互库给出一个编号 $x$，交互库改变 $x$ 这个球在 $S$ 中的状态：如果原本不存在就放进去，不然就拿出来。然后交互库返回 $S$ 中的颜色数量。
要求在 $10^6$ 次操作内求出每一对颜色相同的球的编号。
$n\le 43000$。
### 解法
一开始容易想到分治。这部分可以参考 DaiRuiChen007 大神的题解。
考虑交互能做什么：如果颜色总数与上一次相比没有变化，说明在操作前和操作后的 $S$ 中，都存在一个球与询问的 $x$ 颜色一样；不然就说明这样的球不存在。
这样容易用 $2n$ 次操作求出两个集合，满足两个集合里面 $n$ 种颜色的球恰好各出现一次。
接下来分治，维护两个集合 $L,R$ 满足两个集合大小一样、颜色种类一样，这些颜色的两个球都恰好在 $L$ 和 $R$ 中各有一个。过程中保证任意一次分治开始时，$L$ 里所有的球全都在 $S$ 中或全都不在 $S$ 中，并且知道是全都在还是全都不在。
每次把 $L$ 分成两半 $L_0$ 和 $L_1$，对其中某一个集合整个交互一遍，使得 $L_0$ 全都在 $S$ 中而 $L_1$ 全都不在，当然反过来也行。
然后把 $R$ 中每个球拿去交互，返回值拿来判断这个球对应的同色球是在 $L_0$ 中还是在 $L_1$ 中，把 $R$ 分成 $R_0$ 和 $R_1$。
> 比如说 $L_0$ 全都在 $S$ 中而 $L_1$ 全都不在，则询问一个球 $x$ 时，如果颜色总数发生变化（不论是增加还是减少都是如此，你乐意的话可以自行仔细分类讨论一下），都说明 $x$ 对应的同色球**不**在 $L_0$ 中，如果在的话颜色数不会变化。
> $L_0$ 全都不在 $S$ 中而 $L_1$ 全都在的情况是完全对称的，比较方便的想法是直接交换两个集合。
然后往 $L_0,R_0$ 和 $L_1,R_1$ 递归分治，容易发现仍旧满足一开始“$L$ 里所有的球全都在 $S$ 中或全都不在 $S$ 中，并且知道是全都在还是全都不在”的要求。
并且很方便的是往这两边递归的过程中操作的球的颜色不同（任意一侧都完全由同色球对组成），所以操作互不干扰，返回时不需要撤销影响。
每次递归交互了半个 $L$ 和一整个 $R$，这样的复杂度是 $2n+\frac{3}{2}n\log_2 n$，过不去。
### 优化
考察这个复杂度的形式，不妨设我每次都把整个 $L_0$ 交互一遍，考虑不把 $L_0$ 设成 $L$ 的一半，而是稍小一些，复杂度或许可能更优。
具体地，设 $L_0$ 的大小为 $k$ 倍 $L$ 的大小（当然这个可以记为 $n$），则操作次数大概为 $T(n)=(1+k)n+T(kn)+T((1-k)n)$。
> DaiRuiChen007 大神说可以动态规划求这个最优大小。
毛估估看一下发现 $k=\frac{1}{2}$ 并没能取到最值。
据称求导或者三分一下，大概取到 $0.36$ 最优。
不过实际上打个表就行了，因为式子其实是 $T(n)=\lceil kn\rceil +n+T(\lceil kn\rceil)+T(n-\lceil kn\rceil)$，一看一堆取整就知道精度高了没啥用。比如以 $10^{-4}$ 为步长枚举可能的 $k$，发现 $k=\frac{1}{3}$ 就足够优秀了。
```cpp
int n=43000;
int f[N];
int dfs(int n,db k){
if(n<=1)return 0;
if(f[n])return f[n];
return f[n]=n+ceil(n*k)+dfs(ceil(n*k),k)+dfs(n-ceil(n*k),k);
}
signed main(){
static const db eps=1e-4;
pair<int,db>res={inf,inf};
for(db k=eps;k<0.5;k+=eps){
int w=dfs(n,k);
res=min(res,pair<int,db>(w,k));
fill(f+1,f+n+1,0);
}
cout<<res.x<<" "<<res.y<<endl;
return 0;
}
```
所以让这个分治过程右偏，每次取 $\lceil 0.36n\rceil$ 作为 $L_0$ 的大小，发现还是过不去，需要 $86000+962799$ 次交互。
考虑扫描 $R$ 过程中，如果 $R_0$ 与 $R_1$ 之一已经填到预期的大小了，就可以直接把剩下部分塞到另一个集合里，不需要额外消耗交互次数。如果不放心，还可以随机打乱 $L$ 和 $R$。
估计一下就会觉得这个常数比较小，实际上跑出来最多的询问次数大概 $9.94\times 10^5$ 左右。
```cpp
mt19937 rnd(random_device{}());
using bsi=basic_string<int>;
bool q(int x){
int w=Query(x);
static int lst=0;
return lst==w?0:(lst=w,1);
}
void dfs(bsi&L,bsi&R,bool t){
// for(int x:L)cerr<<x<<" ";
// cerr<<" | ";
// for(int y:R)cerr<<y<<" ";
// cerr<<endl;
assert(L.size()==R.size());
int n=L.size(),n0=ceil(n*0.36),n1=n-n0;
if(L.size()==1)
return Answer(L[0],R[0]);
shuffle(all(L),rnd),shuffle(all(R),rnd);
bsi L0=L.substr(0,n0),L1=L.substr(n0,n),R0,R1;
for(int x:L0)q(x);
if(!t){
for(int y:R){
if((int)R0.size()!=n0&&(int)R1.size()!=n1)
(q(y)?R1:R0)+=y;
else ((int)R0.size()!=n0?R0:R1)+=y;
}
dfs(L0,R0,1),dfs(L1,R1,0);
}
else{
for(int y:R){
if((int)R0.size()!=n0&&(int)R1.size()!=n1)
(q(y)?R0:R1)+=y;
else ((int)R0.size()!=n0?R0:R1)+=y;
}
dfs(L0,R0,0),dfs(L1,R1,1);
}
}
void Solve(int n){
bsi L,R;
for(int i=1;i<=n*2;i++)
(q(i)?L:R)+=i;
dfs(L,R,1);
}
```
嘛，写动态规划也没有麻烦很多。