床长人工智能教程50免费pdf文档——「noip模拟题」
.
声明:本人只是分享一些床长人工智能教程相关的免费pdf文档而已,并非床长人工智能网校的收费文章。尊重版权,支持原创!
模拟题华尔街的秘密【模拟题】华尔街的秘密
最近美国人致力于掀翻华尔街的资本家们,因为他们的生活并不太好,可是那些资本家却依然过着奢华的享乐生活。
一些人在游行,而另一些人则试揭开华尔街的金融家们获取财富的秘密,终于,白宫发现了这个秘密,那就是一个括号矩阵!!!
所谓括号矩阵,就是一个的矩阵,其中的每一个元素要么是,要么是。
矩阵中有公共边的格子是相邻的。
从矩阵的左上角,到右下角,的一条路径,如果满足下一步要么走到右边相邻的格子,要么走到下边相邻的格子,它就是一条最短路径。
一条路径是合法的,当且仅当它形成的括号序列是可以匹配的,例如等等都是可匹配的,而等等是不可匹配的。
一个括号矩阵合法,当且仅当其所有的最短路径合法。
现在,我们定义两个大小相等的合法括号矩阵和的比较。
数组是和括号矩阵大小相等的矩阵,规模也是,其中的元素是~间整数,且互不相同,即个整数出现且仅出现了一次。
找到满足如下条件的,,≠,且最小。
若,则,否则。
现在奥巴马已经得知某个括号矩阵里面藏着金融家们的致富密码,他会告诉你三个整数,你需要找出第小的的矩阵,这就是那个秘密矩阵。
输入第一行有三个整数,。
接下来有行,每行个数,第行第个数表示。
输出一个的矩阵,由和组成。
,中所有元素保证不同
保证存在答案矩阵
刘峻琳
首先感谢刘峻琳学长留下的这道题目。
还有,题目样例太水,这里提供一组加强版大大的方便了解题
题目大概就是这个样子了。
我们读一读题,发现是让我们输出一个以数组为映射或者这样理解,就是说按照数组的大小进行比较的第大的合法矩阵。
那么什么是合法的矩阵呢?题目中说道,就是从左上角只能够向右或者向下走到右下角的所有路径都是合法的括号序列。
怎么做呢?
我们得出一个惊人的事实所有的路径都是同一个括号序列
我们试从样例来解释一番
是不是竖着的一样呢?
或者说,从右上到左下的对角线都是一样的。
所以我们只需要找出第大的长度为括号序列即可。
注意,这里的比较方式不是从左往右,而是按照数组的顺序。
||
括号序列的总数是超过范围的,但是是在范围之内的。
||
所以说,只要的大小超过了,那么显然超过了
||
在当前已选的部分括号序列的情况下,可能的括号序列的个数
是当前位置在括号序列中对应的排名
得到比较括号序列大小的顺序
||
根据括号序列输出合法矩阵。。。