CF1257F Make Them Similar

题目链接

题意分析

一看这道题我们 我们第一反应是枚举然后判断 但是这样的复杂度达到了\(O(2^{30}*n)\)

很显然是过不了的

我们冷静一波可以发现 如果将每一个数的前15位以及后15位拆开的话 也就是只考虑15位 这个复杂度是可以接受的

那么我们可以考虑使用Meet in The Middle

关键是匹配该如何匹配

我们对于前十五位 处理出一个序列\(popcount(a1 \bigoplus x)-popcount(ai \bigoplus x)\)

我们对于后十五位 处理出一个序列\(popcount(a1 \bigoplus x)-popcount(ai \bigoplus x)\)

我们把题意转化一下就可以发现 对于我们要求的x 上下两个序列是依次互为相反数的

那么我们将下面的序列取反 就是\(popcount(ai \bigoplus x)-popcount(a1 \bigoplus x)\) 也就成为了相等关系

这就成为了匹配标准

具体实现的时候 可以使用vector存储系列 然后使用map对于vector进行标记

强大的STL啊！

CODE:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#define N 33000
using namespace std;
int n;bool flag;
int num[N];
vector<int> G;
map<vector<int>,int> vis;
int popcount(int x)
{
	int res=0;
	while(x)
	{
		x-=x&-x;
		++res;
	}
//	printf("pop(%d) = %d\n",tmp,res);
	return res;
}
int main()
{
	scanf("%d",&n);vis.clear();
	for(int i=1;i<=n;++i) scanf("%d",&num[i]);
	for(int i=0;i<(1<<15);++i)
	{
		G.clear();
		int tmp=popcount(i^(num[1]&((1<<15)-1)));
		for(int j=2;j<=n;++j)
		{
			int x=i^(num[j]&((1<<15)-1));
			G.push_back(popcount(x)-tmp);
		}
		vis[G]=i;
	}
	for(int i=0;i<(1<<15);++i)
	{
		G.clear();
		int tmp=popcount(i^(num[1]>>15));
		for(int j=2;j<=n;++j)
		{
			int x=i^(num[j]>>15);
			G.push_back(tmp-popcount(x));
		}
		if(vis.count(G))
		{
			printf("%d\n",(i<<15)+vis[G]);
			flag=1;
			break;
		}
	}
	if(flag==0) puts("-1"); 
	return 0;
}