CF1729E Guess the Cycle Size 题解

· · 题解

Div.3 出交互题了，好感动。

因为询问次数限制为 50 次，所以我们需要利用图的一些性质。

对于两个点 a,b，连接他们的路径有且仅有两条，它们互相包围成了这个环。

因为交互库会从两条路径中随机选择一条，这样，我们对于点 a,b 问两次，如果两次询问的回答不一样，就说明反馈的两次值是 a 到 b 的两条路径。这两条路径围成了这个环，所以环的长度就是两次回答的和。

我们设 a=1，b 从 2 枚举到 26（每个点问 2 次，25 个点刚好问 50 次），一直询问下去，如果两次结果不等就输出并结束程序。

注意特判输出 -1 的情况。

可以证明，这种算法出锅的概率几乎为 0。如果你还是不放心，可以在循环结束后（如果能结束）加一句 while(1)，将 WA 变成 TLE。因为 CF 对 TLE 的程序会重测 3 遍，所以在其他随机化算法出锅概率比较大的交互题中，这种方法十分好用。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  for(int i=2;i<=26;i++){
    cout<<"? 1 "<<i<<endl;
    int x; cin>>x;
    if(x==-1){
      cout<<"! "<<i-1<<endl;
      return 0;
    }
    cout<<"? "<<i<<" 1"<<endl;
    int y; cin>>y;
    if(x!=y){
      cout<<"! "<<x+y<<endl;
      return 0;
    }
  }
  while(1);
}