当前位置: 首页 > news >正文

【蓝桥杯集训·每日一题】AcWing 1562. 微博转发

文章目录

  • 一、题目
    • 1、原题链接
    • 2、题目描述
  • 二、解题报告
    • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、知识风暴
  • 宽搜BFS

一、题目

1、原题链接

1562. 微博转发

2、题目描述

微博被称为中文版的 Twitter。

微博上的用户既可能有很多关注者,也可能关注很多其他用户。

因此,形成了一种基于这些关注关系的社交网络。

当用户在微博上发布帖子时,他/她的所有关注者都可以查看并转发他/她的帖子,然后这些人的关注者可以对内容再次转发…

现在给定一个社交网络,假设只考虑 L 层关注者,请你计算某些用户的帖子的最大可能转发量

补充 如果 B 是 A 的关注者,C 是 B 的关注者,那么 A 的第一层关注者是 B,第二层关注者是 C。

输入格式

第一行包含两个整数,N 表示用户数量,L 表示需要考虑的关注者的层数。

假设,所有的用户的编号为 1∼N。

接下来 N 行,每行包含一个用户的关注信息,格式如下:

M[i] user_list[i] M[i] 是第 i 名用户关注的总人数,user_list[i] 是第 i 名用户关注的 M[i] 个用户的编号列表。

最后一行首先包含一个整数 K,表示询问次数,然后包含 K 个用户编号,表示询问这些人的帖子的最大可能转发量。

输出格式

按顺序,每行输出一个被询问人的帖子最大可能转发量。

假设每名用户初次看到帖子时,都会转发帖子,只考虑 L 层关注者。

数据范围

1≤N≤1000,1≤L≤6,1≤M[i]≤100,1≤K≤N

输入样例

7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6

输出样例

4
5

二、解题报告

1、思路分析

思路来源:y总讲解视频
y总yyds

(1)可以将本题关系存储在图中,将每个人和他的粉丝之间连一条有向边,由被关注者指向粉丝。
(2)该问题就变成了从每个人开始,经过的边数不超过l可以到达的点数,即为答案。
(3)可以利用宽搜来实现,从询问的人开始搜索l层,统计可以到达的点数即为答案。

2、时间复杂度

时间复杂度为O(k(n+m))(k为询问数,n为点数,m为边数,宽搜时间复杂度为O(n+m))

3、代码详解

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N=1010,M=100010;    //N代表点数,M代表边数
int n,l,k;
int h[N],e[M],ne[M],idx;  //h[]存储每个点的第一条边的编号,e[]存储每条边终点的值,ne[]存储每条边同起点的下一条边的编号,idx为边的编号
bool st[N];          //st[]存储每个点是否已经遍历过
//添加一条边a->b
void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int bfs(int id){int ans=0;queue<int> q;memset(st,0,sizeof st);q.push(id);st[id]=true;//循环l层,统计ansfor(int i=0;i<l;i++){int cnt=q.size();    //记录该层的点数while(cnt--){        //依次遍历该层的每个点,将每个点可以到达且没有遍历过的点加入队列int t=q.front();q.pop();//遍历每个点可以到达的点for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){st[j]=true;q.push(j);ans++;}}}}return ans;
}
int main(){cin>>n>>l;memset(h,-1,sizeof h);for(int i=1;i<=n;i++){int num,id;cin>>num;for(int j=0;j<num;j++){cin>>id;add(id,i);         //添加一条边,由被关注者指向粉丝}}cin>>k;while(k--){int m;cin>>m;cout<<bfs(m)<<endl;}return 0;
}

三、知识风暴

宽搜BFS

  • 尽可能向横向搜索,具有“最短性”(边权都为1时可以用BFS求最短路)。

相关文章:

【蓝桥杯集训·每日一题】AcWing 1562. 微博转发

文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴宽搜BFS一、题目 1、原题链接 1562. 微博转发 2、题目描述 微博被称为中文版的 Twitter。 微博上的用户既可能有很多关注者&#xff0c;也可能关注很多其他用户。 因此&am…...

[busybox] busybox生成一个最精简rootfs(下)

书接上回&#xff1a;[busybox] busybox生成一个最精简rootfs(上) 本篇介绍几个rootfs中用到的“不是那么重要的”几个文件。 9 /etc/shadow 和 /etc/passwd 曾经&#xff0c;/etc/passwd 文件用于存储独立 Linux 系统中的所有登录信息。 后来&#xff0c;由于以下原因&…...

Java奠基】运算符的讲解与使用

目录 运算符与表达式的使用 算术运算符 隐式转换与强制转换 自增自减运算符 赋值运算符 关系运算符 逻辑运算符 三元运算符 运算符与表达式的使用 运算符是指&#xff1a;对字面量或者变量进行操作的符号。 表达式是指&#xff1a;用运算符把字面量或者变量连接起来&…...

开发一个会员管理系统

背景 由于现在公司内客户量剧增&#xff0c; 简单的靠电话及笔记本记录&#xff0c;来维护客户有些困难&#xff0c;但又不想去花钱购买那些专业版的会员管理系统&#xff0c;只能自己动手撸一个相对简易的会员系统来使用了。 开发语言及使用技术 后端&#xff1a;java、mys…...

华为OD机试题【找出通过车辆最多颜色】用 C++ 进行编码 (2023.Q1)

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明找出通…...

如何根据子网掩码计算出网络前缀(prefix)

我们知道子网掩码是对IP地址的网络地址的标注。把IP地址中网络地址位设置为1,主机地址位设置为0,得到的就是子网掩码。除了用子网掩码表示IP地址的网络地址和主机地址外,还可以用network prefix(网络前缀),比如192.168.0.1/16,这里的16就是prefix,也就是网络地址位的位…...

【FATE联邦学习】Fateboard的使用

fateboard文档 https://fate.fedai.org/fateboard/ github Fateboard文档 https://github.com/FederatedAI/FATE-Board/blob/master/README-CN.md 背景 Fateboard是FATE框架的任务看板。 在配置FATE时&#xff0c;Fateboard一般是被安装好了的&#xff0c;安装过程查看这里 A…...

解决vue3没有this造成的无法使用vue2

在Vue2项目中可以使用this.$router.push等方法进行路由的跳转&#xff0c;但是在Vue3的setup函数里&#xff0c;并没有this这个概念&#xff0c;因此如何使用路由方法 1.// 在新的vue-router里面尤大加入了一些方法&#xff0c;比如这里代替this的useRouter&#xff0c;具体使用…...

百度前端二面vue面试题指南

Vue 组件间通信有哪几种方式&#xff1f; ​ Vue 组件间通信是面试常考的知识点之一&#xff0c;这题有点类似于开放题&#xff0c;你回答出越多方法当然越加分&#xff0c;表明你对 Vue 掌握的越熟练。Vue 组件间通信只要指以下 3 类通信&#xff1a;父子组件通信、隔代组件通…...

【备战面试】每日10道面试题打卡-Day1

本篇总结的是Java基础知识相关的面试题&#xff0c;后续也会更新其他相关内容 文章目录1、JVM、JRE和JDK的关系&#xff1f;2、Java语言有哪些特点&#xff1f;3、Java和C的区别有哪些&#xff1f;4、Java有哪些数据类型&#xff1f;5、访问修饰符 public、private、protected&…...

服务器重启后jar包自动重启

1、创建自动启动脚本 vi /etc/rc.d/auto_start_script.sh #!/bin/bash #添加本地Java环境&#xff0c;这两句必须添加&#xff01;不然报错&#xff0c;找不到java命令 export JAVA_HOME/java/jdk1.8.0_181 export PATH$JAVA_HOME/bin:$PATH #系统引导后延迟5秒执行脚本&#x…...

Ubuntu 交叉编译工具链安装

Ubuntu 交叉编译工具链安装 1 交叉编译器安装 ARM 裸机、Uboot 移植、Linux 移植这些都需要在 Ubuntu 下进行编译&#xff0c;编译就需要编译器&#xff0c;我们在第三章“Linux C 编程入门”里面已经讲解了如何在 Liux 进行 C 语言开发&#xff0c;里面使用 GCC 编译器进行代…...

Vue3中ref、reactive、toRef、toRefs基本用法和区别

ref、reactivesetup 函数中默认定义的变量并不是响应式的&#xff08;即数据变了以后页面不会跟着变&#xff09;&#xff0c;如果想让变量变为响应式的变量&#xff0c;需要使用 ref 和 reactive 函数修饰变量。区别&#xff1a;reactive只能传入对象类型的参数&#xff0c;所…...

python hash 不一致踩坑总结

背景 在线上的一次模型对照实验中&#xff0c;发现对同一个用户进行 hash 分流时&#xff0c;会生成不同的 random 值&#xff0c;导致实验数据污染 原因 参考&#xff1a;https://www.zhihu.com/question/57526436 python 的字符串 hash 算法并不是直接遍历字符串每个字符去…...

qt5.15 快速安装 国内源

1 qt5.15 安装问题 最大的问题就是需要在线下载与安装。即使挂了科学上网&#xff0c;国外的服务器下载速度也还是超级慢。 在网上找了各种解决办法后&#xff0c;终于找到一个快速下载安装的办法。 2 安装器下载 阿里源、清华源都没有Windows的安装器了&#xff0c;在腾讯…...

JavaScript 对象

文章目录JavaScript 对象所有事物都是对象JavaScript 对象访问对象的属性访问对象的方法创建 JavaScript 对象创建直接的实例使用对象构造器创建 JavaScript 对象实例把属性添加到 JavaScript 对象把方法添加到 JavaScript 对象JavaScript 类JavaScript for...in 循环JavaScrip…...

数据库设计三大范式

数据库设计遵循三大范式的理由&#xff1a;在面对复杂是数据库设计的时候&#xff0c;设计数据库要遵循一定的规则&#xff0c;有了一定的规范&#xff0c;这样就可以是自己看起来舒服。 1&#xff0e;第一范式(确保每列保持原子性) 第一范式主要是保证数据表中的每一个字段的…...

cesium学习记录02-vue项目中cesium的配置与使用

1&#xff0c;下载cesium包 &#xff08;当然&#xff0c;使用npm install cesium安装也是可以的&#xff0c;不过在这里选择下载包放到本地&#xff09; 官方下载地址 笔者的cesium版本为1.101 2&#xff0c;将下载的Cesium文件夹放到项目里某个位置 这里&#xff0c;笔者将…...

【微服务】-认识微服务

目录 1.1 单体、分布式、集群 单体 分布式 集群 1.2 系统架构演变 1.2.1 单体应⽤架构 1.2.2 垂直应⽤架构 1.2.3 分布式架构 1.2.4 SOA架构 1.2.5 微服务架构 1.3 微服务架构介绍 微服务架构的常⻅问题 1.4 SpringCloud介绍 1.4.1 SpringBoot和SpringCloud有啥关…...

容器的线程安全性

&#xff08;1&#xff09;c的map、vector等容器以及go中的slice、map都不是线程安全的。 &#xff08;2&#xff09;线程安全&#xff1a;多线程访问执行n次每次结果都是确定的 &#xff08;3&#xff09;保证线程安全&#xff1a;同步 &#xff08;4&#xff09;c同步相关…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...

麒麟系统使用-进行.NET开发

文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的&#xff0c;如果需要进行.NET开发&#xff0c;则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET&#xff0c;所以要进…...