zd的小窝
0%

CF1729E 题解

发表于 更新于

交互题

题意简述

给定一个节点数为 $n$ 的环，每次询问两点之间的路径，如果超出范围则会回答 $-1$。

现在请在最多可以进行 $50$ 次询问，请求出这个环的点数。

注意两点显然会有两条路径，但是会随机确定一条为两点的路径，换句话说，多次询问同两个点的答案总是一定的（坑点）。

题目分析

注意到 $n \le 10^{18}$ 二分显然会超出询问次数。

我们再来考虑这么一个问题：如果回答的两点路径一定是最短路径的话，我们询问 $(a,b)$ 与我们询问 $(b,a)$ 的答案总会相同。

可是回答不一定为最短路径，并且如果我们知道了两点的两条路径，答案便已知。

所以我们不妨询问 $25$ 组，从 $2$ 开始，每组分别询问 $(1,i)$ 和 $(i,1)$ ，如果两次回答不一样，设两个答案分别为 $x,y$ 则点数为 $x+y$。

如果中间出现了 $-1$ 答案直接就是询问的那个点减一。

这个方法当然又可能出错，不过我们可以分析一下，设错误的概率 $p$ ，则 $p= \frac{1}{2^{25}}$ ，这个题又有 $50$ 的数据点，总的错误概率就是 $p^{50}$，基本上就是 $0$ 了。

代码

注意数据范围，显然需要开 long long，赛时白交了一发。

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
/*
	Author:zd
	Status:WA on pretest 2
*/

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define int long long
int ask(int a,int b);
signed main(){
	for(int i=2;i<=26;i++){
		int fr=ask(1,i);
		int to=ask(i,1);
		if(fr==-1){
			cout<<"! "<<i-1<<endl;
			return 0;
		}
		if(to!=fr){
			cout<<"! "<<fr+to<<endl;
			return 0;
		}
	}
	return 0;
}
int ask(int a,int b){
	int l;
	cout<<"? "<<a<<' '<<b<<endl;
	cin>>l;
	return l;
}