最长反链与最小链覆盖

大家好,这里蒟蒻霞客

今天给大家讲解一下一个定理
在有向无环图中,最长反链长度=最小链覆盖数
这个定理在二分图匹配,网络流等问题中有较大用处,比如这道题
本文是在我学完vfleaking的博客后写的,可以算是自己对这篇博文的理解,在此感谢vfleaking写出这篇超棒的博客,大家如果看我的看不懂,可以去看看vfleaking的博客
最后,由于我水平很低,如果有错误,烦请务必告知我,十分感激
那么——

我们开始吧

Continue reading “最长反链与最小链覆盖”

组合数的一点小性质

C_{n}^{m}mod 2为0还是为1
我们得出这一结论
如果n & m == m
那么 C_{n}^{m} mod 2= 1
下面给出证明
引理1:对于 n ,在二进制下如果 n 的第 i 位为1,则此位对 n! 的2的个数的贡献为 2^{i-1}-1
证明:首先,我们知道如何求解 n 的阶乘的2的个数
F\left ( x \right )=\left \lfloor \frac{x}{2} \right \rfloor + \left \lfloor \frac{x}{4} \right \rfloor + \cdots
而每除以2的i次幂,就相当于将x左移i为
于是我们得出,第i位的1,将在第 i-1 , i-2 , i-3, \cdots 2,1 位产生相应的贡献
其和为 2^{i-1}-1
证毕
而当 n & m == m 时,有一个性质,就是n-m==n^m(不难,自证)
也就是说,二进制下n中所有的1,都将在m或n-m中出现,且位置相同
我们回顾一下组合数的计算公式 C_{n}^{m}=\frac{n!}{m!\ast \left ( n-m \right )! }
也就是说,n!中的2将会全被抵消掉,因此得证
如果n & m == m
那么 C_{n}^{m} mod 2= 1

并查集的一点小知识

大家好,这里蒟蒻霞客

今天讲讲并查集的一点小知识
果然我太弱了只能讲讲并查集。。。
为了更好的理解这篇博客,您需要以下前置技能:
1. 额大概没有什么前置技能
并查集可是高级数据结构,虽然使用与理解起来都挺简单,但是细研究可研究的地方很多的,最重要的就是复杂度的分析
嘛,闲话少说——

我们开始吧!!

Continue reading 并查集的一点小知识

哈夫曼编码,哈夫曼树及其构建方法讲解

大家好,这里蒟蒻霞客

这篇博客是关于哈夫曼树,哈夫曼编码,以及哈夫曼树的构建方法的
相关的论文在上方有下载链接,如果想要可以自行下载然后抛弃本篇博客
为了更好的理解本博客,您需要如下前置技能:
额好像没啥
那么——

我们开始吧!!

Continue reading “哈夫曼编码,哈夫曼树及其构建方法讲解”

次小生成树讲解

大家好,这里蒟蒻霞客

这次给大家讲解一下次小生成树
想要透彻的理解本篇文章的内容,您需要点亮如下前置技能
1. 掌握至少一种求最小生成树的算法(网上各路神犇的讲解有很多)
2. 会树上倍增(如果不嫌弃,可以看本蒟蒻的博客:传送门


如果您已经掌握了以上技能——我们开始吧!
Continue reading “次小生成树讲解”

树上倍增讲解

大家好,这里蒟蒻霞客

这次给大家讲讲树上倍增这一很方便有效的处理关于树的方法——树上倍增
为了更好的理解这篇文章,您需要如下前置技能:
1. 明白树形结构
2. 理解二进制


如果您点亮了如上前置技能,无疑会对您理解这篇文章有帮助。
如果您已经点亮了如上前置技能——我们开始吧!
Continue reading “树上倍增讲解”