题解 P7045 【「MCOI-03」金牌】
Owen_codeisking
2020-11-03 21:33:35
交互好题！前排膜拜出题人。
首先有个经典算法：若序列中存在一个数出现次数 $>\lfloor \frac n2\rfloor$，那么执行下列算法即可找到这个数：
- $i=1,count=1,value=a_1$
- $i\leftarrow i+1$。若 $value=a_i$，令 $count=count+1$。否则，令 $count=count-1$。
- 若 $count=0$，令 $count=1,value=a_i$。
- 重复执行操作 $2,3$ 直到 $i=N$。
（正确性容易证明？）
对于一般序列，可以发现执行这个算法后，$value$ 是唯一有可能出现次数 $>\lfloor \frac n2\rfloor$ 的数。
那么这个经典算法又和这题有什么关系呢？
若存在一个数出现次数 $>\lfloor \frac n2\rfloor$，那么一定无解。
那么，可以先用 $n-1$ 次询问找出 $value$，再用 $n-1$ 次询问得到 $value$ 的出现次数。
什么？你说了这么多只能判个无解？就这就这？
~~怎么可能就这~~
我们发现，当这个算法 $count=0$ 时，实际能得到两个序列 $A,B$，满足 $A$ 所有元素相同，$B$ 所有元素与 $A$ 不同，且 $|A|=|B|$。
若原来的 $value=V$，更新过后是 $V'$，那么我们可以构造序列 $C'=C+\{V,B_1,V,B_2,...,V,V'\}$。
重复上述过程，我们最后会得到序列 $A,B,C$，同时 $|A|>|B|$。那么再次执行类似这个过程，会得到序列 $A$ 和空序列 $B$。那么我们要将序列 $A$ 中的元素插入序列 $C$。
因为构造出来序列 $C$ 相邻的数不同，所以这个序列有一个很强的性质：保证 $A$ 能插入的位置数量最多。
（正确性容易证明？）
那么，我们先用 $n-1$ 次询问找出 $value$，再用 $n-1$ 次询问序列 $C$ 中每个元素是否等于 $value$，即可在 $Q=2n-2$ 次询问内解决问题。
~~感觉用 vector 模拟代码有些长~~
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=50005;
int n,q,x[maxn],sta[maxn],top;
vector<int> a,b,res;
inline int query(int x,int y)
{
printf("%d %d\n",x,y);
fflush(stdout);
int res;
scanf("%d",&res);
return res;
}
inline void end()
{
puts("-1");
fflush(stdout);
}
inline void solve()
{
a.clear(),b.clear(),res.clear();
scanf("%d%d",&n,&q);
a.push_back(0);
int lst=0,val=1;
for(int i=1;i<n;i++)
if(!query(lst,i)) val++,a.push_back(i);
else
{
val--,b.push_back(i);
if(val==0)
{
b.pop_back();
for(int i=0;!a.empty() || !b.empty();i++)
if(!(i&1)) res.push_back(a.back()),a.pop_back();
else res.push_back(b.back()),b.pop_back();
lst=i,val=1,a.push_back(i);
}
}
while(!a.empty() && !b.empty())
res.push_back(a.back()),res.push_back(b.back()),a.pop_back(),b.pop_back();
if(res.empty()) { end(); return; }
int sz=(int)res.size();
for(int i=0;i<sz;i++) x[i]=query(res[i],a.back());
int ans=x[0]+x[sz-1];
for(int i=0;i<sz-1;i++) ans+=(x[i] && x[i+1]);
if(ans<(int)a.size()) { end(); return; }
top=0;
if(!a.empty() && x[0])
sta[top++]=a.back(),a.pop_back();
for(int i=0;i<sz-1;i++)
{
sta[top++]=res[i];
if(!a.empty() && x[i] && x[i+1])
sta[top++]=a.back(),a.pop_back();
}
sta[top++]=res[sz-1];
if(!a.empty() && x[sz-1])
sta[top++]=a.back(),a.pop_back();
printf("%d\n",top);
for(int i=0;i<top;i++)
printf("%d%c",sta[i],i==top-1?'\n':' ');
fflush(stdout);
}
int main()
{
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
```