贪心 + 分层图bfs,newcoder 76652/B
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
https://ac.nowcoder.com/acm/contest/76652/B
二、解题报告
1、思路分析
以(0, 0) 为起点,进行bfs
bfs可以每次扩展一层,我们每次选择可扩展位置中字符最小的那些
这样我们会进行多路增广
由于路径长度为n + m - 1,所以只需增广 n + m - 1 次
2、复杂度
时间复杂度: O(NMlogNM)空间复杂度:O(NM)
3、代码详解
#include <bits/stdc++.h>using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int n, m;std::cin >> n >> m;std::vector<std::string> g(n);for (int i = 0; i < n; ++ i)std::cin >> g[i];int t = n + m - 1;std::string ans;std::queue<int> q;q.push(0);std::vector<int> vis(n * m);vis[0] = true;constexpr int dir[3]{1, 0, 1};while (t --) {ans += g[q.front() / m][q.front() % m];std::vector<int> buf;while(q.size()) {int i = q.front();q.pop();int x = i / m, y = i % m;for (int k = 0; k < 2; ++ k) {int nx = dir[k] + x, ny = dir[k + 1] + y;if (nx < 0 || ny < 0 || nx >= n || ny >= m || vis[nx * m + ny]) continue;buf.push_back(nx * m + ny);vis[nx * m + ny] = true;}}std::sort(buf.begin(), buf.end(), [&](int i, int j) -> bool{return g[i / m][i % m] < g[j / m][j % m];});for (int i = 0; i < buf.size() && g[buf[0] / m][buf[0] % m] == g[buf[i] / m][buf[i] % m]; ++ i)q.push(buf[i]);}std::cout << ans;
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();int main () {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifint T = 1;// std::cin >> T;while (T --)solve();return 0;
}
相关文章:
贪心 + 分层图bfs,newcoder 76652/B
目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 https://ac.nowcoder.com/acm/contest/76652/B 二、解题报告 1、思路分析…...
如何在Linux上部署Java Web应用程序
在Linux上部署Java Web应用程序是一个常见的任务,本文将介绍一种常用的方法,分为以下几个步骤: 准备服务器 首先,你需要准备一台运行Linux操作系统的服务器。你可以选择使用各种不同的Linux发行版,如Ubuntu、CentOS等…...
SpringBoot 整合 Excel 轻松实现数据自由导入导出
01、背景介绍 在实际的业务系统开发过程中,操作 Excel 实现数据的导入导出基本上是个非常常见的需求。 之前,我们有介绍一款非常好用的工具:EasyPoi,有读者提出在数据量大的情况下,EasyPoi 会占用内存大,…...
PyTorch 基础学习(13)- 混合精度训练
系列文章: 《PyTorch 基础学习》文章索引 基本概念 混合精度训练是深度学习中一种优化技术,旨在通过结合高精度(torch.float32)和低精度(如 torch.float16 或 torch.bfloat16)数据类型的优势,…...
Mycat分片-垂直拆分
目录 场景 配置 测试 全局表配置 续接上篇:MySQ分库分表与MyCat安装配置-CSDN博客 续接下篇:Mycat分片-水平拆分-CSDN博客 场景 在业务系统中, 涉及以下表结构 ,但是由于用户与订单每天都会产生大量的数据, 单台服务器的数据 存储及处理能力是有限…...
一元四次方程求解-【附MATLAB代码】
目录 前言 求解方法 编辑 MATLAB验证 附:一元四次方程的故事 前言 最近在研究机器人的干涉(碰撞)检测,遇到了一个问题,就是在求椭圆到原点的最短距离时,构建的方程是一个一元四次方程。无论是高中的…...
【极限性能,尽在掌控】ROG NUC:游戏与创作的微型巨擘
初见ROG NUC,你或许会为它的小巧体型惊讶。然而,这看似不起眼的机身内,蕴藏着游戏、创意的强大能量。 掌中风暴,性能无界 ROG NUC搭载英特尔高性能处理器,配合高速NVMe SSD固态硬盘以及可选的高端独立显卡(…...
Ecosmos开启公测,将深度赋能CIOE中国光博会元宇宙参会新体验
如今,生成式AI技术的发展,极大地降低了3D数字资产的制作成本,元宇宙作为一种可以无缝将物理和数字资产进行融合的技术,在推动电子产业数字化进程、助力产业高质量发展的方面展现出了巨大的潜力。 当前,发展新质生产力是…...
【Kubernetes】k8s集群之包管理器Helm
目录 一.Helm概述 1.Helm的简介 2.Helm的三个重要概念 3.Helm2与Helm3的的区别 二.Helm 部署 1.安装 helm 2.使用 helm 安装 Chart 3.Helm 自定义模板 4.Helm 仓库 每个成功的软件平台都有一个优秀的打包系统,比如Debian、Ubuntu 的 apt,RedH…...
嵌入式linux系统镜像制作day3(构建镜像)
点击上方"蓝字"关注我们 01、上节回顾 嵌入式linux系统镜像制作day1嵌入式linux系统镜像制作day2提前下载好准备工具,不然失败了大眼瞪小眼。 02、构建 Poky 的 Sato 镜像1 环境: ubuntu18.04poky版本:Dizzy 工具git 在开始之前,针对不同的发行版,需要先执行…...
【生日视频制作】教师节中秋节国庆节车模特美女举牌AE模板修改文字软件生成器教程特效素材【AE模板】
教师节中秋节国庆节车模特美女举牌生日视频制作教程AE模板改文字软件生成器素材 怎么如何做的【生日视频制作】教师节中秋节国庆节车模特美女举牌AE模板修改文字软件生成器教程特效素材【AE模板】 生日视频制作步骤: 安装AE软件下载AE模板把AE模板导入AE软件修改图…...
RongCallKit iOS 端本地私有 pod 方案
RongCallKit iOS 端本地私有 pod 方案 需求背景 适用于源码集成 CallKit 时,使用 pod 管理 RTC framework 以及源码。集成 CallKit 时,需要定制化修改 CallKit 的样式以及部分 UI 功能。适用于 CallKit 源码 Debug 调试便于定位相关问题。 解决方案 从…...
C++11:可变参数模板
目录 一、概述 二、场景 1.深拷贝的类 2.浅拷贝的类 C使用指南 一、概述 // Args是一个模板参数包,args是一个函数形参参数包 // 声明一个参数包Args...args,这个参数包中可以包含0到任意个模板参数。 template <class ...Args> void ShowList(…...
C++ 与 QML 之间进行数据交互的几种方法
https://www.cnblogs.com/jzcn/p/17774676.html 一、属性绑定 这是最简单的方式,可以在QML中直接绑定C 对象的属性。通过在C 对象中使用Q_PROPERTY宏定义属性,然后在QML中使用绑定语法将属性与QML元素关联起来。 1. person.h #include <QObject&g…...
Javaweb学习之Vue项目的创建(二)
学习资料 Vue.js - 渐进式 JavaScript 框架 | Vue.js (vuejs.org) 准备工作都做完了,接下来开始Vue的正式学习。 第一步,打开VS Code 在VS Code里,我们也需要使用到终端,如果不是以管理员身份打开,在新建Vue项目的时候…...
『深度长文』4种有效提高LLM输出质量的方法!
LLM,全称Large Language Model,意为大型语言模型,是一种基于深度学习的AI技术,能够生成、理解和处理自然语言文本,也因此成为当前大多数AI工具的核心引擎。LLM通过学习海量的文本数据,掌握了词汇、语法、语…...
【工业机器人】工业异常检测大模型AnomalyGPT
AnomalyGPT 工业异常检测视觉大模型AnomalyGPT AnomalyGPT: Detecting Industrial Anomalies using Large Vision-Language Models AnomalyGPT是一种基于大视觉语言模型(LVLM)的新型工业异常检测(IAD)方法。它利用LVLM的能力来理…...
【PGCCC】PostgreSQL案例:planning time超长问题分析#PG初级
在使用 PostgreSQL 时,查询的执行计划(planning time)有时会出现异常长的情况,这可能会影响数据库的整体性能。分析和解决这种问题可以从多个角度入手,以下是常见原因和相应的解决思路: 1. 统计信息不准确…...
【图文并茂】ant design pro 如何给后端发送 json web token - 请求拦截器的使用
上一节有讲过 【图文并茂】ant design pro 如何对接后端个人信息接口 还差一个东西,去获取个人信息的时候,是要发送 token 的,不然会报 403. 就是说在你登录之后才去获得个人信息。这样后端才能知道是谁的信息。 token 就代码了某个人。 …...
【微信小程序】自定义组件 - behaviors
1. 什么是 behaviors 2. behaviors 的工作方式 3. 创建 behavior 调用 Behavior(Object object) 方法即可创建一个共享的 behavior 实例对象,供所有的组件使用: 4. 导入并使用 behavior 5. behavior 中所有可用的节点 6. 同名字段的覆盖和组合规则* 关…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...


