NOIP2010提高组.引水入城
*前置题目
901. 滑雪
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 310, INF = 0x3f3f3f3f;
const int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};int n, m, h[N][N];
int f[N][N];
int ans;int dfs(int x, int y) {if (f[x][y] != -1) return f[x][y];f[x][y] = 1;for (int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m || h[nx][ny] >= h[x][y]) continue;int son = dfs(nx, ny);f[x][y] = max(f[x][y], son + 1);}return f[x][y];
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> h[i][j];}}memset(f, -1, sizeof f);for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (f[i][j] == -1) ans = max(ans, dfs(i, j));}}cout << ans << "\n";return 0;
}
907. 区间覆盖
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;int s, e, n;
struct Seg {int l, r;bool operator< (const Seg &s) const {return l < s.l;}
} segs[N];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> s >> e >> n;for (int i = 0; i < n; ++i) cin >> segs[i].l >> segs[i].r;sort(segs, segs + n);int ans = 0;for (int i = 0; i < n;) {int r = -INF;while (i < n && segs[i].l <= s) {r = max(r, segs[i].r);i++;}ans++;if (r < s) {cout << -1 << "\n";return 0;}if (r >= e) {cout << ans << "\n";return 0;}s = r;}cout << -1 << "\n";return 0;
}
题目
497. 引水入城
算法标签: 记忆化搜索, 贪心, d p dp dp
思路
发现每个水库覆盖的城市必须是连续的, 因为如果不连续, 其他地方的水也无法连接到当前城市, 因此问题就转化为了最少需要多少区间能将最后的城市全部覆盖?
也就是经典的区间覆盖问题, 计算每个第一层的城市可以覆盖哪些最后一层的城市可以记忆化搜索求解
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;const int N = 510, INF = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int n, m, h[N][N];
struct Seg {int l, r;bool operator<(const Seg &s) const {return l < s.l;}
} f[N][N];void dfs(int x, int y) {auto &p = f[x][y];if (p.l != -1) return;p.l = N;if (x == n) p = {y, y};for (int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];;if (nx < 1 || nx > n || ny < 1 || ny > m || h[nx][ny] >= h[x][y]) continue;dfs(nx, ny);p.l = min(p.l, f[nx][ny].l);p.r = max(p.r, f[nx][ny].r);}}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> h[i][j];}}memset(f, -1, sizeof f);for (int i = 1; i <= m; ++i) dfs(1, i);int cnt = 0;for (int i = 1; i <= m; ++i) {if (f[n][i].l == -1) cnt++;}if (cnt) {cout << 0 << "\n";cout << cnt << "\n";return 0;}vector<Seg> vec;for (int i = 1; i <= m; ++i) vec.push_back(f[1][i]);sort(vec.begin(), vec.end());int ans = 0;for (int i = 0, s = 1; i < m;) {int r = 0;while (i < m && vec[i].l <= s) {r = max(r, vec[i].r);i++;}ans++;if (r >= m) break;s = r + 1;}cout << 1 << "\n";cout << ans << "\n";return 0;
}
相关文章：
NOIP2010提高组.引水入城
*前置题目 901. 滑雪 #include <iostream> #include <algorithm> #include <cstring>using namespace std;const int N 310, INF 0x3f3f3f3f; const int dx[4] {0, -1, 0, 1}, dy[4] {1, 0, -1, 0};int n, m, h[N][N]; int f[N][N]; int ans;int dfs(i…...
NLP高频面试题（二十九）——大模型解码常见参数解析
在大语言模型的实际应用中，如何更有效地控制文本生成的质量与多样性，一直是热门研究话题。其中，模型解码（decode）策略至关重要，涉及的主要参数包括 top_k、top_p 和 temperature 等。本文将详细介绍这些常见…...
【AI产品分享】面向图片的原始位置翻译功能
1. 背景 在撰写文字材料时，往往需要配套图像以增强表达效果。然而，有时自己绘制的图可能达不到理想的质量，而在其他文献材料中却能发现更清晰、直观的示例。希望在“站在巨人的肩膀上”优化自己的图像时，通常希望在保留原始图像的…...
为什么要为 REST API 添加认证
在不断发展的 Web 服务领域，REST API 在各种软件系统之间的通信中扮演着至关重要的角色。然而，强大的功能也伴随着巨大的责任。确保敏感数据的安全性和通信的可靠性是至关重要的。这时，认证就显得尤为重要。通过使用认证，我们可以…...
AI 数字人短视频数字人源码部署揭秘：开启虚拟内容创作新纪元
在当下短视频盛行的时代，AI 数字人短视频以其独特的魅力吸引着大众的目光。虚拟偶像在舞台上活力四射，电商平台中数字人不知疲倦地推荐产品，这些令人瞩目的表现背后，源码的部署起着至关重要的作用。它如同幕后的神奇工匠ÿ…...
佳能imageRUNNER 2206N基本参数及管理员密码
基本参数： 产品类型 激光数码复合机 颜色类型 黑白 涵盖功能 复印/打印/扫描 速度类型 低速 最大原稿尺寸 A3 复印/打印方式 激光静电转印方式 感光材料 OPC 显影系统 干式单组分显影 定影…...
【Linux篇】探索进程地址空间：计算机背后的虚拟世界
进程地址空间的奥秘：让你理解程序如何在计算机中生存 一. 程序地址空间1.1 基本概念1.2 虚拟内存管理1.3 为什么存在虚拟地址空间1.3.1 意义 2. 最后 本文将介绍进程地址空间的基本概念与结构，帮助读者理解操作系统如何管理和分配内存。进程地址空间指的…...
Docker部署sprintboot后端项目
创建Docker网络 docker network create icjs 部署Redis docker run -d \--network icjs \--name redis \-p 6379:6379 \redis:latest数据持久化 docker run --restartalways --network icjs -p 6379:6379 --name redis -v /opt/docker/redis/redis.conf:/etc/redis/redis.c…...
1.4 基于模拟退火改进蛇算法优化VGG13SE网络超参数的故障诊断模型
本博客来源于CSDN机器鱼，未同意任何人转载。 更多内容，欢迎点击本专栏，查看更多内容。 目录 0 引言 1 改进原理 2 本文改进方法 3 改进蛇优化VGG13SE的故障诊断模型 4 结语 0 引言 在【博客】中，我们采用了蛇算法来对VGG1…...
Vue + Scss项目中实现自定义颜色主题的动态切换
当时面试的时候遇到面试官问的一个问题如何实现自定义颜色主题切换,当时我做的只是elementUIPlus提供的暗黑和默认主题切换 theme.scss // 增加自定义主题类型 $themes: (light: (/* 原有配置保持不变 */),dark: (/* 原有配置保持不变 */),custom: () // 空映射…...
C#实现HiveQL建表语句中特殊数据类型的包裹
用C#实现搜索字符串中用’(‘和’)‘包裹的最外层的里面里面的字符串，将里面的记录按一个或多个空格、换行或tab，或者是它的在一起的组合作为分隔，分隔出多个字符串组，如果组中有字符串中同时包含’<‘和’>’，则…...
27 python 标准库概览
在办公室里，每个员工都有一套预装的办公软件：Word 处理文档、Excel 制作表格、Outlook 收发邮件... Python 的标准库就像公司预装的 "办公全家桶"，包含 100 多个模块，覆盖文件操作、时间管理、数据分析等日常需求，无需额外安装即可直接使用。 一、文件管理 1.…...
whisper 语音识别的安装与使用
Whisper 是由OpenAI开发的开源自动语音识别（ASR）模型，不仅支持音频转录，还可以用于视频转录。通过调用ffmpeg处理视频，支持主流音视频格式的转录。 安装 安装ffmpeg：下载ffmpeg，Releases B…...
搜广推校招面经六十四
滴滴搜推算法 一、定义一个树结构、特征结构。写一个决策树对样本打分 逆天啊，上来就是暴击 import numpy as np class TreeNode:def __init__(self, feature_indexNone, thresholdNone, leftNone, rightNone, scoreNone):self.feature_index feature_index #…...
zabbix监控网站（nginx、redis、mysql）
目录 前提准备： zabbix-server主机配置： 1. 安装数据库 nginx主机配置： 1. 安装nginx redis主机配置： 1. 安装redis mysql主机配置： 1. 安装数据库 zabbix-server： 1. 安装zabbix 2. 编辑配置文…...
动态规划，如何应用动态规划解决实际问题？
一、动态规划核心概念 动态规划是一种分阶段解决问题的数学方法，它将复杂问题分解为更小的子问题，通过存储子问题的解来避免重复计算。 关键特征： 最优子结构：问题的最优解包含子问题的最优解重叠子问题：问题可…...
常见操作系统特点及区别对比
操作系统名称类型特点主要用途许可证类型内核类型Windows桌面/服务器图形界面友好，软件生态丰富，闭源个人电脑、企业办公专有商业许可混合内核macOS桌面 (Unix-like)高度优化的硬件整合，Unix基础，闭源创意设计、开发专有商业许可混…...
【资讯分享】为Apple Intelligence打造的有效屏障：“隐私保护气泡”
导读：苹果在WWDC大会上推出Apple Intelligence，主打个性化智能服务，深度整合iOS生态，支持跨App操作与内容感知。通过本地计算与私密云计算（PCC）技术实现端到端加密，确保数据匿名化处理与高透明度…...
AT_abc306_b [ABC306B] Base 2
题目描述 给定一个长度为64的序列A(A\_0,A\_1,\dots,A\_{63})A(A_0,A_1,…,A_63)，由0和1组成。 求A\_0 2^0 A\_1 2^1 \dots A\_{63} 2^{63}A_020A_121⋯A_63263。 约束条件 A\_iA_i是0或1。 输入 从标准输入中以以下格式给出输入： A_0A0 A_1A…...
C++IO流类库
一、输入输出流(I/O strea) 编译系统已经以运算符或函数的形式做好了对标准外设（键盘、屏幕、打印机、文件）的接口，使用时只需按照要求的格式调用即可。 cin>>x; cout<<x; cin.get(ch); C语言的I/O系统向用户提供一个统一…...
常见的锁策略+synchronized（特性解释）
该篇文章主要是对常见的锁策略的总结（主要的作用是扫盲），如想要了解其他部分，这部分可以不用看 目录 一、常见的锁策略1. 悲观锁vs乐观锁举例： 2. 重量级锁vs轻量级锁3. 挂起等待锁vs自旋锁举例 4.普通互斥锁vs读写锁…...
spring打包，打包错误
打包(idea) 通过点击井盖样式的符号可以将test测试类取消打包进去 点击“M”，双击package即可打包 打包出错 ❯ java -jar /home/ying/Documents/java_workspace/spring-01-ioc/target/spring-01-ioc-0.0.1-SNAPSHOT.jar Error: LinkageError occurred while loadi…...
【Linux系统】进程间通信-System V消息队列
🎁个人主页：我们的五年 🔍系列专栏：Linux网络编程 🌷追光的人，终会万丈光芒 🎉欢迎大家点赞👍评论📝收藏⭐文章 Linux网络系列文章计算机网络（Linux网…...
DeepSeek×擎创科技：当智能运维遇见大模型「懂行」革命
运维人最懂「动态阈值」的痛 在数字化转型浪潮中，运维监控正经历从"人工经验"到"智能决策"的跃迁。传统动态阈值设置依赖人工分析历史数据、反复调整规则的模式，既难以应对业务波动性，又消耗大量技术资源。 擎创科技基…...
手绘风格流程图工具：简单高效的在线流程图绘制工具
手绘风格流程图：简单高效的在线流程图绘制工具 🎉 项目介绍 大家好！我很高兴向大家分享我最近开发的一个项目 —— 在线绘制手绘风格流程图，这是一个简单高效的在线流程图绘制工具。无论是整理思路、规划项目还是准备演示&#…...
leetcode287.寻找重复数
与寻找链表环的起始点一样 ，用快慢指针让二者相遇后，慢指针回到起始点二者以同样速度移动最终会在环的起始点相遇 class Solution {public int findDuplicate(int[] nums) {int slow nums[0], fast nums[0];do {slow nums[slow];fast nums[nums[fas…...
error LNK2019: 无法解析的外部符号 __imp__XXXX，该符号在函数xxxxx中被引用
这个链接错误表明在编译过程中，链接器无法找到 XXXX 函数的实现。以下是解决这个问题的步骤： 可能的原因和解决方案： 函数声明与实现不匹配： 检查 XXXX 函数的声明和实现是否完全一致（包括返回类型、参数列表和调用约…...
【LeetCode基础算法】二叉树所有类型
1.遍历二叉树 二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历叶子相似的树 1288 LCP 44. 开幕式焰火左叶子之和 2.自顶向下DFS 二叉树的最大深度二叉树的最小深度路径总和求根节点到叶节点数字之和二叉树的右视图统计二叉树中好节点的数目 1360 3.自底向上 DFS 二叉树…...
AIGC5——AIGC的伦理与法律挑战：数据隐私、真实性危机与版权治理
引言 随着生成式AI（AIGC）的爆发式增长，其引发的伦理与法律问题日益凸显。从数据隐私泄露到AI幻觉导致的虚假信息，再到训练数据版权争议，AIGC正在挑战现有法律框架与社会信任体系。本文将系统分析三大核心问题…...
LLM架构解析：词嵌入模型 Word Embeddings（第二部分）—— 从基础原理到实践应用的深度探索
本专栏深入探究从循环神经网络（RNN）到Transformer等自然语言处理（NLP）模型的架构，以及基于这些模型构建的应用程序。 本系列文章内容： NLP自然语言处理基础词嵌入（Word Embeddings）…...
marked库（高效将 Markdown 转换为 HTML 的利器）
文章目录 前言使用基本使用自定义渲染器例子 代码高亮 前言 最近尝试了一下通过星火大模型将ai引入到项目上，但是ai返回的数据可以显而易见的发现是markedown语法的，那么就需要一个工具，将类似这种的格式转换为markdown格式 Marked 是一个用…...
Vue3 + Element Plus + AntV X6 实现拖拽树组件
Vue3 Element Plus AntV X6 实现拖拽树组件 介绍 在本篇文章中，我们将介绍如何使用 Vue 3 和 Element Plus 结合 antv/x6 实现树形结构的拖拽功能。用户可以将树节点拖拽到图形区域，自动创建相应的节点。我们将会通过简单的示例来一步步讲解实现过程…...
在 Rocky Linux 9.2 上编译安装 Redis 6.2.6
文章目录 在 Rocky Linux 9.2 上编译安装 Redis 6.2.6Redis 介绍官网Redis 的核心特性高性能支持多种数据结构多种持久化机制复制与高可用2.5 事务与 Lua 脚本消息队列功能 Redis 适用场景Redis 与其他数据库对比Redis 的优势与劣势Redis 优势Redis 劣势 部署过程系统环境信息环…...
中和农信：让金融“活水”精准浇灌乡村沃土
2025年政府工作报告首提“投资于人”概念，并22次提及“金融”，强调要着力抓好“三农”工作，深入推进乡村全面振兴；一体推进地方中小金融机构风险处置和转型发展；扎扎实实落实促进民营经济发展的政策措施，切…...
4. 理解Prompt Engineering：如何让模型听懂你的需求
引言：当模型变成“实习生” 想象一下，你新招的实习生总把“帮我写份报告”理解为“做PPT”或“整理数据表”——这正是开发者与大模型对话的日常困境。某金融公司优化提示词后，合同审查准确率从72%飙升至94%。本文将用3个核心法则+5个行业案例，教你用Prompt Engineering让…...
cocos 图片上传与下载
创建一个场景 在 Cocos Creator 中，我们将从接口获取的图片 URL 列表动态创建图片节点并显示在页面上。使用 assetManager.loadRemote 来加载这些图片并显示。 目录结构如下 为按钮button和文本Lable挂载ts脚本 运行界面 图片上传测试 背景会变成上传的图片 以下是…...
Unity中的UI坐标和点击接口
默认已经知道UI中的基础知识，这里提供一些细节 📚️锚点和轴心点 锚点是根据父物体的确定的，锚点Anchor分为两种状态，Min Max 和 Min ! Max Min ! Max时会根据锚点进行自适应拉伸 参考文章：Unity 锚点 Anchors的通俗…...
，源码可白嫖!)
基于JavaWeb的二手图书交易系统(源码+lw+部署文档+讲解)，源码可白嫖!
摘要 人类现已迈入二十一世纪，科学技术日新月异，经济、资讯等各方面都有了非常大的进步，尤其是资讯与网络技术的飞速发展，对政治、经济、军事、文化等各方面都有了极大的影响。 利用电脑网络的这些便利，发展一套二手图…...
人脸表情识别数据集的正确使用方法（Affectnet、RAF-DB、FERPlus数据集通用）
众所周知深度学习是个很玄学的东西，不同的数据集加载方式会训练出不一样的精度，导致无法复现论文精度。 这里分享下正确的加载数据集的方法： 拿RAF-DB数据集举例： ①准备好RAF-DB数据集，训练集和测试集放进同一目录&…...
【408--考研复习笔记】操作系统----知识点速览
目录 一、计算机系统概述 1.计算机系统的组成 2.操作系统的定义与作用 3.操作系统的发展历程 4.操作系统的基本特性 5.操作系统的结构 简单结构 分层结构 微内核结构 模块化结构 宏内核结构 6.用户接口 7.系统调用 8.处理机的工作状态 9.中断机制 10.特权指令与…...
Java常用异步方式总结
使用建议 完整代码见https://gitee.com/pinetree-cpu/parent-demon 提供了postMan调试json文件于security-demo/src/main/resources/test_file/java-async.postman_collection.json 可导入postMan中进行调试 Java异步方式以及使用场景 继承Thread类 新建三个类继承Thread&…...
算法设计学习3
实验目的及要求： 1.加强对结构体的应用。 2.熟悉字符计数排序。 实验设备环境： 1.微型计算机 2.DEV C(或其他编译软件) 实验步骤： 任务：要求使用自定义函数来实现 输入一段文本，统计每个字符出现的次数，按…...
)
OpenCV 图形API（或称G-API）(1)
操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 引言 OpenCV 图形API（或称G-API）是一个新的OpenCV模块，旨在使常规图像处理更快且更便携。通过引入一种新的基于图的执行…...
解决Luckysheet在线预览编辑Excel、PDF.....无法在同一个界面创建多个luckysheet实列问题
luckysheet插件由于是实列挂载到windows.luckysheet实列上，导致同时只能使用一个luckysheet于是我们使用<iframe/>标签进行隔离： 1.每个<iframe>创建独立的浏览器上下文环境，避免多个Luckysheet实例共享同一JavaScript执行环境 …...
php8属性注解使用教程
简介 PHP 8 引入了 属性（Attributes）作为新的元数据机制，用于替代传统的 PHPDoc 注解，使得代码更具类型安全性和结构化。 基本语法 PHP 8 的属性（Attributes）使用 #[...] 语法表示，并可以用于…...
Redis6数据结构之List类型
redis的List类型底层结构是双向链表，插入删除时间复杂度O(1)快,查找为O(n)慢。 应用场景：简单队列、最新评论列表、非实时排行榜（定时计算榜单，如笔记本日销榜单）。 常用命令： lpush将一个或多个值从左边…...
【视觉与语言模型参数解耦】为什么？方案？
一些无编码器的MLLMs统一架构如Fuyu，直接在LLM内处理原始像素，消除了对外部视觉模型的依赖。但是面临视觉与语言模态冲突的挑战，导致训练不稳定和灾难性遗忘等问题。解决方案则是通过参数解耦方法解决模态冲突。 在多模态大语言模型…...
[笔记.AI]初始向量
（借助 DeepSeek-V3 辅助生成） 初始向量的生成方式 在自然语言处理（NLP）中，初始向量是指模型在处理输入文本时，将每个 Token（如词、子词或字符）映射到高维向量空间的起点。这些初始…...
MySQL（一）
MySQL定义 ⭐ MySQL是一个“客户端——服务器”结构的软件 客户端：主动给服务器发起的数据，称为请求。 服务器：被动接收，给客户端返回的数据，称为响应。 客户端和服务器是通过网络通信进行的。 内存和硬盘的区别&am…...
（C语言）虚数运算（结构体教程）（指针解法）（C语言教程）
#include <stdio.h> //定义结构体 typedef struct {float realpart;float imagpart; }Complex; //初始化虚数 //传递值，和指针分开 void assign(const float real,const float imag,Complex* A){A->imagpartimag;A->realpartreal; } //虚数相加 //同样…...