【51nod】1312 最大异或和

题解

很显然我们求出一组线性基来，如果有M个基，那么可以构造N - M + 1个最大异或值

而对于线性基中的元素，除了最大的元素，我们用最大异或值异或掉每个元素累加进答案

~~而不是把线性基中的元素处理成一个下三角矩阵!~~

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

#define enter putchar('\n')

#define space putchar(' ')

#define MAXN 1000005

//#define ivorysi

#define pb push_back

#define mo 1000007

#define pii pair<int,int>

#define mp make_pair

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 - '0' + c;

	c = getchar();

    }

    res = res * f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

int N;

int64 a[60],b[60];

bool vis[60],has[60];

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) {

	read(a[i]);

	for(int j = 55 ; j >= 0 ; --j) {

	    if(a[i] >> j & 1) {

		if(b[j]) a[i] ^= b[j];

		else {

		    has[j] = 1;

		    b[j] = a[i];vis[i] = 1;

		    for(int k = 0 ; k < j ; ++k) if(b[j] >> k & 1) b[j] ^= b[k];

		    for(int k = j + 1 ; k <= 55 ; ++k) if(b[k] && (b[k] >> j & 1)) b[k] ^= b[j];

		    break;

		}

	    }

	}

    }

    int64 ans = 0;

    for(int i = 1 ; i <= N ; ++i) {

	if(!vis[i]) {

	    for(int j = 55 ; j >= 0 ; --j) {

		if(!(a[i] >> j & 1)) a[i] ^= b[j];

	    }

	    ans += a[i];

	}

    }

    int64 t = 0;

    for(int i = 55 ; i >= 0 ; --i) {

	if(has[i]) {

	    for(int j = 0 ; j <= 55 ; ++j) t ^= b[j];

	    has[i] = 0;

	    break;

	}

    }

    ans += t;

    for(int i = 55 ; i >= 0 ; --i) {

	if(has[i]) ans += t ^ b[i];

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

巴特西

【51nod】1312 最大异或和

题解

代码

最新文章

热门文章