【bzoj4296】再见Xor

4269: 再见Xor

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 176 Solved: 107
[Submit][Status][Discuss]

Description

给定N个数，你可以在这些数中任意选一些数出来，每个数可以选任意多次，试求出你能选出的数的异或和的最大值和严格次大值。

Input

第一行一个正整数N。

接下来一行N个非负整数。

Output

一行，包含两个数，最大值和次大值。

Sample Input

3
3 5 6

Sample Output

6 5

【题解】

这算是一道高斯消元求线性基的模板题，我尽量讲得详细点。

首先把每个数拆成二进制的形式，用矩阵表示。

如样例：

　　　　0 1 1

　　　　1 0 1

　　　　1 1 0

然后高斯消元：

　　　　0 1 1　　交换前2行　 1 0 1　　处理2和3行　 1 0 1 处理第3行 1 0 1

　　　　1 0 1 =======> 0 1 1 ========> 0 1 1 =======> 0 1 1

　　　　1 1 0　　　　　　　 1 1 0　　　　　　　　 0 1 1　　　　　　　　 0 0 0

此时只能保证第二行二进制第二位为1，记录temp=2

然后把矩阵的前temp行求异或和，就是最大值ans，然后ans^a[temp]就是次大值。

可以yy一下，或者自己动手推推。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<ctime>

 #include<algorithm>

 using namespace std;

 #define MAXN 100010

 int n,ans,a[MAXN];

 inline int read()

 {

     int x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 void guess()

 {

     int temp=;

     for(int i=(<<),j;i;i>>=)//枚举2进制每一位

     {

         for(j=temp+;j<=n;j++)  if(a[j]&i)  break;//找到当前二进制位上是1的第一个数

         if(j>n)  continue;//找不到，继续

         swap(a[++temp],a[j]);//高斯消元固有的

         for(int j=;j<=n;j++)  if(j!=temp&&(a[j]&i))  a[j]^=a[temp];//处理其他行

     }

     for(int i=;i<=temp;i++)  ans^=a[i];

     printf("%d %d\n",ans,ans^a[temp]);

 }

 int main()

 {

     //freopen("cin.in","r",stdin);

     //freopen("cout.out","w",stdout);

     n=read();

     for(int i=;i<=n;i++)  a[i]=read();

     guess();

     return ;

 }

巴特西