HDU 3949 XOR （异或消元）

不念不忘少年蓝@ 2024-04-17 05:56 74阅读 0赞

给定你由N个整数构成的整数序列，你可以从中选取一些（甚至一个）进行异或（XOR）运算，从而得到很多不同的结果。

请问，所有能得到的不同的结果中第k小的结果是多少。  
输入格式

第一行包含整数T，表示共有T组测试数据。

对于每组测试数据，第一行包含整数N。

第二行包含N个整数(均在1至1018

之间)，表示完整的整数序列。

第三行包含整数Q，表示询问的次数。

第四行包含Q个整数k1,k2,…,kQ

,表示Q个询问对应的k。  
输出格式

对于每组测试数据，第一行输出“Case \#C:”，其中C为顺序编号（从1开始）。

接下来Q行描述Q次询问的结果，每行输出一个整数，表示第i次询问中第ki

小的结果。

如果能得到的不同结果的总数少于ki

，则输出“-1”。  
数据范围

1≤N,Q≤10000  
,  
1≤ki≤1018

输入样例：

2  
2  
1 2  
4  
1 2 3 4  
3  
1 2 3  
5  
1 2 3 4 5

输出样例：

Case \#1:  
1  
2  
3  
\-1  
Case \#2:  
0  
1  
2  
3  
\-1

注意:只选取一个数字进行运算，则结果为该数字本身。

分析：  
参考博客：https://mp.csdn.net/mdeditor/100060669  
https://www.cnblogs.com/andyqsmart/p/4957420.html

wa的心态不好了。  
莫名其妙的wa。  
x >> i & 1 和 x & (1LL <<ｉ)我一开始判断语句写的后面这个式子就wa，换成前面的式子就可以过了。 求大佬救一下这里。

简单分析一下这个题把。  
本题要求从N个数里面任意选取n个数异或得到第k大的值。  
从N个数任意选取n个数所得到的可能值是一个线性空间。那么我们首先用高斯消元就可以把这个线性空间的基求出来。

现在，我们在考虑第k大。  
eg：  
5个数（一组基）：1 2 4 8 16  
现在我们求此异或空间的第3大。3的二进制位011.  
那么我们把基里面的第1个和第2个(即1和2)异或起来就是此线性空间的第3大。  
其他，可类推。  
同时，注意0是否是可取的情况。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    int T,N,Q,row;
    ll a[10010],b[10010],max_num;
    
    void init()
    {
        scanf("%d",&N);
        for(int i = 1; i <= N; i ++)
            scanf("%lld",&a[i]);
        scanf("%d",&Q);
        for(int i = 1; i <= Q; i ++)
            scanf("%lld",&b[i]);
    }
    void Gauss()
    {
        row = 1;
        for(int x = 63; x >= 0; x --)
        {
            int i;
            for(i = row; i <= N; i ++)
                if(a[i] & (1LL << x))
                   break;
            if(i == N + 1) continue;
            swap(a[i],a[row]);
            for(int j = 1; j <= N; j ++)
                if(j != row && ((a[j] >> x & 1) == 1))
                    a[j] ^= a[row];
            ++ row;
        }
    
        row --;
       /* printf("bug\n");
        for(int i = 1; i <= row; i ++)
            printf("%lld \n",a[i]);
        printf("\n");*/
        max_num = 1LL << row;
        if(row == N)
            max_num --;
    }
    
    void work(ll x)
    {
        if(x > max_num)
        {
            printf("-1\n"); return ;
        }
        if(row < N)
        {
            if(x == 1)
            {
                printf("0\n"); return ;
            }
            x --;
        }
        ll sum = 0;
        for(int i = row - 1; i >= 0; i --)
            if(x >> i & 1) sum ^= a[row - i];
        printf("%lld\n",sum);
    }
    int main()
    {
        int cnt = 1;
        scanf("%d",&T);
        while(T --)
        {
            init();
            Gauss();
            printf("Case #%d:\n",cnt ++);
            for(int i = 1; i <= Q; i ++)
                work(b[i]);
        }
    }