集训笔记——杂题选讲(带数学推导的递推、递归和dp,卡特兰数)

2020年3月3日更新

开课讲了一下昨天留的题目:

第一道:

https://nanti.jisuanke.com/t/41290
• 给定大小为N的带点权,带边权的完全图, N<200。 然后Q次询问,每次给出(u,v,w), 让你求在除了起点终点的其他途经点的点 权都<=w的条件下的最短路。

昨天whh就说了做该题的最关键两点:floyd和离线处理

课件讲解:

• 还记得floyd的循环顺序吗? 
• kij,f[i][j]=min(f[i][j],f[i][k]+f[k][j]) 
• 将每个点按照点权排序,然后每次询问按 照点权排序,然后根据询问的w加入比w小 的点与该点所有的边,同时跑floyd
• 实际上你只需要对k那层做点手脚就好了, 正确性就是floyd的正确性,复杂度n^3

第二题:

• 一共有n个人要上飞机,这班飞机有n个座 位,第i个人的座位号是i。 
• 现在n个人按照座位号是从1到n的顺序上飞 机,但1号随机选了一个位置坐下了,而其 余人都记得自己的位置,如果他们中的一 个人上飞机之后发现自己的位置被占了, 则会在剩下的位置中等概率随机选一个坐 下,如果没被占,则会直接坐到自己的位 置上。 
• 你需要计算最后一个上飞机的人坐到了自 己位置上的概率。
• 还有一问:返程的时候,有m个人会按照一个随机的座位号上飞机。 

讲解:

• 这班飞机有m个座位,还是1号随机选了一 个位置坐下了,而其余人都记得自己的位 置。现在所有人找座位的规则和出发时完 全相同,任何一个发现自己座位已经被占了的人会等概率随机选一个没被占的座位 坐下。 
• 你需要计算最后一个上飞机的人坐到了自己位置上的概率。
• 题面很长,耐心读完就好。 
• 先从第一问开始,不难发现n=1时为1,n=2为0.5,如果你愿意继续算下去的话会发现怎么全是0.5?
• 设f[i]为飞机上一共有i个人时的答案 
• 当1坐在1号位,那么剩下n-1个人包括最后 一个人在内,肯定都能坐到自己的位置, 所以此时概率为1
• 当1坐在n号位,那么第n个人最后上飞机, 肯定坐不到自己的位置了,所以此时概率 为0 
• 当1坐在第k号位,那么第2~k-1个人可以坐 在自己的位置上,轮到第k个人时会开始随 机坐,那么我们不妨将第k个人视为1,将 剩余的n-k个空位,视为新的n,以此类推, 这样递推关系就很清晰了: f(n)=(1+f(2)+f(3)+……+f(n-2)+f(n-1))/n 
• 之后不难证n>=2时恒等于0.5

• 接下来我们在第一问的基础上讨论第二问: 
• 如果1第1个上飞机,那么问题就转化成了 求f(m) 
• 如果1第2个上飞机,因为第一个人肯定坐 在了自己的位置上,那么就是求f(m-1) 
• 如果1第3个上飞机,因为前两个人肯定坐 在了自己的位置上,那么就是求f(m-2) 
• ……如果1第k个上飞机,因为前k-1个人肯 定坐在了自己的座位上,那么就是求f(m- k+1) 
• 如果1最后一个上飞机,那概率肯定是1
• 如果1不是最后一个上飞机,概率为0.5 而第一种情况为1/m,第二种为(m-1)/m 答案就是(1/m)*1+(m-1/m)*0.5=(m+1)/(2*m)

然后讲了一下卡特兰数(说实话本人对卡特兰数的理解不深刻没搞懂这个东西是用来干啥的)

![]()

然后讲了一下洛谷P1044栈

一开始王子恒大佬问大家做没做过这题的时候,大家都说做过。后来发现实在cf讲搜索的时候用记忆化搜索做的。

emmm然后这种做法被wzh大佬diss批驳了,说是如果数据大的话类似的题肯定不能用这种做法。

然后就是ppt上的讲解:

• 设f[x]为进出x个数的序列的总数目,显然 f[0]=f[1]=1 
• 我们思考,对于第x个数,假设它正好是最 后一位输出的,那么在它之前入栈出栈的 就有x-1个数,然后再把x入栈,然后再入栈 出栈n-x个数,最后把x出栈,所以此时进出 x个数的序列的总数目为f[x-1]*f[n-x]。 
• 因为x可以取值1~n,所以其实答案就是把 它们累加起来,于是最终答案就是卡特兰 数第n项了。

• 这道题做完了,我们还要接着思考。 
• 不难发现,其实方案数实际等于入栈出栈 的方案数,于是我们可以将问题转换为: 
• 1为入栈,0为出栈,在合法的情况下入栈n 次,求入栈出栈序列数。 
• 答案就是卡特兰数第n项。

(代码明天有时间再敲)

下一道题是洛谷P1754球迷购票问题

原题:

• 每位购票者限购一张门票,且每张票售价为50元。在排成长龙的球迷中有N个人手持面值50元的钱币,另有N个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这2N个球迷有多少种排队方式

可使售票处不致出现找不出钱的尴尬局面。

ppt讲解:

• 这个就是刚才我说的变形

经过分析可发现其本质与前一道栈是一样的。

即1为入栈,0为出栈。求合法的所有情况数(即当栈空时不得出栈)

思路一模一样呀!!

下一道:

给一个凸n边形,要求连接n-3条对 角线,划分n-2个三角形,求方案数。

讲解:

• 我们先给凸n边形的顶点编号,假设先连两 条线构造一个三角形V1VnVx,这样我们其 实就把这个凸n边形分成了一个三角形,一 个k边形,一个n-k边形…… 
• 和栈那道题是不是已经很像了? 
• 这也是卡特兰数的起源,是欧拉发现的 (怎么还是欧拉。。。)

下一题:休息一会,玩会硬币

• 抛一枚硬币,如果是反面就继续抛,问抛 出正面的期望次数。 
• (期望如果不会的话可以理解为概率*代价, 比如说小A投球中的概率为1/3,那么投三 个球中的期望就是3*(1/3)=1)

讲解:

• x=1+1/2*0+1/2*x发现递归下去了。 
• 解这类方程其实需要运用极限的思想,但 是一种简单的解法是直接移项整理解出x=2 即可

说实话ROS直到现在也没太理解“x=1+1/2*0+1/2*x”中等式右端为什么要加1,lzw大佬的解释是因为先抛了一次所以不管之后怎么样都要加1.

emmmm不得不说很迷呀

(这就是一道期望dp的例子)

下一道题(简直就是脑筋急转弯)

原题:

https://nanti.jisuanke.com/t/43375

• 从上往下摞n(n<=60)个字母(字母只有Z与 O),然后进行操作:
• 从下往上找到第一个O,把它变成Z,把它 下面的Z变成O 
• 问多少次操作之后可以全部变成Z 

怎么办怎么办要是模拟的话可能会炸鸭!(wzh大佬也说了他当年写模拟就炸了)

变换过程有没有觉得很像进位的过程???

没错,把它看成二进制就对了!!!

• 这个操作多少让人想起了二进制,事实也 是如此。 
• 把塔放倒,Z视作0,O为1,求二进制。

课后练习题:

https://www.luogu.org/problem/P1309

![]()

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。