HDU 3949 XOR 线性基

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

求异或第k小,结论是第k小就是 k二进制的第i位为1就把i位的线性基异或上去。

但是这道题和上一道线性基不同的地方是要缩一下位使得k的每一位都有线性基(毕竟是组合为基础的)。

要在往里塞线性基的时候把每个线性基上的1能往后放的尽量往后放emmm这么搞非常重要,以后写线性基都加一下这个可以处理的东西更多了。

(这个东西维护之后,线性基中所有数都变为二进制的话那么每个二进制位上至多有一个1)

这道题不能取空集所以还要注意一下0能不能取到。

没了。

感谢一下这位神犇的代码 https://www.cnblogs.com/kkkkahlua/p/7800932.html

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define LL long long
 8 int n,m,f=0;
 9 LL b[65]={},c[65]={};
10 inline void init(LL x){
11     for(int i=60;i>0;i--){
12         if(x&c[i]){
13             if(!b[i]){
14                 for(int j=1;j<i;++j)if((x>>(j-1))&1)x^=b[j];
15                 for(int j=i+1;j<=60;++j)if((b[j]>>(i-1))&1)b[j]^=x;
16                 b[i]=x;break;
17             }
18             x^=b[i];
19             if(!x)f=1;
20         }
21     }
22 }
23 inline LL getit(LL x){
24     LL ans=0;
25     for(int i=60;i>0;i--){
26         if(x&c[i]){
27             ans^=b[i];
28         }
29     }
30     return ans;
31 }
32 int main(){
33     int T,cc=0;LL x;
34     scanf("%d",&T);
35     while(T-->0){
36         scanf("%d",&n);
37         c[1]=1;b[1]=0;f=0;
38         for(int i=2;i<=60;i++){b[i]=0;c[i]=c[i-1]*2;}
39         for(int i=1;i<=n;i++){scanf("%lld",&x);init(x);}
40         int siz=1;
41         for(int i=1;i<=60;i++){if(b[i]){b[siz]=b[i];++siz;}}--siz;
42         printf("Case #%d:
",++cc);
43         scanf("%d",&m);
44         LL sz=((long long)1<<(siz))-1;
45         for(int j=0;j<m;j++){
46             scanf("%lld",&x);
47             if(f)--x;
48             if(x>sz)printf("-1
");
49             else printf("%lld
",getit(x));
50         }
51     }
52     return 0;
53 }
View Code

原文地址:https://www.cnblogs.com/137shoebills/p/8832406.html