题目链接:
http://codeforces.com/contest/1257/problem/F
题意:
给出$n$个30位整数
找到一个数,让它与这$n$个数分别异或,得到的$n$个数二进制1的个数相同
数据范围:
$1\leq n \leq 100$
分析:
CF官方题解称这是中间相遇技巧
枚举答案的低15位,这时有$2^{15}$种情况
与给出的$n$个数的低15位去异或,得到1的数量定义为$low[i]$
把$(low[2]-low[1],low[3]-low[1],…..low[n]-low[1])$这个vector放入set
再枚举答案的高15位,得到$high[i]$数组
在set中寻找$(high[1]-high[2],high[1]-high[3],…..high[1]-high[1])$
AC代码:
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
using namespace std;
const int maxn=100+7;
const int maxm=(1<<15)+7;
struct Node{
int ans;
vector<int>ve;
bool operator<(const Node &a)const{
return ve<a.ve;
}
}node;
set<Node>se;
int l[maxn],h[maxn];
int getlen[maxm],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
l[i]=(x&((1<<15)-1));
h[i]=x>>15;
}
for(int i=0;i<maxm;i++){
int v=i;
while(v){
if(v&1)getlen[i]++;
v/=2;
}
}
int len=(1<<15);
for(int i=0;i<len;i++){
node.ans=i;
node.ve.clear();
int v=getlen[i^l[1]];
for(int j=2;j<=n;j++)
node.ve.push_back(v-getlen[i^l[j]]);
se.insert(node);
}
for(int i=0;i<len;i++){
node.ans=i;
node.ve.clear();
int v=getlen[i^h[1]];
for(int j=2;j<=n;j++)
node.ve.push_back(getlen[i^h[j]]-v);
if(se.find(node)!=se.end()){
Node now=*se.find(node);
printf("%d\n",(i<<15)+now.ans);
//if((i<<15)+now.ans==1073709057)return 0;
return 0;
}
}
printf("-1\n");
return 0;
}