最短路:P8674 [蓝桥杯 2018 国 B] 调手表

这篇具有很好参考价值的文章主要介绍了最短路:P8674 [蓝桥杯 2018 国 B] 调手表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

P8674 [蓝桥杯 2018 国 B] 调手表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

小明买了块高端大气上档次的电子手表,他正准备调时间呢。

在 M78 星云,时间的计量单位和地球上不同,M78 星云的一个小时有 n 分钟。

大家都知道,手表只有一个按钮可以把当前的数加一。在调分钟的时候,如果当前显示的数是 0,那么按一下按钮就会变成 1,再按一次变成 2。如果当前的数是 n−1,按一次后会变成 0。

作为强迫症患者,小明一定要把手表的时间调对。如果手表上的时间比当前时间多 1,则要按 n−1 次加一按钮才能调回正确时间。

小明想,如果手表可以再添加一个按钮,表示把当前的数加 k 该多好啊……

他想知道,如果有了这个 +k 按钮,按照最优策略按键,从任意一个分钟数调到另外任意一个分钟数最多要按多少次。

注意,按 +k 按钮时,如果加 k 后数字超过 n−1, 则会对 n 取模。

比如,n=10,k=6 的时候,假设当前时间是 0,连按 2 次 +k 按钮,则调为 2。

输入格式

一行两个整数 n,k,意义如题。

输出格式

一行一个整数。表示:按照最优策略按键,从一个时间调到另一个时间最多要按多少次。

输入输出样例

输入 #1复制

5 3

输出 #1复制

2

说明/提示

【样例解释】

如果时间正确则按 00 次。否则要按的次数和操作系列之间的关系如下:

  1. +1
  2. +1, +1
  3. +3
  4. +3, +1

【数据约定】

对于 30% 的数据 0<k<n≤5。

对于 60% 的数据 0<k<n≤100。

对于 100% 的数据 0<k<n≤10^5。

时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛

解析:bfs,最短路

(不要一谈到最短路就想到那几个经典的算法,别忘了bfs也是最简单的最短路算法)

这是一道 bfs 题目。

使用一个数组 s,si​ 存储从时间 1 调到时间 i 最少需要调多少次。

从 1 开始搜索,直到 s1​ 至 si​ 都被搜索到

最终的答案就是 s 数组中的最大值。

 又因为如果令s[1]=0.则会与其他没有bfs过的点弄混,因为没有bfs过的点s[i]=0,所以这里我们令s[1]=1,最后计算最终结果的时候再减去1文章来源地址https://www.toymoban.com/news/detail-622938.html

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n, k;
int s[N];

void bfs() {
	queue<int >q;
	s[1] = 1;
	q.push(1);
	int t;
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		if (s[(t + 1) % n] == 0) {
			s[(t + 1) % n] = s[t] + 1;
			q.push((t + 1) % n);
		}
		if (s[(t + k) % n] == 0) {
			s[(t + k) % n] = s[t] + 1;
			q.push((t + k) % n);
		}
	}
}

int main() {
	cin >> n >> k;
	bfs();
	int mx = 0;
	for (int i = 0; i < n; i++) {
		mx = max(mx, s[i]-1);
	}
	cout << mx << endl;
	return 0;
}

到了这里,关于最短路:P8674 [蓝桥杯 2018 国 B] 调手表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【职业人生】如何有效的在职场当中避免工作失误和提高个人发展

         《左传·宣公二年》:“人谁无过,过而能改,善莫大焉。”古往今来,多少人犯过错误。强大如“智绝”的诸葛孔明,也有街亭之失。职场人更是难免会在工作中出现失误。     在职场生涯当中避免不了在工作当中带来的失误,在这过程当中,我们应当要学会怎么去

    2024年02月08日
    浏览(43)
  • [office] excel成绩表格数据排名次的教程 #职场发展#知识分享#媒体

    excel成绩表格数据排名次的教程 Excel 中经常需要使用到 排名 次的技巧,成绩表格数据具体该如何排名呢?接下来是小编为大家带来的excel成绩表格数据排名次的教程,供大家参考。 步骤1:不管在学校还是各个统计领域,排名应用随处可见,如果排序会打乱原有次序,那么好多

    2024年02月21日
    浏览(39)
  • [洛谷]P8662 [蓝桥杯 2018 省 AB] 全球变暖(dfs)

    读题不规范,做题两年半!  注意:被海水淹没后的陆地应用另一个字符表示,而不是把它变为海洋,这个点可以便利,但不能被当作起点,不然就只有 36 分。 ACocde:  over~

    2024年02月16日
    浏览(37)
  • 突破职场竞争,引领未来发展:考取《研发效能(DevOps)工程师职业技术认证》

    就业形势堪忧,什么最有保障?考个“国家级”证书傍身吧! 工信部教考中心作为中国领先的行业技能认证机构,其颁发的认证证书不仅代表了个人在信息技术领域的专业能力,更可以录入工业和信息化技术技能人才数据库,这是一个重要的信息资源平台,它可以帮助企业和

    2024年02月05日
    浏览(44)
  • [office] Excel中函数进行计算两个日期参数差值的方法 #职场发展#学习方法#媒体

    Excel中函数进行计算两个日期参数差值的方法 在excel使用中,如果想计算两个日期参数的差值,该用什么函数和如何使用呢?今天,小编就教大家在Excel中函数进行计算两个日期参数差值的方法。 Excel中函数进行计算两个日期参数差值的步骤 在excel中计算两个日期参数的差值,

    2024年02月20日
    浏览(47)
  • 苹果手机丢了手表怎么解绑(苹果手机解绑丢失手表方法)

    1苹果手机打开设置 打开Apple Watch的【设置】,找到【通用】,点击进入。 2苹果手机点击还原 在【通用】的界面中找到【还原】,点击进入。 3苹果手机抹掉所有内容 在【还原】的界面中选择【抹掉所有内容和设置】即可解绑手机。 1、打开Apple Watch的“设置”,选择“通用

    2024年02月12日
    浏览(176)
  • 华为手表开发:WATCH 3 Pro(10)获取心率_java 华为手表获取心跳

    文章浏览阅读1.2k次。鸿蒙开发,获取手表心跳,按钮点击后触发的方法,我们将跳转页面的代码写在这个位置就可以实现点击按钮进行跳转页面的动作。在HTML文件“index.hml”,添加按钮,这里按钮用到是标签。在文本框中输入页面名称(showHeartbeat)名称可以自己拟定。佩戴

    2024年01月16日
    浏览(57)
  • 基于HarmonyOS的华为智能手表APP开发实战——Fitness_华为手表app开发

    、 文章浏览阅读8.7k次,点赞6次,收藏43次。本文针对华为HarmonyOS智能穿戴产品(即HUAWEI WATCH 3)开发了一款运动健康类的游戏化APP——Fitness,旨在通过游戏化的方式,提升用户运动动机。_华为手表app开发 **开发环境:**客户端UI是基于HarmonyOS进行开发的,所以IDE使用的是华为

    2024年02月01日
    浏览(57)
  • 智能手表:华米稳、华为猛

    随着科技的进步与发展,消费电子产品的功能和品类越来越丰富,人们也愈发习惯使用消费电子产品了。消费电子产品一词听起来陌生,实际上却离人们很近,比如智能手机、笔记本电脑等等,都属于消费电子产品。现如今,以智能手机为代表的消费电子产品已经逐渐深入到

    2024年02月11日
    浏览(38)
  • 小天才手表系统指南

    2024年02月05日
    浏览(271)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包