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

[蓝桥杯 2019 国 B] 排列数

目录

前言

题解

思路

疑问

解答


前言

对于本篇文章是站在别人的基础之上来写的,对于这道题作为2019年国赛B组的最难的一题,他的难度肯定是不小的,这道题我再一开始接触的时候连思路都没有,也是看了两三遍别人发的题解,才慢慢明白了怎么去写。那么对于题解我就直接引用别人的优秀题解,但后再加上我对题解写的不详细的地方进行尽可能详细的描述补充。

题解

以下题解全来自洛谷

思路

设状态 dp[i][j]dp[i][j] 其中 ii 表示前 ii 个数中,有 jj 个折点的方案数。

考虑状态转移,显然 dp[i][j]dp[i][j] 只能影响到 dp[i+1][j]dp[i+1][j]、dp[i+1][j+1]dp[i+1][j+1]、dp[i+1][j+2]dp[i+1][j+2],证明如下:

首先需要确定,在原序列中插入第 i+1i+1 个数,这个 i+1i+1 是所有数中最大的,所以只要在非头/尾部插入这个点,这个点一定就是新的折点。

  1. dp[i+1][j]dp[i+1][j] 表示插入第 i+1i+1 个点后没有新增折点:

    例:

    情况一如图,当 i+1i+1 插入波峰 xx 左右侧时,xx 不再是折点,折点变成了 i+1i+1,此时折点数不变。

    情况二如图,当 i+1i+1 插入序列头尾 xx 左右时,xx 依然不是折点,序列没有新增折点,此时折点数不变(如果头或尾的点是向下走的那么插入后新增了一个点,不属于该范围,此时只有在其中一边插入 i+1i+1 才能满足不增加新折点)。

  2. dp[i+1][j+1]dp[i+1][j+1] 表示插入第 i+1个点后新增了一个转折点。

    只有一种情况,即当在序列头和尾向下走时在头和尾前后插入 i+1只增加一个转折点,如图,xx 为新增的一个转折点。

    所以转移方程:

    dp[i+1][j+1]=dp[i][j]×2dp[i+1][j+1]=dp[i][j]×2
  3. dp[i+1][j+2]dp[i+1][j+2] 表示插入第 i+1 个点后新增了两个转折点。

    显然在除了以上所有情况,其他地方插入 i+1i+1 都会新增两个折点,转移方程:

初始值:dp[1][0]=1dp[1][0]=1、dp[i][0]=2(1<i<n)dp[i][0]=2(1<i<n)。

答案:dp[n][k−1]dp[n][k−1]。

疑问

我问的疑问的地方就是我上面标红的地方以及图片插入的地方,是由这些地方而引出的疑问。

1>:为什么只在波峰处的左右插入?在峰谷处插入不符合?为什么呢?

2>:为什么第一种情况下的公式,为什么奇数情况下是j-1/2,偶数下是j/2?

 3>:插入第 i+1 个点后新增了一个转折点,这种情况按照如图所表示,他应该是只由特殊情况下,只会增加二啊,为什么用公式总结下来是直接*2呢?

就比如这种情况,我也没在头尾处插入啊?那他这种情况也是属于增加了一个转折点啊?

 4>:对于题解中的第三种情况是什么呢?

解答

相信你看完上面的四个疑问,心里肯定会有所疑问,那也相信通过你自己的思考,肯定会解决一两个疑问。无论如何,下面就由我来为大家解决四个疑问。

疑问一 :为什么只在波峰处的左右插入?在峰谷处插入不符合?为什么呢?

其实这个疑问人家题解也说的很明确了,也解释了在波峰处插入确实不会增加转折点,但我还是要说一点,这里人家只说是在波峰的左右处插入,没有说在峰谷插入的问题,这个一定要注意。而且在疑问三中,我也用图解释了在峰谷处插入也确实是会增加一个转折点的。所以不增加转折点的插入方法就只有两种情况,也就是题解说的两种情况。

疑问二: 为什么第一种情况下的公式,为什么奇数情况下是j-1/2,偶数下是j/2?

关于这个疑问,我们首先要知道一个结论:当转折点是奇数时:转折点数=峰谷+波峰=波峰*2+1/峰谷*2+1(相差不超过1。这是因为在一个排列中,波峰和峰谷是交替出现的。例如,如果一个排列从一个波峰开始,那么接下来可能是一个峰谷,然后再是一个波峰

当转折点时偶数时:峰谷=波峰

 这可以通过大量的举例来观察得到。我这里就简单的给大家简单的证明一下

首先我们假设,他的头与尾都是朝上的情况,大致如图所示

那么如果图中有一个波峰,那么他一定是比他的左右都是大的(图略有粗糙,能看明白就行)

假如这个波峰的高度是小于两边的高度的,那他还是会至少存在两个峰谷的。

假如这个波峰的高度在两边高度之间,那么同样因为存在一个波峰的原因,他至少会存在两个峰谷。

假如这个波峰的高度高于两边的高度,那么这时候会存在两种情况,第一种情况是没有峰谷,还有一种情况就是至少存在两个峰谷。

以次类推,在讨论当两边的头尾是向下的情况,

 如果在中间插入一个波峰

然后再分三种情况,与两边的高度做套路

假设他的高度高于两边,那么峰谷的数量为0,或者至少为两个

假设他的高度再二者中间,那么必定还存在一个与之相对应的波峰,还有中间存在一个峰谷。

假设他的高度再二者之下,那么,那么他必有一个向下的调整,那么对于这种情况,他必定会至少由三个波峰,两个峰谷。

 对于上面的解释说明肯定说的不是很清楚,但是只要知道一点:

当转折点是奇数时:转折点数=峰谷+波峰=波峰*2+1/峰谷*2+1(相差不超过1。这是因为在一个排列中,波峰和峰谷是交替出现的。例如,如果一个排列从一个波峰开始,那么接下来可能是一个峰谷,然后再是一个波峰

当转折点时偶数时:峰谷=波峰

 所以公式中也就是用 j-1/2 来计算的。

疑问三:插入第 i+1 个点后新增了一个转折点,这种情况按照如图所表示,他应该是只由特殊情况下,只会增加二啊,为什么用公式总结下来是直接*2呢?

 关于这个疑问,也是我疑惑时间最长的。

但想明白了其实还是蛮简单的,其实就是题解描述的不够清楚,

这个只是不同构型下会产生不同的结果,但是这个加的位置也就是题解里考虑的范围,硬要说就是题解表述不完全,没有对全部构型画图。

注意:人家说的是在头尾的前后插入!!! 

疑问四:对于题解中的第三种情况是什么呢?

其实就是 

对于这四个疑问就全解答完毕了,如果有帮助,还请点赞。 

相关文章:

[蓝桥杯 2019 国 B] 排列数

目录 前言 题解 思路 疑问 解答 前言 对于本篇文章是站在别人的基础之上来写的&#xff0c;对于这道题作为2019年国赛B组的最难的一题&#xff0c;他的难度肯定是不小的&#xff0c;这道题我再一开始接触的时候连思路都没有&#xff0c;也是看了两三遍别人发的题解&#x…...

[bug] StarRocks borker load意向之外的bug

意向之外&#xff0c;又清理之中 背景&#xff1a; StarRocks各方面碾压相同类型的数据库&#xff0c;最近我们要从生成HIVE导历史数据&#xff08;ORC格式&#xff09;到StarRocks&#xff0c;前期小测一下&#xff0c;在测试是没问题&#xff0c;上生产先导2个月的数据&…...

2025年前端面试热门题目——HTML|CSS|Javascript|TS知识

以下是对这些 HTML 面试问题的详细解答&#xff1a; 1. HTML 的 src 和 href 属性有什么区别? src (Source) 属性&#xff1a; 用于嵌入资源&#xff0c;例如图像、脚本或 iframe。加载资源时&#xff0c;当前页面的加载会暂停&#xff0c;直到资源加载完成。常用于 <img&g…...

Linux中部署项目

1.下载JDK17 进入 /usr/local 目录&#xff0c;创建 java 文件夹。并将 JDK17 上传到 java 目录下。 上传成功后&#xff0c;通过cd命令进入Java文件夹目录&#xff0c;解压 JDK17 压缩包&#xff0c;命令 unzip zulu17.44.53-ca-jdk17.0.8.1-linux_x64.zip。 如果报错说 u…...

在 CentOS 上安装 MySQL 8

在 CentOS 上安装 MySQL 8 您可以按照以下步骤操作&#xff1a; 1. 更新系统 首先&#xff0c;更新系统软件包以确保安装的最新版本。 sudo yum update -y 2. 安装 MySQL 8 安装 MySQL 存储库 wget https://dev.mysql.com/get/mysql80-community-release-el7-3.noarch.r…...

gradle项目下载依赖报错

报错信息 Cannot resolve external dependency org.projectlombok:lombok:1.18.36 because no repositories are defined. Required by:project :Possible solution:- Declare repository providing the artifact, see the documentation at https://docs.gradle.org/current/…...

solon 集成 activemq-client (sdk)

原始状态的 activemq-client sdk 集成非常方便&#xff0c;也更适合定制。就是有些同学&#xff0c;可能对原始接口会比较陌生&#xff0c;会希望有个具体的示例。 <dependency><groupId>org.apache.activemq</groupId><artifactId>activemq-client&l…...

LRU 缓存

LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中&#xff0c;则返回关键字的值&#xff0c;否…...

使用ZLMediaKit 开源项目搭建RTSP 服务器

ZLMediaKit 是啥&#xff1f; ZLMediaKit是国人开发的开源C流媒体服务器&#xff0c;同SRS一样是主流的流媒体服务器。 ZLToolKit是基于C11的高性能服务器框架&#xff0c;和ZLMediaKit是同一个作者&#xff0c;ZLMediaKit正是使用该框架开发的。 官网 ZLMediaKit开源地址&…...

数组晨考2day08

1.用一句话描述数组 在内存中 一块连续的空间 存储相同类型的数据 长度是固定的 2.数组各个类型的默认值 整数&#xff1a;0 浮点&#xff1a;0.0 布尔&#xff1a;false 字符&#xff1a;\u0000 其他&#xff1a;null 3.Arrays类toString&#xff0c;copyOf&#xff0c;sort&a…...

《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介

《鸿蒙HarmonyOS应用开发从入门到精通&#xff08;第2版&#xff09;》已于近日上市&#xff0c;该书由北京大学出版社出版。距离第1版上市已经过去二年半多。本文希望与读者朋友们分享下这本书里面的大致内容。 封面部分 首先是介绍封面部分。 《鸿蒙HarmonyOS应用开发从入门…...

麒麟操作系统服务架构保姆级教程(二)sersync、lsync备份和NFS持久化存储

如果你想拥有你从未拥有过的东西&#xff0c;那么你必须去做你从未做过的事情 上篇文章我们说到rsync虽好&#xff0c;但是缺乏实时性&#xff0c;在实际应用中&#xff0c;咱们可以将rsync写进脚本&#xff0c;然后写进定时任务去备份&#xff0c;如果每天凌晨1&#xff1a;00…...

将OBJ或GLB文件转换为3DTiles

格式简介 GLB文件&#xff08;.GLB&#xff09;代表“GL传输格式二进制文件”&#xff0c;是用于共享3D数据的标准化文件格式。确切地说&#xff0c;它可以包含有关三维模型、场景、模型、光源、材质、节点层次和动画的信息。 OBJ文件是一种文本文件格式&#xff0c;这就意味…...

Flink DataStream API 编程指南

(对于Flink的开发,建议使用Java,Scala的支持未来会被移除) DataStream是什么 DataStream API得名于DataStream这个Java类,可以将它们视为可以包含重复项的不可变数据集合。该数据可以是有限的,也可以是无限的,用于处理它们的API是相同的。 DataStream在用法上和普通的…...

tryhackme-Pre Security-HTTP in Detail(HTTP的详细内容)

任务一&#xff1a;What is HTTP(S)?&#xff08;什么是http&#xff08;s&#xff09;&#xff09; 1.What is HTTP? (HyperText Transfer Protocol)&#xff08;什么是 HTTP&#xff1f;&#xff08;超文本传输协议&#xff09;&#xff09; http是你查看网站的时候遵循的…...

探索 Plotly:一个强大的交互式数据可视化库

探索 Plotly&#xff1a;一个强大的交互式数据可视化库 数据可视化是数据分析过程中不可或缺的一部分&#xff0c;它能帮助我们更直观地理解数据&#xff0c;发现数据中的趋势和规律。在众多可视化库中&#xff0c;Plotly 是一个非常强大的工具&#xff0c;它以其交互式、易用…...

Oracle 查询表占用空间(表大小)的方法

目录 概述方法一&#xff1a;使用 dbms_space 包方法二&#xff1a;查询 dba_extents 视图方法三&#xff1a;查询 dba_segments 视图总结 1. 概述 在Oracle数据库管理中&#xff0c;了解特定表或索引所占用的空间对于性能调优、存储规划以及资源分配至关重要。本文档介绍了三…...

机器人国际会议IROS论文latex模板

机器人国际会议IROS论文latex模板 文档 root.tex 可以配置为 US Letter 纸或 A4。请注意以下重要行&#xff1a;\documentclass[letterpaper, 10 pt, Conference]{ieeeconf} % 如果需要 a4paper&#xff0c;请注释掉此行%\documentclass[a4paper, 10pt, Conference]{ieeeconf} …...

雪泥鸿爪和屈指可数

paw这个单词&#xff0c;表示“爪或手”&#xff0c;是一个和hoof相对的单词&#xff1a; hoof n.(马等动物的)蹄paw n.爪子&#xff1b;(动物的)爪&#xff1b;(人的)手 v.挠&#xff0c;抓&#xff1b;动手动脚 所以&#xff0c;当你理解了 paw 和 hoof 是相对的概念时&…...

2024年度个人总结

一转眼已经2024年度最后一个月了&#xff0c;今年基本没有在CSDN发布内容&#xff0c;包括其他平台&#xff08;B站&#xff09;&#xff0c;倒是在其他地方&#xff08;我的个人网站和V2EX&#xff09;发布一些零碎的东西&#xff0c;主要是因为今年换了工作后太累了&#xff…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

Selenium 查找页面元素的方式

Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素&#xff0c;以下是主要的定位方式&#xff1a; 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...