当前位置: 首页 > news >正文

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

蓝桥杯备赛 | 洛谷做题打卡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后成功编译并运行出正确结果真的会感到很幸福!

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

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

相关文章:

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

蓝桥杯备赛 | 洛谷做题打卡day18 文章目录 蓝桥杯备赛 | 洛谷做题打卡day18旅行计划题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题解代码我的一些话 旅行计划 题目描述 Kira酱要去一个国家旅游。这个国家有 N N N 个城市&#xff0c;编号为 1 1 1 至 N N…...

Ultraleap 3Di配置以及在 Unity 中使用 Ultraleap 3Di手部跟踪

0 开发需求 1、硬件&#xff1a;Ultraleap 手部追踪相机&#xff08;Ultraleap 3Di&#xff09; 2、软件&#xff1a;在计算机上安装Ultraleap Gemini (V5.2) 手部跟踪软件。 3、版本&#xff1a;Unity 2021 LTS 或更高版本 4、Unity XR插件管理&#xff1a;可从软件包管理器窗…...

HarmonyOS鸿蒙学习基础篇 - Text文本组件

该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 Text文本组件是可以显示一段文本的组件。该组件从API Version 7开始支持&#xff0c;从API version 9开始&#xff0c;该接口支持在ArkTS卡片中使用。 子组件 可…...

pytorch学习笔记(十一)

优化器学习 把搭建好的模型拿来训练&#xff0c;得到最优的参数。 import torch.optim import torchvision from torch import nn from torch.nn import Sequential, Conv2d, MaxPool2d, Flatten, Linear from torch.utils.data import DataLoaderdataset torchvision.datas…...

【并发编程】 synchronized的普通方法,静态方法,锁对象,锁升级过程,可重入锁,非公平锁

目录 1.普通方法 2.静态方法 3.锁对象 4.锁升级过程 5.可重入的锁 6.不公平锁 非公平锁的 lock 方法&#xff1a; 1.普通方法 将synchronized修饰在普通同步方法&#xff0c;那么该锁的作用域是在当前实例对象范围内,也就是说对于 SyncDemosdnewSyncDemo();这一个实例对象…...

jQuery 删除元素 —— W3school 详解 简单易懂(十四)

通过 jQuery&#xff0c;可以很容易地删除已有的 HTML 元素。 删除元素/内容 如需删除元素和内容&#xff0c;一般可使用以下两个 jQuery 方法&#xff1a; remove() - 删除被选元素&#xff08;及其子元素&#xff09;empty() - 从被选元素中删除子元素 jQuery remove() 方…...

在 Linux 上搭建 Java 环境

目录 一、安装jdk 1. 挑选 jdk 版本 2. 安装 3. 验证 jdk 二、安装tomcat 1. 下载压缩包 2. 上传压缩包给 Linux &#xff08;需要用到 rz 命令&#xff09; 3. 解压压缩包&#xff08;需要用到 unzip&#xff09; 4. 进入 bin 目录 5. 给启动脚本增加可执行权限 6. 启…...

深度学习-Pytorch如何保存和加载模型

深度学习-Pytorch如何保存和加载模型 用pytorch构建模型&#xff0c;并训练模型&#xff0c;得到一个优化的模型&#xff0c;那么如何保存模型&#xff1f;然后如何又加载模型呢&#xff1f; pytorch 目前在深度学习具有重要的地位&#xff0c;比起早先的caffe&#xff0c;te…...

2.数据结构 顺序表(自留笔记)

文章目录 一.静态顺序表&#xff1a;长度固定二.动态顺序表1.下面证明原地扩容和异地扩容代码如下&#xff1a;2.下面是写一段Print&#xff0c;打印数字看看&#xff1a;3.头插4.尾删5.头删6.越界一定会报错吗7.下标插入8.下标删除9.查找数字10.应用&#xff1a;利用顺序表写一…...

将python打包成exe文件

将python打包成exe文件 文章目录 将python打包成exe文件1.安装PyInstaller2.配置pyinstaller到环境变量3.打包 以上一篇文章&#x1f517;用python删除重复文件并放入回收站为例&#xff0c;演示了如何用python写一个删除重复文件并放入回收站的功能代码&#xff0c;但是每次都…...

大数据处理,Pandas与SQL高效读写大型数据集

大家好&#xff0c;使用Pandas和SQL高效地从数据库中读取、处理和写入大型数据集&#xff0c;以实现最佳性能和内存管理&#xff0c;这是十分重要的。 处理大型数据集往往是一项挑战&#xff0c;特别是在涉及到从数据库读取和写入数据时。将整个数据集加载到内存中的传统方法可…...

【2024年5月备考新增】《软考高项论文专题 (2)论文背景(合集)》

1 论文的项目背景 1.1 论文写法 段落字数 - 正文全部字数不少于2000字孙悟空大闹天宫,被如来镇压,唐僧收服孙悟空,开始去西天取经。背景500字因为路途遥远,所以需要九九八十一难,才能取得正经。过渡段150字第一难、第二难 … 第八十一难过程1300字取得正经,唐僧只受了八…...

Mysql复习1--理论基础+操作实践--更新中

Mysql 索引索引的分类索引失效sql优化 删除数据库数据恢复 索引InnoDB引擎MyISAM引擎Memory引擎Btree索引支持支持支持hash索引不支持不支持支持R-tree索引不支持支持不支持Full-text索引5.6版本以后支持支持不支持 索引 解释说明: 索引指的是帮助mysql高效的获取数据的结构叫…...

微信小程序打卡定位实现方案

1背景 业务场景是考勤打卡,在考勤打卡这个业务场景中有两个关键技术点:定位和人员识别。用户界面初步确定是用微信小程序来实现,本文就定位问题做了技术上的调研。 2调研内容 平台注意事项 获取位置 选择位置 查看位置 距离计算 定位精度 防作弊 Demo 3调研结果 3.1平台注…...

小迪安全23WEB 攻防-Python 考点CTF 与 CMS-SSTI 模版注入PYC 反编译

#知识点&#xff1a; 1、PYC 文件反编译 2、Python-Web-SSTI 3、SSTI 模版注入利用分析 各语言的SSIT漏洞情况&#xff1a; SSIT漏洞过程&#xff1a; https://xz.aliyun.com/t/12181?page1&time__1311n4fxni0Qnr0%3DD%2FD0Dx2BmDkfDCDgmrYgBxYwD&alichlgrefhtt…...

计算机毕业设计 基于SpringBoot的律师事务所案件管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

如何使用宝塔面板配置Nginx反向代理WebSocket(wss)

本章教程&#xff0c;主要介绍一下在宝塔面板中如何配置websocket wss的具体过程。 目录 一、添加站点 二、申请证书 三、配置代理 1、增加配置内容 2、代理配置内容 三、注意事项 一、添加站点 二、申请证书 三、配置代理 1、增加配置内容 map $http_upgrade $connection_…...

vulhub之redis篇

CVE-2022-0543 | redis的远程代码执行漏洞 简介 CVE-2022-0543 该 Redis 沙盒逃逸漏洞影响 Debian 系的 Linux 发行版本,并非 Redis 本身漏洞, 漏洞形成原因在于系统补丁加载了一些redis源码注释了的代码 原理分析 redis一直有一个攻击面,就是在用户连接redis后,可以通过ev…...

Lua简介和应用场景介绍

Lua 的介绍 起源&#xff1a;Lua 于 1993 年在巴西里约热内卢的天主教大学&#xff08;PUC-Rio&#xff09;由 Roberto Ierusalimschy、Waldemar Celes 和 Luiz Henrique de Figueiredo 开发。 设计目的&#xff1a;Lua 设计的主要目标是为了嵌入到其他应用程序中&#xff0c;…...

【手写数据库toadb】10 开发数据库内核开发阶段-数据库模型

数据库内核模型介绍 ​专栏内容: 手写数据库toadb 本专栏主要介绍如何从零开发,开发的步骤,以及开发过程中的涉及的原理,遇到的问题等,让大家能跟上并且可以一起开发,让每个需要的人成为参与者。 本专栏会定期更新,对应的代码也会定期更新,每个阶段的代码会打上tag,方…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

高分辨率图像合成归一化流扩展

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 1 摘要 我们提出了STARFlow&#xff0c;一种基于归一化流的可扩展生成模型&#xff0c;它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流&#xff08;TARFlow&am…...

SQL进阶之旅 Day 22:批处理与游标优化

【SQL进阶之旅 Day 22】批处理与游标优化 文章简述&#xff08;300字左右&#xff09; 在数据库开发中&#xff0c;面对大量数据的处理任务时&#xff0c;单条SQL语句往往无法满足性能需求。本篇文章聚焦“批处理与游标优化”&#xff0c;深入探讨如何通过批量操作和游标技术提…...

【QT控件】显示类控件

目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏&#xff1a;QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...

CppCon 2015 学习:Simple, Extensible Pattern Matching in C++14

什么是 Pattern Matching&#xff08;模式匹配&#xff09; ❝ 模式匹配就是一种“描述式”的写法&#xff0c;不需要你手动判断、提取数据&#xff0c;而是直接描述你希望的数据结构是什么样子&#xff0c;系统自动判断并提取。❞ 你给的定义拆解&#xff1a; ✴ Instead of …...