首页 > 代码库 > 【bzoj4269】再见Xor 高斯消元求线性基
【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 高斯消元求线性基
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。