【蓝桥杯冲冲冲】旅行计划

2024-01-26 12:12

本文主要是介绍【蓝桥杯冲冲冲】旅行计划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

蓝桥杯备赛 | 洛谷做题打卡day18

文章目录

  • 蓝桥杯备赛 | 洛谷做题打卡day18
  • 旅行计划
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
    • 题解代码
    • 我的一些话

旅行计划

题目描述

Kira酱要去一个国家旅游。这个国家有 N N N 个城市,编号为 1 1 1 N N N,并且有 M M M 条道路连接着,Kira准备从其中一个城市出发,并只往东走到城市 i i i 停止。

所以她就需要选择最先到达的城市,并制定一条路线以城市 i i i 为终点,使得线路上除了第一个城市,每个城市都在路线前一个城市东面,并且满足这个前提下还希望游览的城市尽量多。

现在,你只知道每一条道路所连接的两个城市的相对位置关系,但并不知道所有城市具体的位置。现在对于所有的 i i i,都需要你为Kira酱制定一条路线,并求出以城市 i i i 为终点最多能够游览多少个城市。

输入格式

第一行为两个正整数 N , M N, M N,M

接下来 M M M 行,每行两个正整数 x , y x, y x,y,表示了有一条连接城市 x x x 与城市 y y y 的道路,保证了城市 x x x 在城市 y y y 西面。

输出格式

N N N 行,第 i i i 行包含一个正整数,表示以第 i i i 个城市为终点最多能游览多少个城市。

样例 #1

样例输入 #1

5 6
1 2
1 3
2 3
2 4
3 4
2 5

样例输出 #1

1
2
3
4
3

提示

均选择从城市 1 1 1 出发可以得到以上答案。

  • 对于 20 % 20\% 20% 的数据, 1 ≤ N ≤ 100 1\le N ≤ 100 1N100
  • 对于 60 % 60\% 60% 的数据, 1 ≤ N ≤ 1000 1\le N ≤ 1000 1N1000
  • 对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 100000 1\le N ≤ 100000 1N100000 1 ≤ M ≤ 200000 1\le M ≤ 200000 1M200000

在这里插入图片描述

题解代码

学会利用新知,自己多试试并尝试积攒一些固定解答方案,debug,以下是题解代码 ~

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath> //别忘记头文件哦
using namespace std;
int n,m,lin[100010],in[100010],total,f[100010];
queue<int>q;
struct cym{int to,next;
}e[400010];
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);e[++total].to=y;e[total].next=lin[x];lin[x]=total;in[y]++;}for(int i=1;i<=n;i++)if(in[i]==0){f[i]=1;q.push(i);}while(!q.empty()){int cnt=q.front();q.pop();for(int i=lin[cnt];i;i=e[i].next){f[e[i].to]=max(f[e[i].to],f[cnt]+1);if(--in[e[i].to]==0)q.push(e[i].to);	}	}for(int i=1;i<=n;i++)printf("%d\n",f[i]);
}

我的一些话

  • 今天来巩固动态规划dp,很显然,每个点的答案是它所有前驱节点的答案加1,即f[i]=max(f[i],f[j]+1); 考虑空间复杂度用邻接表存图,在拓扑排序同时DP就好了不用再外面再做什么工作。多思考思路还是很好掌握的,虽然一次性AC有一定难度,需要通盘的考虑和理解,以及扎实的数据结构基础才能独立写出AC代码。但无论难易,大家都要持续做题,保持题感喔!一起坚持(o´ω`o)

  • 如果有非计算机专业的uu自学的话,关于数据结构的网课推荐看b站上青岛大学王卓老师的课,讲的很细致,有不懂都可以私信我喔

  • 总结来说思路很重要,多想想,多在草稿纸上画画,用测试数据多调试,debug后成功编译并运行出正确结果真的会感到很幸福!

  • 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识,之前的博文我都有写,欢迎大家关注我,翻阅自取哦~

  • 不管什么都要坚持吧,三天打鱼两天晒网无法形成肌肉记忆和做题思维,该思考的时候一定不要懈怠,今天就说这么多啦,欢迎评论留言,一起成长:)

这篇关于【蓝桥杯冲冲冲】旅行计划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

《计算机视觉工程师养成计划》 ·数字图像处理·数字图像处理特征·概述~

1 定义         从哲学角度看:特征是从事物当中抽象出来用于区别其他类别事物的属性集合,图像特征则是从图像中抽取出来用于区别其他类别图像的属性集合。         从获取方式看:图像特征是通过对图像进行测量或借助算法计算得到的一组表达特性集合的向量。 2 认识         有些特征是视觉直观感受到的自然特征,例如亮度、边缘轮廓、纹理、色彩等。         有些特征需要通

Claude Enterprise推出计划

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领域的领跑者。点击订阅,与未来同行! 订阅:https://rengongzhineng.io/ 今天推出的Claude Enterprise计划,专为企业打造安全的

为备份驱动器制定备份计划:维护数据的3大方法

时间:2014-02-26 14:49 来源:网管之家 字体:[大 中 小]   您可能已经对您的电脑进行了备份,但其实这样还是远远不够的,其并非如您所认为的那样安全。您企业备份驱动器上的文件可能与您的主系统上的文件一样,容易受到灾难的影响。根据最近流行的恶意软件CryptoLocker的感染途径显示,连接到PC的外置驱动器——辅助硬盘驱动器,例如,用于备份的外部USB硬盘驱动器,可以像

基于开源链动 2 + 1 模式、AI 智能名片与 S2B2C 商城小程序的用户忠诚度计划

摘要:本文深入探讨了在商业环境中执行用户忠诚度计划的创新途径。通过整合开源链动 2 + 1 模式、AI 智能名片以及 S2B2C 商城小程序等先进元素,从提供福利、解决问题和创造赚钱机会三个核心方面展开详细阐述。研究表明,这些新技术和新模式的有机结合,能够为企业打造更具吸引力和影响力的用户忠诚度计划,从而实现商业效益的最大化与可持续发展。 一、引言 在当今竞争激烈且市场环境快速变化的时代,

[置顶] 2014训练计划进阶版

动态规划: 区间dp,树状dp,数位dphdu3555, sgu258, sgu390  队列优化: zoj3399 最小表示法的状态压缩DP: spoj2159  专题链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38881#overview 专题链接: http://acm.hust.edu.cn/vjudg

[置顶] 2014训练计划

每个专题结束后会有5小时的专题赛~ 1、hustOJ目前支持谷歌、火狐浏览器等部分浏览器。 2、欢迎吐槽~ 3、推荐该阶段用书(以下具体算法实现多数可在此书中找到详解):算法竞赛入门经典之训练指南(刘汝佳) 4、题解报告:专题中的题目多是经典题目,百度搜索即有详细解答~ 5、专题相关知识点红字标出,建议先百度红字部分,有助于专题学习~ 6、专题时间会在"ACM 今天你AC了吗?"(12

Windows 一键定时自动化任务神器 zTasker,支持语音报时+多项定时计划执行

简介 zTasker(详情请戳 官网)是一款完全免费支持定时、热键或条件触发的方式执行多种自动化任务的小工具,支持win7-11。其支持超过100种任务类型,50+种定时/条件执行方法,而且任务列表可以随意编辑、排列、移动、更改类型,支持任务执行日志,可覆盖win自带的热键,同时支持任务列表等数据的备份及自动更新等。 简言之,比微软系统自带的任务计划要强好几倍,至少灵活性高多了,能大幅提高电脑使

【Oracle篇】全面理解优化器和SQL语句的解析步骤(含执行计划的详细分析和四种查看方式)(第二篇,总共七篇)

💫《博主介绍》:✨又是一天没白过,我是奈斯,DBA一名✨ 💫《擅长领域》:✌️擅长Oracle、MySQL、SQLserver、阿里云AnalyticDB for MySQL(分布式数据仓库)、Linux,也在扩展大数据方向的知识面✌️ 💖💖💖大佬们都喜欢静静的看文章,并且也会默默的点赞收藏加关注💖💖💖 SQL优化续新篇,第二篇章启幕时。 优化器内藏奥秘,解析SQL步