P16434

Xuan_tmp · 2026-05-09 23:54:42 · 题解

场切了，来写个题解。

sub 1

随便怎么做都能过。比较简单的一种做法是直接放 M 个 1，然后枚举。

sub 2

发现需要用一次询问区分 1\sim 3，容易想到对 2 做大小比较。但是直接放一个 2 可能无法准确定位到新放进去的 2，怎么办呢？把 2 拆成两个 1，这样这两个 1 一定是排在最前面的，而 d 一定在最后面，就可以用一次询问解决了。

sub 3

发现 2^{29}<10^9<2^{30}，考虑对 2 的幂次做二分。比较好想的是使用 \{a\}=\{2^0\sim 2^{29}\}，但是该怎么使用是个问题。

注意到如果没有加入 d，那么总有 2^0+\dots+2^{i-1}+1=2^{i}，考虑询问 S_1=\{a_0,\dots,a_{i-1}\},S_2=\{a_i\}。讨论 d 会在什么位置加入：

于是可以做到每次询问如果返回大于则把 d 所在区间长度减半，返回等于则询问是否为 1（可以取 S_1=\{a_0\},S_2=\{a_1\}），返回小于则可以转换为普通二分。于是可以在 \log 次内求出 d。

sub 4

看到这个 7 感觉很神秘。对着这个东西拟合一下发现 3^7=2187，很优美啊！

于是考虑如何用一次询问将区间长度除以三，这个东西应该是一个类似三分状物。我们可以使用 1\sim W+200 内全部的数各出现一次的 \{a\}。设当前的区间为 (L,R]，为了方便初始时可以取 L=0,R=3^7。

取出 (L,R] 的三等分点 x=\frac{2L+R}{3},y=\frac{L+2R}{3} 并考虑询问 S_1=\{x,y\},S_2=\{x+y\}，发现对于 L<d<x,x\le d< y,y\le d\le R 返回的结果是不一样的。于是就可以做到三分。

但是有时候 x+y>W+200，怎么办呢？我们发现可以取 c=\frac{R-L}{3}，每次考虑询问 S_1=\{L+c,L+2c\},S_2=\{L+3c,L\}，可以达到一样的效果。于是这道题就做完了。