首页 > 试题广场 >

隐匿社交网络

[编程题]隐匿社交网络

热度指数：1822 时间限制：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

说明

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

算法知识视频讲解

C++

TQ988

状态压缩，用个map存key是状态value是网络成员数量。

每个元素x输入后遍历map，(x & key) >= 1就加入到这个网络，注意把原来的网络删掉插入新的进去，也就是插入{key | x, map[key] + 1}

如果(x & key) < 1就自建网络，即把{x, 1}加到map

处理完该组所有输入后要把map合并，map元素数量不会超过20个，遍历然后两两合并即可。

最后再遍历map输出最大的value

发表于 2025-07-08 18:50:14 回复(0)

C++

牛客733789154号

#include <bits/stdc++.h>
using namespace std;

int main(){
    int T;
    cin>>T;
    while(T--){
     int n,maxnum=0,temp;
    cin>>n;
    vector<bitset<64>> acc(n);
    bitset<64> bve;
    for(int i=0;i<n;i++){
        cin>>temp;
        acc[i]=temp;     
    }
    for(int i=0;i<n;i++){
        int count=1;
        bve =acc[i];
        for(int j=i+1;j<n;j++){
            if((bve & acc[j])!=0) {
            bve |= acc[j];    
            count++;
            swap(acc[++i],acc[j]);
            j=i;
            }
        }
        maxnum=max(count,maxnum);
    }
   cout<<maxnum<<endl;
    }
}

发表于 2025-07-10 12:50:30 回复(0)

C++

理智的打工人是单身

// 用例不通过。实在看不出问题在哪
#include <iostream>
#include <vector>
using namespace std;


void calConnected(const vector<long long>& data, vector<vector<bool>>& connected)
{
    int n=data.size();
    connected.resize(n, vector<bool>(n, false));

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            connected[i][j] = data[i]&data[j];
        }
    }
}

long long getAccountNum(vector<long long>& w, int x, vector<vector<bool>>& connected)
{
    long long account_num = 1;
    for(int i=0; i<w.size(); i++)
    {
        if(i!=x && connected[i][x])
            account_num++;
    }
    return account_num;
}


long long getMaxAccountNum(vector<long long>& w, vector<vector<bool>>& connected)
{
    int n = w.size();
    // vector<bool> visited(n, false);
    long long max_account_num = 0;
    for(int i=0; i<w.size(); i++)
    {
        // int cur_account_num = getAccountNum(w, i, connected);
        max_account_num = max(max_account_num, getAccountNum(w, i, connected));
    }
    return max_account_num;
}


int main() {
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        vector<long long> weight(n);
        for(long long& x:weight)
            cin>>x;

        //题目的空间限制很宽泛。这里预处理任意两个账号的权重
        vector<vector<bool>> connected;
        calConnected(weight, connected);

        long long max_account_num = getMaxAccountNum(weight, connected);
        cout<<max_account_num<<endl;
    }
    
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2025-06-14 18:59:53 回复(0)

提交观点

问题信息

难度：

3条回答 51收藏 76浏览

隐匿社交网络

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题