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

K-01BFS(2023河南萌新联赛第(五)场:郑州轻工业大学)

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

思路:

直接枚举这个图中的拐点

这个拐点是经过左右平移到上下平移或者上下平移到左右平移

假设这个点事左到右后然后再从下到上

左到右就相当于走了个最长上升子序列,然后再从下到上

从下到上的过程你可以反过来看,就是从上走到下,就相当从上到下走了个最长下降子序列

然后最长上升/下降子序列可以用dp+二分来求

按题解的话来说就是

预处理出对于每个单元格四个方向上最多跳多少个单元格可以跳到当前单元格(最长上升子序列),以及从当前单元格跳出最多能跳多少个单元格(最长下降子序列)

-----------------------------------

下面是最长上升子序列的代码

memset(q,0x3f,sizeof q);q[0]=-inf;int maxx=0;
for(int i=0;i<n;i++){int pos=lower_bound(q,q+n,a[i])-q-1;q[pos+1]=a[i];maxx=max(maxx,pos+1);}

最长下降子序列代码

for (int i = 0; i < n; i++) {cin >> v[i];}dp.push_back(v[0]);for (int i = 1; i < n; i++) {if (v[i] < dp.back()) dp.push_back(v[i]);else {int l = 0, r = dp.size()-1;while (l < r) {int m = l + (r - l) / 2;if (v[i] < dp[m])l = m + 1;else r = m;}dp[l] = v[i];}

-------------------

经过每个点4个方向的预处理

#include<iostream>
#include<algorithm>
#include<numeric>//accumulate(be,en,0)
#include<cstring>//rfind("string"),s.find(string,begin)!=s.npos,find_first _of(),find_last_of()
#include<string>//to_string(value),s.substr(int begin, int length);
#include<cstdio>
#include<cmath>
#include<vector>//res.erase(unique(res.begin(), res.end()), res.end()),reverse(q.begin(),q.end()),vector<int>().swap(at[mx])
#include<queue>//priority_queue(big)  /priority_queue<int, vector<int>, greater<int>> q(small)
#include<stack>
//#include<map>//unordered_map
#include<set>//iterator,insert(),erase(),lower(>=)/upper_bound(>)(value)/find()return end()
#include<unordered_map>
#include<unordered_set>
#include<bitset>//size,count(size of 1),reset(to 0),any(have 1?)
//#include<ext/pb_ds/assoc_container.hpp>//gp_hash_table
//#include<ext/pb_ds/hash_policy.hpp>
//using namespace __gnu_pbds;
#define int long long//__int128 2^127-1(GCC)
#define PII pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f, N = 1e5 + 5, mod = 1e9 + 7;
signed main() {ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {int n, m;cin >> n >> m;vector<vector<int>>q(n + 5, vector<int>(m + 5));//存储原来矩阵vector<vector<int>>q2(n + 5, vector<int>(m + 5));//存储第一次上下移动的矩阵的最大值vector<vector<int>>q1(n + 5, vector<int>(m + 5));//存储第一次左右移动的矩阵的最大值vector<vector<int>>q3(n + 5, vector<int>(m + 5));//存储第二次上下移动的矩阵的最大值vector<vector<int>>q4(n + 5, vector<int>(m + 5));//存储第二次左右移动的矩阵的最大值for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> q[i][j];}}vector<int>w, tmp(m + 5), tmp2(n + 5);for (int i = 1; i < m + 5; i++) tmp[i] = inf;for (int i = 1; i < n + 5; i++) tmp2[i] = inf;for (int i = 1; i <= n; i++) {//求每一行从左到右的最长上升子序列w = tmp;w[0] = -inf;for (int j = 1; j <= m; j++) {int pos = lower_bound(w.begin(), w.end(), q[i][j]) - w.begin() - 1;w[pos + 1] = q[i][j];q1[i][j] = pos + 1;}}for (int i = 1; i <= n; i++) {w = tmp;w[0] = -inf;for (int j = m; j >= 1; j--) {int pos = lower_bound(w.begin(), w.end(), q[i][j]) - w.begin() - 1;w[pos + 1] = q[i][j];q1[i][j] = max(q1[i][j], pos + 1);}}for (int i = 1; i <= m; i++) {//每一行从右到左 的上升子序列(下面同理)w = tmp2;w[0] = -inf;for (int j = 1; j <= n; j++) {int pos = lower_bound(w.begin(), w.end(), q[j][i]) - w.begin() - 1;w[pos + 1] = q[j][i];q2[j][i] = pos + 1;}}for (int i = 1; i <= m; i++) {w = tmp2;w[0] = -inf;for (int j = n; j >= 1; j--) {int pos = lower_bound(w.begin(), w.end(), q[j][i]) - w.begin() - 1;w[pos + 1] = q[j][i];q2[j][i] = max(q2[j][i], pos + 1);}}//------------------------for (int i = 1; i <= n; i++) {//每一行从左到右的下降子序列q3[i][1] = 1;vector<int>dp;dp.push_back(q[i][1]);for (int j = 2; j <= m; j++) {if (q[i][j] < dp.back()) {dp.push_back(q[i][j]); q3[i][j] = dp.size();}else {int l = 0, r = dp.size() - 1;while (l < r) {int mid = l + (r - l) / 2;if (q[i][j] < dp[mid]) l = mid + 1;else r = mid;}q3[i][j] = l + 1;dp[l] = q[i][j];}}}for (int i = 1; i <= n; i++) {vector<int>dp;dp.push_back(q[i][m]);for (int j = m - 1; j >= 1; j--) {if (q[i][j] < dp.back()) {dp.push_back(q[i][j]); q3[i][j] = max(q3[i][j], (int)dp.size());}else {int l = 0, r = dp.size() - 1;while (l < r) {int mid = l + (r - l) / 2;if (q[i][j] < dp[mid]) l = mid + 1;else r = mid;}q3[i][j] = max(q3[i][j], l + 1);dp[l] = q[i][j];}}}for (int i = 1; i <= m; i++) {q4[1][i] = 1;vector<int>dp;dp.push_back(q[1][i]);for (int j = 2; j <= n; j++) {if (q[j][i] < dp.back()) {dp.push_back(q[j][i]); q4[j][i] = dp.size();}else {int l = 0, r = dp.size() - 1;while (l < r) {int mid = l + (r - l) / 2;if (q[j][i] < dp[mid]) l = mid + 1;else r = mid;}q4[j][i] = l + 1;dp[l] = q[j][i];}}}for (int i = 1; i <= m; i++) {vector<int>dp;dp.push_back(q[n][i]);for (int j = n - 1; j >= 1; j--) {if (q[j][i] < dp.back()) {dp.push_back(q[j][i]); q4[j][i] = max(q4[j][i], (int)dp.size());}else {int l = 0, r = dp.size() - 1;while (l < r) {int mid = l + (r - l) / 2;if (q[j][i] < dp[mid]) l = mid + 1;else r = mid;}q4[j][i] = max(q4[j][i], l + 1);dp[l] = q[j][i];}}}int maxx = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {maxx = max({ maxx,q1[i][j] + q4[i][j],q2[i][j] + q3[i][j] });
//第一次上下+第二次左右,第一次左右+第二次上下}}cout << maxx - 1 << '\n';}
}

相关文章:

K-01BFS(2023河南萌新联赛第(五)场:郑州轻工业大学)

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 思路&#xff1a; 直接枚举这个图中的拐点 这个拐点是经过左右平移到上下平移或者上下平移到左右平移 假设这个点事左到右后然后再从下到上 左到右就相当于走了个最长上升子序列&#xff0…...

CSP复习每日一题(四)

树的重心 给定一颗树&#xff0c;树中包含 n n n 个结点&#xff08;编号 1 ∼ n 1∼n 1∼n&#xff09;和 n − 1 n−1 n−1条无向边。请你找到树的重心&#xff0c;并输出将重心删除后&#xff0c;剩余各个连通块中点数的最大值。 重心定义&#xff1a; 重心是指树中的一…...

dubbo之整合SpringBoot

目录 zookeeper安装 1.拉取ZooKeeper镜像 2.新建文件夹 3.挂载本地文件夹并启动服务 4.查看容器 5.进入容器&#xff08;zookeeper&#xff09; Dubbo Admin安装 1.下载dubbo-admin 2.zip包解压 3.修改配置文件 4.打包项目 5.启动jar 6.访问 构建项目 api模块 1.创建…...

UE 5 GAS 在项目中处理AttributeSet相关

这一篇文章是个人的实战经验记录&#xff0c;如果对基础性的内容不了解的&#xff0c;可以看我前面一篇文章对基础的概念以及内容的讲解。 设置AttributeSet 使用GAS之前&#xff0c;首先需要设置参数集AS&#xff0c;这个是用于同步的一些参数&#xff0c;至于如何设置GAS&a…...

JDBC数据库连接

目录 引言 一&#xff0c;基本概念 二&#xff0c;常用操作步骤 三&#xff0c;连接操作 引言 JDBC(Java DataBase Connectivity,java数据库连接)是一种用于执行SQL语句的Java API&#xff0c;可以为多种 关系数据库提供统一访问&#xff0c;它由一组用Java语言编写的类和接口…...

gitee分支合并

合并dev分支到master&#xff08;合并到主分支&#xff09; git checkout master git merge dev //这里的dev表示你的分支名称 git push //推送到远程仓库 效果如下图 不报错就表示推送成功了&#xff0c;希望能帮助各位小伙伴...

Python小白入门:文件、异常处理和json格式存储数据

这里写自定义目录标题 所用资料 一、从文件中读取数据1.1 读取整个文件1.2 文件路径1.3 逐行读取1.4 创建一个包含文件各行内容的列表1.5 使用文件的内容1.6 包含一百万位的大型文件1.7 圆周率值中包含你的生日吗练习题 二、写入文件2.1 写入空文件2.2 写入多行2.3 附加到文件练…...

16bit、8 通道、500kSPS、 SAR 型 ADC——MS5188N

MS5188N 是 8 通道、 16bit 、电荷再分配逐次逼近型模数 转换器&#xff0c;采用单电源供电。 MS5188N 拥有多通道、低功耗数据采集系统所需的所有 组成部分&#xff0c;包括&#xff1a;无失码的真 16 位 SAR ADC &#xff1b;用于将输入配 置为单端输入&#xff0…...

Chapter 12: Regular expressions | Python for Everybody 讲义笔记_En

文章目录 Python for Everybody课程简介Regular ExpressionsRegular ExpressionsCharacter matching in regular expressionsExtracting data using regular expressionsCombining searching and extractingEscape characterSummaryBonus section for Unix / Linux usersDebugg…...

Android javaMail mergeDebugJavaResource FAILED解决

Java mail 引入这两个jar之后 implementation com.sun.mail:android-mail:1.6.7implementation com.sun.mail:android-activation:1.6.7build直接报错 > Task :app:mergeDebugJavaResource FAILED Execution failed for task :app:mergeDebugJavaResource. > A failure o…...

【ArcGIS Pro二次开发】(57):地图系列

在ArcGIS Pro中&#xff0c;有一个地图系列&#xff0c;可以在一个布局中导出多个地图。 在SDK中为ArcGIS.Desktop.layout.MapSeries类和映射系列导出选项&#xff0c;可以以支持多页导出。 MapSeries类提供了一个静态CreateSpatialMapSeries方法&#xff0c;该方法使用指定的…...

秋招打卡015(20230811)

文章目录 前言一、今天学习了什么&#xff1f;二、动态规划之股票问题1、总结2、题目 三、SQL总结 前言 提示&#xff1a;这里为每天自己的学习内容心情总结&#xff1b; Learn By Doing&#xff0c;Now or Never&#xff0c;Writing is organized thinking. 提示&#xff1a…...

如何使用Word转PDF转换器在线工具?在线Word转PDF使用方法

Word转PDF转换器在线&#xff0c;是一种方便快捷的工具&#xff0c;可帮助您在不需要下载任何软件的情况下完成此任务。无论您是需要在工作中共享文档&#xff0c;还是将文件以PDF格式保存以确保格式不变&#xff0c;都可以依靠这款在线工具轻松完成转换。那么如何使用Word转PD…...

自然语言处理从入门到应用——LangChain:记忆(Memory)-[记忆的类型Ⅰ]

分类目录&#xff1a;《自然语言处理从入门到应用》总目录 会话缓存记忆ConversationBufferMemory 本节将介绍如何使用对话缓存记忆ConversationBufferMemory。这种记忆方式允许存储消息&#xff0c;并将消息提取到一个变量中&#xff0c;我们首先将其提取为字符串&#xff1a…...

Camunda 7.x 系列【7】Spring Boot 集成 Camunda 7.19

有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 2.7.9 本系列Camunda 版本 7.19.0 源码地址:https://gitee.com/pearl-organization/camunda-study-demo 文章目录 1. 前言2. Camunda Platform Run3. Spring Boot 版本兼容性4. 集成 Spring Boot5. 启动项目…...

24华东交通软件工程837考研题库

1&#xff0e;Jackson设计方法是由英国的M&#xff0e;Jackson所提出的。它是一种面向( )的软件设 计方法。 A&#xff0e;对象 B&#xff0e;数据流 C&#xff0e;数据结构 D&#xff0e;控制结构 答案:C 2&#xff0e;软件设计中&#xff0c;Jackson方法是一种面向…...

nginx 以及nginx优化

目录 nginx功能介绍 静态文件服务 反向代理 动态内容处理 SSL/TLS 加密支持 虚拟主机支持 URL 重写和重定向 缓存机制 日志记录 可扩展性和灵活性 nginx的主要应用场景 nginx常用命令 nginx另外一种安装方式 nginx常用的信号符&#xff1a; nginx配置文件详解 n…...

cesium学习记录04-坐标系

一、地理坐标系和投影坐标系的关系 地理坐标系 (Geographic Coordinate System, GCS) 定义&#xff1a;地理坐标系是一个基于三维地球表面的坐标系统。它使用经度和纬度来表示地点的位置。 特点&#xff1a; 使用经纬度来定义位置。 基于特定的地球参考椭球体。 适用于全球范…...

P5737 【深基7.例3】闰年展示

题目描述 输入 x , y x,y x,y&#xff0c;输出 [ x , y ] [x,y] [x,y] 区间中闰年个数&#xff0c;并在下一行输出所有闰年年份数字&#xff0c;使用空格隔开。 输入格式 输入两个正整数 x , y x,y x,y&#xff0c;以空格隔开。 输出格式 第一行输出一个正整数&#xf…...

Nacos的安装使用教程Linux

在 Linux 操作系统上安装和使用 Nacos 与 Windows 类似&#xff0c;以下是详细的步骤教程。我们将使用 Nacos 的 Standalone 模式进行安装和使用。请注意&#xff0c;对于生产环境&#xff0c;建议使用集群模式来实现高可用性和可扩展性。 步骤 1&#xff1a;准备环境 Java 安…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...