题解：P12099 [NERC2024] Hunting Hoglins in Hogwarts

· · 题解

找一个随机移动的球，一个很显然的想法就是二分。假设现在球在 [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;