HJ133 隐匿社交网络

• 题目
• 题解(19)
• 讨论(9)
• 排行

中等 通过率：28.40% 时间限制：1秒 空间限制：1024M

知识点并查集

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

牛客网有一个名为牛爱网神秘的入口。这天，牛可乐正在策划牛爱网的全新社交活动。
每个人的账号在初始时都会被分配一个权重，第 ii 个账号的权重为 wiwi​。对于任意的两个账号 ii 和 jj，如果权重满足 (wiand⁡wj)≧1(wi​andwj​)≧1，那么就会被分配到同一个社交网络。
现在，牛可乐已经为 nn 个账号分配了权重，他想知道，包含账号数量最多的社交网络中，包含多少个账号。
牛爱网的日常维护工作忙坏了牛可乐，请你帮帮他。

其中，and⁡and 表示按位与运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节 。

输入描述：

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦105)T(1≦T≦105) 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 n(1≦n≦105)n(1≦n≦105) 代表账号数量。
第二行输入 nn 个整数 w1,w2,…,wn(1≦wi≦1018)w1​,w2​,…,wn​(1≦wi​≦1018) 代表账号权重。

除此之外，保证单个测试文件的 nn 之和不超过 105105 。

输出描述：

对于每组测试数据，新起一行。输出一个整数，代表包含账号数量最多的社交网络中，包含的账号数量。

示例1

输入：

2 5 2 1 6 7 16 2 2 16

复制输出：

4 1

复制说明：

对于第一组测试数据，连接示意图如下图所示：

#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; i++) cin >> a[i]; map<long long, int> m; int ans = 0; for (int i = 0; i < n; i++) { vector<long long> ks; for (auto [k, v] : m) { if ((a[i] & k) >= 1) { ks.push_back(k); } } long long kk = a[i]; int cnt = 0; for (long long k : ks) { kk |= k; cnt += m[k]; m.erase(k); } m[kk] = cnt + 1; ans = max(ans, cnt + 1); } cout << ans << "\n"; } int main() { int n; cin >> n; while (n--) { solve(); } }