首页 > 代码库 > 2014百度之星资格赛第三题
2014百度之星资格赛第三题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 4445 Accepted Submission(s): 652
Problem Description
Zeus 和 Prometheus 做了一个游戏，Prometheus 给 Zeus 一个集合，集合中包含了N个正整数，随后 Prometheus 将向 Zeus 发起M次询问，每次询问中包含一个正整数 S ，之后 Zeus 需要在集合当中找出一个正整数 K ，使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大，随即同意 Zeus 可以向人类求助。你能证明人类的智慧么？
Input
输入包含若干组测试数据，每组测试数据包含若干行。
输入的第一行是一个整数T（T < 10），表示共有T组数据。
每组数据的第一行输入两个正整数N，M（<1=N,M<=100000），接下来一行，包含N个正整数，代表 Zeus 的获得的集合，之后M行，每行一个正整数S，代表 Prometheus 询问的正整数。所有正整数均不超过2^32。
Output
对于每组数据，首先需要输出单独一行”Case #?:”，其中问号处应填入当前的数据组数，组数从1开始计算。
对于每个询问，输出一个正整数K，使得K与S异或值最大。
Sample Input
2
3 2
3 4 5
1
5
4 1
4 6 5 6
3
Sample Output
Case #1:
4
3
Case #2:
4
这道题最常规的解法就是简单的循环，一个个的比较判断那个数的异或最大，时间复杂度为0（TNM），在OJ平台上肯定是时间会超时的。
因此，应该采用其他的方法，减少计算的次数，降低时间复杂度。首先要知道的是什么情况下，给定一个数a，如何在一组数据中找到其异或的最大值。一般我们现将数首先取反。在该组数据中与已知的异或最大的数的特点就是从该数二进制的最高开始匹配，尽可能与~a的二进制相同。
基于此，第一种解法就是使用二叉树，左边表示0，右边表示1。所以该树的深度最多为32。在匹配的时候从树开始，往下匹配，到叶子节点时，就是其最大的异或数。该算法的缺点就是要构建二叉树，浪费了一点时间（可以自己去算一算）。但是匹配的时候大大减少了时间。
第二种解法就是现将一组数进行排序，然后采用二分查找的方式去查找数据，缺点就是要排序。2种算法都是常见的减少时间复杂度的经典算法。
代码如下：
/*#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<fstream>
using namespace std;
#define MAXSIZE 100000
typedef bool bits;
typedef struct bitTree
{
bits data;
bitTree *left,*right;
//bitTree(bits _data=http://www.mamicode.com/0):data(_data),left(NULL),right(NULL){}>
第二种解法：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<fstream>
using namespace std;
const int maxn=100000+5;
const int inf=1<<31;
unsigned int s[maxn];
int main(){
freopen("d.txt","r",stdin);
ofstream fs( "e.txt");
int kase;
cin>>kase;
for(int run=1;run<=kase;run++){
printf("Case #%d:\n",run);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
scanf("%d",&s[i]);
sort(s,s+n);
while(m--){
unsigned int x;
scanf("%d",&x);
x=~x;
int L=0,R=n-1;
unsigned int bit=inf;
while(bit){
if(L==R) break;
unsigned int y=bit&x;
if(y){
int l=L,r=R,mid,ans=-1;
while(l<=r){
mid=(l+r)/2;
if(s[mid]&bit){
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
if(ans!=-1)
L=ans;
}
else{
int l=L,r=R,mid,ans=-1;
while(l<=r){
mid=(l+r)/2;
if((s[mid]&bit)==0){
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
if(ans!=-1)
R=ans;
}
bit=bit>>1;
}
// printf("%u\n",s[L]);
fs<<s[L]<<" ";
}
fs<<endl;
}
}