当前位置: 首页 > 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…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

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

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

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...