Codeforces Round #538 (Div. 2) E. Arithmetic Progression( 交互题 )

人生第一道交互题，确实挺有意思的，hhh，就是调试起来费劲

原题链接

题目大意：
直接用vjudge里的翻译了

思路：
首先我们可以通过>操作，来找出序列的最大值maxx
这个过程最多用30次左右,2^30直接到1e10了

对于每一个序列内的数
a n = a 1 ( n − 1 ) d = m a x x − k 1 d a 1 = m a x x − ( n − 1 ) d a_n = a_1 (n-1)d=maxx - k_1d\\ a1 = maxx-(n-1)d an=a1 (n−1)d=maxx−k1da1=maxx−(n−1)d
所以我们只要确定d即可
怎么去求d呢
我们还有另一个操作？，可以查询序列中任意一位的数（序列是乱）
如果k1 与 k2 互质，也就是说gcd（k1,k2）=1
那么 gcd(k1 * d , k2 * d) = d
k1和k2,我们可以通过
maxx - ai得来
也就是说只要不断随机查询，来找到k1,k2互质的情况即可

注意：

交互题里输出最好用cout<<…<<endl
不要用printf，用printf的话要清理缓冲区，不然。。。
会犯下懒惰之罪 （Idleness limit exceeded）
不要问我怎么知道的QWQ

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<random>
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn = 5e3   7;
int n;
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
map<int, int > map1;
int main() {
	scanf("%d", &n);
	int maxx = 0;
	int l, r;
	l = 0; r = 1e9;
	while (l <= r) {
		int mid = (l   r) >> 1;
		cout << "> " << mid << endl;
		cout.flush();
		int x;
		scanf("%d", &x);
		if (x)l = mid   1;
		else r = mid - 1;
	}
	maxx = l;
	mt19937 rnd(1e9   7);
	int d = 0;
	for (int i = 1; i <= min(30, n);   i) {
		int idx;
		while (idx = rnd() % n   1) {
			if (map1[idx])continue;
			map1[idx] = 1;
			break;
		}
		//printf("? %d\n", idx);
		cout << "? " << idx << endl;
		int x;
		scanf("%d", &x);
		d = gcd(d, maxx - x);
	}
	//printf("! %d %d\n",maxx - (n-1)*d,d);
	cout << "! " << maxx - (n - 1) * d << " " << d << endl;
}

这篇好文章是转载于：学新通技术网