[0x11] 130.火车进站问题【卡特兰数】
题意
简化题意:给定严格从 \(1\thicksim n\) 这 \(n(n\leqslant 6\times10^4)\) 个整数,规定每个数都要进出栈各一次,求所有可能的出栈序列的数量。
这题有多种做法(爆搜,递推,dp,数学),最主要是 \(n\) 的范围,刚好会把像递推和 dp 这样的 \(O(n^2)\) 的次优化算法卡掉。
显然复杂度就要求是线性的,如此,可以使用组合数学中的 卡特兰数Catalan(link)。
理论推导
首先,我们以 \(n=3\) 为例,可以得到所有合法序列为: \(\{123,132,213,231,321\}\) 。
可以想到合法序列的数量就是 \(n\) 的全排列与其非法序列的差,但由此还无法得到非法序列的普遍特性,而影响它是否是合法序列的,无外乎就是 压入、弹出两个操作 。
那么我们可以具象化压入为 +
,弹出为 -
,可以得到对应的 +-
序列为:
123&+-+-+-
\\132&+-++--
\\213&++--+-
\\231&++-+--
\\321&+++---
\end{cases}\]
合法序列规律
观察可得:
- \(num(+)=num(-)=n\);(注意:非法序列也可以)
- ∵在合法序列中,每一次弹出都与前面的一次压入是对应的,∴易得 \(\boxed{ sum_i\geqslant0(i\in[1,2n])}\) .(根据y总的说法,此乃 Catalan 的本质也)
非法序列规律
可能有的人和我一样,认为这里讨论的非法序列定义为:全排列中在栈中不可能存在的序列,但就是不存在,那我们也无法用 +-
序列表示出来。
那么,非法序列岂不是随便乱糊,可以有无数个了吗?
因此,我们必须在保证包括所有合法序列在其中的所有序列的集合中探求,形象地:
回到合法序列的两个规律中,显然非法序列就必须有两种性质:
- \(num(+)=num(-)=n\);
- \(sum_i<0(i\in[1,2n]).\)
所有序列的组合数
诶,我们顺便可以得到所有序列的公式啦,∵不管合不合法,都保证了同一性质,相当于在 \(2n\) 个空位中插入 \(n\) 个 +
或 -
,即: \(\large C_{2n}^n\) .
格式有点乱,不要紧,继续探求非法序列。
我们在 平面直角坐标系 上对其进行进一步探究。(我们把 \(+,-\) 分别对应 \(x,y\) 作为一个单位的增量,且只能有这两种操作)
由于 \(num(+)=num(-)=n\) ,∴研究范围是 \((0,0)\) 到 \((n,n)\) ,可以建立 \(Oxy\) ,并随便把合法和非法的序列表示在上面:
根据图像并结合先前的规律二,当在某一时刻 \(sum_i<0\) 时,则此时 \((x,y)\) 中 \(y>x\) ,总结易得,定义 \(y=x\) 为法线,当图像越过法线时,就为非法序列。
∵不好判断 越过 ,且合法路径也可以与法线有交点。
且 \(y>x\iff y\geqslant x+1\)
∴,当它越过法线就必然与 \(y=x+1\) 有交点,如图:
名字随便取着玩的
接下来这一步思想,可以说 前无古人,后无来者 了。
我们找到图中非法路径与高压法线的 第一个 交点,把交点后的原路径关于高压法线轴对称,与交点前的原路径形成一条从 \((0,0)\) 到 \((n-1,n+1)\) 的路径,如图:
现在要开始转换了:(目的是将有条件限制的路径转换为无条件限制的路径)
我们把原路径叫做 \(A\) ,轴对称后的路径叫做 \(B\) .
在 \((0,0)\) 到 \((n,n)\) 中, \(A\) 是唯一的,且在 \((0,0)\) 到 \((n-1,n+1)\) 中, \(B\) 是唯一的, 且有且仅有 \(A\) 和 \(B\) 关于高压法线成轴对称;
∴ \(A\) 和 \(B\) 是一一对应的。
那么 非法路径的数量就等于从 \((0,0)\) 到 \((n-1,n+1)\) 的路径的数量 。
这下简单了,非法序列的数量等于该路径的数量,而该路径的数量,相当于走了 \((n-1)+(n+1)=2n\) 步,其中向右走了 \((n-1)\) 步、向上走了 \((n+1)\) 步,那么总数就为: \(\large C_{2n}^{n-1}\) 或 \(\large C_{2n}^{n+1}\) ,这两个显然是等价的:
\]
\]
合法序列的组合数
综上所述,可抽象为:
由分别 \(n\) 个 0 和 1 排成的,任意前缀和都 \(\geqslant 0\) 的序列的数量为:
\]
∴定义卡特兰数 \(\large Cat_n=\frac{C_{2n}^n}{n+1}\) .
此题思路
不知道要鸽多久,代码还没弄懂...
最新文章
- Openfire集群源码分析
- centos安装mono
- Jqgrid学习API
- Apache(ApacheHaus)安装配置教程
- ActiveX控件dsoFramer的使用(word、excel、PPT)
- linux之条件判断
- 测试过程中LR的关联报错
- [STL]set/multiset用法详解[自从VS2010开始,set的iterator类型自动就是const的引用类型]
- oracle11g ORA-12505
- MyArrayList——实现自己的ArrayList!
- Custom Action : dynamic link library
- jQuery.fn.serialize 阅读
- Json,Gson,FastJson解析笔记
- echarts学习总结(一):图表溢出窗口,图表数据窗口显示不全
- MQ通道搭建以及连通性检查
- html图片上传阅览并且点击放大
- [JavaScript]iframe的contentWindow
- redis(二)--用Redis作MySQL数据库缓存
- django, tornado
- SpringAOP来监控service层中每个方法的执行时间
热门文章
- UVA12186 工人的请愿书 Another Crisis (树形DP)
- 洛谷P2880 [USACO07JAN] Balanced Lineup G(树状数组/线段树)
- 利用Java集合实现学生信息的”增删查“
- [Thread] 多线程顺序执行
- C#--对上传的Excel文档的处理
- 只能用于文本与图像数据?No!看TabTransformer对结构化业务数据精准建模
- Aspose.Cell和NPOI生成Excel文件2
- 2022极端高温!机器学习如何预测森林火灾?⛵ 万物AI
- JAVA-注解之 TODO、FIXME、XXX
- Halocn双目相机标定