【CF1257F】Make Them Similar【meet in the middle+hash】

题意：给定n个数，让你给出一个数，使得n个数与给出的数异或后得到的数的二进制表示中1的数量相同

题解：考虑暴搜2^30去找答案，显然不可接受

显然可以发现，这是一个经典的meet in the middle模型，直接套用然后hash一下即可

设前15位异或完之后1的个数为ai，那么差分一下得

a1 a2-a1 a3-a2 a4-a3 ......

设后15位异或之后1的个数为bi，那么查分一下得

b1 b2-b1 b3-b2 b4-b3 ......

差分完之后表示的是后一个数1的个数与前一个数的区别，当所有的ai-ai-1+bi-bi-1都为0时，则表示后一个数和前一个数的1的个数相同

即a2-a1=-(b2-b1)

所以只要将后15位得到的bi数组取相反数即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<map>

#define ll long long

#define mod 145141247483647

using namespace std;

int bit[],a[],b[];

int n;

map<ll,int> fl;

map<ll,int>::iterator I;

const int T=(<<)-;

int main()

{

    for(int i=;i<=;i++)bit[i]=bit[i>>]+(i&);

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    for(int i=;i<=;i++)

    {

      for(int j=;j<=n;j++)b[j]=(a[j]>>)^i;

      for(int j=n;j>;j--)b[j]=bit[b[j]]-bit[b[j-]]+;

      ll t=;

      for(int j=;j<=n;j++)t=(t*+b[j]+mod)%mod;

      fl[t]=i;

    }

    for(int i=;i<=;i++)

    {

      for(int j=;j<=n;j++)b[j]=(a[j]&T)^i;

      for(int j=n;j>;j--)b[j]=-bit[b[j]]+bit[b[j-]]+;

      ll t=;

      for(int j=;j<=n;j++)t=(t*+b[j]+mod)%mod;

      I=fl.find(t);

      if(I!=fl.end())

      {

        return !printf("%d\n",((*I).second<<)+i);

      }

    }

    return !printf("-1");

}

巴特西

【CF1257F】Make Them Similar【meet in the middle+hash】

最新文章

热门文章