现在的位置: 首页 > 综合 > 正文

THU组合数学第二周作业

2018年04月28日 ⁄ 综合 ⁄ 共 491字 ⁄ 字号 评论关闭

第二周主要就是向我们介绍了很多排列与组合的知识,以及其中的一些典型的模型,QAQ,这个视频的跨度时间真是太大了,导致忘了具体的细节了,以后没看完一个专题,就认认真真的来这里写总结吧。

先说说几道经典的作业题目吧,虽然二周的作业,我都是用程序跑出来的,懒得用脑子算了,直接O(n^任何次幂)的枚举,总之还挺快的,没有一个超过2秒出来结果的,结果还很满意,都算对了~

先说下留下来最为深刻印象的一道题吧,就是一个n*m的格子中,从这个格子的某个点开始走,一直走到指定点的最短步数问题,这个应该是属于高中的排列组合的知识,但是在这里确实是一个不错的应用,也因为CFdiv2的前两道题越来越重视这样的题目类型。其实如果你在(0,0)要走到(a,b),那么实际上要走的步数为|a|+|b|步,如果要走到(2,3)的点处,那么最短的路径数有C(2+3,3or2)的选择,因为我们由组合数的性质知道,其中满足相等的关系。如果要在一条长长的路径中,又存在了几个中间节点的话,我们就必须把我们的路程分为几个阶段来分别处理了,有了前面的思路,不管题目中要求经过格子中的哪些点,我们都是可以轻松做出来的。。。

【上篇】
【下篇】

抱歉!评论已关闭.