牛客春招刷题训练营-2025.03.28题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 不要三句号的歪

数据范围会超过 unsigned long long，用 python 编写会更加方便。
split(',') 会将输入切片成三个数字字符串和一个 ... 字符串。
输出第 个数字减第 个数字再减 。

s = input().split(',')
print(int(s[3]) - int(s[1]) - 1)

中等题 尼科彻斯定理

设 为奇数数组，， 为 的前缀和。
从 到 枚举 ，如果 ，输出 。

a = [(2 * i - 1) for i in range(10100)]
pre = [(i * i) for i in range(10100)]
n = int(input())
for i in range(10000):
    if pre[i + n] - pre[i] == n ** 3:
        print(*a[i + 1 : i + n + 1], sep="+")
        exit(0)

困难题 隐匿社交网络

并查集。
可以证明社交网络数量最多不超过 个，因为 范围内只有 个二进制位。
下面以集合称社交网络。
初始化一个大小为 的并查集，每一个集合的 都设为 。
编号为 的集合包含满足 的所有 。
例如： 属于集合 ， 属于集合 ， 属于集合 。
如果一个数的二进制表示下有 个 ，那这个数所属的所有集合需要合并成一个集合。
例如： 属于集合 ，则合并 集合。
遍历 ，如果 且 ，则合并集合 。
再遍历 ，将 所属集合的 加 。
最后输出 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 0);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};
void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    DSU d(64);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 64; j++) {
            for (int k = 0; k < 64; k++) {
                if ((a[i] & (1LL << j)) && (a[i] & (1LL << k))) {
                    d.merge(j, k);
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 64; j++) {
            if (a[i] & (1LL << j)) {
                d.siz[d.find(j)]++;
                break;
            }
        }
    }
    cout << *max_element(d.siz.begin(), d.siz.end()) << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}