题解 [email protected]洛谷 | [email protected] 【Interactive LowerBound】

有趣的交互题。

题意:有一个递增的单向链表,需要通过询问权值和下一项编号,求出其中 x\ge x 的最小元素。

这还不简单?挨个询问一遍就切了嘛(

n50000n\le 50000,询问最多 20002000 次。

笑容逐渐凝固。


考虑其他方法:

因为已知该链表是递增的,可以先随机询问 min(n,1000)1\min(n,1000)-1 个点,记录好 x\le x 的最大元素以及他下一项的地址。因为询问数远小于 nn 的最大可能值,我们将这些询问近似地看做随机的。

经过这些询问后,如果最大元素恰好为 xx,直接输出即可,因为不能得到更小的解了。

否则,我们从下一项的地址开始询问最多 10001000 次(因为地址随机,两个被询问的数之间数的个数的期望可以通过除法求得,远小于 10001000),每次移动到获取的 nxt 指针,直到该指针为 1-1 或找到 x\ge x 的数。对于第二种,因为单调递增的性质,可以知道获取到的是最优解,直接输出;对于第一种,跳出循环后判断最大值与 xx 的大小关系,输出该值或者 1-1 即可。

注意几点:

  1. 经过几次错误,发现这里翻译得很毒瘤,实际上只能进行 19991999 次询问(原文如此,经尝试也确实如此),注意不要被坑。
  2. C++ 的 rand() 好像被毒瘤出题人卡掉了,换了几种方式都在第六个点错了,这里可以利用 int 自然溢出手写一个随机。

甚至这个都被卡了:

srand(time(0));
srand(rand()); srand(rand()+19849);

我是用的随机函数可以见代码。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define per(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define fil(x,y) memset((x), (y), sizeof(x))
using namespace std;
typedef long long ll;
const int N = 5e4+5, inf = 0x3f3f3f3f;

int n, front, x, ans = -inf, nxt;
vector<int> interact(int _) {
	printf("? %d\n", _);
	fflush(stdout);
	int a, b;
	scanf("%d%d", &a, &b);
	return vector<int>({a, b});
}
void give(int _) {
	printf("! %d\n", _);
	fflush(stdout);
}

int seed, seed2;
void srand(int x, int y) {seed = x; seed2 = y;}
int frand() {return (seed *= 19260817) += ((seed2 += 114514) ^= 1919810);}
int rand() {int res = frand(); while(res <= 0) res += n; return res;}

int main() {
//	srand(time(0));
//	srand(rand()); srand(rand()+19849);
	srand(998244353, 1000000007);
//	rep(i, 1, 100) printf("%d %d %d\n", seed, seed2, rand());
	scanf("%d%d%d", &n, &front, &x);
	nxt = front;
	rep(i, 1, min(n, 1000)-1) {
		int pos = rand() % n + 1;
		vector<int> res = interact(pos);
		if(res[0] <= x && res[0] > ans) nxt = res[1], ans = res[0];
	}
	if(ans == x) return give(x), 0;
	rep(i, 1, 1000) {
		if(nxt == -1) break;
		vector<int> res = interact(nxt);
		if(res[0] >= x) return give(res[0]), 0;
		ans = res[0]; nxt = res[1];
	}
	give(ans>=x?ans:-1);
	return 0;
}