1 异或，两个集合中异或位数最小的

57 阅读 0 评论 38 点赞

我是靠谱客的博主兴奋小兔子，最近开发中收集的这篇文章主要介绍1 异或，两个集合中异或位数最小的，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

For 2 non-negative integers x and y, f(x, y) is defined as the number of different bits in the binary format of x and y. For example, f(2, 3)=1,f(0, 3)=2, f(5, 10)=4. Now given 2 sets of non-negative integers A and B, for each integer b in B, you should find an integer a in A such that f(a, b) is minimized. If there are more than one such integer in set A, choose the smallest one.

Input
The first line of the input is an integer T (0 < T ≤ 100),
indicating the number of test cases. The first line of each test case
contains 2 positive integers m and n (0 < m, n ≤ 100), indicating the
numbers of integers of the 2 sets A and B, respectively. Then follow
(m + n) lines, each of which contains a non-negative integers no
larger than 1000000. The first m lines are the integers in set A and
the other n lines are the integers in set B.

Output
For each test case you should output n lines, each of which contains the result for each query in a single line.
Sample Input
2
2 5
1
2
1
2
3
4
5
5 2
1000000
9999
1423
3421
0
13245
353

Sample Output
1
2
1
1
1
9999
0

I am so vegetable ！！！
真的菜阿别的同学几分钟十分钟做出来的题我要看一个多小时还无限WA，真的佛了自己。。。

题意就是定义一个f函数，求a和b两个数的二进制位有多少位不同，然后现在给出两个集合A和B，在找出B中每一个元素和A中元素最小的f值（就是b和A中的哪个a二进制位数不同数量最小）。

思路就是弄个函数作异或，c=a^b，然后c一直右移，count++就可以求出两个数不同位数有多少，主函数中就输入A和B两个集合，接着两层循环先循环B中元素，对b求A中每一个元素都和b异或，求出最小的那个（注意答案不是要求有多少位数count，而是求得和A中的哪个数的count最小，这里就被坑了半个多小时）

最后还是没ac，一直错误，看到一个大佬写的要对A先降序排序不知道有没有用。。。拿来提交就编译不过。。

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
int m[101];
int n[101];
int fun(int a,int b)
{
int c=a^b;
int count=0;
while(c)
{
count+=c%2;
c=c>>1;
}
return count;
}
int main(){
int t,a,b;
cin>>t;
while(t--)
{
cin>>a>>b;
for(int i=0;i<a;i++)
cin>>m[i];
for(int i=0;i<b;i++)
cin>>n[i];
sort(m,m+a,greater<int>());
//
对a降序排列，这一点很巧妙 
for(int i=0;i<b;i++)
{
int k=1000000,ans=0;
int count;
for(int j=0;j<a;j++)
{
count=fun(n[i],m[j]);
if(count<=k)
{
k=count;
ans=m[j];
}
}
cout<<ans<<endl;
}
}
return 0;
}