Codeforces Round #755 (Div. 2) Guess the Permutation 题解 (Java/C++)

题解

我们考量查询[x, n]的图像。也就是说,随着x的变化,查询(? x n)的结果的变化。

也就是说,当$x\leq i$时,(? x n)=(? 1 n)。而当$x \geq k$时,(? x n)=0。
而因为x=j-1时,因为此时a[j-1]<a[y](其中$j\leq y \leq k$),所以(? j-1 n)=(? j n)。除此处之外,其他位置图像都是严格单调递减的。

于是很显然的,i和k可以通过二分搜索找到。
但是这样会面临两个问题:1. 根据n的规模,每次二分都需要30次查询,同时搜索i和k会需要60次查询。2. j的值如何求解?

不难发现,当$x\geq j$时,对于$\text{(? x n)}=\frac {len\cdot (len -1)} 2$中的y必有整数解。而当$x< j-1$时,y大概率不存在整数解(以i=1, j=10,k=12,x=7为例,(? 7 12)=6,此时y依然有整数解,但这种情况属于少数情况)。
于是,当我们发现一次查询后的y有整数解时,我们可以根据x和y计算出k的值,k=x + y -1。
但考虑到上面说的少数情况,我们可以通过查询(? x+y-2 x+y-1)来判断,如果查询结果是1,那么k=x+y-1。如果查询结果是3,可能是x=j-1,因此我们再尝试一次即可。

同理,当x=j时,不仅(? x n)有整数解,(? 1 n) - (? x n)也必有整数解,且(? x-1 n)=(? x n)。当x=j-1时,(? 1 n) - (? x n)必有整数解,且(? x-1 n)=(? x n) + 1。

于是我们就能判断x到底是在j-1左边,还是在j右边,还是x就是j或j-1。

代码

Java

Submission #136085045 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #136085165 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论