「EZEC-6」分组 题解

· · 题解

官方题解。

Subtask 1：直接爆搜。

Subtask 2：留给一些看起来很对的乱搞。

Subtask 3：所有的 0 都能单独分，所有的 1 必须分在一组，因为如果把 1 分开的话按位或的和会增大。故答案为 0 的个数，若出现 1 则还要 +1。

Subtask 4：猜答案，为 1。考虑完 Subtask 5 的做法，由于数据随机，这些二进制位很容易连通起来。

Subtask 5：对于一个数的第 x 位为 1，则所有第 x 位为 1 的都要分在一起，若分开这个二进制位会被统计两次。这样每个数会把一些二进制位链接起来，这些链接起来的肯定要放在一起。二进制拆位之后并查集求解即可。复杂度 \mathcal{O}(n\log a)。

Subtask 6：只有 60 个位置，直接并查集太浪费了。考虑用一个 ull 来表示状态，每次需要合并的时候才合并。最多合并 60 次，每次合并共 60 次。复杂度 \mathcal{O}(n+60^2)。

至此，问题解决。

#include<iostream>
#include<cstdio>
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define ull unsigned long long
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline T& read(T& r) {
    r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
    while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
    return r = w ? -r : r;
}
const int N = 1000100;
int n, ans;
ull f[64], all;
signed main() {
    read(n);
    for(int i = 1; i <= 61; ++i) f[i] = 1ll << (i-1);
    for(int i = 1; i <= n; ++i) {
        ull x; read(x);
        if(!x) {
            ++ans;
            continue;
        }
        all |= x;
        int p = __builtin_ffsll(x); ull t = f[p] | x;
        if(t == f[p]) continue;
        for(int j = 1; j <= 61; ++j)
            if((1ll << (j-1)) & t)
                t |= f[j];
        for(int j = 1; j <= 61; ++j)
            if((1ll << (j-1)) & t)
                f[j] |= t;
    }
    for(int i = 1; i <= 61; ++i)
        if((1ll << (i-1)) & all)
            if(f[i]) {
                ++ans; ull t = f[i];
                for(int j = 1; j <= 61; ++j)
                    if((1ll << (j-1)) & t)
                        f[j] = 0;
            }
    printf("%d\n", ans);
    return 0;
}