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

【NOIP提高组】引水入城

【NOIP提高组】引水入城


💐The Begin💐点点关注,收藏不迷路💐

在这里插入图片描述

在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊,刚好构成一个N行M列的矩形,如上图所示,其中每个格子都代表一座城 市,每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施 有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的 蓄水池中。因此,只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通 过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是 存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。 由于第N行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利 设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干 旱区中不可能建有水利设施的城市数目。

输入

输入的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N和M,表示矩形的规模。 接下来N行,每行M个正整数,依次代表每座城市的海拔高度。输入的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N和M,表示矩形的规模。 接下来N行,每行M个正整数,依次代表每座城市的海拔高度。

输出

输出有两行。如果能满足要求,输出的第一行是整数1,第二行是一个整数,代表最少 建造几个蓄水厂;如果不能满足要求,输出的第一行是整数0,第二行是一个整数,代表有 几座干旱区中的城市不可能建有水利设施。

样例输入

2 5
9 1 5 4 3
8 7 6 1 2

样例输出

1
1

提示

【样例说明】只需要在海拔为9的那座城市中建造蓄水厂,即可满足要求。

在这里插入图片描述

C语言实现:

#include <stdio.h>
#include <string.h>// 定义二维数组的最大维度,可根据实际需求调整
#define MAX_SIZE 520// 存储地形高度信息的二维数组
int h[MAX_SIZE][MAX_SIZE];
// 用于标记每个位置是否已被访问的二维数组
int vis[MAX_SIZE][MAX_SIZE];
// 记录从每个位置出发能到达的最左列索引的二维数组
int l[MAX_SIZE][MAX_SIZE];
// 记录从每个位置出发能到达的最右列索引的二维数组
int r[MAX_SIZE][MAX_SIZE];
// 定义四个方向的偏移量,用于在二维数组中移动
int fx[4][2] = { {0, -1}, {-1, 0}, {1, 0}, {0, 1} };
// 用于计数的变量,根据不同情况有不同用途
int cnt;
// 存储二维数组的行数和列数
int n, m;
// 标记是否能从第一行到达最后一行所有位置的标志变量
int flag = 1;// 深度优先搜索函数,用于遍历二维数组
void dfs(int x, int y) {vis[x][y] = 1; // 标记当前位置 (x, y) 已被访问int xx, yy;// 遍历四个方向for (int i = 0; i < 4; i++) {xx = x + fx[i][0];yy = y + fx[i][1];// 判断新位置是否在合法范围内if (xx < 1 || yy < 1 || xx > n || yy > m) continue;// 如果当前位置的高度小于等于新位置的高度,跳过if (h[x][y] <= h[xx][yy]) continue;// 如果新位置未被访问,则递归调用dfs继续探索if (!vis[xx][yy]) dfs(xx, yy);// 更新当前位置能到达的最左列索引l[x][y] = l[x][y] < l[xx][yy]? l[x][y] : l[xx][yy];// 更新当前位置能到达的最右列索引r[x][y] = r[x][y] > r[xx][yy]? r[x][y] : r[xx][yy];}
}int main() {// 读取二维数组的行数和列数scanf("%d %d", &n, &m);// 初始化l数组为较大的值,这里使用0x3f作为较大值的表示memset(l, 0x3f, sizeof(l));// 初始化最后一行的最左列索引和最右列索引为对应的列号for (int i = 1; i <= m; i++) {l[n][i] = r[n][i] = i;}// 读取二维数组中的地形高度信息for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%d", &h[i][j]);}}// 从第一行的每个位置开始进行深度优先搜索for (int i = 1; i <= m; i++) {if (!vis[1][i]) dfs(1, i);}// 检查最后一行的每个位置是否都被访问到for (int i = 1; i <= m; i++) {if (!vis[n][i]) {flag = 0;cnt++;}}// 如果最后一行存在未被访问到的位置if (flag == 0) {printf("0\n%d", cnt);return 0;}// 用于逐步扩展覆盖范围的变量,表示当前覆盖范围的最左列int left = 1;while (left <= m) {int maxr = 0;// 遍历第一行的每个位置for (int i = 1; i <= m; i++) {if (l[1][i] <= left) {maxr = maxr > r[1][i]? maxr : r[1][i];}}cnt++;left = maxr + 1;}printf("1\n%d", cnt);return 0;
}

在这里插入图片描述


💐The End💐点点关注,收藏不迷路💐

相关文章:

【NOIP提高组】引水入城

【NOIP提高组】引水入城 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 在一个遥远的国度&#xff0c;一侧是风景秀美的湖泊&#xff0c;另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊&#xff0c;刚好构成一个N行M列的矩形&#xff…...

openvino python推理demo

openvino python推理demo import openvino from openvino.runtime import Core import numpy as np import argparse import hashlib import os import ioclass OpenvinoInfer:def __init__(self,device_id0):self.device_iddevice_idself.ie Core()self.available_devices …...

JavaWeb项目-----博客系统

一.设计数据库 1.创建数据库 create database if not exists java108_blog_system character set utf8; drop table if exists user; drop table if exists blog;2.创建博客列表 create table blog(blogId int primary key auto_increment,title varchar(20),content varcha…...

GY-56 (VL53L0X) 激光测距

文章目录 一、GY-56 简介二、引脚功能三、通信协议1.串口协议&#xff1a; 当 GY-56 PS 焊点开放时候使用(默认)&#xff08;1&#xff09;串口通信参数&#xff08;默认波特率值 9600bps&#xff09;&#xff08;2&#xff09;模块输出格式&#xff0c;每帧包含 8-13 个字节&a…...

当今陪玩系统小程序趋势,陪玩系统源码搭建后的适用于哪些平台

一、市场规模持续扩大 随着全球游戏市场的不断膨胀&#xff0c;游戏陪玩行业正逐渐从一个新兴领域成长为游戏产业链中不可或缺的一环。据《2024年1~6月中国游戏产业报告》显示&#xff0c;今年上半年&#xff0c;国内游戏市场实际销售收入达到1472.67亿元&#xff0c;同比增长…...

qt QListWidget详解

1、概述 QListWidget 是 Qt 框架中的一个类&#xff0c;它提供了一个基于模型的视图&#xff0c;用于显示项目的列表。QListWidget 继承自 QAbstractItemView 并为项目列表提供了一个直观的接口。与 QTreeView 和 QTableView 不同&#xff0c;QListWidget 是专门为单行或多行项…...

java ssm 校园快递物流平台 校园快递管理系统 物流管理 源码 jsp

一、项目简介 本项目是一套基于SSM的校园快递物流平台&#xff0c;主要针对计算机相关专业的和需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、数据库脚本、软件工具等。 项目都经过严格调试&#xff0c;确保可以运行&#xff01; 二、技术实现 ​后端技术&#x…...

西安电子科技大学考研网报审核通过了,然后呢?

报考西安电子科技大学的宝贝们&#xff0c;考研网上确认已经截止的同学们&#xff0c;不用担心&#xff01; 最近&#xff0c;有很多同学问到一个问题&#xff1a;网上确认时看到有消息说禁止使用海马体照片&#xff0c;但我明明用了海马体的照片&#xff0c;审核却通过了&…...

pandas习题 051:将字符串数据读取到 DataFrame

编码题)有以下逗号隔开和空格隔开的字符串数据,如何将它读取为 DataFrame ? data = ‘’’ a,b,c 1,3,4 2,4,5 ‘’’ data2 = ‘’’ a b c 1 13 214 2 4 15 ‘’’ Python 代码如下:import pandas as pd import iodata = a,b,c 1,3,4 2,4,5 df = pd.read_csv(io.Stri…...

改进探路者算法复现

本文所涉及所有资源均在 传知代码平台 可获取。 目录 一、背景及意义介绍 (一)背景 ࿰...

PostgreSQL 学习笔记:PostgreSQL 主从复制

PostgreSQL 笔记&#xff1a;PostgreSQL 主从复制 博客地址&#xff1a;TMDOG 的博客 在现代应用程序中&#xff0c;数据库的高可用性和扩展性是至关重要的。PostgreSQL 提供了主从复制功能&#xff0c;可以在多个数据库实例之间复制数据&#xff0c;以实现冗余和负载均衡。本…...

【系统架构设计师(第2版)】十一、未来信息综合技术

未来信息综合技术是指近年来新技术发展而提出的一些新概念、新知识、新产品&#xff0c;主要包括信息物理系统&#xff08;CPS&#xff09;、人工智能&#xff08;AI&#xff09;、机器人、边缘计算、数字孪生、云计算和大数据等技术。这些技术涉及多学科、多领域&#xff0c;具…...

Pytorch学习--神经网络--优化器

一、头文件 torch.optim.Optimizer(params, defaults) optim文档 for input, target in dataset:optimizer.zero_grad()output model(input)loss loss_fn(output, target)loss.backward()optimizer.step()二、代码 不带优化器的代码框架 import torch import torchvision…...

w~自动驾驶合集11

我自己的原文哦~ https://blog.51cto.com/whaosoft/12329152 #特斯拉的“纯视觉”路线 , 也许不是最好的 BEVTransformer占用网络技术路线的大热&#xff0c;再次将激光雷达推向风口浪尖。 激光雷达该不该被抛弃&#xff1f; 对车企来说&#xff0c;这是一个艰难的抉择&am…...

大数据新视界 -- 大数据大厂之 Impala 性能优化:解锁大数据分析的速度密码(上)(1/30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...

GESP4级考试语法知识(算法概论(三))

爱因斯坦的阶梯代码&#xff1a; //算法1-12 #include<iostream> using namespace std; int main() {int n1; //n为所设的阶梯数while(!((n%21)&&(n%32)&&(n%54)&&(n%65)&&(n%70)))n; //判别是否满足一组同余式cout<<n<…...

x-cmd pkg | gum - 轻松构建美观实用的终端界面,解锁命令行新玩法

目录 简介快速上手安装使用 功能特点竞品和相关作品进一步探索 简介 gum 是由 Charm 团队于 2022 年使用 Go 开发的终端 UI 组件工具箱&#xff0c;能帮用户在终端中快速构建交互式 TUI 界面&#xff08;如表单、菜单、提示框等&#xff09;&#xff0c;简化命令行应用程序的开…...

WMS系统打通仓储全链条数据势在必行,该如何做呢

一、引言 在当今竞争激烈的商业环境中&#xff0c;高效的仓储管理对于企业的生存和发展至关重要。仓储管理系统&#xff08;WMS&#xff09;作为现代仓储管理的核心工具&#xff0c;其作用不仅仅是简单地记录库存数量和位置&#xff0c;更在于打通仓储全链条数据&#xff0c;实…...

基于Python的校园爱心帮扶管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…...

如何基于pdf2image实现pdf批量转换为图片

最近为了将pdf报告解析成为文本和图片&#xff0c;需要将大量多页的pdf文件拆分下单独的一页一页的图像&#xff0c;以便后续进行OCR和图像处理&#xff0c;因此就需要实现将pdf2image&#xff0c;本文主要结合开源的pdf2image和poppler&#xff0c;实现了pdf转换为png格式图片…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...