Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 474 Solved: 291
给定N个数,你可以在这些数中任意选一些数出来,每个数可以选任意多次,试求出你能选出的数的异或和的最大值和严格次大值。
第一行一个正整数N。
接下来一行N个非负整数。
一行,包含两个数,最大值和次大值。
3 3 5 6
6 5
100% : N <= 100000, 保证N个数不全是0,而且在int范围内
一眼线性基,取最大值是最基本的操作,就是一路异或过去,能变大就异或
次大值可以由最大值和最小值异或得到
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 10, B = 31;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, P[MAXN];
void Insert(int x) {
for(int i = B; i >= 0; i--) {
if(x >> i) {
if(P[i]) x = x ^ P[i];
else {P[i] = x; return ;}
}
}
}
int QueryMax() {
int ans = 0;
for(int i = B; i >= 0; i--)
if((ans ^ P[i]) > ans)
ans = ans ^ P[i];
return ans;
}
int QueryMin() {
for(int i = 0; i <= B; i++)
if(P[i])
return P[i];
}
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
N = read();
for(int i = 1; i <= N; i++) {
Insert(read());
}
int Mx = QueryMax(), Mn = QueryMin();
printf("%d %d", Mx, Mx ^ Mn);
}