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

最小单调子序列的长度+联通最小乘积

news 来源：原创 2025/7/14 18:33:30

因为题目ICPC是英文版，基于大家都不怎么看的懂的情况下直接给大家进行题目讲解

题目1：

题目分析：

构造一个长度为n的排列 p（里面的数是1-n),不能重复得 max⁡(lis(p),lds(p)) 最小。
其中，lis(p)是 p 的最长递增子序列长度，lds(p) 是 p 的最长递减子序列长度。

排列：由 1 到 n 的整数组成的序列，每个整数恰好出现一次。例如，[2,3,1,5,4]是一个排列，但[1,2,2] 不是（重复出现 2），[1,3,4] 也不是（包含超出范围的数 4）。

问题正式描述：
设排列 p 的值为 max⁡(lis(p),lds(p))，其中：

lis(p) 表示 p 的最长递增子序列（LIS）的长度，
lds(p) 表示 p 的最长递减子序列（LDS）的长度。

对于所有长度为 n的排列，你需要构造一个排列 p，使得其值（即 LIS 和 LDS 长度的最大值）最小。

递增子序列（Increasing Subsequence）：若序列 a 可以通过删除序列 b 中的若干元素（可能为零或全部）得到，且 a 中的元素从头到尾严格递增，则称 a 是 b 的递增子序列。

递减子序列（Decreasing Subsequence）：类似地，若 a 中的元素从头到尾严格递减，则称其为 b 的递减子序列。

思路讲解：

当n=3时，如何保证我们的递增子序列和递减子序列在所有的序列的情况当中最小呢，我们可以模拟一下来试试，其实感觉和规律很重要

当我们正常排列的时候发现这种的序列长度最长，但是题目是要一个最小的，应该怎么办呢

根据上图，我们这样排列，最长上升子序列的长度为3，最长下降子序列的长度也为0，这个情况下得到的max⁡(lis(p),lds(p))最大为2，根据样例，说明我们这种排列一定是错误的，那我们来分析一下样例中的输出样例吧

根据上图，由此可见，这个情况下得到的max⁡(lis(p),lds(p))最小，因为最长上升子序列的长度为2，最长下降子序列的长度也为2，符合条件

到这里大家应该明白了题目的意思，那么我们应该如何进行排列得到最小的值呢，当n变大时，怎么排呢？其实这里大家也可以去找规律，如果不太了解这样的情况，可以一个一个试试，去找合适并且有规律的最好形式

4 21 43

5 321 54

6 321 654

...

9 321 654 987

10 4321 8765 109

想必大家到这里一定有答案了，没错，就是每次让长度为平方根加1，然后进行反转，平方根是关键，通过4和9大家就可以清楚的了解

这道题主要就是思考过程，解答出来时很容易的，如果大家最开始没有思路，应该多想想这道题的目的，而且确实是一个有规律的题，毕竟是要用代码进行来实现的，大家遇到这种没有思路题就可以去模拟过程，有时候确实很好用

代码实现：

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;while(n--){int m;cin>>m;int a=ceil(sqrt(m));for(int i=1;i<=a;i++){int tmp=a*i;while(tmp>(i-1)*a){if(tmp<=m) cout<<tmp<<" ";tmp--;}}cout<<endl;}return 0;
}

题目2：

思路分析：

这个不是英文版的不做解释了大家直接看题吧

实现根据题目要求，我们要联通所有的块，就是说我们每个至少连接到一个，一个也可以连多个，题目说要得到最小值，我们这里就分三种情况（让0放到正数里面）

1.有正数也有负数（让所有正数×所有负数）

2.只有正数（让最小的正数×其他正数）

3.只有负数（让最大负数×其他负数）

代码实现：

#include<bits/stdc++.h>
using namespace std;
int main(){int n;long long a=0,b=0;  //a 正  b 付 int maxb=-1010,mina=1010;//maxb 负数中最大   mina 证书最大值 cin>>n;for(int i=0;i<n;i++){int j;cin>>j;if(j<0) {b += j;maxb=max(maxb,j);}else {a += j;mina=min(mina,j);}	}if(a>0&&b<0) cout<<a*b;else if(a==0&&b<0) cout<<(b-maxb)*maxb;else cout<<(a-mina)*mina;return 0;
}

最小单调子序列的长度+联通最小乘积

因为题目ICPC是英文版，基于大家都不怎么看的懂的情况下直接给大家进行题目讲解题目1： 题目分析： 构造一个长度为n的排列 p（里面的数是1-n),不能重复得 max⁡(lis(p),lds(p)) 最小。其中，lis(p)是 p 的最长递增子序…...

编程日记 2025/7/14 18:33:30

OpenHarmony平台驱动开发（一），ADC

OpenHarmony平台驱动开发（一） ADC 概述功能简介 ADC（Analog to Digital Converter），即模拟-数字转换器，可将模拟信号转换成对应的数字信号，便于存储与计算等操作。除电源线和地线之外&#…...

编程日记 2025/7/14 18:30:32

数据结构与算法：回溯

回溯先给出一些leetcode算法题，以后遇见了相关题目再往上增加主要参考代码随想录 2.1、组合问题关于去重：两种写法的性能分析需要注意的是：使用set去重的版本相对于used数组的版本效率都要低很多，大家在leetcode上提交&#x…...

编程日记 2025/7/11 22:00:24

KaiwuDB X 遨博智能 | 构建智能产线监测管理新系统

01 项目背景遨博智能作为国内协作机器人行业领军企业，深度布局制造、农业、医疗、教育、民生等场景，出货量连续四年蝉联国内第一、世界第二。随着工业自动化的蓬勃发展，遨博智能生产规模不断扩大，先后在常州、淄博等地建设完成…...

编程日记 2025/6/29 7:35:55

高等数学第三章---微分中值定理与导数的应用（§3.6 函数图像的描绘§3.7 曲率）

3.6 函数图像的描绘一、曲线的渐近线对于某些函数，其图形向无穷远处延伸时，会越来越趋近于某一条直线，这条直线被称为曲线的渐近线 (Asymptote)。 1. 定义若曲线 y f ( x ) yf(x) yf(x) 上一点 P ( x , y ) P(x, y) P(x,y) 沿曲线趋…...

编程日记 2025/6/29 8:17:48

【PostgreSQL数据分析实战：从数据清洗到可视化全流程】4.2 数据类型转换（CAST函数/自定义函数）

👉 点击关注不迷路 👉 点击关注不迷路 👉 点击关注不迷路文章大纲 PostgreSQL数据分析实战：数据清洗之数据类型转换（CAST函数/自定义函数）4.2 数据类型转换：让数据「格式正确，类型对…...

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

1.dockerfile制作镜像示例内容： 1.创建一个index.js的文件 console.log("hello world")2.在相同目录下创建名为dockerfile的文件 FROM node:alpine COPY index.js /index.js CMD node /index.js3.构建镜像 docker build -t minterra/hello-docker . …...

编程日记 2025/6/29 8:20:22

信息系统监理师第二版教材模拟题第三组（含解析）

信息系统监理师模拟题第三组（30题）监理基础理论信息系统工程监理的性质是（） A. 服务性、独立性、公正性、科学性 B. 强制性、营利性、行政性、技术性 C. 临时性、从属性、随意性、主观性 D. 单一性、封闭性、被动性、保守性答案：A 解析：监理具有服务性、独立性、公正…...

编程日记 2025/6/29 6:19:27

潮乎盲盒商城系统全开源多级分销推广海报奖品兑换试玩概率OSS云存储多端源码

一、源码描述这是一套潮乎盲盒商城源码，仿小叮当盲盒商城，后端Laravel框架前端uniappvue，前后端数据库分离，支持四端同步数据（H5小程序等），测试环境: php7.4，mysql5.6，…...

编程日记 2025/6/28 20:05:34

文章记单词 | 第64篇（六级）

一，单词释义 residence [ˈrezɪdəns] n. 住宅；居住；住所；居住期fling [flɪŋ] v. （用力地）扔，掷，抛；猛动（身体或身体部位）；急冲&a…...

编程日记 2025/6/29 8:17:47

数据同步实战篇

文章目录数据同步实战篇1. mysql数据同步1.1 mysql集群部署1.2 数据同步1.2.1 同步复制1.2.2 异步复制1.2.3 半同步复制 2. redis数据同步2.1 redis集群部署2.2 数据同步 3. mq数据同步3.1 mq集群部署3.2 数据同步 4. es数据同步4.1 es集群部署4.2 数据同步数据同步实战篇数…...

编程日记 2025/6/29 7:38:24

具身系列——Double DQN算法实现CartPole游戏（强化学习）

完整代码参考： rl/ddqn_cartpole.py 陈先生/ailib - Gitee.com 部分训练得分： Model saved to ./output/best_model.pth New best model saved with average reward: 9.6 Episode: 0 | Train Reward: 25.0 | Epsilon: 0.995 | Best Eval Avg: 9.6…...

编程日记 2025/6/29 6:59:58

以下是在 Ubuntu 上的几款PDF 阅读器，涵盖轻量级、功能丰富和特色工具：

默认工具：Evince（GNOME 文档查看器） 特点：Ubuntu 预装，轻量快速，支持基本标注和书签。安装：已预装，或手动安装： sudo apt install evince功能全面：Okular&…...

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

有关水下图像增强的论文

4.21 TEBCF：Real-World Underwater Image Texture Enhancement Model Based on Blurriness and Color Fusion 基于模糊和颜色融合的现实水下图像纹理增强模型 2022年的一篇文章，基于传统方法，基于不同的色彩方法构建了两个新的融合输入。一…...

编程日记 2025/6/29 7:56:31

Raycaster光线投射

Raycaster光线投射 3D虚拟工厂在线体验描述光线投射Raycaster，用于进行raycasting（光线投射）。光线投射用于进行鼠标拾取（在三维空间中计算出鼠标移过了什么物体）。构造器 Raycaster( origin : Vector3, dire…...

编程日记 2025/7/8 19:36:21

javaEE——单例模式

目录前言1.概念2. 实现3. 比较和改进总结前言本篇文章来介绍单例模式，并讲述在保证线程安全的前提下，单例模式的写法。 1.概念单例模式是一种设计模式，可以说是写代码的一种模板，如果在一些固定的场景下按照设计模式进行写…...

编程日记 2025/6/29 5:11:29

WSL在D盘安装Ubuntu

目录前提条件步骤一：查看可用的Linux发行版步骤二：安装Ubuntu 22.04步骤三：导出已安装的Ubuntu到D盘步骤四：注销当前Ubuntu安装步骤五：在D盘导入Ubuntu启动Ubuntu 前提条件 Windows 10或Windows 11系统已启用WSL功能…...

编程日记 2025/7/12 15:19:31

Java并发编程-多线程基础（三）

文章目录线程间通信线程间通信的核心问题volatile 关键字1. 核心特性2. 使用限制3. 示例 synchronized 关键字1. 核心特性2. 示例 volatile 与 synchronized 的对比Volatile 和 Synchronized 最佳实践线程间通信线程间通信的核心问题多个线程通过共享内存实现信息交换&am…...

编程日记 2025/7/4 4:03:38

React--》掌握react构建拖拽交互的技巧

在这篇文章中将深入探讨如何使用react-dnd，从基础的拖拽操作到更复杂的自定义功能带你一步步走向实现流畅、可控且用户友好的拖拽体验,无论你是刚接触拖拽功能的初学者还是想要精细化拖拽交互的经验开发者，都能从中找到适合自己的灵感和解决方案。目录 …...

编程日记 2025/7/14 7:15:36

【Qt】常用的类与数据类型

目录一、Qt常见基本数据类型二、Qt 字符串类应用 2.1 操作字符串 2.2 查询字符串三、QMap 类&QHash 类&QVector 类 3.1 QMap 类 3.2 QHash 类 3.3 QVector 类四、QList 类&QLinkedList 类 4.1 QList 类 4.2 QLinkedList 类 4.3 STL 风格迭代器遍历…...

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

React实现B站评论Demo

该Demo涉及的技术点 useState函数（数据驱动视图）子组件的封装条件判断回调函数的封装 1、评论数据 {"list": [{"rpid": 3,"user": {"uid": "13258165","avatar": "http://toutiao.…...

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

从实列中学习linux shell12 通过Shell脚本来优化MySQL数据库性能，特别是慢SQL跟踪和索引优化

在Shell脚本中优化MySQL数据库性能，特别是慢SQL跟踪和索引优化可以通过以下步骤实现。以下是一个结构化的解决方案，包含示例代码和详细说明： 1. 启用慢查询日志目标：动态启用慢查询日志并配置参数，收集慢SQL数据。…...

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

ES6入门---第三单元模块一：类、继承

补充： prototype 属性使您有能力向对象添加属性和方法。 object.prototype.namevalue <script>function Person(name, age){this.name name;this.age age;}/* Person.prototype.showName function(){return 名字为: ${this.name};};Person.prototype.showA…...

编程日记 2025/6/28 20:05:32

CSS 变量与原生动态主题实现

CSS 变量与原生动态主题实现 CSS 变量基础 CSS 变量（自定义属性）是 CSS 语言的一项强大功能，允许我们在样式表中定义和重用值。与 SCSS 或 LESS 等预处理器中的变量不同，CSS 变量在运行时计算，这意味着它们可以动态更…...

编程日记 2025/7/14 10:32:54

Ubuntu 安装 Docker

安装 Docker 1. 卸载旧版本（如果有） sudo apt-get remove docker docker-engine docker.io containerd runc 2. 更新 APT 包的索引 sudo apt-get update 3. 安装依赖包 sudo apt-get install -y \ca-certificates \curl \gnupg \lsb-release4. 添加…...

编程日记 2025/6/28 20:05:28

SpringMVC——第三章：获取请求数据

假设有这样一个请求：http://localhost:8080/springmvc/register?namezhangsan&password123&emailzhangsanpowernode.com 在SpringMVC中应该如何获取请求提交的数据呢？ 在SpringMVC中又应该如何获取请求头信息呢？ 在SpringMVC中又应…...

编程日记 2025/6/28 20:05:26

动静态库【Linux操作系统】

文章目录动静态库制作静态库如何把第三方库安装在Linux系统中，如何使用第3方库方案一：为什么我们之前使用gcc/g编译C/C标准库的时候不用加选项-l xxx呢？方案二：方案三： 为什么不同平台的库不一样呢？动态库…...

编程日记 2025/7/9 12:28:23

Day 4:牛客周赛Round 91

好久没写了，问题还蛮多的。听说这次是苯环哥哥出题 F题小苯的因子查询思路考虑求因子个数，用质因数分解；奇数因子只需要去掉质数为2的情况，用除法。这里有个比较妙的细节是，提前处理出数字x的最小质因数&#xff0…...

编程日记 2025/6/28 20:05:21

drawDB：打造高效数据库设计流程

drawDB：打造高效数据库设计流程 drawDB 简介资源链接核心功能详解1. 直观的实体关系图设计2. SQL 脚本生成3. SQL 导入功能4. 本地化存储与分享功能5. 自定义主题与外观安装和使用教程本地开发环境搭建构建生产版本Docker 部署基本使用方法应用场景和实际价值适用…...

编程日记 2025/7/10 16:39:34

【心海资源】子比主题新增注册与会员用户展示功能模块及实现方法

内容改写： 本次分享的是子比主题顶部展示注册用户与会员信息的功能模块及其实现方式。你可以通过两种方式启用该功能： 直接在后台进入“外观 → 小工具”启用该展示模块，操作简便；也可将提供的代码覆盖至子比主题目录中&#…...

编程日记 2025/6/29 7:49:24

gitblit安装教程，搭建一个属于自己的Git版本仓库

本章教程，主要记录如何在Windows服务器上利用gitblit搭建GIT私有化仓库。一、gitblit简介官网地址：https://www.gitblit.com/ Gitblit 是一个开源的纯 Java 技术栈，用于管理、查看和服务Git仓库。它主要设计为一款面向希望托管集中式仓库的小型工作组的工具。二、基础环…...

编程日记 2025/6/28 20:05:17

2023年第十四届蓝桥杯省赛B组Java题解【简洁易懂】

2023年第十四届蓝桥杯省赛B组Java题解题型概览与整体分析题目编号题目名称题型难度核心知识点通过率（预估）A阶乘求和结果填空★☆☆模运算、数学规律95%B幸运数字结果填空★★☆进制转换、数位和计算80%C数组分割编程题★★☆组合数学、奇偶性分析65…...

编程日记 2025/6/29 7:57:06

Javase 基础加强 —— 01 异常

本系列为笔者学习Javase的课堂笔记，视频资源为B站黑马程序员出品的《黑马程序员JavaAI智能辅助编程全套视频教程，java零基础入门到大牛一套通关》，章节分布参考视频教程，为同样学习Javase系列课程的同学们提供参考。 01 课程安排…...

编程日记 2025/6/29 7:30:10

iview 表单验证问题 Select 已经选择还是弹验证提示

问题：iview 的 Select 下拉框的时候，数据验证必填，明明选择了数据，却一直提示验证不能通过 html代码： <Form ref"FormData" :model"FormData" :rules"ruleValidate" :label-width&qu…...

编程日记 2025/6/29 8:15:36

OrCAD中离图连接器、端口及网络标签的作用范围与选择指南

一、OrCAD主要连接元素概述在OrCAD Capture原理图设计环境中，有三种主要的网络连接元素：离图连接器(Off-Page Connector)、端口(Port)和网络标签(Net Alias)。理解它们的作用范围和使用场景对设计清晰、可维护的原理图至关重要。 PS： 电源和…...

编程日记 2025/6/29 7:48:36

dpm_sysfs_add

这段代码是 Linux 内核中**设备电源管理（PM）子系统**与 **sysfs 文件系统**交互的核心实现，主要功能是为设备创建电源管理相关的 sysfs 属性文件。以下从五个关键维度进行深度解析： --- ### 一、功能架构全景 mermaid graph TD …...

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

【AI论文】Phi-4-reasoning技术报告

摘要：我们引入了Phi-4-reasoning，这是一种拥有140亿参数的推理模型，在复杂的推理任务中表现出了强大的性能。通过监督式微调Phi-4，在精心策划的“可教”提示集上进行训练，这些提示集是根据复杂性和多样性的适当水平选…...

编程日记 2025/7/12 6:07:23

Android ART运行时无缝替换Dalvik虚拟机的过程分析

目录一,概述二,dex文件优化一,概述 Android 4.4发布了一个ART运行时，准备用来替换掉之前一直使用的Dalvik虚拟机，希望籍此解决饱受诟病的性能问题。老罗不打算分析ART的实现原理，只是很有兴趣知道ART是如何无缝替换掉原来的Dalvik虚拟机…...

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

node.js为什么产生？

从官网得知介绍如下 https://nodejs.org/zh-cn/learn/getting-started/introduction-to-nodejs Node.js是一个开源和跨平台的JavaScript运行时环境。 Node.js在浏览器之外运行V8 JavaScript引擎，这是Google Chrome的核心。这使得Node.js具有很高的性能。 Node.js应…...

编程日记 2025/6/29 7:49:26

智能工厂边缘计算：从数据采集到实时决策

智能工厂边缘计算：从数据采集到实时决策引言在智能制造场景中，传统云计算架构面临三大核心挑战：平均200ms的网络延迟无法满足实时控制需求，90%的工业数据未被有效利用，以及每月高达15TB的数据传输成本。边缘计算技术通过将计算能力下沉到数据源头，正在构建"端-边…...

编程日记 2025/6/29 7:13:59

个人健康中枢的多元化AI网络革新与精准健康路径探析

引言随着数字化转型的深入推进，个人健康中枢作为集成化健康管理系统，正在从传统的单一功能向多元化的AI驱动方向快速发展。在这一背景下，新兴网络硬件技术，特别是DPU（数据处理单元）和全光网络的出现，为个人健康中枢的革新提供了前所未有的机遇。本研究将深入探讨这些技…...

编程日记 2025/6/29 5:11:39

前端面试宝典---性能优化

一、加载优化 1. 第三方模块放在CDN 例如 leaflet通过cdn引入，这样就不会占用打包体积了 2. prefetch 预加载例如，之后马上有个场景需要一个图片，我们就可以通过link 的 prefetch 对资源进行预先加载再例如，我们公司是无网络开…...

编程日记 2025/6/29 7:53:02

【Springboot进阶】springboot+mybatis+jsqlparser实现数据权限控制

文章目录 SpringBoot JSqlParser MyBatis 数据权限实现方案一、环境准备1. 添加依赖二、用户上下文管理1. 用户上下文持有类三、数据权限拦截器实现1. MyBatis拦截器核心类四、Spring Security集成1. 用户信息注入五、配置项示例application.yml 六、使用示例1. 业务查询…...

编程日记 2025/7/14 16:38:06

【PostgreSQL数据分析实战：从数据清洗到可视化全流程】2.3 窗口函数与高级聚合（ROW_NUMBER()/RANK()/SUM() OVER()）

👉 点击关注不迷路 👉 点击关注不迷路 👉 点击关注不迷路文章大纲 PostgreSQL窗口函数与高级聚合：从排序到动态分析的全场景应用1. 窗口函数核心概念解析1.1 窗口函数语法结构1.2 核心组成要素2. 排名窗口函数深度解析2.1 ROW_NUMBER()：唯一顺序排名示例演示2.2 `RANK…...

编程日记 2025/6/29 6:38:45

python全自动爬取m3u8网页视频（各类网站都通用）

当前人工智能，大语言模型的火热，使得python这门编程语言的使用越来越广泛。最近也开始学习了python，发现它在自动化方面的确有得天独厚的优势。python的简单易用，丰富的开源库，完善的生态，使得它有可能成为…...

编程日记 2025/6/29 7:53:05

C++负载均衡远程调用学习之上报功能与存储线程池

目录 1. Lars-reportV0.1 report模块介绍 2.Lars-reporterV0.1 reporter项目目录构建 3.Lars-ReporterV0.1 数据表和proto协议环境搭建 4.Lars-ReporterV0.1上报请求业务处理 5.Lars-ReporterV0.1上报请求模块的测试 6.Lars-ReporterV0.2开辟存储线程池-网络存储分离 1. L…...

编程日记 2025/7/3 20:28:29

今天python练习题

目录一、每日一言二、练习题三、效果展示四、下次题目五、总结一、每日一言不要害怕失败，失败可能成为我们前进的动力！ 二、练习题有列表lst [[1,2,3],[4,5,6],[7,8,9]],取出其中的元素1/5/9组成新的列表 # 有列表lst [[1,2,3],[4,5,6],[…...

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

【leetcode100】最长递增子序列

1、题目描述给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 …...

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

R绘图|3分钟复现瑞士“苏黎世大学”Nature全球地图——基于R包ggplot2+sf等

一、引言本文我们复现苏黎世大学团队Franois Keck等在Nature最新文章“The global human impact on biodiversity”中的全球地图。之前的图纸是在平面坐标系里面进行绘制，本次我们在罗宾逊投影中进行绘制。整体代码逻辑非常简单，就是采样点坐标系的转换…...

编程日记 2025/6/29 7:38:22

百度系列产品学习

1.react-bmapgl封装逻辑 Map 分析react-bmapgl库中Map组件的封装流程，并以mermaid图展示。首先分析Map组件的核心实现，包括生命周期方法和子组件渲染逻辑。然后研究WrapperHOC和Component基类的封装模式，理解事件绑定和属性处理的通用逻辑。…...

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

题目1：

题目分析：

思路讲解：

代码实现：

题目2：

思路分析：

代码实现：

相关文章：