P9178题解

slzx2022YuYihan · 2023-08-09 09:07:36 · 题解

Solution

看到此题，相信很多人会想到字典树。但是写到一半，突然发现写不下去了。这道题求的是最多的不同位，而不是异或最大值。异或最大值可以用字典树来实现，而且挺好理解的，可以自行学习一下。接下来，我们对问题进行一个转化。

根据题意，m 为最大的二进制位数，那么有如下定理。

引理：a_i 与 x 的哈明距离加上 a_i 取反与 x 的哈明距离等于 m。

证明可以自行脑补一下所以，我们只要知道最小的 a_i 取反与 x 的哈明距离，就能求出答案。时间复杂度 O(2^mm)。具体实现还是比较简单的，用状压的思路。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>inline void read(T &x){
    x = 0; T w = 1; char ch = getchar();
    while (!isdigit(ch)){if (ch == '-') w = -1; ch = getchar();}
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x *= w;
}
template<typename T>inline void write(T x){
    if (x < 0)  putchar('-'), x = ~(x - 1);
    if (x > 9)  write(x / 10);
    putchar(x % 10 ^ 48);
}

const int M = 21;

ll n, m, a[1 << M], ham[1 << M];

int main(){
//  freopen(".in", "r", stdin), freopen(".out", "w", stdout);
//  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    read(n), read(m);
    memset(ham, 0x3f, sizeof ham);
    for (int i = 1; i <= n; ++i)
        read(a[i]), ham[a[i]] = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < (1 << m); ++j)
            ham[j ^ (1 << i)] = min(ham[j ^ (1 << i)], ham[j] + 1);
    for (int i = 1; i <= n; ++i){
        ll res = ((1 << m) - 1) ^ a[i];//a[i]取反
        write(m - ham[res]), putchar(' '); 
    }

    return 0;
}