这道题很恶心,我们只要对a数组处理一位,对b数组处理一位,如果异或值相同就是只有2位为1,然后我们减去两两重合的数量即可。
但是unordered_map爆了,下面的代码就过了10的点,于是我们要手写一个hash表,就可以愉快地AC了。
#include <bits/stdc++.h> int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); int n, m; std::cin >> n >> m; std::vector <int> a(n), b(m); for(int i = 0; i < n; ++i) std::cin >> a[i]; for(int i = 0; i < m; ++i) std::cin >> b[i]; std::unordered_map <int, int> num; for(int i = 0; i < n; ++i) { for(int j = 0; j < 30; ++j) { num[a[i] ^ (1 << j)]++; } } long long ans = 0; for(int i = 0; i < m; ++i) { for(int j = 0; j < 30; ++j) { ans += num[b[i] ^ (1 << j)]; } } std::unordered_map <int, int> temp; for(int i = 0; i < n; ++i) num[a[i]]++; for(int i = 0; i < m; ++i) ans -= num[b[i]] * 30ll; ans >>= 1; std::cout << ans << '\n'; return 0; }
AC代码:
#include <bits/stdc++.h> struct Hash_set{ struct Hash{ int val, v, nxt; Hash() : val(0), v(0), nxt(0) {} Hash(int x,int y,int z) {val = x, v = y, nxt = z;} }; const int P = 1e6 + 7; int tot; std::vector <int> head; std::vector <Hash> e; Hash_set() : tot(0), head((int)3e6, 0), e((int)3e6) {} void insert(int x) { int u = x % P; for(int i = head[u]; i; i = e[i].nxt) { if(e[i].v == x) { e[i].val++; return ; } } e[++tot] = Hash(1, x, head[u]); head[u] = tot; } long long query(int x){ long long u = x % P; for(int i = head[u]; i; i = e[i].nxt) { if(e[i].v == x) return e[i].val; } return 0; } }; int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); int n, m; std::cin >> n >> m; std::vector <int> a(n), b(m); for(int i = 0; i < n; ++i) std::cin >> a[i]; for(int i = 0; i < m; ++i) std::cin >> b[i]; Hash_set T; for(int i = 0; i < n; ++i) { for(int j = 0; j < 30; ++j) { T.insert(a[i] ^ (1 << j)); } } long long ans = 0; for(int i = 0; i < m; ++i) { for(int j = 0; j < 30; ++j) { ans += T.query(b[i] ^ (1 << j)); } } Hash_set T1; for(int i = 0; i < n; ++i) T1.insert(a[i]); for(int i = 0; i < m; ++i) ans -= T1.query(b[i]) * 30ll; ans >>= 1; std::cout << ans << '\n'; return 0; }