自动搬运

查看原文

来自洛谷，原作者为

	fydj 你能改变的只有你自己

搬运于2025-08-24 23:12:45，当前版本为作者最后更新于2025-04-12 16:05:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

找一个随机移动的球，一个很显然的想法就是二分。假设现在球在 $[l,r]$ 中，且球的移动范围是 $[l,r]$，可以在 $mid=\lfloor \frac {l+r}{2}\rfloor$ 处放置一面墙，直到听到一声巨响，或者抓到球。如果没有抓到，球的范围是 $[l,mid)$ 或 $(mid,r]$。由于要二分，所以要知道球在哪边，因此可以在左半部分的中点处再放一面墙，一直等，等 $c$ 步后如果一直没有巨响，则说明球不在左半部分，而在右半部分。期望需要 $O(\frac 1 2k\log n(4+c))$ 步。而 $c$ 需要取到 $16,17$ 时才能保证正确率过半，且由于二分算法的需求，一步错了就满盘皆输。两个限制都很不好处理。

等这个操作的困难在于，如果球所在的区间已经放了一面墙，它有 $\frac 1 2$ 的概率发出巨响；否则需要等很久才能保证球所在的区间是没有放墙的区间，而不是已经放了墙的区间。但是如果每个区间都放了墙的话，期望等 $2$ 步就能听到巨响。

这时就可以想到利用听到巨响的时间。假设现在球可能出现在 $[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]$ 这些区间，且球的移动范围是这些区间中的某一个。从左到右依次把每一个区间的中点都放一面墙，并且把这个区间划分成两半，如果放完 $[l_i,r_i]$ 中的墙时听到巨响，那么球不可能出现在 $[l_{i+1},r_{i+1}],\dots,[l_k,r_k]$ 这些区间，可以把它们删去。如果全部区间都放完墙时都没有听到巨响，那么期望等 $2$ 步就可以听到巨响，并且球的移动范围缩小到 $[l_1,r_1],\dots,[l_{2k},r_{2k}]$ 区间中的某一个。

注意到，如果一开始是从左到右放置的，放完 $[l_i,r_i]$ 中的墙时听到巨响，那么球有较高概率出现在 $[l_i,r_i]$，其次是 $[l_{i-1},r_{i-1}]$，这样下一轮放墙时就从右往左放。

这种方法相较于二分来说有更大的容错，且可以更好利用题目中随机的性质。实测平均需要 $180000$ 步可以抓到 $800$ 个球。

int i,rey; ll l,r;
init();
loop : ;
vector<pair<ll,ll>>(1,make_pair(1,n)).swap(nxt);
while(1) {
  pos.swap(nxt);
  vector<pair<ll,ll>>(0).swap(nxt);
  for(i=0;i<int(pos.size());++i) {
    ll mid=pos[i].first+pos[i].second>>1;
    if(pos[i].first<mid)
      nxt.push_back(make_pair(pos[i].first,mid-1));
    if(mid<pos[i].second)
      nxt.push_back(make_pair(mid+1,pos[i].second));
    rey=magic(mid);
    if(rey==2) goto loop;
    else if(rey==3) return 0;
    else if(rey==1) break;
  }
  if(i==pos.size()) { while(magic(0)!=1); }
  reverse(nxt.begin(),nxt.end());
}
goto loop;