2020第11届蓝桥杯矩阵的真·详细题解

这篇具有很好参考价值的文章主要介绍了2020第11届蓝桥杯矩阵的真·详细题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

本文章主要面向算法初学者、蓝桥杯参赛者。

今天重温一手第十三届的统计子矩阵,搜索的时候发现了第十一届的矩阵题,然后看了下网上的文章,好家伙!全网对于此题没有高质量的文章和解答思路,全是贴个代码最多说一两句别的话,代码里注释都没几行,对于初学者而言简直是灾难, 下午整理了下思路,现在我会分享我的思路,以及如何从思路转变为代码。


一、从简单样例入手,解释为什么选择DP动态规划解法

原题大意如下:
把 1 ∼ 2020 放在 2 × 1010 的矩阵里。要求同一行中右边的数字比左边数字大,同一列中下边的数字比上边的数字大。一共有多少种方案?
答案很大,你只需要给出方案数除以 2020 的余数即可。

我们先别想解答2020个数,那个太漫长,我们可以先想想,如果我只需要排列几个数字,比如2个数呢,他们分别是1、2,这2个数分配到2行有什么结果呢?
1、2 ------两种排列,其中第一行2个第二行0个出现1次,第一行1个第二行1个出现1次
第一行:1、2  1
第二行:无    2
如果是3个数字呢?1、2、3?
1、2、3 ------三种排列,第一行3个第二行0个数字出现1次,第一行2个第二行1个数字出现2次
第一行:1、2、3  1、2 1、3
第二行:无      3    2
4个数字?1、2、3、4?
1、2、3、4 ------六种排列,第一行4个第二行0个数字出现1次,第一行3个第二行1个数字出现3次,第一行2个第二行2个数字出现2次
第一行:1、2、3、4  1、2、3  1、2、4  1、3、4  1、2  1、3
第二行:无       4     3      2     3、4  2、4

乍一看,里面似乎蕴含着这么一种规律:前一种情况会作为后一种情况的基础,比如一开始的1、2到1、2、3到1、2、3、4,三个数字的1、2 + 3会出现在四个数字的1、2 + 3、4里,新加入的数字总是继承前一种结果,然后会“粘”在前一种情况的某一行的后面,判断合法后形成本次数字的结果。
好像有点绕?看看下图吧
2020第11届蓝桥杯矩阵的真·详细题解
2020第11届蓝桥杯矩阵的真·详细题解
啊哈!现在看到这种规则,后一个结果由前一个结果得来的思路,恰恰符合动态规划DP的思路,一个一个结果继承,到最后就是想要的2020个数字的结果啦!

注意!千万不要陷进去找全部的数字排列,题目要找的是这2020个数字,每行装1010个数字的情况下一共有几个排列结果。第一行有1、2、3或者1、3、4,不用管是哪种排列,你应当都看成第一行有3个数字。这是我当初纠结了一会的点。

当第一行数字个数==第二行数字个数,说明最新的数加在了第二行,结果会与同等第一行数字但第二行数字个数-1的情况相同。
当第一行数字个数>第二行数字个数,说明可能是最新数字加在第一行或者第二行,都符合规则就加一起。
若第一行数字个数<第二行数字个数,非法,违反了题意直接毙掉。
动态状态方程:
i、j分别为第一行的数字和第二行的数字下,
当i == j,dp[i][j]=dp[i][j-1],
当i > j,dp[i][j] = dp[i-1][j] + dp[i][j-1]

二、答案与代码实现(C++)

#include<iostream>
using namespace std;
/*
dp[i][j] i为第一行的个数 j为第二行的数字个数
研究发现(其实是在纸上自己写):dp[2][1] = 2  dp[2][2] = 2  dp[3][0] = 1  dp[3][1] = 3  dp[3][2]=5
即当i>j  dp[i][j] = dp[i-1][j] + dp[i][j-1]
而当i==j dp[i][j] = dp[i][j-1]
不存在i<j,因为题目规则限定了第一行一定不小于第二行的数字个数。
*/

// 小技巧: 把要开很大的数组放main外面不会把栈空间撑爆. 
int dp[1011][1011];// 每一项初始值是0 
int main() {
	// 问题都是从小到大的,一开始排1个数,然后2个数,3个数...一直到排2020个数
	// dp[i][j] i为第一行的数字个数,j是第二行的数字个数,规则为i>j或i==j
	for (int i = 0; i <= 1010; i++) {
		// dp[i][0] 就是数字只放第一行,被限制死了排序,只能一路都是 右>左,12345... 134...
		// 所以只有1个排序结果 
		dp[i][0] = 1;
		for (int j = 1; j <= 1010; j++) {
			// 不存在i<j的情况 
			if (i < j) {
				break;
			}
			if (i > j) {
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 2020;
			}
			else if (i == j) {
				dp[i][j] = dp[i][j - 1] % 2020;
			}
		}
	}
	// 答案输出
	cout << "只有四个数的情况第一行2个第二行2个:" <<dp[2][2] << endl;
	cout << "只有四个数的情况第一行3个第二行1个:" << dp[3][1] << endl;
	cout << "只有四个数的情况第一行4个第二行0个:" << dp[4][0] << endl;
	cout << "那么排列2020个数字下,按要求每一行都是1010个:" << dp[1010][1010] << endl;
	return 0;
}

答案:1340


总结

人非圣贤,孰能无过,如果我的文章哪里有误或是解释不清楚,请您指正;亦或者您有什么不懂,欢迎留言评论呀,我会尽我所能解答。所有的评论、私信我都会定期查看并且回复。文章来源地址https://www.toymoban.com/news/detail-415535.html

到了这里,关于2020第11届蓝桥杯矩阵的真·详细题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【蓝桥杯嵌入式】第十四届蓝桥杯嵌入式[模拟赛2]客观题及详细题解

    解析 USART_CR1:控制寄存器1,其中的M位定义了数据字的长度,由软件对其设置和清零。 USART_CR2:控制寄存器2。 USART_BRR:波特率寄存器。 USART_DR:数据寄存器。 (如果现场不记得,可以查阅芯片手册) 答案: A 解析 在STM32微控制器中,DMA可编程的数据传送数目:最大为65535。(如果现场不

    2023年04月10日
    浏览(62)
  • 【蓝桥杯嵌入式】第十三届蓝桥杯嵌入式国赛程序设计试题以及详细题解

      本届国赛试题主要包含 LCD 、 LED 、 按键 、 EEPROM 、 串口 、 模拟电压输入 、 脉冲输入输出 七大部分,其中前面三个部分是蓝桥杯嵌入式的“亲儿子”(必考部分),而剩下的四个部分都为“干儿子”(考频相对较高)。   相对于本届省赛两套试题:   本套试题 串口数

    2024年02月02日
    浏览(84)
  • 【蓝桥杯嵌入式】第十二届蓝桥杯嵌入式国赛程序设计试题以及详细题解

      本套试题较为常规,试题主要需要使用的模块有:LCD、LED、按键、定时器输入捕获功能、采集光照传感器的值以及串口,其中最重要的是 串口收发数据 以及 定时器的输入捕获功能 ,其余的各个部分还算比较常规、比较简单。下面咱就一起来看看这届赛题的题解吧!🤤🤤

    2024年02月06日
    浏览(50)
  • 【蓝桥杯嵌入式】第十四届蓝桥杯嵌入式[模拟赛1]程序设计试题及详细题解

    模拟赛1的题目中需要的准备的知识点不多,其中只用到了 串口 、 LCD 、 LED 、 按键 、 定时器的PWM输出 、以及 ADC 等几个模块,题目要求也简单详细并且数量不多,非常适合入门比赛,以及整合自己比赛的模块。 与模拟赛2相比,当然是模拟赛2的试题比较难啦,虽然需要的模

    2023年04月13日
    浏览(122)
  • 【蓝桥杯嵌入式】第十四届蓝桥杯嵌入式[模拟赛2]程序设计试题及详细题解

    这次的模拟赛试题模块还是一些常见模块: LCD 、 LED 、 按键 、 定时器 以及 串口 ,相对比较常规,相比于真正的省赛也比较简单。但是它 适合刚刚学完各个模块需要做真题的同学 ,可以借此来巩固自己之前所学;对于已经能够掌握各个模块的同学也是有帮助的,就是平台

    2023年04月13日
    浏览(111)
  • 【蓝桥杯嵌入式】第十四届蓝桥杯嵌入式省赛[第一场]程序设计题以及详细题解

      今年的第一场比赛绝对np,官方将串口直接省掉了,将其替换成很多小功能,如:切换计时、频率均匀变化、锁机制等等,总的来说本届赛题的难度提升了不少。   本届试题需要用到的功能模块有 LCD 、 LED 、 按键 、 定时器输入捕获 、 定时器PWM输出 、 ADC获取 ,虽然这

    2023年04月17日
    浏览(75)
  • [USACO11MAR] Brownie Slicing G题解(二分+二维前缀和+矩阵分割)

    题目地址 P3017 [USACO11MAR] Brownie Slicing G 二分最大化最小值 切割思路: 一行一行进行切割,如果这一行可以切割出b块大于等于mid的块,就开始切割下一行 如果无法切割出b块,就把正在切割的行与下一行拼起来一起切割 最后通过能切割出b块的水平块块够不够a条来判断m是否合

    2024年02月07日
    浏览(38)
  • 图书管理系统(Java实现,十个数据表,含源码、ER图,超详细报告解释,2020.7.11更新)...

    图书管理系统数据库设计实验报告 2020.7.11 修改了表的结构,表之间增加了外键联系,更加完整且符合第三范式。 数据库设计实验报告 疫情期间,大家都只能够在家里,不能去到学校,此时需要在图书馆借书,就是只能通过网络来操作了。因此,网上图书馆就此诞生了,有了

    2024年02月05日
    浏览(122)
  • 2020 CSP - J初赛 题解

    快要CSP了,最近疯狂刷题中… 终于 抽出时间 乘爸妈不在 写了一篇题解 如需做题,请到以下网站自行练习。 本博客只提供讲解。 洛谷有题 初赛真题 - 信奥赛题库 题号 1~5: A A D C C 6~10: B A A A A 11~15: A D C A A 16~20: 对 错 对 错 A 21~25: D 错 错 对 D 26~30: B D 错 对 错 31~35:

    2024年02月11日
    浏览(41)
  • 2020ICPC南京【个人题解EFHKLM】

    首先如果炸弹在(0,0)或者机器人最终停在炸弹处,那么一定Impossible。 对于其他的情况,如果存在一条路径使得机器人可以不经过炸弹,那么一定存在一种方案,使得相同的方向在这个方案种是连在一起的。 于是可以直接枚举所有方向的排列,共4!个,判断每一种排列能否绕过

    2023年04月09日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包