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

GESP2024年6月认证C++八级( 第三部分编程题（2）空间跳跃）

news 来源：原创 2025/7/17 22:15:50

参考程序：

#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;// 定义一个结构体，用于 Dijkstra 优先队列中的节点
struct Node {int v, w; // v 表示图中的节点编号，w 表示当前从源点到 v 的最短距离bool operator < (const Node &b) const {// C++ 优先队列默认是大顶堆，这里重载为距离小的优先出队return w > b.w;}
};// 假设最多 n 个挡板，我们编号为 1..n
const int MAXN = 10010;  // 挡板数量上限（可根据题目数据范围调整）
const int INF = 2000000000;// 图的邻接表表示，每个节点存储 (目标节点, 权值) 对
vector<pair<int,int>> G[MAXN*2]; // 每个挡板有两个端点，编号方案见下// 存储挡板数据
int l[MAXN], r[MAXN], h[MAXN]; // l[i], r[i] 为挡板 i 的左右横坐标，h[i] 为高度
int n, s, t; // n 挡板个数，s 起点挡板编号，t 目标挡板编号// 将挡板编号转换为节点编号：例如取左端点编号 2*i，右端点编号 2*i+1
inline int LL(int x) { return 2*x; }
inline int RR(int x) { return 2*x+1; }// Dijkstra 算法求单源最短路
int dis[MAXN*2];
bool vis[MAXN*2];
void Dijkstra(int src) {// 初始化距离为无穷大，标记都为未访问for(int i = 0; i < 2*n+2; i++) {dis[i] = INF;vis[i] = false;}// 源点距离置 0，入队dis[src] = 0;priority_queue<Node> pq;pq.push({src, 0});while(!pq.empty()) {Node cur = pq.top(); pq.pop();int u = cur.v;if(vis[u]) continue; // 如果已访问，跳过vis[u] = true;// 遍历所有从 u 出发的边for(auto &edge : G[u]) {int v = edge.first;int w = edge.second;if(!vis[v] && dis[v] > dis[u] + w) {dis[v] = dis[u] + w; // 松弛pq.push({v, dis[v]});}}}
}int main(){// 读入挡板数量和起点、终点挡板编号scanf("%d %d %d", &n, &s, &t);// 读入每个挡板的左右坐标和高度for(int i = 1; i <= n; i++){scanf("%d %d %d", &l[i], &r[i], &h[i]);// 添加挡板 i 水平移动的双向边：左端到右端，权值为挡板长度G[LL(i)].push_back({RR(i), r[i] - l[i]}); G[RR(i)].push_back({LL(i), r[i] - l[i]});}// 以下构造竖直掉落的边，采用辅助节点思路或直接加边思路任选其一// 这里以直接连边（两条边）为例：// 对于每个挡板 i 的左端点和右端点，找到其下方第一个挡板 j// 可以用两重循环暴力检查（效率 O(n^2)），寻找最低高度却高于 i 的挡板// 或者按照高度排序后逐一处理。此处示意逻辑：for(int i = 1; i <= n; i++){// 初始化记录，第一个落点挡板索引int dropL = 0, dropR = 0;for(int j = 1; j <= n; j++){if(h[j] < h[i]) { // 下方的挡板// 左端点下落：如果挡板 j 横跨了 i 的左端点位置if(l[i] >= l[j] && l[i] <= r[j]) {// 取最近的挡板（高度最大的）if(dropL == 0 || h[j] > h[dropL]) dropL = j;}// 右端点下落：如果挡板 j 横跨了 i 的右端点位置if(r[i] >= l[j] && r[i] <= r[j]) {if(dropR == 0 || h[j] > h[dropR]) dropR = j;}}}// 如果找到了下方挡板，则添加掉落边if(dropL != 0) {int dh = h[i] - h[dropL]; // 竖直高度差// 从 i 的左端点掉落到 dropL 左端点、右端点G[LL(i)].push_back({LL(dropL), dh + (l[i] - l[dropL])});G[LL(i)].push_back({RR(dropL), dh + (l[dropL] + (r[dropL]-l[dropL]) - l[i])});}if(dropR != 0) {int dh = h[i] - h[dropR];// 从 i 的右端点掉落到 dropR 左端点、右端点G[RR(i)].push_back({LL(dropR), dh + (r[i] - l[dropR])});G[RR(i)].push_back({RR(dropR), dh + (r[dropR] - r[i])});}}// 求解最短路径。源点可以取 s 挡板的任意一端（比如左端 LL(s)）Dijkstra(LL(s));// 计算答案：目标挡板 t 两端点的距离，以及可能的下落方式int ans = INF;// 直接到达目标挡板左/右端点ans = min(ans, dis[LL(t)]);ans = min(ans, dis[RR(t)]);// 如果允许从上方掉落到目标挡板（假设提前在循环中记录了落在 t 上的端点）// 也可以遍历所有节点，判断它们是否落到 t 上，并更新距离// 例如，我们可在上面循环中记录一组 “dropable” 节点，此处略写：// for(int u : dropable_to_t) ans = min(ans, dis[u] + (h[u/2] - h[t]));// 输出结果if(ans >= INF) {// 不可达，输出 -1printf("-1\n");} else {printf("%d\n", ans);}return 0;
}

GESP2024年6月认证C++八级( 第三部分编程题（2）空间跳跃）

参考程序： #include <cstdio> #include <vector> #include <queue> #include <utility> #include <cstring> using namespace std;// 定义一个结构体，用于 Dijkstra 优先队列中的节点 struct Node {int v, w; // v 表示图…...

编程日记 2025/7/17 22:15:50

使用DeepSeek定制Python小游戏——以“俄罗斯方块”为例

前言本来想再发几个小游戏后在整理一下流程的，但是今天试了一下这个俄罗斯方块的游戏结果发现本来修改的好好的的，结果后面越改越乱，前面的版本也没保存，根据AI修改他是在几个版本改来改去，想着要求还是不能这么高。…...

编程日记 2025/7/17 22:09:34

Linux中安装mysql8，转载及注意事项

一、先前往官网下载mysql8 下载地址： https://dev.mysql.com/downloads/选择Linux 二、删除Linux中的mysql（如果有的话），上传安装包 1、先查看mysql是否存在，命令如下： rpm -qa|grep -i mysql如果使用这…...

编程日记 2025/7/17 21:47:58

网站即时备份,网站即时备份的方法有哪些

网站数据的安全性与业务连续性直接关系到企业的核心竞争力。无论是因硬件故障、人为误操作、网络攻击还是自然灾害，数据丢失或服务中断都可能带来难以估量的损失。因此，网站即时备份成为保障业务稳定性的关键技术手段。一、核心即时备份技术方案云服…...

编程日记 2025/6/29 5:16:37

LVM扩容小计

文章目录 [toc]当前磁盘使用问题分析关键问题定位推荐解决方案方案一：扩展根分区（LVM 动态扩容）方案二：清理磁盘空间（紧急临时处理） 当前磁盘使用问题分析根据你的磁盘信息，根文件系统 (/) 已…...

编程日记 2025/6/29 5:15:10

【2025软考高级架构师】——案例分析总结（13）

摘要本文对2025年软考高级架构师的考纲及案例分析进行了总结。内容涵盖系统规划、架构设计、系统建模、安全架构、可靠性分析、大数据架构等多方面知识点，还涉及软件质量特性、系统流程图与数据流图、嵌入式系统架构、分布式系统设计等考查内容，详细列…...

编程日记 2025/6/29 5:15:09

Jedis 通过 Jedis 可以连接 Redis 服务器。通过 Maven 引入 Jedis 依赖。  <dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId><versi…...

编程日记 2025/7/17 9:03:17

aidermacs开源程序使用 Aider 在 Emacs 中进行 AI 配对编程

一、软件介绍文末提供程序和源码下载 Aidermacs 通过集成 Aider（最强大的开源 AI 配对编程工具之一）为 Emacs 带来了 AI 驱动的开发。如果您缺少 Cursor，但更喜欢生活在 Emacs 中，Aidermacs 提供了类似的 AI 功能，同…...

编程日记 2025/6/29 5:23:18

HarmonyOS NEXT——DevEco Studio的使用（还没写完）

一、IDE环境的搭建 Windows环境运行环境要求为保证DevEco Studio正常运行，建议电脑配置满足如下要求： 操作系统：Windows10 64位、Windows11 64位内存：16GB及以上硬盘：100GB及以上分辨率：1280*8…...

编程日记 2025/7/12 16:21:34

使用PageHelper实现分页查询（详细）

一：需求分析与设计 1.1 产品原型 （1）分页展示，每页展示10条数据，根据员工姓名进行搜索 （2）业务规则 1.2 接口设计 （1）操作：查询，请求方式&#xf…...

编程日记 2025/6/29 5:14:52

神经网络基础-从零开始搭建一个神经网络

一、什么是神经网络人工神经网络（Articial Neural Network，简写为ANN）也称为神经网络（NN),是一种模仿生物神经网络和功能的计算模型，人脑可以看做是一个生物神经网络，由众多的神经元连接而成，…...

编程日记 2025/6/29 5:17:33

数据库原理与应用实验二题目七

利用sql建立教材数据库，并定义以下基本表：学生（学号，年龄，性别，系名）教材（编号，书名，出版社编号，价格）订购（学号，书号，数量）出版社（编号，名称，地址） 1定义主码、外码、和价格、数量的取值范围。 2 在三个表中输入若干记录，注意如果输入违反完整…...

编程日记 2025/6/29 6:24:54

如何在 CentOS 7 命令行连接 Wi-Fi？如何在 Linux 命令行连接 Wi-Fi？

如何在 CentOS 7 命令行连接 Wi-Fi？如何在 Linux 命令行连接 Wi-Fi？ 摘要本教程覆盖如何在多种 Linux 发行版下通过命令行连接 Wi-Fi，包括： CentOS 7、Ubuntu、Debian、Arch Linux、Fedora、Alpine Linux、Kali Linux、OpenSU…...

编程日记 2025/7/9 22:01:22

【学习笔记】强化学习：实用方法论

作者选择了由 Ian Goodfellow、Yoshua Bengio 和 Aaron Courville 三位大佬撰写的《Deep Learning》(人工智能领域的经典教程，深度学习领域研究生必读教材),开始深度学习领域学习，深入全面的理解深度学习的理论知识。之前的文章参考下面的链接&#xf…...

编程日记 2025/6/29 5:18:51

ElasticSearch深入解析（十）：字段膨胀（Mapping 爆炸）问题的解决思路

文章目录一、核心原理：动态映射的双刃剑1. 动态映射的工作机制2. 映射爆炸的触发条件3. 底层性能损耗二、典型场景与案例分析1. 日志系统：动态标签引发的灾难2. 物联网数据：设备属性的无序扩展三、系统性解决方案1. 架构层优化2. 配置层控…...

编程日记 2025/7/9 23:23:02

react18基础速成

1、项目搭建 npx create-react-app my-react-app（项目名） cd 项目名进入项目目录终端输入 npm start 启动项目浏览器查看项目搭建成功 2、JSX JavaScript语法和HTML语法写在一起就是JSX语法 jsx只能返回一个根元素，即最外层的div&a…...

编程日记 2025/6/29 5:14:58

18、状态库：中央魔法仓库——React 19 Zustand集成

一、量子熔炉的诞生 "Zustand是记忆水晶的量子纠缠体，让状态流无需魔杖驱动即可自洽！"霍格沃茨炼金术研究院的工程师挥动魔杖，Zustand 的原子化状态流在空中交织成星轨矩阵。 ——基于《魔法国会》第2025号协议，Zustan…...

编程日记 2025/7/7 12:50:16

PyCharm中全局搜索无效

发现是因为与搜狗快捷键冲突了，把框选的那个勾选去掉或设置为其他键就好了...

编程日记 2025/7/9 3:50:38

【Hive入门】Hive与Spark SQL深度集成：执行引擎性能全面对比与调优分析

目录引言 1 Hive执行引擎架构演进 1.1 Hive执行引擎发展历程 1.2 执行引擎架构对比 1.2.1 MapReduce引擎架构 1.2.2 Tez引擎架构 1.2.3 Spark引擎架构 2 执行引擎切换与配置指南 2.1 引擎切换配置方法 2.1.1 全局配置 2.1.2 会话级配置 2.2 资源管理配置 2.2.1 T…...

编程日记 2025/6/29 6:52:52

【算法基础】快速排序算法 - JAVA

一、算法基础 1.1 什么是快速排序快速排序（Quick Sort）是一种高效的分治排序算法，由英国计算机科学家Tony Hoare于1960年提出。它的核心思想是： 选择一个基准元素（pivot）将数组分成两部分：小…...

编程日记 2025/6/29 5:14:51

Ubuntu 24.04 通过 update-alternatives 切换GCC版本

在 Ubuntu 中编译项目, 会遇到项目依赖于某个特定版本 GCC 的情况, 例如 Ubuntu 24.04 的默认 GCC 版本是 13, 但是有一些项目需要 GCC11才能正常编译, 在 Ubuntu 24.04 默认的环境下编译会报错. 这时候可以通过 update-alternatives 切换GCC版本. all 展示全部用--all参数会…...

编程日记 2025/7/9 3:49:38

Linux中的时间同步

一、时间同步服务扩展总结 1. 时间同步的重要性多主机协作需求：在分布式系统、集群、微服务架构中，时间一致性是日志排序、事务顺序、数据一致性的基础。安全协议依赖：TLS/SSL证书、Kerberos认证等依赖时间有效性，时间偏差可能…...

编程日记 2025/6/29 5:52:56

数据赋能（209）——质量管理——时效性原则

概述数据时效性原则在数据收集、处理、分析和应用的过程中确保数据在特定时间范围内保持其有效性和相关性，为决策提供准确、及时的依据。在快速变化的市场环境中，数据时效性对于企业的竞争力和决策效率具有决定性的影响。原则定义数据时效性原则&a…...

编程日记 2025/7/14 11:57:13

AnimateCC教学：照片旋转飞舞并爆炸....

1.核心代码: <!DOCTYPE html> <html><head><meta charset="UTF-8" /><title>旋转照片演示</title><script src="https://code.createjs.com/1.0.0/createjs.min.js"></script><script src="http…...

编程日记 2025/6/29 5:15:21

腾讯混元-DiT 文生图

1 混元-DiT所需的模型大小一共是41G https://huggingface.co/Tencent-Hunyuan/HunyuanDiT https://colab.research.google.com/ HunyuanDiT_jupyter.ipynb %cd /content !GIT_LFS_SKIP_SMUDGE1 git clone -b dev https://github.com/camenduru/HunyuanDiT %cd /content/Hun…...

编程日记 2025/6/29 8:06:30

优化高搜索量还是低竞争关键词？SEO策略解析

在2025年的SEO环境中，关键词研究仍然是优化网站排名的基石。然而，一个常见的问题困扰着SEO从业者：在使用谷歌关键词规划师（Google Keyword Planner）进行关键词研究时，是否应该优先选择月搜索量较高的关键词…...

编程日记 2025/6/29 5:15:01

对比表格：数字签名方案、密钥交换协议、密码学协议、后量子密码学——密码学基础

文章目录一、数字签名方案1.1 ECDSA：基于椭圆曲线的数字签名算法1.2 EdDSA：Edwards曲线数字签名算法1.3 RSA-PSS：带有概率签名方案的RSA1.4 数字签名方案对比二、密钥交换协议2.1 Diffie-Hellman密钥交换2.2 ECDH：椭圆曲线Diffi…...

编程日记 2025/6/29 5:18:09

在MySQL中建索引时需要注意哪些事项？

在 MySQL 中建立索引是优化查询性能的重要手段，但不当的索引设计可能导致资源浪费、性能下降甚至拖慢写入速度。所以我们我们首先要判断对于一个字段或者一些字段要不要建立索引。适合建立索引的字段通常是： 主键字段：MySQL 会自动为主键…...

编程日记 2025/6/29 5:45:36

dstack 是 Kubernetes 和 Slurm 的开源替代方案，旨在简化 ML 团队跨顶级云、本地集群和加速器的 GPU 分配和 AI 工作负载编排

一、软件介绍文末提供程序和源码下载 dstack 是 Kubernetes 和 Slurm 的开源替代方案，旨在简化顶级云和本地集群中 ML 团队的 GPU 分配和 AI 工作负载编排。二、Accelerators 加速器 dstack 支持 NVIDIA 开箱即用的、 AMD 、 Google TPU 和 Intel Gaudi 加速器…...

编程日记 2025/7/10 19:06:16

Linux 的 epoll 与 Windows 的 IOCP 详解

如果你在搞网络编程或者高性能服务器，一定要搞懂这两个模型——它们都是用来解决“多路复用”问题的工具，让你同时处理大量的网络连接变得高效又可控。一、什么是“多路复用”？简单说，就是你手里有很多任务（比如很多客户端的请求），但系统的核心（线程或者进程）资源…...

编程日记 2025/6/29 5:15:02

C# 方法(控制流和方法调用)

本章内容: 方法的结构方法体内部的代码执行局部变量局部常量控制流方法调用返回值返回语句和void方法局部函数参数值参数引用参数引用类型作为值参数和引用参数输出参数参数数组参数类型总结方法重载命名参数可选参数栈帧递归控制流方法包含了组成程序的…...

编程日记 2025/6/29 5:14:59

Webug4.0靶场通关笔记11- 第15关任意文件下载与第16关MySQL配置文件下载

目录一、文件下载二、第15关任意文件下载 1.打开靶场 2.源码分析 3.渗透实战三、第16关 MySQL配置文件下载 1.打开靶场 2.源码分析 3.渗透实战 （1）Windows系统 （2）Linux系统四、渗透防御一、文件下载本文通过…...

编程日记 2025/6/29 5:27:12

More Effective C++学习笔记

条款1 指针与引用的区别条款2 尽量使用C风格的类型转换条款3 不要对数组使用多态条款4 避免无用的缺省构造函数条款5 谨慎定义类型转换函数条款6 自增(increment)、自减(decrement)操作符前缀形式与后缀形式的区别条款7 不要重载“&&”,“||”, 或“,” 条款8 理…...

编程日记 2025/6/29 5:15:08

如何设计抗Crosstalk能力强的PCB镀穿孔

一个高速PCB通道通常包含芯片SerDes IP、走线、穿层Via、连接器和Cable。其中内层走线对于Crosstalk影响甚微（请参考什么？ Stripline的FEXT为0！ Why？ ），而Via与连接器由于其参考路径较差的关系&#xff0c…...

编程日记 2025/7/9 4:00:08

多线程系列三：这就是线程的状态？

1.认识线程的状态 NEW：Thread对象已经创建好了，但还没有调用start方法在系统中创建线程 RUNNABLE：就绪状态，表示这个线程正在CPU上执行，或准备就绪，随时可以去CPU上执行 BLOCKED：表示由于锁竞争…...

编程日记 2025/6/29 5:15:03

生成对抗网络（GAN, Generative Adversarial Network）

定义：一种通过对抗训练让两个神经网络（生成器与判别器）相互博弈的深度学习模型，用于生成逼真的数据（如图像、音频、文本等）。一、核心思想：对抗博弈 GAN的核心是让两个神…...

编程日记 2025/7/5 9:50:33

用可视化学习逆置法

1.逆置法思路目标：将这个彩色数组向右旋转3步 🔴1 → 🟠2 → 🟡3 → 🟢4 → 🔵5 → 🟣6 → ⚪7我们希望得到 🔵5 → 🟣6 → ⚪7 → 🔴1 → 🟠…...

编程日记 2025/6/29 5:44:04

家用服务器 Ubuntu 服务器配置与 Cloudflare Tunnel 部署指南

Ubuntu 服务器配置与 Cloudflare Tunnel 部署指南本文档总结了我们讨论的所有内容，包括 Ubuntu 服务器配置、硬盘扩容、静态 IP 设置以及 Cloudflare Tunnel 的部署步骤。目录硬盘分区与扩容设置静态 IPCloudflare Tunnel 部署SSH 通过 Cloudflare Tunnel常见…...

编程日记 2025/6/29 5:36:37

【C++篇】类和对象(上）

目录类的定义格式： 内敛函数： 类与struct的区别： 类的访问权限： 类域： 类的实例化： 对象大小： 计算对象的大小时，也存在内存对齐（与结构体一样）&…...

编程日记 2025/7/17 9:58:12

ES6/ES11知识点续一

模板字符串在 ECMAScript（ES）中，模板字符串（Template Literals）是一种非常强大的字符串表示方式，它为我们提供了比传统字符串更灵活的功能，尤其是在处理动态内容时。模板字符串通过反引号&…...

编程日记 2025/6/29 7:47:37

ES6入门---第二单元模块二：关于数组新增

一、扩展运算符。。。 1、可以把ul li转变为数组 <script>window.onloadfunction (){let aLi document.querySelectorAll(ul li);let arrLi [...aLi];arrLi.pop();arrLi.push(asfasdf);console.log(arrLi);};</script> </head> <body><ul><…...

编程日记 2025/6/29 5:18:00

使用python加edge-tts实现文字转语音

文章目录使用python加edge-tts实现文字转语音1. 使用 Python 安装 Edge-TTS2. 进一步优化3. 使用说明3.1 查看语音列表3.2 单语音转换3.3 批量生成所有语音3.4 改进亮点4. 使用教程最终代码文章创作不易使用python加edge-tts实现文字转语音 Edge-TTS（edge-tts Python 模块）本…...

编程日记 2025/6/29 5:20:50

如何用CSS实现HTML元素的旋转效果：从基础到高阶应用

在网页设计中，元素的动态效果能显著提升用户体验，而旋转效果是其中最常用的交互方式之一。CSS的transform属性提供了强大的旋转功能，结合动画（animation）和过渡（transition），开发者可…...

编程日记 2025/7/9 20:47:58

轻量级RTSP服务模块：跨平台低延迟嵌入即用的流媒体引擎

在音视频流媒体系统中，RTSP（Real-Time Streaming Protocol）服务模块通常扮演着“视频分发中心”的角色，它将编码后的音视频内容转为标准的流媒体格式，供客户端（播放器、云端平台、AI模块等）拉流…...

编程日记 2025/7/10 13:38:42

AVInputFormat 再分析

AVInputFormat 是 FFmpeg 中用于描述输入格式（如文件容器、设备流等）的核心结构体，属于 libavformat 库的一部分。其主要功能是定义解封装（demuxing）过程中如何解析不同格式的输入数据。以下是其关键特性与使用方式的总…...

编程日记 2025/7/11 16:10:36

wpf CommandParameter 传递MouseWheelEventArgs参数

在 WPF 中通过 CommandParameter 传递 MouseWheelEventArgs 参数时，需结合 ‌事件到命令的转换机制‌ 和 ‌参数转换器‌ 来实现。以下是具体实现方案及注意事项： 一、核心实现方法 1. ‌使用 EventToCommand 传递原始事件参数‌ 通过 Interaction.Tr…...

编程日记 2025/6/29 8:06:26

摆脱养生误区泥沼，拥抱科学养生阳光

在养生的道路上，人们总是满怀热忱地追寻健康之道，然而，诸多似是而非的养生误区却如同泥沼一般，让不少人深陷其中，难以自拔。只有奋力摆脱这些误区的束缚，才能拥抱科学养生的温暖阳光，真正实现身…...

编程日记 2025/6/29 5:15:04

FreeRtos实战从入门到精通--任务创建和删除（动态方法）--事了拂衣去，深藏功与名

FreeRtos是之前的一些聪明的工程师写的免费且开源的嵌入式实时操作系统代码，由于我们实际工作中不需要再去写rtos，我们只需要用就行了，所以博主这里只分享项目工程实战相关的内容，具体rtos源码，可以无需理会&#xff0…...

编程日记 2025/6/29 6:48:22

卷积神经网络进化史：从LeNet-5到现代架构的完整发展脉络

摘要本文系统梳理卷积神经网络(CNN)从诞生到繁荣的发展历程。从1998年Yann LeCun开创性的LeNet-5出发，重点解析2012年引爆深度学习革命的AlexNet，并详细拆解后续演进的五大技术方向：网络深度化(VGG)、卷积功能强化(ResNet)、检测任务迁移(F…...

编程日记 2025/7/16 12:42:06

《Qt C++ 项目中升级 GCC 版本的完整指南》

Qt C++ 项目中升级 GCC 版本的完整指南在 Qt C++ 项目中升级 GCC 版本可能会影响编译工具链、Qt 库兼容性以及项目配置。以下是针对不同操作系统的升级步骤和注意事项：一、为什么需要升级 GCC 版本？ C++ 标准支持：新版本 GCC 支持 C++17/20 等新标准特性性能优化：编译速…...

编程日记 2025/6/29 8:00:14

相关文章：