自动搬运

查看原文

来自洛谷，原作者为

	do_while_true 水

搬运于2025-08-24 22:29:21，当前版本为作者最后更新于2021-02-07 21:16:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解。

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;
}