[蓝桥杯 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呢?

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

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

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

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

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

其实就是 

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/491505.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VCU--新能源汽车VCU电控开发

课程目标 信号采集的原理 使用simulink处理信号 做一个MIL仿真测试 零、参考 构建Simulink模型——CAN通信 | chans Bloggerrrrr 一、功能概述 1.硬线信号 定义&#xff1a;通过物理导线直接连接的电气信号&#xff0c;一根导线传输一个信号。本质&#xff1a;是一种点对…

Codeforces Round 993 (Div. 4)题解

A. Easy Problem 思路&#xff1a;经过看了一眼&#xff0c;我们发现&#xff0c;ab的和一定是n&#xff0c;且两个都是正整数&#xff0c; 所以a的范围就是从1~n-1 所以输出n-1即可 #include<bits/stdc.h> using namespace std; #define int long long int t; int n…

日期格式、JSR303校验

日期格式 public class Monster() {DateTimeFormat(pattern "yyyy-MM-dd")private Date birthday; } 输入&#xff1a;2024-11-12&#xff0c; 输出&#xff1a;Monster{birthdaySun Nov 12 00:00:00 CST 2024} public class Monster {JsonFormat(pattern &…

数据结构——队列的模拟实现

大家好&#xff0c;上一篇博客我带领大家进行了数据结构当中的栈的模拟实现 今天我将带领大家实现一个新的数据结构————队列 一&#xff1a;队列简介 首先来认识一下队列&#xff1a; 队列就像我们上学时的排队一样&#xff0c;有一个队头也有一个队尾。 有人入队的话就…

红外测温原理及设计

1、红外测温仪 经过新冠疫情的洗礼&#xff0c;大家对红外测温枪应该不陌生。在公共场所、企业单位乃至家庭门口&#xff0c;它都成了守护健康的第一道防线。然而&#xff0c;关于红外测温枪有个细节常被误解——它那闪烁的红点&#xff0c;大部分人会认为就是用这个红色的点测…

了解垃圾回收机制与内存泄漏

目录 一、垃圾回收机制的基本原理 &#xff08;1&#xff09;基本原理理解 &#xff08;2&#xff09;回收 二、垃圾回收的算法 1.标记清除算法 2.引用计数算法 三、减少垃圾回收 &#xff08;1&#xff09;减少对象创建 &#xff08;2&#xff09;优化数据结构及内存…

Stable Diffusion Controlnet常用控制类型解析与实战课程 4

本节内容&#xff0c;是stable diffusion Controlnet常用控制类型解析与实战的第四节课程。上节课程&#xff0c;我们陆续讲解了几个与图像风格约束相关的控制类型&#xff0c;本节课程我们再学习一些实用价值较高的控制类型&#xff0c;看一看他们提供了哪些控制思路。 一&…

C++之二:类和对象

相关代码&#xff1a; C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析求解问题的步骤&#xff0c;调用函数逐步解决问题。 C是面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情的完成分为不同的几个参与者&#xff08;对象&#xff09;&#xff0c;靠…

B站bilibili视频转文字字幕下载方法

本文将讲述介绍一种使用本地工具如何快速的下载B站的字幕为本地文本文件的方法。 通常获取B站字幕需要在浏览器中安装第三方插件&#xff0c;通过插件获取字幕。随着大模型&#xff0c;生成式AI&#xff0c;ChatGPT的应用&#xff0c;B站也提供了AI小助手对视频的内容进行总结…

EM算法的参数更新过程

1. 计算每个高斯分布的责任度 责任度&#xff08;Responsibility&#xff09; 表示数据点 由第 k 个高斯分布生成的概率占总概率的比例。在 E步&#xff08;Expectation Step&#xff09; 中计算。 公式&#xff1a; 其中&#xff1a; ​: 责任度&#xff0c;表示数据点 ​ …

文件包含include

文件包含 第一道题是攻防世界的fileclude 这里第二行我们可以看见告诉我们在flag.php里面 然后检查了两次file1和file2是否为空 如果file2"hello ctf"成立 那么就可以包含file1 这里我们要使用php伪协议 来访问我们需要的flag.php并且将file2的数值改为"hello…

优选算法——链表

1. 链表常用技巧和操作总结 2. 两数相加 题目链接&#xff1a;2. 两数相加 - 力扣&#xff08;LeetCode&#xff09; 题目展示&#xff1a; 题目分析&#xff1a;本题给的是逆序&#xff0c;其实降低了难度&#xff0c;逆序刚好我们从第一位开始加&#xff0c;算法原理其实就…

【5G】5G的主要架构选项

最初&#xff0c;在3GPP讨论中考虑了所有可能的聚合和核心网络组合&#xff0c;共有八个架构选项。以下重点介绍option2、3、4和7。 1. 独立组网 (Standalone, SA) 架构选项 2 &#xff1a;Standalone architecture with 5G-core 特点&#xff1a; 5G核心网&#xff08;5GC, …

css 动画实现从中间到两边亮度逐渐变暗的流水灯效果

先看效果&#xff1a; 快结束效果 随着离中心点距离逐渐边远&#xff0c;亮度逐渐变暗 完整的视线代码如下&#xff1a; <template><div class"container"><div class"runner bottom to-right"></div><div class"runner …

kubeadm_k8s_v1.31高可用部署教程

kubeadm_k8s_v1.31高可用部署教程 实验环境部署拓扑图**部署署架构****Load Balance****Control plane node****Worker node****资源分配&#xff08;8台虚拟机&#xff09;**集群列表 前置准备关闭swap开启ipv4转发更多设置 1、Verify the MAC address and product_uuid are u…

测评|携程集团25年社招在线测评北森题库、真题分析、考试攻略

携程集团社招入职测评北森题库主要考察以下几个方面&#xff1a; 1. **言语理解**&#xff1a;这部分主要测试应聘者运用语言文字进行思考和交流、迅速准确地理解和把握文段要旨的能力。 2. **资料分析**&#xff1a;包括文字题和图表题&#xff0c;考察应聘者快速找出关键信息…

workman服务端开发模式-应用开发-websockt应用介绍

一、workerman介绍 1、框架介绍 workerman-chat框架是基于workerman的GatewayWorker框架开发的一款高性能支持分布式部署的聊天室系统。 workerman框架官网&#xff1a;http://www.workerman.net/ GatewayWorker框架文档&#xff1a;http://www.workerman.net/gatewaydoc/ 2、特…

34. 在排序数组中查找元素的第一个和最后一个位置 二分法

34. 在排序数组中查找元素的第一个和最后一个位置 class Solution { public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> res(2,-1);res[0]findleft(nums,target);if(res[0] -1) return res;res[1] findright(nums,target);…

#渗透测试#漏洞挖掘#红蓝攻防#护网#sql注入介绍03-SQL注入联合查询注入(Union-Based SQL Injection)

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…

你了解TCP/IP参考模型吗

前言 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新。 作者&#xff1a;神的孩子都在歌唱 你了解TCP/IP参考模型吗 一. TCP/IP参考模型二. TCP/IP模型图解三. TCP/IP模型的对比与OSI模型四. TCP/IP协议族五. 总结 TCP/IP参考…