博客

hdu3949 XOR

原题地址

：

http://acm.hdu.edu.cn/showproblem.php?pid=3949

题意：


T组数据，

每组数据给n个数，m个询问，对于每个询问给出一个k，询问给的n个数，选取任意非空子集，能异或出的数中第k小的，重复的数不计算。


数据范围


T<=30，1<=N<=10000，1<=Q<=10000

each number is between 1 and 10^18

题解：


理解线性基性质的好题。

这个大佬的博文讲的非常透彻

消法一般有两种，一种是直接消成上三角阵，一种是消成对角线阵

第一种跑得比较快，但第二种贪心起来比较价简单，也算各有利弊

这样是因为譬如1,3两个数，用第一种消法得到1,3两个线性基，然而因为3^1=2，所以贪心起来要多判断一些东西

第二种消法直接得到1,2,从大到小选线性基异或只会越来越大

同时对角阵有一个特性是有线性基的位上只有线性基的那一位为1，其余均为0

但是这里要注意没有线性基的位不一定为0，譬如只有一个数3

——引用自

一个大佬的博客

这题能够二进制拆分逐位去选，也就因为线性基在消成对角阵后，每一位的基互不影响，

如果有n个基，每一个都有选与不选两种方案，

除去空集，能够组成的数的数量就有2^k-1，

正好与二进制数相契合。

但是由于线性基保证不能异或出0，

所以这题还要判断原数组能否异或出0。

就是如果高消后的基的数量s小于n,

就说明原数组中存在一个数，它不能为线性基带来任何贡献，

它没有加入线性基的原因，是它的每一位在加入之前就被异或成了0，

因此，如果高消后的基的数量s小于n，则可以异或出0，k- -。

于是把k二进制拆分，从高位到低位，如果第k大的位有1，就选上第k大的基。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int N=10005;
int T,n,m,size;
LL a[N];
int gauss()
{
    int cnt=0;LL top=1LL<<60;
    for(LL i=top;i;i>>=1)
    {
        int j=-1;
        for(int k=cnt+1;k<=n;k++)
        if(a[k]&i) {j=k; break;}
        if(j==-1) continue; else swap(a[cnt+1],a[j]);
        for(int j=1;j<=n;j++)
        {
            if(j==cnt+1||(a[j]&i)==0) continue;
            a[j]=a[j]^a[cnt+1];
        }
        cnt++; if(cnt==n) break;        
    }
    return cnt;
}
LL query(LL k)
{
    k-=(n>size);
    if(k==0) return 0;
    if(k>=(1LL<<size)) return -1;
    LL ans=0;
    for(int i=size;k;k>>=1,i--)
    if(k&1) ans=ans^a[i];
    return ans;
}
int main()
{
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        size=gauss();
        scanf("%d",&m);
        printf("Case #%d:\n",t);
        for(int i=1;i<=m;i++)
        {
            LL k; scanf("%lld",&k);
            printf("%lld\n",query(k));  
        }
    }   
    return 0;
}