输出共 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); } }