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(…...
嵌入式软件开发中的柔性数组机制
在嵌入式系统开发中,内存资源始终是最核心的约束之一。无论是微控制器还是低功耗控制终端,程序设计都必须在有限的存储空间中实现功能、效率与可靠性的平衡。因此,开发者不仅需要关注算法逻辑,还必须重视数据结构对内存的占用方式。 在这种背景下,柔性数组成为嵌入式软件…...
基于VLFM的中文指令视觉语言导航系统设计与实现
基于VLFM的中文指令视觉语言导航系统设计与实现 一、引言 1.1 项目背景 视觉语言导航(Vision Language Navigation,VLN)是具身智能领域的核心任务之一,其目标是让智能体根据自然语言指令在三维环境中自主导航,完成路径规划与空间定位任务[reference:0]。近年来,随着大…...
星闪实战指南:10分钟掌握WS63 SDK任务调度与调试技巧
1. 星闪WS63 SDK任务调度基础 第一次接触星闪WS63 SDK的任务调度功能时,我完全被各种API搞晕了。经过几个项目的实战,才发现这套任务管理系统设计得非常巧妙。简单来说,它就像个智能管家,能帮你把各种工作安排得井井有条。 任务调…...
hiSHtory 配置管理完全指南:从基础设置到高级调优
hiSHtory 配置管理完全指南:从基础设置到高级调优 【免费下载链接】hishtory Your shell history: synced, queryable, and in context 项目地址: https://gitcode.com/gh_mirrors/hi/hishtory hiSHtory 是一款革命性的 shell 历史记录工具,它不仅…...
全国霸王餐 API 接口聚合平台,Java 后端多数据源路由策略设计
全国霸王餐 API 接口聚合平台,Java 后端多数据源路由策略设计 在构建全国性的霸王餐(Free Meal)与外卖CPS聚合平台时,单一的数据源架构往往无法支撑海量的并发请求与复杂的业务隔离需求。随着业务规模的扩张,系统通常面…...
从零构建极简大语言模型:MiniLLMDemo 原理与实现详解
一、项目背景与核心价值 在LLM技术快速迭代的今天,理解底层原理比调用API更重要。本文将带您用200行代码实现一个可运行的极简大模型MiniLLMDemo,通过代码与原理的深度结合,掌握Transformer架构的核心设计思想。二、完整代码实现 import torc…...
基于STM32LXXX的无线收发芯片(CMT2300A-EQR)应用程序设计
一、简介: CMT2300A是一款超低功耗,高性能,适用于各种127至 1020 MHz无线应用的OOK,(G)FSK射频收发器。它是 CMOSTEK NextGenRFTM射频产品线的一部分,这条产品线 包含完整的发射器,接收器和收发器。CMT2300A的高集成 度,简化了系统设计中所需的外围物料。高达+20 dBm及-…...
Cursor Free VIP:彻底解决AI编程助手使用限制的智能解决方案
Cursor Free VIP:彻底解决AI编程助手使用限制的智能解决方案 【免费下载链接】cursor-free-vip [Support 0.45](Multi Language 多语言)自动注册 Cursor Ai ,自动重置机器ID , 免费升级使用Pro 功能: Youve reached yo…...
零基础入门机器人抓取:在快马平台轻松搞定龙虾openclaw安装与第一个程序
最近在学习机器人抓取相关的知识,发现龙虾openclaw是个不错的入门工具。作为一个完全零基础的小白,我在安装和配置环境时遇到了不少困难。好在发现了InsCode(快马)平台,它帮我轻松解决了这些问题。下面分享一下我的学习过程。 了解openclaw …...
A*、遗传、蚁群优化和元胞自动机四种经典算法实现四种场景下六边形网格路径规划,Python代码
基于六边形网格的路径规划算法摘要路径规划是机器人导航、智能交通和游戏AI等领域的核心问题。本期推文基于六边形网格结构,系统地对比了四种经典路径规划算法:A*算法、遗传算法、蚁群优化算法和元胞自动机算法。通过设计四组不同规模和复杂度的测试场景…...
