CF1257F Make Them Similar

一、题目

点此看题

二、解法

$meet-in-middle$

我们把每一位拆开来看，那么最后 $1$的个数就等于原来的个数和修改的叠加，如下图：

这些操作都是独立的，可以考虑前 $15$位和后 $15$位暴力枚举，再用相遇中间的算法。

实现不就简简单单吗

#include <cstdio>
#include <vector>
#include <map>
using namespace std;
const int M = 105;
const int N = 1<<15;
int read()
{int num=0,flag=1;char c;while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar();return num*flag;
}
int n,a[M],b[N][M];
map<vector<int> ,int> mp;
void work1()
{for(int i=0;i<N;i++)for(int j=0;j<15;j++){if(!(i&(1<<j))) continue;for(int k=1;k<=n;k++)if(a[k]&(1<<j))b[i][k]--;elseb[i][k]++;}
}
void work2()//nmb
{for(int i=0;i<N;i++){vector<int> v;for(int j=0;j<=n;j++)v.push_back(0);for(int j=0;j<15;j++){if(!(i&(1<<j))) continue;for(int k=1;k<=n;k++)if(a[k]&(1<<j+15))v[k]--;elsev[k]++;}mp[v]=i;}
}
int main()//cnm
{n=read();for(int i=1;i<=n;i++)a[i]=read();work1();work2();vector<int> v;v.push_back(0);for(int j=1;j<=n;j++){//mlgbint x=0;for(int k=0;k<30;k++)if(a[j]&(1<<k))x++;v.push_back(x);}for(int i=0;i<N;i++){//nmslvector<int> v1=v;for(int j=1;j<=n;j++)v1[j]+=b[i][j];vector<int> v2=v1;for(int j=0;j<30;j++){for(int k=1;k<=n;k++)v2[k]=j-v1[k];if(mp.count(v2)){printf("%d\n",i|(mp[v2]<<15));return 0;}}}puts("-1");
}