&运算，异或运算，结构体，delete(),指针一题全有

http://acm.hdu.edu.cn/showproblem.php?pid=4825
&运算，异或运算，结构体，delete(),指针这一题包含了综上所述的知识，请耐心看。

Xor Sum

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
这是一道模板题，具体的解析请看注释，很详细。
#include<iostream>
#include<cstdio>
using namespace std;</cstdio></iostream>

struct node
{
int cut;
node *son[2];
//初始化结构体 http://c.biancheng.net/view/1407.html
node (){
cut=0;
son[0]=son[1]=NULL;
}
};
node *root; //新建字典树为 root
void Insert(int x) ///建字典树
{
bool a[32]; //将数字x存储为二进制，长度为32位，
int xx=x;
node *p=root; //开始时指针p指向字典树根节点
node *q; //q用于新建子节点

for(int i=0;i<32;i++){///将传入的数化成二进制

/* https://blog.csdn.net/xiaoshazheng/article/details/81297736
&是二进制“与”运算，参加运算的两个数的二进制按位进行运算，运算的规律是：
0 & 0=0
0 & 1=0
1 & 0=0
1 & 1=1
*/
a[i]=x&1; //存储在数组a中，低位在前，高位在后。
x>>=1; //二进制右移一位，如原来x=5（101） x>>=1后，x=2(10)
}
for(int i=31;i>=0;i--){///倒着建树查找时从高位开始

    if(p->son[a[i]]!=NULL){  //如果此时p对应的数（二进制）已经在树上了                                                         
        p=p->son[a[i]];       //将指针p指向下一位，继续判断下一个数是否存储                                                  
    }                                                                                               

    else{                  //如果当前的树上没有新加的数字对应这一位的数 
        q=new node ;       //则新建一个子节点 
        p->son[a[i]]=q;    //将对应数字指向新建节点，所以对应的子节点指向不再为空 
        p=q;               //将指针p指向下一个节点，（即新建的子节点）。 
    }
}                
            //存储结束，指针p指向存储数字的结尾
p->cut=xx;  //将值存在结束位置

}
int Find(int x) ///查找
{
bool a[32];
node *p=root; //开始查找时指针指向树的根节点
//将查找数字转换成二进制，长度为32位，
for(int i=0;i<32;i++){
a[i]=x&1; //将存储的二进制数字存在数组a中，低位在前，高位在后，剩余补零
x>>=1; //例如 x=11 (1011) 数组a存储顺序为，（下标从0 --> 31：11010000000000000000000000000000）
}
for(int i=31;i>=0;i--){ //异或运算：如果a、b两个值不相同，则异或结果为1。
//如果a、b两个值相同，异或结果为0。
if(p->son[!a[i]]!=NULL) //求异或最大如果有不同的先走不同的
p=p->son[!a[i]];

    else 
        p=p->son[a[i]];
}
return p->cut;

}
void del(node *p) ///销毁字典树
{
for(int i=0;i<2;i++)
if(p->son[i]!=NULL) del(p->son[i]);
//https://www.cnblogs.com/chucks123/p/7764449.html
//在回收用 new 分配的单个对象的内存空间的时候用 delete
delete(p);
}
int main()
{
int t,n,m,k;
scanf("%d",&t);
for(k=1;k<=t;k++){
scanf("%d%d",&n,&m);
int x;
root = new node;
//建立一个字典树
for(int i=0;i<n;i++){
scanf("%d",&x);
Insert(x);
}

&运算，异或运算，结构体，delete(),指针一题全有

全站热榜

创作者周榜