1312 最大异或和

题目来源： TopCoder

基准时间限制：1 秒空间限制：131072 KB 分值: 320 难度：7级算法题

有一个正整数数组S，S中有N个元素，这些元素分别是S[0],S[1],S[2]...,S[N-1]。现在你可以通过一个操作来更新数组。操作方法如下：

选择两个不同的数i、j（0<=i,j<N 且 i!=j），先计算A = S[i] xor S[j], B = S[j]。然后用A、B替换S[i]，S[j]，即 S[i]=A , S[j]=B。其中xor表示异或运算。

你可以进行任意多次操作，问最后生成的数组S的元素和 SUM = S[0]+S[1]+S[2]+...+S[N-1] 最大可能值是多少。输出这个最大值。

例如：S = {1,0}，去A = S[1] xor S[0] = 1,B = S[0] = 1,新的S={1,1}，SUM = 1+1 = 2.

Input

第一行一个整数N，且1<=N<=50

接下来N行每行一个整数S[i]，且0<=S[i]<=1,000,000,000,000,000 (10^15)

Output

一个整数，即最后集合可能的最大值SUM。

Input示例

Output示例

题解

处理出来线性基直接求得结果即可

代码

//by 减维

#include<set>

#include<map>

#include<ctime>

#include<cmath>

#include<queue>

#include<bitset>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define il inline

#define db double

#define rg register

#define mpr make_pair

#define maxn 105

#define eps 1e-8

#define inf (1<<30)

#define pi 3.1415926535897932384626L

using namespace std;

inline int read()

{

    int ret=;bool fla=;char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-'){fla=;ch=getchar();}

    while(ch>=''&&ch<=''){ret=ret*+ch-'';ch=getchar();}

    return fla?-ret:ret;

}

int n,cnt;

ll mx,ans,a[maxn],b[maxn],p[],bin[];

int main()

{

    n=read();

    bin[]=;for(int i=;i<=;++i) bin[i]=bin[i-]<<;

    for(int i=;i<=n;++i) scanf("%lld",&a[i]),b[i]=a[i];

    for(int i=;i<=n;++i)

        for(int j=;j>=;--j)

            if(a[i]&bin[j])

                if(!p[j]){p[j]=a[i];break;}

                else a[i]^=p[j];

    for(int i=;i>=;--i)

        for(int j=i-;j>=;--j)

            if(p[i]&bin[j]) p[i]^=p[j];

    for(int i=;i>=;--i)

        if(p[i])

        {

            if((mx^p[i])>mx) mx^=p[i];

            cnt++;

        }

    ans+=mx*(n-cnt+);

    cnt--;

    for(int i=;cnt&&i<=;i++)

        if(p[i]) ans+=(mx^p[i]),cnt--;

    printf("%lld",ans);

    return ;

}

#114. k 大异或和

题目描述

这是一道模板题。

给由 n n n 个数组成的一个可重集 S S S，每次给定一个数 k k k，求一个集合 T⊆S T \subseteq S T⊆S，使得集合 T T T 在 S S S 的所有非空子集的不同的异或和中，其异或和 T1xorT2xor…xorT|T| 是第 k k k 小的。

输入格式

第一行一个数 n n n。
第二行 n n n 个数，表示集合 S S S。
第三行一个数 m m m，表示询问次数。
第四行 m m m 个数，表示每一次询问的 k k k。

输出格式

输出 m m m 行，对应每一次询问的答案，第 k k k 小的异或和。如果集合 S S S 的所有非空子集中，不同的异或和数量不足 k k k，输出 −1 -1 −1。

样例

样例输入

样例输出

数据范围与提示

1≤n,m≤10^5,0≤Si≤250,0≤Si≤250

题解

要把线性基求出来后再消下元

对于询问，把k二进制拆分再求即可

代码

//by 减维

#include<set>

#include<map>

#include<ctime>

#include<cmath>

#include<queue>

#include<bitset>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define il inline

#define db double

#define rg register

#define mpr make_pair

#define maxn 100005

#define eps 1e-8

#define inf (1<<30)

#define pi 3.1415926535897932384626L

using namespace std;

inline int read()

{

    int ret=;bool fla=;char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-'){fla=;ch=getchar();}

    while(ch>=''&&ch<=''){ret=ret*+ch-'';ch=getchar();}

    return fla?-ret:ret;

}

int n,m,cnt;

ll p[],bin[],a[];

int main()

{

    n=read();int pd=;

    bin[]=;for(int i=;i<=;++i) bin[i]=bin[i-]<<;

    for(int i=;i<=n;++i)

    {

        ll x;scanf("%lld",&x);

        for(int j=;j>=;--j)

            if(x&bin[j]){

                if(!p[j]){p[j]=x;break;}

                x^=p[j];

            }

        if(!x) pd=;

    }

    for(int i=;i>=;--i)

        for(int j=i-;j>=;--j)

            if(bin[j]&p[i]) p[i]^=p[j];

    for(int i=;i<=;++i) if(p[i]) a[cnt++]=p[i];

    m=read();

    ll k;

    for(int i=;i<=m;++i)

    {

        scanf("%lld",&k);k-=pd;

        ll ans=;

        if(k>bin[cnt]-){puts("-1");continue;}

        for(int j=cnt-;j>=;--j)

            if(k&bin[j]) ans^=a[j];

        printf("%lld\n",ans);

    }

    return ;

}

异或

【线性基】51nod1312 最大异或和&LOJ114 k大异或和