传送门：https://ac.nowcoder.com/acm/contest/11160/D
题意
小G定义LY数对为两个数x，y在二进制的异或操作后恰好有两位是1 小G现在有两个数组a,b长度分别为n,m 现在小G想知道有多少对i,j满足 (1<=i<=n,1<=j<=m)满足a[i]和b[j]是LY数对
思路
如果是暴力枚举a[i]的同时暴力枚举两个位置上的数，复杂度为$O(30^2n)$。 必然会T，怎么办能把其中一个30变小呢？直到复杂度在$O(1e8)$之内？
我们知道题目的意思是$x \bigoplus y=两位2次方数相加=(1<<i)\bigoplus (1<<j).(i!=j)$
$转化为x\bigoplus (1<<i)=y\bigoplus (1<<j).(i!=j)$ $转化为x\bigoplus (1<<j)=y\bigoplus (1<<i).(i!=j)$
所以我们可以通过这个。 枚举i，Hash保存所有的$a_x\bigoplus (1<<i).$ 枚举j所有的$b_y\bigoplus (1<<j)$，查找是否有和它相等的数，ans+个数。
可是我们之前说过i!=j，所以要提前减掉这个i==j的情况。 i==j必然x==y，所以减掉x==y的数量即可。
总时间复杂度为$O(30n*C)$,C是一个小于30的常数。
Code（690MS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e7 + 7;
const int mod = 1e6 + 7;
struct Hash {
int v, next, w;
}e[N];
int head[N], cnt;
void Insert(int x) {
int u = x % mod;
for(int i = head[u]; ~i; i = e[i].next) {
if(e[i].v == x) {
e[i].w++;
return ;
}
}
e[cnt] = Hash{x, head[u], 1};
head[u] = cnt++;
}
int get(int x) {
int u = x % mod;
for(int i = head[u]; ~i; i = e[i].next) {
if(e[i].v == x) {
return e[i].w;
}
}
return 0;
}
map<int, int> mp;
void solve() {
mem(head, -1);
int n, m; cin >> n >> m;
vector<int> a(n + 1), b(m + 1);
for(int i = 1;i <= n; i++) cin >> a[i], mp[a[i]]++;
ll res = 0;
for(int i = 1;i <= m; i++) {
cin >> b[i];
res += mp[b[i]] * 30;
}
for(int i = 1;i <= n; i++) {
for(int k = 0;k < 30; k++) {
Insert(a[i] ^ (1ll << k));
}
}
ll ans = 0;
for(int i = 1;i <= m; i++) {
for(int k = 0;k < 30; k++) {
ans += get(b[i] ^ (1ll << k));
}
}
cout << (ans - res) / 2 << endl;
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/27/nowcoder-practice77-d/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！