题解：CF1354G Find a Gift
ltl0825
·
·
题解
更好的阅读体验
题目传送门
题意简述
给定 $n$ 个盒子，$n\le 10^3$，每个盒子可能有石头或礼物，已知石头的重量严格大于礼物重量且石头重量都相等，礼物的重量可能不同，礼物数量 $k$ 严格小于 $\frac{n}{2}$。
现在你可以与机器交互，每次向其询问两段交集为空的区间
机器会告诉你那段区间里盒子总重更重或相等。
对于每组数据，你最多询问 $50$ 次，要找出第一个装有礼物的盒子。
---
# 题目思路
首先，我们可以从1号位置下手。
分类讨论：
- 若 $1$ 号盒子是礼物，答案就是 $1$。
- 若 $1$ 号盒子是石头，我们可以倍增的向后找，具体见下。
倍增：
每次询问 $1 \sim len$ 和 $len+1 \sim 2\times len$，若前一段重，则礼物在 $len+1 \sim 2\times {len}$，若是相等，$1 \sim 2\times {len}$ 都是石头，${len}$ 每次乘 $2$ 这些询问是 $\log_2 n$ 的。
举个例子：
一开始，我们问 $1$ 和 $2$ 若相同，因为石头一样重，长度一样长，我们又确定了 $1$ 是石头，所以 $2$ 也是石头。接着问 $1$，$2$ 和 $3$，$4$，若重量不同，所以礼物肯定在 $3 \sim 4$ 中，因为 $1\sim 2$ 都是石头。
我们找到一段区间中有礼物了，接着去二分找礼物位置。
设礼物在 $l \sim r$ 中。
我们二分长度 ${le}$ 每次询问 $1 \sim {le}$ 和 $ l \sim l+{le}-1$，若前者重，礼物在 $ l \sim l + {le} -1$ 中，否则在 $ l + {le} -1 \sim r$ 中，因为前者我们已经确定都是石头了。
二分询问次数：$\log_2 n$。
$1$ 号是石头消耗总次数：$2\times \log_2 n$。
现在最重要的是如何确定：$1$ 是否是石头。
我们知道现在除去 $1$ 号是石头消耗总次数外还有大约 $30$ 次机会，每次我们可以随机一个除 $1$ 以外的位置，判断两个东西的重量，若 $1$ 更轻，则我们可以知道 $1$ 一定是礼物，因为没有比石头更重的东西，判断 $30$ 次后，若没有比 $1$ 更重的东西，我们可以认为 $1$ 是石头。 错误概率约为 $(\frac{1}{2})^{30}$ 因为 $k \le \frac{n}{2}$。
# 注意：
1. 边界问题，倍增时可能没有完全倍增到 $n$ 位置。
2. 输出问题，记得刷新缓冲区。
# 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int t;
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
srand(time(0));
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int tmp=__lg(n)*2;
int p=1;
for(int i=1;i<=20;i++)
{
cout<<"? 1 1\n";
fflush(stdout);
cout<<"1\n";
fflush(stdout);
int kk=min(rand()%n+2,n);
cout<<kk<<'\n';
fflush(stdout);
string s;
cin>>s;
if(s == "WASTED")
{
return 0;
}
else
{
if(s == "FIRST")
{
}
if(s == "SECOND")
{
p=0;
break;
}
}
}
if(p>0)
{
int flag=1;
int len=1;
for(len=1;2*len<=n;len*=2)
{
int tmpx=1+len;
cout<<"? "<<len<<' '<<len<<'\n';
fflush(stdout);
for(int i=1;i<=tmpx-1;i++)
{
cout<<i<<' ';
fflush(stdout);
}
cout<<'\n';
fflush(stdout);
for(int i=tmpx;i<=tmpx+len-1;i++)
{
cout<<i<<' ';
fflush(stdout);
}
cout<<'\n';
fflush(stdout);
string s;
cin>>s;
if(s == "FIRST")
{
int l=1,r=len,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
cout<<"? "<<mid<<' '<<mid<<'\n';
fflush(stdout);
for(int i=1;i<=mid;i++)
{
cout<<i<<' ';
fflush(stdout);
}
cout<<'\n';
fflush(stdout);
for(int i=tmpx;i<=tmpx+mid-1;i++)
{
cout<<i<<' ';
fflush(stdout);
}
cout<<'\n';
fflush(stdout);
string s1;
cin>>s1;
if(s1 == "FIRST")
{
r=mid-1;
ans=mid;
}
if(s1 == "EQUAL")
{
l=mid+1;
}
}
cout<<"! "<<tmpx+ans-1<<'\n';
fflush(stdout);
flag=0;
goto it;
}
if(s == "SECOND")
{
return 0;
}
if(s == "EQUAL")
{
continue;
}
if(s == "WASTED")
{
return 0;
}
}
it:;
if(flag)
{
int l=1,r=n-len,ans=0,tmpx=len+1;
while(l<=r)
{
int mid=(l+r)/2;
cout<<"? "<<mid<<' '<<mid<<'\n';
fflush(stdout);
for(int i=1;i<=mid;i++)
{
cout<<i<<' ';
fflush(stdout);
}
cout<<'\n';
fflush(stdout);
for(int i=tmpx;i<=tmpx+mid-1;i++)
{
cout<<i<<' ';
fflush(stdout);
}
cout<<'\n';
fflush(stdout);
string s1;
cin>>s1;
if(s1 == "FIRST")
{
r=mid-1;
ans=mid;
}
if(s1 == "EQUAL")
{
l=mid+1;
}
}
cout<<"! "<<tmpx+ans-1<<'\n';
fflush(stdout);
}
}
else
{
cout<<"! 1\n";
fflush(stdout);
continue;
}
}
return 0;
}
```