F. Make Them Similar （暴力折半枚举 + 小技巧）

传送门

题意：给你 n 个数 a[ 1 ] ~ a[ n ]， n <= 100；让你找一个 x ，使得 a[ 1 ] = a[ 1 ] ^ x ~ a[ n ] = a[ n ] ^ x；

　　　且 a[ 1 ] ~ a[ n ] 的二进制位上的 1 的个数相等。每个 a[ i ] <= 2^30；

解： a[ i ] <= 2 ^ 30；那么x也不会超过 2^30；那我们暴力枚举两个 2 ^ 15;

　　分别枚举 x 异或上 a[ i ] 的低 15，和 x 异或上 a[ i ] 的高15位；

　　然后我们用 cnt[ 0 ][ 1 ]代表 a[ 1 ] 这个数异或上你枚举的这个x后，的低15位上 1 的个数。

　　 cnt[ 1 ][ 1 ] 代表 a[ 1 ] 这个数异或上你枚举的这个 x后，的高 15 位上 1 的个数。

　　那我们要找到一个 x，使得 cnt[ 0 ][ 1 ] + cnt[ 1 ][ 1 ] = cnt[ 0 ][ 2 ] + cnt[ 1 ][ 2 ] = ...... = cnt[ 0 ][ n ] + cnt[ 1 ][ n ]；

　　那我们是 cnt[ 0 ] 和 cnt[ 1 ] 分开枚举的嘛。　　

　　那当我们枚举低15位时。我们就开个 vector 存一下， cnt[ 0 ] 的后一位减去前一位。即 vector 存的是

　　 cnt[ 0 ][ 2 ] - cnt[ 0 ][ 1 ], cnt[ 0 ][ 3 ] - cnt[ 0 ][ 2 ]； ........ cnt[ 0 ][ n ] - cnt[ 0 ][ n - 1 ]；

　　那我们枚举高15位时。我们的 vector 存的就是 -1 * cnt[ 1 ]的后一位减去前一位。即

　　　-1 * ( cnt[ 1 ][ 2 ] - cnt[ 1 ][ 1 ] ) ........ -1 * ( cnt[ 1 ][ n ] - cnt[ 1 ][ n - 1 ] )；

　　然后，当 cnt[ 0 ] 的vector 和 cnt[ 1 ] 的vector 是一样的时候，就意味着，每个数的 cnt[ 0 ] + cnt[ 1 ] 是相等的。

　　因为， cnt[ 0 ][ 2 ] - cnt[ 0 ][ 1 ] = -1 * ( cnt[ 1 ][ 2 ] - cnt[ 1 ][ 1 ] )；即

　　cnt[ 0 ][ 2 ] + cnt[ 1 ][ 2 ] = cnt[ 0 ][ 1 ] + cnt[ 1 ][ 1 ]；

　　所以，我们就找到 x 了，我们开个 map，存一下每个 vector 对应的状态（statu）；就行了。

#include <bits/stdc++.h>

#define LL long long

#define rep(i, j, k) for(int i = j; i <= k; i++)

#define dep(i, j, k) for(int i = k; i >= j; i--)

#define INF 0x3f3f3f3f

#define inf 0x3f3f3f3f3f3f3f3f

#define mem(i, j) memset(i, j, sizeof(i))

#define pb push_back

using namespace std;

int ans = -, n;

map < vector< int >, int > mp;

vector< int > Q;

int a[];

void dfs1(int num, int statu) {

    if(num > ) {

        Q.clear();

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

            Q.push_back(__builtin_popcount((statu ^ a[i]) % ( << )));

        }

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

            Q[i - ] = Q[i] - Q[i - ];

        }

        Q.pop_back();

        if(!mp[Q]) mp[Q] = statu;

        return ;

    }

    dfs1(num + , statu);

    dfs1(num + , statu | ( << (num - )));

}

void dfs2(int num, int statu) {

    if(num > ) {

        Q.clear();

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

            ///__builtin_popcount(x) 用于计算x的二进制位上1的个数。

            Q.push_back(__builtin_popcount(statu ^ (a[i] >> )));

        }

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

            Q[i - ] = - * (Q[i] - Q[i - ]);

        }

        Q.pop_back(); /// 弹出最后一个元素。

        if(mp[Q]) {

            ans = mp[Q] | (statu << );

        }

        return ;

    }

    dfs2(num + , statu);

    dfs2(num + , statu | ( << (num - )));

}

int main() {

    scanf("%d", &n);

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

        scanf("%d", &a[i]);

    }

    dfs1(, ); dfs2(, );

    printf("%d\n", ans);

    return ;

}

巴特西

F. Make Them Similar （暴力折半枚举 + 小技巧）

最新文章

热门文章

巴特西

F. Make Them Similar （ 暴力折半枚举 + 小技巧 ）

最新文章

热门文章

F. Make Them Similar （暴力折半枚举 + 小技巧）