louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共3篇）

题解 | 信息学奥赛一本通树屋阶梯

思路很明显所有的阶梯都顶到某一列的顶部.枚举顶到第一列阶梯顶部的阶梯的长度,接下来列都不能到第一列,前列的最下面行全部空出来,这样子就形成一个子问题,而最后列也是一个子问题,中间空出来那部分也由该子问题扩充过去.如图,第一列选了黄色部分的三块,红色部分是一个子问题,绿色部分是一个子问题,中间白色部...

高精度卡特兰数

2019-09-01

0 761

题解 | 信息学奥赛一本通有趣的数列

思路我们将按次序填入,填入未填的,编号最小且为奇/偶数的项.也就是说,位置必须在之后再填.因为,任何时候已填的奇数项不能少于偶数项.这样子可以看成一个栈,填入一个奇数项表示一个元素进栈,填入一个偶数项表示栈顶弹出.所以答案就是卡特兰数第项.复杂度大概为. 代码 #include<bits/s...

卡特兰数

2019-09-01

0 573

题解 | 信息学奥赛一本通网格

思路首先所有的路径数为,也就是选出个时间点向上,其他时候向右.然后只要减去越过的路径即可.先上图:将上移,变成,也就是路径不能碰到.将路径最后一个碰到的点与以为对称轴翻折.也就是粉色点路径翻折成紫色点路径.这样的路径一定是一一对应的,因为从到的路径一定可以唯一地翻折回来,而且这样的路径肯定是碰到的...

高境地卡特兰数

2019-08-24

0 695