【BZOJ4269】再见Xor

Description

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

Input

第一行一个正整数N。

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

Output

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

Sample Input

3
3 5 6

Sample Output

6 5

HINT

100% ： N <= 100000, 保证N个数不全是0，而且在int范围内

题解：大水~

在线性基上贪心得到最大值，用最大值异或最小的线性基就得到了次大值，没了~

#include <cstdio>#include <cstring>#include <iostream>using namespace std;int n,tot,ans;int v[100010];int main(){	int i,j;	scanf("%d",&n);	for(i=1;i<=n;i++)	scanf("%d",&v[i]);	for(i=(1<<30);i;i>>=1)	{		for(j=++tot;j<=n;j++)	if(v[j]&i)		{			swap(v[j],v[tot]);			break;		}		if(!(v[tot]&i))		{			tot--;			continue;		}		for(j=1;j<=n;j++)	if(j!=tot&&(v[j]&i))	v[j]^=v[tot];	}	for(i=1;i<=tot;i++)	if((ans^v[i])>ans)	ans^=v[i];	printf("%d %d",ans,ans^v[tot]);	return 0;}

【BZOJ4269】再见Xor 高斯消元

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【BZOJ4269】再见Xor 高斯消元