AtCoder Beginner Contest 228 D - Linear Probing

题意

给定一个序列A和N=2^20，A的范围为[0,N-1]，初始值均为-1。

操作1：设h=x（给出），如果a[h%MOD]!=-1就h+1，直到a[h%MOD]==-1为止。之后，设a[h%MOD]的值为x。

操作2：输出a[x%MOD]。

数据范围：x>=0，保证操作1有答案。

题解

性质1：不能打暴力（时间复杂度超额）

性质2：只要a[h]的值被设置，a[h]就不会再在判断a[h%MOD]时不断+1。

性质3（性质1、2）：对于每个h，如果a[h]==-1，那么它就要连到a[h]!=-1的一个点去。

答案1（性质3）：考虑使用并查集维护连通性。

值得注意的是，在使用并查集维护连通性时，由于（x%MOD）本身具有自环的性质，那么f[x%MOD]=f[(x+1)%MOD]即可。

#include
#include
#include
#define int long long
using namespace std;
const int MOD = 1 << 20;
int a[MOD];

int f[MOD];

int find(int x) {
	while (f[x] != x) {
		x=f[x] = f[f[x]];
	}
	return f[x];
}

void init() {
	for (int i = 0; i < MOD; i++) {
		a[i] = -1;
		f[i] = i;
	}
		
}


void add(int x) {
	int h = find(x%MOD);
	a[h%MOD] = x;
	f[h%MOD] = f[(h + 1) % MOD];
}

int val(int x) {
	return a[x%MOD];
}

signed main() {
	init();
	int q;
	scanf("%lld", &q);
	for (int i = 1; i <= q; i++) {
		int t, x;
		scanf("%lld%lld", &t, &x);

		if (t == 1) {
			add(x);
		}

		if (t == 2) {
			printf("%lld\n", val(x));
		}

	}
	return 0;
}

TRANSLATE with

Bing Webmaster Portal