Codeforces 1257 F Make Them Similar —— 哈希+折半状压

本文主要是介绍Codeforces 1257 F Make Them Similar —— 哈希+折半状压，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有n个数，让你求一个数，让这些数异或上这个数，得到的新数组，每个数二进制下1的个数相同。

题解：

和我们这次新生校赛上的一道题目很像，解法都是相同的。
首先要想到将每一位分解出来，也就是第2的i次方这位取的话，对这些数的影响是什么，如果这一位上有的话，那么就是-1，否则+1.然后怎么将每个数都变成1个数相同的呢，我们只需要枚举0-30这些情况，然后检查我们异或之后是不是这个情况，很明显不能将每个数组存下来，需要用哈希存到map中。然后看每一位取不取的话，我们不能直接做，一因为这样是$2^{30}$种情况，一般出现这样子的情况的话，就是使用对半的方法。我们处理出前15位的情况，存到map中，然后做后15位的时候，对于每一种情况我都检查一遍0-30这些是否可能。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define pa pair<ull,ull>
int a[105],b[35][105],c[105];
map<pa,int>mp;
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),c[i]=a[i];for(int i=0;i<30;i++){for(int j=1;j<=n;j++){if(a[j]&(1<<i))b[i][j]=-1;elseb[i][j]=1;}}for(int i=1;i<=n;i++)a[i]=__builtin_popcount(a[i]);for(int i=1;i<(1<<15);i++){pa h={0,0};int t[105]={0};for(int j=0;j<=14;j++){if(i&(1<<j))for(int k=1;k<=n;k++)t[k]+=b[j][k];}for(int j=1;j<=n;j++)h={h.first*31ll+(ull)(28+t[j]),h.second*23ll+(ull)(28+t[j])};mp[h]=i;}mp[{0,0}]=0;int t[105];for(int i=0;i<(1<<15);i++){pa h={0,0};for(int j=1;j<=n;j++)t[j]=a[j];for(int j=0;j<=14;j++){if(i&(1<<j))for(int k=1;k<=n;k++)t[k]+=b[j+15][k];}for(int bit=0;bit<=30;bit++){h={0,0};for(int j=1;j<=n;j++)h={h.first*31ll+(ull)(28ll+bit-t[j]),h.second*23ll+(ull)(28ll+bit-t[j])};if(mp.count(h)){int pre=mp[h],aft=i;int ans=pre+(aft<<15);printf("%d\n",ans);//for(int i=1;i<=n;i++)//printf("%d%c",__builtin_popcount(ans^c[i])," \n"[i==n]);return 0;}}}printf("-1\n");return 0;
}
/*
3
324994 321920 371974
*/

这篇关于Codeforces 1257 F Make Them Similar —— 哈希+折半状压的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---