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

2024-05-04 15:36

本文主要是介绍蓝桥杯练习系统(算法训练)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。

 

这篇关于蓝桥杯练习系统(算法训练)ALGO-947 贫穷的城市的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/959531

相关文章

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

Linux系统之dns域名解析全过程

《Linux系统之dns域名解析全过程》:本文主要介绍Linux系统之dns域名解析全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、dns域名解析介绍1、DNS核心概念1.1 区域 zone1.2 记录 record二、DNS服务的配置1、正向解析的配置

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Linux系统之authconfig命令的使用解读

《Linux系统之authconfig命令的使用解读》authconfig是一个用于配置Linux系统身份验证和账户管理设置的命令行工具,主要用于RedHat系列的Linux发行版,它提供了一系列选项... 目录linux authconfig命令的使用基本语法常用选项示例总结Linux authconfi