【bzoj4269】再见Xor 高斯消元求线性基

题目描述

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

输入

第一行一个正整数N。

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

输出

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

样例输入

3
3 5 6

样例输出

6 5

题解

高斯消元求线性基裸题

由于线性基可以表示所有能够求出的异或和，所以我们只需要考虑线性基即可。

先求出线性基，然后按照从高位到低位的贪心思想来选择。

由于每个线性基的最高位在之前都没有出现过，所以每次选择一定会使答案增大，故直接从大到小选择即可。

#include <cstdio>

#include <algorithm>

using namespace std;

int a[100010];

int main()

{

	int n , i , j , tot = 0 , ans = 0;

	scanf("%d" , &n);

	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);

	for(i = 1 << 30 ; i ; i >>= 1)

	{

		for(j = ++tot ; j <= n ; j ++ )

		{

			if(a[j] & i)

			{

				swap(a[tot] , a[j]);

				break;

			}

		}

		if(j > n)

		{

			tot -- ;

			continue;

		}

		for(j = 1 ; j <= n ; j ++ )

			if(j != tot && a[j] & i)

				a[j] ^= a[tot];

	}

	for(i = 1 ; i < tot ; i ++ ) ans ^= a[i];

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

	return 0;

}

巴特西

【bzoj4269】再见Xor 高斯消元求线性基

最新文章

热门文章