首页 > 试题广场 >

隐匿社交网络

[编程题]隐匿社交网络

热度指数：3022 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

$\hspace{15pt}$ 牛客网有一个名为牛爱网神秘的入口。这天，牛可乐正在策划牛爱网的全新社交活动。
$\hspace{15pt}$ 每个人的账号在初始时都会被分配一个权重，第 $i$ 个账号的权重为 $w_i$ 。对于任意的两个账号 $i$ 和 $j$ ，如果权重满足 $(w_i \operatorname{and} w_j) \geqq 1$ ，那么就会被分配到同一个社交网络。
$\hspace{15pt}$ 现在，牛可乐已经为 $n$ 个账号分配了权重，他想知道，包含账号数量最多的社交网络中，包含多少个账号。
$\hspace{15pt}$ 牛爱网的日常维护工作忙坏了牛可乐，请你帮帮他。

$\hspace{15pt}$ 其中， $\operatorname{and}$ 表示按位与运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节 。

输入描述:

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

第一行输入一个整数  代表账号数量。
第二行输入  个整数  代表账号权重。

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

输出描述:

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

示例1

输入

输出

4
1

说明

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

算法知识视频讲解

Gnomeshgh112

发表于 2025-03-28 14:39:55

因为权重在18次方以内，变为2进制不超过64位，最多情况下只有64个网络，从左到右针对每一个数字，可以通过遍历网络，来看自己是否属于某一个网络。网络的标志为：网络内各个数字的或，如果这个位置上为1，说明网络内至少存在一个用户，在这个位置上为1。判断一个数字是否属于一个网络：这个数字和网络标识与，如果展开全文

lhp_zml

发表于 2025-03-09 16:38:12

按位与操作，同时是 1 才会是 1，数据两两做与操作会超时。所以可以先考虑吧每个数转为其二进制形式存储起来，一个数的二进制形式存一行，n个数，总共n行。时间复杂度为：nlogn 遍历每一列，把是 1 的每一行下标用并查集合并，因为它们做与操作结果会大于等于 1 并查集，p[N], si[N]，p 展开全文

TQ988

发表于 2025-07-08 18:41:59

import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static int merge(Map<Long, Integer> m 展开全文

11155454

发表于 2025-03-30 00:37:51

#include <bits/stdc++.h> using namespace std; #define ll unsigned long long #define fo(i,a,b) for(int i=a;i<b;i++) vector<ll>a(64); i 展开全文

牛客856751393号

发表于 2025-03-11 22:24:20

超时了 def find(a): if p[a] != a: p[a] = find(p[a]) # 查找父节点 return p[a] def merge(a, b): # 合并两个集合 pa = find(a) pb = fi 展开全文

Goldminer

发表于 2025-04-23 23:08:28

#include <bits/stdc++.h> using namespace std; #define ll unsigned long long #define fo(i,a,b) for(int i=a;i<b;i++) // 定义一个循环宏，用于简化循环代码 vecto 展开全文

牛客907437933号

发表于 2025-04-01 22:21:36

import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc = new S 展开全文

牛客754921490号

发表于 2025-12-20 23:35:06

#include <iostream> #include <unordered_map> #include <vector> #include <algorithm> using namespace std; //w范围是1e18 32位装不下，需要6 展开全文

番禺小韭菜

发表于 2025-03-05 20:00:07

#include <any> #include <iostream> #include <vector> using namespace std; class Total_set { public: vector<int> parent; 展开全文

Whhhhhhhhhhhhhh

发表于 2025-03-30 21:08:50

#include <iostream> #include <vector> using namespace std; #define int long long const int N = 100010; int w[N],s[N]; int fa[N]; int find( 展开全文

问题信息

并查集

难度：

9条回答 87收藏 297浏览

隐匿社交网络

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题