neuq-acm预备队训练week 8 P2661 [NOIP2015 提高组] 信息传递
题目背景
NOIP2015 Day1T2
题目描述
有 n 个同学(编号为 1 到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为 Ti 的同学。
游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?
题目限制

输入格式

输出格式
共一行一个整数,表示游戏一共可以进行多少轮。
输入输出样例

解题思路
把每个同学看成一个点,信息的传递就是在他们之间连有向边,游戏轮数就是求最小环
AC代码
#include <bits/stdc++.h>
using namespace std;
int n,Min,last;
int f[200005],d[200005];
int F(int x);
void check(int a,int b);
int main()
{int t;Min=0x7777777;cin>>n;for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=n;i++){cin>>t;check(i,t);}cout<<Min;return 0;
}void check(int a,int b)
{int x=F(a),y=F(b);if (x!=y){f[x]=y;d[a]=d[b]+1;} //若不相连,则连接两点,更新父节点和路径长。elseMin=min(Min,d[a]+d[b]+1); //若已连接,则更新最小环长度
}int F(int x)
{if(f[x]!=x){int last=f[x];f[x]=F(f[x]);d[x]+=d[last];}return f[x];
}
相关文章:
neuq-acm预备队训练week 8 P2661 [NOIP2015 提高组] 信息传递
题目背景 NOIP2015 Day1T2 题目描述 有 n 个同学(编号为 1 到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为 Ti 的同学。 游戏开始时,每人都…...
《C++新经典设计模式》之第18章 备忘录模式
《C新经典设计模式》之第18章 备忘录模式 备忘录模式.cpp 备忘录模式.cpp #include <iostream> #include <vector> #include <memory> using namespace std;// 保存对象内部状态,必要时恢复 // 在不破坏封装性的前提下,捕获对象的内部…...
OWASP安全练习靶场juice shop-更新中
Juice Shop是用Node.js,Express和Angular编写的。这是第一个 完全用 JavaScript 编写的应用程序,列在 OWASP VWA 目录中。 该应用程序包含大量不同的黑客挑战 用户应该利用底层的困难 漏洞。黑客攻击进度在记分板上跟踪。 找到这个记分牌实际上是&#…...
当使用RSA加密,从手机前端到服务器后端的请求数据存在+
将转成了空格,导致解密出错 将空格转成了...
BUUCTF crypto做题记录(3)新手向
目录 一、Rabbit 二、篱笆墙的影子 三、丢失的MD5 四、Alice与Bob 一、Rabbit 得到的密文:U2FsdGVkX1/ydnDPowGbjjJXhZxm2MP2AgI 依旧是看不懂是什么编码,上网搜索,在侧栏发现Rabbit解码,直接搜索就能有在线解码网站 二、篱笆…...
SpringMVC修炼之旅(2)基础入门
一、第一个程序 1.1环境配置 略 1.2代码实现 package com.itheima.controller;import org.springframework.stereotype.Controller; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.ResponseBody;//定义…...
matlab 最小二乘拟合空间直线(方法二)
目录 一、算法原理1、算法过程2、参考文献二、代码实现三、结果展示四、相关链接本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法原理...
ASPICE-汽车软件开发能力评级
Automotive SPICE(简称A-SPICE 或 ASPICE),全称是“Automotive Software Process Improvement and Capacity dEtermination”,即“汽车软件过程改进及能力评定”模型框架。 常被用于评估一家汽车软件供应商的软件开发能力&#x…...
准确!!!在 CentOS 8 上配置 PostgreSQL 14 的主从复制
在 CentOS 8 上配置 PostgreSQL 14 的主从复制,并设置 WAL 归档到特定路径 /home/postgres/archive 的步骤如下: 主服务器配置(主机) 配置 PostgreSQL: 编辑 postgresql.conf 文件: vim /data/postgres/p…...
leetcode 1466
leetcode 1466 使用dfs 遍历图结构 如图 node 4 -> node 0 -> node 1 因为节点数是n, 边长数量是n-1。所以如果是从0出发的路线,都需要修改,反之,如果是通向0的节点,例如节点4,则把节点4当作父节点的节点&…...
想学编程,但不知道从哪里学起,应该怎么办?
怎样学习任何一种编程语言 我将教你怎样学习任何一种你将来可能要学习的编程语言。本书的章节是基于我和很多程序员学习编程的经历组织的,下面是我通常遵循的流程。 1.找到关于这种编程语言的书或介绍性读物。 2.通读这本书,把…...
Python数据科学视频讲解:Python概述
2.1 Python概述 视频为《Python数据科学应用从入门到精通》张甜 杨维忠 清华大学出版社一书的随书赠送视频讲解2.1节内容。本书已正式出版上市,当当、京东、淘宝等平台热销中,搜索书名即可。内容涵盖数据科学应用的全流程,包括数据科学应用和…...
数据结构之内部排序
目录 7-1 直接插入排序 输入格式: 输出格式: 输入样例: 输出样例: 7-2 寻找大富翁 输入格式: 输出格式: 输入样例: 输出样例: 7-3 PAT排名汇总 输入格式: 输出格式: 输入样例: 输出样例: 7-4 点赞狂魔 输入格式: 输出格式: 输入样例&a…...
软考高级备考-系统架构师(机考后新版教材的备考过程与资料分享)
软考高级-系统架构设计师 考试复盘1.考试结果2.备考计划3.个人心得 资料分享 考试复盘 1.考试结果 三科压线过,真是太太太太太太太幸运了。上天对我如此眷顾,那不得不分享下我的备考过程以及一些备考资料,帮助更多小伙伴通过考试。 2.备考…...
Spring Boot 整合kafka:生产者ack机制和消费者AckMode消费模式、手动提交ACK
目录 生产者ack机制消费者ack模式手动提交ACK 生产者ack机制 Kafka 生产者的 ACK 机制指的是生产者在发送消息后,对消息副本的确认机制。ACK 机制可以帮助生产者确保消息被成功写入 Kafka 集群中的多个副本,并在需要时获取确认信息。 Kafka 提供了三种…...
Java+Swing: 主界面组件布局 整理9
说明:这篇博客是在上一篇的基础上的,因为上一篇已经将界面的框架搭好了,这篇主要是将里面的组件完善。 分为三个部分,北边的组件、中间的组件、南边的组件 // 放置北边的组件layoutNorth(contentPane);// 放置中间的 Jtablelayou…...
pytorch:YOLOV1的pytorch实现
pytorch:YOLOV1的pytorch实现 注:本篇仅为学习记录、学习笔记,请谨慎参考,如果有错误请评论指出。 参考: 动手学习深度学习pytorch版——从零开始实现YOLOv1 目标检测模型YOLO-V1损失函数详解 3.1 YOLO系列理论合集(Y…...
YOLOv8配置文件yolov8.yaml解读
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 | 接辅导、项目定制 位置 该文件的位置位于 ./ultralytics/cfg/models/v8/yolov8.yaml 模型参数配置 # Parameters nc: 80 # number of classes scales: #…...
4-Tornado高并发原理
核心原理就是协程epoll事件循环,再使用协程之后,开销是特别的小,那具体如何提供高并发的呢? 异步非阻塞IO 这意味我们整套开发的模式不在与原来一样,正因为不再一样,所以有时我们在理解代码时就有可能会比…...
基于以太坊的智能合约开发Solidity(事件日志篇)
//声明版本号(程序中的版本号要和编译器版本号一致) pragma solidity ^0.5.17; //合约 contract EventTest {//状态变量uint public Variable;//构造函数constructor() public{Variable 100;}event ValueChanged(uint newValue); //事件声明event Log(…...
若依(ruoyi)RuoYiApp版—页面
ruoyiApp中的页面是一个符合vue规范的文件,如果你熟悉vue,这里将非常快速上手。 1.如何新增页面 uni-app中的页面,默认保存在工程根目录下的pages目录下。 每次新建页面,均需在pages.json中配置pages列表;未在pages.js…...
向量数据库:大模型的高效外存
一、 向量数据库概述:AI大模型的“外部记忆体” 向量数据库是一种专门用于存储、索引和查询**向量嵌入(Vector Embedding)**的数据库系统。在大模型时代,它扮演着至关重要的“外部记忆体”角色,其核心价值在于解决大模…...
深入解析:成为一名卓越的 Android 开发工程师
引言 在移动互联网蓬勃发展的今天,Android 系统凭借其开放性和庞大的用户基数,在全球范围内占据着主导地位。Android 开发工程师作为构建移动应用体验的核心力量,其角色日益重要。本文旨在深入探讨成为一名优秀的 Android 开发工程师所需的核心技能、职责要求以及面对的技术…...
终极跨平台Iwara视频社区客户端:5个核心功能完全指南
终极跨平台Iwara视频社区客户端:5个核心功能完全指南 【免费下载链接】iwrqk Unofficial Iwara Flutter Client 项目地址: https://gitcode.com/gh_mirrors/iw/iwrqk IwrQk是一款基于Flutter框架开发的跨平台Iwara视频社区客户端应用,为你提供在i…...
2025最权威的十大降AI率方案推荐榜单
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 人工智慧写作工具凭借自然语言生成这项技术,能够快速产出契合语法规则的文本内容…...
安全测试左移:在CI/CD中集成安全扫描
安全困境与左移的必要性 在快速迭代的敏捷开发与DevOps浪潮中,软件交付的周期被急剧压缩,然而,传统安全测试模式却显得格格不入。测试阶段末期的一次性渗透测试或代码审计,发现的往往是积重难返的高危漏洞,修复成本高…...
保姆级教学:用FUTURE POLICE和MySQL管理你的语音字幕数据
保姆级教学:用FUTURE POLICE和MySQL管理你的语音字幕数据 1. 为什么需要管理语音字幕数据? 想象一下这样的场景:你刚刚用FUTURE POLICE处理了100个会议录音,得到了精确到毫秒的字幕文件。这些文件散落在各个文件夹里,…...
原料杂乱难管理?合并功能一键搞定
在制造行业的日常运营中,进销存管理的核心痛点往往藏在细节里——尤其是生产环节的领料流程,却常常成为拖慢效率、造成损耗的“隐形绊脚石”。很多企业在生产计划落地时,都会遇到这样的困境:同一份生产计划单中,不同成…...
新能源/电力系统论文中的应用及盲审注意事项
在新能源/电力系统方向学术论文研究中,气象数据的权威性、精度及适配性直接影响论文盲审结果。羲和能源气象大数据平台作为该领域常用的气象数据支撑工具,其数据处理流程、适配特性与学术规范适配性较强,可有效提升论文盲审通过率。本文结合盲…...
hadoop3.3.6上搭建Hbase2.5.13集群
一、什么是Hbase hadoop的局限性 hadoop主要是实现批处理的处理,并且通过顺序方式访问数据 要查找数据必须搜索整个数据集,如果要进行随机读写数据,效率低下 Hbase是Bigtable的开源java版本,是建立在HDFS之上,提供高可靠性、高性能、列存储、可伸缩、实时读写的NoSQL数据…...
