蓝桥杯练习系统(算法训练)ALGO-947 贫穷的城市

资源限制

内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

问题描述

  某城市有n个小镇,编号是1~n。由于贫穷和缺乏城市规划的人才,每个小镇有且仅有一段单向的公路通往别的小镇。有一天,一辆小轿车误入了这座城市,它只能沿着公路走,它走啊走,却再也走不出这座城市了……
  问如果这辆车从某个小镇出发,走了若干段公路,会到达哪个小镇。每组数据有m个询问。

输入格式

  第一行两个数n、m:表示小镇数和询问数;
  接下来一行n个数,第i个数Ai:表示从小镇i出发的公路会通向小镇Ai;
  接下来m行,第i行有两个数Bi和Ci:询问小轿车从小镇Bi出发,走过Ci段路后会达到哪个小镇。

输出格式

  一行m个数回答每个询问。

样例输入

3 3
2 1 3
1 1
2 2
3 3

样例输出

2 2 3

数据规模和约定

  对于60%的数据:1<=n、m<=1000,1<=Ai、Bi<=n,0<=Ci<=1000;
  对于100%的数据:1<=n、m<=100000,1<=Ai、Bi<=n,0<=Ci<=100000。

暴力,超时,仅供理解题意

#include<iostream>
#include<vector>
using namespace std;
const int N=100005;
vector<int> v[N];
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int ai;cin>>ai;v[i].push_back(ai);}int ans[m];for(int i=0;i<m;i++){int b,c;cin>>b>>c;//从b小镇出发 for(int j=0;j<c;j++){if(v[b][0]!=b){int next=v[b][0];b=next;}else{break;}} ans[i]=b;} for(int i=0;i<m;i++){cout<<ans[i]<<" ";}return 0;
} 

倍增思想

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
const int N=100005;
int v[N][20];
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int ai;cin>>ai;v[i][0]=ai;}//倍增思想 for(int i=1;i<20;i++){for(int j=1;j<=n;j++){v[j][i]=v[v[j][i-1]][i-1];}} int ans[m];for(int i=0;i<m;i++){int b,c;cin>>b>>c;//从b小镇出发 int cnt=0;while(c){if(c&1){b=v[b][cnt];}c=c>>1;cnt++;}ans[i]=b;} for(int i=0;i<m;i++){cout<<ans[i]<<" ";}return 0;
} 

思路:倍增思想。

在访问前算出从任意一个小镇走任意段公路最后到达的小镇,但是不是一段一段地走,而是2^0,2^1,2^2,……地走。

v[j][i]表示从j小镇开始,走2^i段公路到达的小镇。v[j][i]=v[v[j][i-1]][i-1];表示从小镇j走2^i段=先走2^(i-1)段到达v[v[j][i-1]]小镇,再走2^(i-1)段。因为2^(i-1)+2^(i-1)=2^i

到后面m次访问时,将要走的段数c转换成二进制即可。例如:7=2^0+2^1+2^2,将原本要走7段优化为走3段:走2^0段,再走2^1段,最后再走2^2。

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3014986.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

[Linux] GDB使用指南----包含CentOS7下安装以及使用

什么是GDB&#xff1f; GDB 是由 GUN 软件系统社区提供的调试工具&#xff0c;同 GCC 配套组成了一套完整的开发环境&#xff0c;GDB 是 Linux 和许多 类Unix系统的标准开发环境。可以用来调试C、C、Go、java、 objective-c、PHP等语言。 GDB的作用 程序启动时&#xff0c;可…

400 Bad Request问题

总结&#xff1a;请求路径写错了 400 问题 原地址&#xff0c;deleteSetmeal的参数应该改为param 更改请求地址正确后即可

视频质量评估

视频质量评估 一、全参考客观视频质量评价方法三、MSSIM四、STRRED五、VMAF六、MOS 一、全参考客观视频质量评价方法 全参考客观视频质量评价方法是指把原始参考视频与失真视频在每一个对应帧中的每一个对应像素之问进行比较。准确的讲&#xff0c;这种方法得到的并不是真正的…

Chromium编译指南2024 Windows11篇-Git工具准备(四)

前言 在《Chromium编译指南2024&#xff08;三&#xff09;》中&#xff0c;我们已经完成了对 Chromium 编译环境的其他相关环境变量的设置&#xff0c; 接下来&#xff0c;我们将进一步探讨如何初始化配置 Git&#xff0c;为获取 Chromium 源代码做好准备。 1. 配置Git 用户…

AI伦理和安全风险管理终极指南

人工智能&#xff08;AI&#xff09;正在迅速改变各个领域的软件开发和部署。驱动这一转变的两个关键群体为人工智能开发者和人工智能集成商。开发人员处于创建基础人工智能技术的最前沿&#xff0c;包括生成式人工智能&#xff08;GenAI&#xff09;模型、自然语言处理&#x…

VBA在Excel中字母、数字的相互转化

VBA在Excel中字母、数字的相互转化 字母转数字的方法 数字转字母的方法 众所周知,Excel表中的行以数字展示,列用字母展示,如下图: 编程时,很多时候需要将列的字母转变为数字使用,如cells(num1,num2).value等,不知大家是怎么将字母转化为数字的,Excel是否有其他方式…

今天看到一个有意思的问题:个人网站被恶意大量访问,怎么办(文末附GPT指令优化)

目录 问题描述 一、GPT 3.5 二、通义千问 三、讯飞星火 四、文心一言 五、Kimi 六、智谱清言 个人分析&#xff1a; 问题描述 大家好&#xff01;我的个人网站每天晚上7点30到11点被固定的十几个IP大量下载exe&#xff0c;造成网站带宽不够&#xff0c;怎么办! 已经把…

耕耘未来——揭秘第一产业的无限潜能

在浩瀚的科技宇宙中&#xff0c;当火星探测器的每一次着陆都能激起全球狂欢&#xff0c;当虚拟现实的浪潮让我们触碰未来&#xff0c;有一个领域&#xff0c;以其恒久不变的坚韧&#xff0c;默默地滋养着人类文明的根脉——这就是第一产业&#xff0c;那片古老而又充满生机的土…

护眼灯有没有护眼的效果?一键查看这五大护眼效果极佳的护眼台灯

在数字时代&#xff0c;护眼灯已成为保护视力的重要工具。但消费者常问&#xff1a;护眼灯有没有护眼的效果&#xff1f;挑选到技术过关的护眼台灯是能够很好地起到护眼效果的。本文将并重点介绍五款具有卓越护眼功能的台灯。这些精选灯具不仅在照明效果上表现出色&#xff0c;…

C#里如何设置输出路径,不要net7.0-windows

官网介绍&#xff1a; 更改生成输出目录 - Visual Studio (Windows) | Microsoft Learn <PropertyGroup> <AppendTargetFrameworkToOutputPath>false</AppendTargetFrameworkToOutputPath> <AppendRuntimeIdentifierToOutputPath>false</Appen…

10000字讲解IoC 思想以及五大注解

文章目录 IoC 思想通过案例讲解 IoC1.传统的开发方式 SpringIoC 和 DI五大注解ControllerServiceComponentRepositoryConfiguration 为什么要有这么多的类注解类注解之间的关系方法注解 Bean重命名 bean扫描路径 IoC 思想 什么是 Spring 呢&#xff1f; 我们经常听到的都是说…

如何使用 iOS系统恢复软件修复 iPhone 问题

苹果公司向世界推出了他们可以拥有的最智能的手机。但即使是 iPhone 也无法避免智能手机常见的损坏和问题。您将熟悉最常见的问题。屏幕黑屏或卡在 Apple 徽标上&#xff1b;冻结或卡在恢复模式的 iPhone。但这样的问题不胜枚举&#xff0c;每天都有 iOS 用户在他们的设备中遇到…

微信小程序知识点归纳(一)

前言&#xff1a;适用于有一定基础的前端开发同学&#xff0c;完成从网页开发到小程序开发的知识转换。 先立框架&#xff0c;后砌墙壁 回顾&#xff1a;了解微信小程序开发流程-CSDN博客 初始页面结构&#xff0c;三部分pages、utils、配置&#xff0c;分别存放页面、工具类…

并发控制互斥笔记

整理总结自蒋炎岩老师的b站课程&#xff0c;https://jyywiki.cn/OS/2022/index.html 多处理器系统中数据的一致性和互斥访问 所有的CPU的一级缓存都是连着的&#xff0c;如果是多个CPU的话&#xff0c;用在内存中放置标志位&#xff0c;来保证对当前内容的原子性读取&#xff0…

JSP语法——[JSP]4

希望你开心&#xff0c;希望你健康&#xff0c;希望你幸福&#xff0c;希望你点赞&#xff01; 最后的最后&#xff0c;关注喵&#xff0c;关注喵&#xff0c;关注喵&#xff0c;大大会看到更多有趣的博客哦&#xff01;&#xff01;&#xff01; 喵喵喵&#xff0c;你对我真的…

(双指针) 有效三角形的个数 和为s的两个数字 三数之和 四数之和

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 文章目录 前言 一、有效三角形的个数&#xff08;medium&#xff09; 1.1、题目 1.2、讲解算法原理 1.3、编写代码 二、和为s的两个数字 2.1、题目 2.2、讲解算…

纯干货分享|源代码泄露的有效方法

企业的源代码怎么加密&#xff1f; 源代码防泄密的重点和方法到底是怎样的&#xff1f; 源代码开发环境复杂&#xff0c;涉及的开发软件、文件类型庞杂多变&#xff0c;究竟有什么源代码加密软件能够适应众多开发软件而不影响原有的工作效率&#xff1f; 相信这是很多IT管理…

宋仕强论道之餐饮业的效率

宋仕强论道之餐饮业的效率&#xff0c;现在餐饮业的竞争非常大&#xff0c;经常会看到很多店转让和倒闭。我们就从客流量、客单量、翻台率、毛利率、营业高峰期、有效营业时间等几个餐饮业的基本要素来分析。对于快餐店来说&#xff0c;客单小、毛利低是短板&#xff0c;只有吸…

搭建Harbor仓库

文章目录 Harbor仓库搭建Harbor仓库安装 docker 服务修改配置文件 Harbor仓库 搭建Harbor仓库 下载 Harbor 仓库 安装 docker 服务 # step 1: 安装必要的一些系统工具 yum install -y yum-utils device-mapper-persistent-data lvm2 # Step 2: 添加软件源信息 yum-config-m…

SH-PEG-SH,聚乙二醇二巯基广泛用于生物学应用、纳米技术和材料研究中

【试剂详情】 英文名称 SH-PEG-SH 中文名称 聚乙二醇二巯基&#xff0c;双硫醇PEG&#xff0c; 双巯基聚乙二醇&#xff0c;双巯基封端聚乙二醇 外观性状 白色固体粉末 分子量 0.4k&#xff0c;0.6k&#xff0c;1k&#xff0c;2k&#xff0c;3.4k&#xff0c;5k&#x…