首页 > ACM题库 > HDU-杭电 > HDU 3949-XOR-数论-[解题报告]HOJ
2015
04-14

HDU 3949-XOR-数论-[解题报告]HOJ

XOR

问题描述 :

XOR is a kind of bit operator, we define that as follow: for two binary base number A and B, let C=A XOR B, then for each bit of C, we can get its value by check the digit of corresponding position in A and B. And for each digit, 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0. And we simply write this operator as ^, like 3 ^ 1 = 2,4 ^ 3 = 7. XOR is an amazing operator and this is a question about XOR. We can choose several numbers and do XOR operatorion to them one by one, then we get another number. For example, if we choose 2,3 and 4, we can get 2^3^4=5. Now, you are given N numbers, and you can choose some of them(even a single number) to do XOR on them, and you can get many different numbers. Now I want you tell me which number is the K-th smallest number among them.

输入:

First line of the input is a single integer T(T<=30), indicates there are T test cases.
For each test case, the first line is an integer N(1<=N<=10000), the number of numbers below. The second line contains N integers (each number is between 1 and 10^18). The third line is a number Q(1<=Q<=10000), the number of queries. The fourth line contains Q numbers(each number is between 1 and 10^18) K1,K2,……KQ.

输出:

First line of the input is a single integer T(T<=30), indicates there are T test cases.
For each test case, the first line is an integer N(1<=N<=10000), the number of numbers below. The second line contains N integers (each number is between 1 and 10^18). The third line is a number Q(1<=Q<=10000), the number of queries. The fourth line contains Q numbers(each number is between 1 and 10^18) K1,K2,……KQ.

样例输入:

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

Hint
If you choose a single number, the result you get is the number you choose. Using long long instead of int because of the result may exceed 2^31-1.

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define M 10010
#define inf 1LL<<60
#define ll long long
#define eps 1e-7
#define bas 9
#define mod 1000000000LL

ll a[M];
ll bit[61];
int n;
void gauss()
{
    int row = 0, col = 60, k;
    while( col >= 0 && row < n ){
        k = row;
        while( k < n && (a[k]&bit[col]) == 0 ) ++k;
        if( k == n ){
            --col;
        }
        else{
            swap( a[row], a[k] );
            for( int i = 0; i < n; ++i ) if( i-row ){
                if( a[i]&bit[col] ) a[i] ^= a[row];
            }
            --col, ++row;
        }
    }
    sort( a, a+n );
    n = unique( a, a+n ) - a;
}

ll cal( int x )
{
    int i = 0;
    if( a[0] == 0 ){
        if( x == 1 ) return 0;
        ++i;
        --x;
    }
    ll ans = 0;
    while( x && i < n ){
        if(x&1) ans ^= a[i];
        x >>= 1;
        ++i;
    }
    if( x ) return -1;
    return ans;
}
int main()
{
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    bit[0] = 1;
    for( int i = 1; i < 61; ++i ) bit[i] = bit[i-1]<<1;
    int T, q, t = 0, x;
    scanf( "%d", &T );
    while( T-- ){
        scanf( "%d", &n );
        for( int i = 0; i < n; ++i ) scanf( "%I64d", a+i );
        gauss();
        printf( "Case #%d:\n", ++t );
        scanf( "%d", &q );
        while( q-- ){
            scanf( "%d", &x );
            cout<<cal(x)<<endl;
        }
    }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/freezuoguan/article/details/8607587


  1. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。