4269: 再见Xor
Description
给定N个数,你可以在这些数中任意选一些数出来,每个数可以选任意多次,试求出你能选出的数的异或和的最大值和严格次大值。
我太愚蠢了连数组开小了以及$2^{31}$爆$int$都不造
线性基裸题啊....
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
const int N=1e5+,INF=1e9;
inline int read(){
char c=getchar();int x=;
while(c<''||c>''){c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int n,p;
int a[N],bin[N];
void ini(){
bin[]=;for(int i=;i<=;i++) bin[i]=bin[i-]<<;
}
int now;
void Gauss(int n){
now=;
for(int i=;i>=;i--){
int j=now;
while(j<=n&&!(a[j]&bin[i])) j++;
if(j==n+) continue;
if(j!=now) swap(a[j],a[now]);
for(int k=;k<=n;k++)
if(k!=now&&(a[k]&bin[i])) a[k]^=a[now];
now++;
}
now--;
}
int main(){
freopen("in","r",stdin);
n=read();
for(int i=;i<=n;i++){
int x=read();
while(x==&&i<n) x=read(),i++;
if(x!=) a[++p]=x;
}
ini();
Gauss(p);
int mx=;
for(int i=;i<=now;i++) mx^=a[i];
printf("%d %d\n",mx,mx^a[now]);
}