当前位置: 首页 > 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,方…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

给网站添加live2d看板娘

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

Electron简介(附电子书学习资料)

一、什么是Electron&#xff1f; Electron 是一个由 GitHub 开发的 开源框架&#xff0c;允许开发者使用 Web技术&#xff08;HTML、CSS、JavaScript&#xff09; 构建跨平台的桌面应用程序&#xff08;Windows、macOS、Linux&#xff09;。它将 Chromium浏览器内核 和 Node.j…...

Qt/C++学习系列之列表使用记录

Qt/C学习系列之列表使用记录 前言列表的初始化界面初始化设置名称获取简单设置 单元格存储总结 前言 列表的使用主要基于QTableWidget控件&#xff0c;同步使用QTableWidgetItem进行单元格的设置&#xff0c;最后可以使用QAxObject进行单元格的数据读出将数据进行存储。接下来…...

FTPS、HTTPS、SMTPS以及WebSockets over TLS的概念及其应用场景

一、什么是FTPS&#xff1f; FTPS&#xff0c;英文全称File Transfer Protocol with support for Transport Layer Security (SSL/TLS)&#xff0c;安全文件传输协议&#xff0c;是一种对常用的文件传输协议(FTP)添加传输层安全(TLS)和安全套接层(SSL)加密协议支持的扩展协议。…...

大语言模型解析

1. Input Embedding embedding&#xff1a;将自然语言翻译成index 每个index对应一个embedding&#xff0c;embedding需要训练&#xff0c;embedding是一个数组...

【读代码】从预训练到后训练:解锁语言模型推理潜能——Xiaomi MiMo项目深度解析

项目开源地址:https://github.com/XiaomiMiMo/MiMo 一、基本介绍 Xiaomi MiMo是小米公司开源的7B参数规模语言模型系列,专为复杂推理任务设计。项目包含基础模型(MiMo-7B-Base)、监督微调模型(MiMo-7B-SFT)和强化学习模型(MiMo-7B-RL)等多个版本。其核心创新在于通过…...