首页 > 其他 > 详细

SGU 275 To xor or not to xor

时间:2015-05-17 20:06:10      阅读:237      评论:0      收藏:0      [点我收藏+]

题意:

  从n个数中选若干个数,使它们的异或和最大。n<=100

 

 


Solution

           经典的异或高斯消元。

技术分享
//O(60*n)
#include <iostream>
using namespace std;
int n;
long long a[109];

int main()
{
    ios::sync_with_stdio();
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 62; i >= 0; --i) {
        for (int j = 1; j <= n; ++j) {
            if (a[j] & 1LL << i ) {
                long long t = a[j];
                if (! (ans & 1LL << i ) ) ans ^= t;
                for (int k = j; k <= n; ++k) {
                    if (a[k] & 1LL << i )
                        a[k] ^= t;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}
O(63*n)

 

SGU 275 To xor or not to xor

原文:http://www.cnblogs.com/keam37/p/4486270.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!