题意
给出\(n\)个数\(a_i\), 和一个整数\(k\). 从这\(n\)个数中选出尽可能多的数, 使得它们之间任意两者按位异或后大于等于\(k\). 输出数字的个数和下标, 如果不存在则输出\(-1\).
\(2 \le n \le 3 \cdot 10^5, 0 \leq a_i,k \leq 2^{30} - 1\)
题解
设\(k\)的最高位是第\(h\)位. 首先会很自然的想到——如果把每个数位数小于等于\(h\)的部分变为0, 按此分类, 从每种里选出一个数字加入答案里一定合法. 因为任意两个数字异或后都至少有一个高于\(h\)的位为\(1\). 以样例\(k = 8(1000)\)为例:
| 处理后组别 |
0 |
0 |
0 |
16(10000) |
0 |
0 |
此时我们选择\(16\), 再从\(2,8,4,10,14\)里任选一个都能组成一个解，但它不是最优的: 例如在\(0\)这一组里选择\(2\)和\(10\)加入答案也是合法解.
进一步思考可以发现, 在每一组里有可能可以选择两个数字且最多只能选择两个. 如果选择了超过两个数字, 那么至少有两个数字在第\(h\)位上是一样的, 这会导致异或后的结果小于\(k\). 使用Trie判断是否有解即可.
注意需要特判\(k = 0\)的情况.
代码
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5+10;
const int maxm = maxn*2;
const int maxc = 1e7+10;
const int p = 1e9+7;
ll Pow(ll x,ll d,ll p){ll ta=1;if(d==0)return 1%p;x %= p;ll a=Pow(x,d/2,p);ta=a*a%p;if(d%2)ta=ta*x%p;return ta%p;}
ll raw[maxn],u[maxn],siz;
int nxt[maxc][2];
int w[maxc*2];
map<int,vector<pair<int,int>> >hsh;
void insert(int s,int idx){
int u = 0;
for(int i = 30;i >= 0;i--){
int c = ((s>>i)&1);
if(nxt[u][c] == -1)nxt[u][c] = ++siz;
u = nxt[u][c];
}
w[u] = idx;
}
int query(int x,int k){
int u = 0,res = 0;
for(int i = 30;i >= 0;i--){
int c = ((x>>i)&1);
if(nxt[u][c^1] != -1){
res += (1<<i);
u = nxt[u][c^1];
}
else if(nxt[u][c] != -1){
u = nxt[u][c];
}
else return -1;
}
if(res < k)return -1;
else return w[u];
}
void clear(){
for(int i = 0;i <= siz;i++){
nxt[i][0] = nxt[i][1] = -1;
w[i] = 0;
}
siz = 0;
}
signed main(){
memset(nxt,-1,sizeof(nxt));
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed,ios::floatfield);
cout.precision(12);
int n,k;
cin >> n >> k;
if(!k){
cout << n << endl;
for(int i = 1;i <= n;i++)cout << i << " ";
return 0;
}
int h = 0;
for(int i = 30;i >= 0;i--)if((1<<i)&k){
h = i;
break;
}
set<int>great,res;
vector<int>gidx;
for(int i = 1;i <= n;i++){
cin >> raw[i];
u[i] = raw[i];
for(int j = h;j >= 0;j--)if((1<<j)&u[i])u[i] -= (1<<j);
cerr << u[i] << " ";
hsh[u[i]].push_back({raw[i],i});
}
vector<int>ans;
for(auto it:hsh){
vector<pair<int,int> > & r = it.second;
clear();
for(auto it2:r)insert(it2.first,it2.second);
bool ok = 0;
for(auto it2:r){
int x = query(it2.first,k);
if(x != -1){
ans.push_back(it2.second);
ans.push_back(x);
ok = 1;
break;
}
}
if(!ok and r.size())ans.push_back(r[0].second);
}
if(ans.size() < 2){
cout << -1;
}
else{
cout << ans.size() << endl;
for(int x:ans)cout << x << " ";
}
return 0;
}
|