神！但是交互题。
题目简介
题目名称：
题目来源：
评测链接 ：https://codeforces.com/problemset/problem/1764/G1
评测链接 ：https://codeforces.com/problemset/problem/1764/G2
评测链接 ：https://codeforces.com/problemset/problem/1764/G3
形式化题意：有一个长度为 的 的未知排列，每一次询问 可以得到 的不同数的个数，求出 使得 。限制询问次数为 。
数据范围：
考虑三个询问次数的限制，一定是 的关系，这启示了我们二分。
考虑利用 的特殊性，当 时，无用，当 时，当且仅当 时为 ，否则为 ，所以可以利用这个性质在 的时间内得到 的 ，当然，对于现在而言，没用。给 随机取一个常数？当然也没什么用。
当 时，对于 ，就会变成 ，容易发现， 只出现了一次，否则就只会存在 只出现一次。
将 的一对数 称为对应关系，并对于一个区间 ，记 的 记为区间 的断点，我们设函数 为区间 的断点个数，可以用 的时间计算得出。
其中 表示询问 ? l r 2 。显然地， 肯定是断点。
奇
我们先讨论 为奇数的情况，假设断点最均匀分布，即对于我们划分的区间 ，都存在了所有断点，但 是多余的，所以 在断点较多的那一侧。二分断点即可，一共二分 次，每次询问 次，一共 次。
奇数部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| inline bool main()
{
int l=1,r=N;
while(l<r)
{
int mid=(l+r)>>1;
int l1=query(1,mid,2),r1=query(mid+1,N,2);
l1=2*l1-mid,r1=2*r1-(N-mid);
if(l1>r1) r=mid;
else l=mid+1;
}
ans(l);
return 0;
}
|
偶
容易发现，抛开所有杂余成分，多余断点可能为 ，也可能为 。所以我们需要用一些方法来解决掉这个 。
朴素
前面提及到，我们可以用 的询问找到 的位置，所以我们可以预处理 的位置，在每次询问将 减掉即可。
询问次数 次，解决 。
G1 AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| int l=1,r=N;
while(l<r)
{
if(l==r-1) break;
int mid=(l+r)>>1;
int s=query(1,mid,N);
if(s==2) r=mid;
else l=mid+1;
}
int s;
if(r==N)
{
s=query(1,l,N);
if(s==2) s=l;
else s=r;
}
else
{
s=query(r,N,N);
if(s==2) s=r;
else s=l;
}
l=1,r=N;
while(l<r)
{
int mid=(l+r)>>1;
int l1=query(1,mid,2),r1=query(mid+1,N,2);
l1=2*l1-mid,r1=2*r1-(N-mid);
if(s<=mid) --l1;
else --r1;
if(l1>r1) r=mid;
else l=mid+1;
}
ans(l);
|
优化
考虑不求出 的关系，而是用更抽象的方式解决问题。
对于当前断点划分，记为 ，不考虑 的情况（暂时），则对于当前断点 存在 的情况，说明一边是 ，一边是 ，此时，我们只需要对任意一边区间进行一次 ? 1 mid n 的询问就可以知道 的相对位置，之后就没有必要再询问了。
总询问次数：，解决 。
G2 AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| int l=1,r=N-1,pos=0;
while(l<=r)
{
int mid=(l+r)>>1;
int a=mid,b=N-mid;
int l1=query(1,mid,2),r1=query(mid+1,N,2);
l1=(l1<<1)-a,r1=(r1<<1)-b;
if(pos)
{
if(pos<=mid) --l1;
else --r1;
}
if(l1==r1)
{
if(mid==1)
{
int x=query(mid+1,N,N);
if(x>=2) r=mid-1,pos=N;
else l=mid+1,pos=1;
}
else
{
int x=query(1,mid,N);
if(x>=2) l=mid+1,pos=1;
else r=mid-1,pos=N;
}
}
else if(l1<r1) l=mid+1;
else r=mid-1;
}
ans(r+1);
|
二次优化
怎么省最后一次？？？怎么省最后一次？？？怎么省最后一次？？？怎么省最后一次？？？怎么省最后一次？？？怎么省最后一次？？？怎么省最后一次？？？怎么省最后一次？？？怎么省最后一次？？？
无论怎么做，判断 相对位置的这一步都无法舍去，所以考虑在二分上进行优化。
当最后 时，可能会存在很多冗杂询问，我们考虑从这一步入手，分类讨论。此二分过程类似于一个反向区间 的过程，我们记忆化一下，记录 。
- 如果已经确定了 位置，则其中一位为 ，另一位为非 数：
则可以通过特判来解决 是否为 位，这里省去一次询问。总询问次数为 ，可以解决 。
- 如果当前尚未确定 位置，则其中一位为 ，另一位为 ：
可以通过向两侧询问一次 来得到 的相对位置，仅花费一次询问。总花费 ，可以解决 。
这样，*2900,*3000,*3300 的题就解决了。
G3 AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| int l=1,r=N-1,pos=-1,res=N;
while(l<=r)
{
int mid=(l+r)>>1;
if(l==r)
{
if((!~pos))
{
if(mid==1){ if(query(mid+1,N,N)>1) res=l; }
else if(query(1,mid,N)==1) res=l;
break;
}
else if(Suf[l]-Suf[l+2]){ if(f(1,l)>Pre[l-1]) res=l; }
else if(f(l+1,N)<Suf[l+2]) res=l;
break;
}
Pre[mid]=f(1,mid);
Suf[mid+1]=f(mid+1,N);
int delta=Pre[mid]-Suf[mid+1];
if(delta>0) res=mid,r=mid-1;
else if(delta<0) l=mid+1;
else
{
if(!~pos)
{
if(mid==1) pos=!(query(mid+1,N,N)-1);
else pos=query(1,mid,N)-1;
}
if(pos) l=mid+1;
else res=mid,r=mid-1;
}
}
ans(res);
|