题意
交互库有一个 \([1,n]\) 的排列 \(p\),你可以询问 \(l,r,k\),交互库会返回 \(\lfloor\dfrac{p_l}{k}\rfloor,\lfloor\dfrac{p_{l+1}}{k}\rfloor,\dots,\lfloor\dfrac{p_r}{k}\rfloor\) 中不同数的个数。你需要在 \(30\) 次询问内找到 \(p\) 中 \(1\) 的位置。
\(n\in[3,1024]\)。
题解
好交互题!
我们发现很难从询问中得出信息,于是观察一些特殊的 \(k\)。当 \(k\) 为 \(n\) 时,若区间包含 \(n\) 则为 \(2\),否则为 \(1\)。于是可以二分出 \(n\)。
但这种方式难以推广到其他 \(k\)。想一下 \(n\) 的特殊之处:其除 \(n\) 取下整的值唯一。而 \(1\) 除 \(2\) 取下整的值也唯一。
于是对于 \(i\in[1,n]\),考虑 \(Q(1,i,2)-Q(1,i-1,2)\) 与 \(Q(i,n,2)-Q(i+1,n,2)\)。不难发现若 \(p_i=1\),二者均为 \(1\);否则必然一者为 \(1\),一者为 \(0\)。
上面是差分形式,前缀和即为 \(Q\)。于是可以二分,每次查询前缀和,找到第一个二者均为 \(1\) 的位置。这里需要 \(2\log n\) 次。
注意到上面的分析忽略了 \(n\) 为偶数的情形,此时 \(n\) 的位置二者也均为 \(1\)。上面我们提到了 \(\log n\) 找 \(n\) 的方法,于是将 \(n\) 的贡献处理掉即可。总查询次数 \(3\log n\)。
标签:lfloor,log,题解,CF1764G1,rfloor,dfrac,交互 From: https://www.cnblogs.com/FishJokes/p/17176931.html