【二进制拆分 随机化】【GDOI2017 day2】凡喵识图

本文主要是介绍【二进制拆分 随机化】【GDOI2017 day2】凡喵识图，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面

输出共 n 行，每行一个整数，表示第 i 张图片插入时的重要度程度。

思路

将64位分成4段，那么必有一段是相同的。
将相同的放在一起，统计答案时枚举。
或是不按顺序乱搞。
因为数据随机，所以可过。

代码

#include <vector>
#include <cstdio>
#include <cstring>
#define int unsigned long long
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
int n;
int x[150001], v[150001];
std::vector<int> a[4][66001];

inline int read() {
	int res = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		res = res * 10 + (c ^ 48), c = getchar();
	return res * f;
}

int cmp(int p1, int p2) {
	int tmp = x[p1] ^ x[p2], res = 0;
	for (; tmp && res <= 3; tmp -= tmp & -tmp)
		res++;
	return !(res ^ 3);
}

signed main() {
	freopen("hashing.in", "r", stdin);
	freopen("hashing.out", "w", stdout);
	n = read();
	for (int i = 1, res; i <= n; i++) {
		res = 0;
		x[i] = read();
		for (int j = 0; j < 4; j++) {
			int s = (x[i] >> 16 * j) & ((1 << 16) - 1);
			for (int k = 0, tmp; k != a[j][s].size(); k++)
				if (v[tmp = a[j][s][k]] < i)
					res += cmp(a[j][s][k], i), v[tmp] = i;
			a[j][s].push_back(i);
		}
		printf("%llu\n", res);
	}
}

这篇关于【二进制拆分 随机化】【GDOI2017 day2】凡喵识图的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！