为什么我写的 fhq 改了随机种子后对答案会有影响?
查看原帖
为什么我写的 fhq 改了随机种子后对答案会有影响?
87696
Lily_White楼主2020/8/15 12:11

Code:

#include <bits/stdc++.h>
using namespace std;
int tot = 0;
struct TreapNode* Null;
struct TreapNode {
	TreapNode *lc, *rc;
	int key, aux, size;
	int id;
	int sum[5];
	TreapNode(int k = 0): key(k), aux(rand()), size(1), lc(Null), rc(Null) {fill(sum, sum + 5, 0); id = ++tot;}
	void pushup() {
	    size = lc -> size + 1 + rc -> size;
		for (int i = 0; i < 5; i++) {
			sum[i] = lc -> sum[i];
//			fprintf(stderr, "sum[%d] of node %d updated to %d\n", i, id, sum[i]);
		}
		int k = lc -> size;
		sum[k % 5] += key;
//		fprintf(stderr, "sum[%d] of node %d updated to %d\n", k % 5, id, sum[k % 5]);
		k++;
		for (int i = 0; i < 5; i++) {
			sum[(k + i) % 5] += rc -> sum[i];
//			fprintf(stderr, "sum[%d] of node %d updated to %d\n", k % 5, id, sum[k % 5]);
		}
	}
}*root;
int getRank(TreapNode* u, int v) {
//    cerr << u -> id << endl;
	if (u == Null) return 0;
	return (v < u -> key) ? getRank(u -> lc, v): getRank(u -> rc, v) + u -> lc -> size + 1;
}
typedef pair <TreapNode*, TreapNode*> PNN;
PNN split(TreapNode* u, int k) {
	if (u == Null) return make_pair(Null, Null);
	PNN ret;
	if (u -> lc -> size < k) {
		ret = split(u -> rc, k - 1 - u -> lc -> size);
		u -> rc = ret.first;
		ret.first = u;
	} else {
		ret = split(u -> lc, k);
		u -> lc = ret.second;
		ret.second = u;
	}
	u -> pushup();
	return ret;
}
TreapNode* merge(TreapNode* u, TreapNode* v) {
	if (u == Null) return v; if (v == Null) return u;
	if (u -> aux < v -> aux) {
		u -> rc = merge(u -> rc, v);
		u -> pushup();
		return u;
	} else {
		v -> lc = merge(u, v -> lc);
		v -> pushup();
		return v;
	}
}
void insert(int v) {
//    fprintf(stderr, "insert %d\n", v);
	int k = getRank(root, v);
//	fprintf(stderr, "ranked %d\n", k);
	PNN t = split(root, k);
	TreapNode* tmp = new TreapNode(v);
	root = merge(merge(t.first, tmp), t.second);
}
void erase(int v) {
	int k = getRank(root, v);
	PNN t1 = split(root, k - 1), t2 = split(t1.second, 1);
	root = merge(t1.first, t2.second);
}
int main() {
    srand(2);
	int n; cin >> n;
	Null = new TreapNode(0); root = new TreapNode(0);
//	cerr << Null -> id << endl;
	Null -> size = 0;
	while (n--) {
		string op; cin >> op;
		if (op == "add") {
			int x; cin >> x;
			insert(x);
		} else if (op == "del") {
			int x; cin >> x;
			erase(x);
		} else {
			cout << root -> sum[3] << endl;
		}
	}
}

对于输入数据

6
add 4
add 5
add 1
add 2
add 3
sum

在种子为 22 时输出 33(Correct)

1926081619260816 时输出 00(Wrong) (试了十几个只有这个会爆)

第二个样例也会出现这种情况,但容易复现的多。

2020/8/15 12:11
加载中...