1、在信息学竞赛中的简单应用侯启明信息论简介信息论是关于信息的本质和传输规律的科学的理论。通过它可以很方便地得到某些交互式问题的一个较好的步数下界 (“信息论下界 ”)让我们先来看一些信息论的基本理论理论基础定义：如果一个随机变量 x共有 n种取值，概率分别为 p0,p2,.,pn， 则其熵为H(x)=f(p0,p2,.,pn)=-Cpilogpi 定理 1：在得到关于随机变量 x的一个熵为 h的信息后， x的熵将会减少 h。定理 2：当一个随机变量的各种取值概率相等时，它的熵最大。这些理论看上去和某些题目关系密切，不是吗？那么，具体应该如何运用呢？让我们来看一些例子：我们宿舍二楼到三楼之间楼梯的
2、窗户外面是相邻的一个平房的房顶。在那一带栖息着三只浑身雪白，有着一只蓝眼睛和一只绿眼睛的 例 1：验证一下定理 1猫 ！A B C例 1：验证一下定理 1在天冷的时候，它们喜欢趴在楼内的暖气上。于是，每只猫就有了两种状态：在屋内和在屋外。因此 ， 三只猫的状态共有 8种可能情况，假设它们是等概率的。现在，我在一楼的小卖部。由于种种原因，我希望知道猫当时的状况，因此，我往上看了一眼，结果发现在这个位置只能知道屋内猫的只数 例 1：验证一下定理 1问题 1： 把所有猫的情况作为一个随机变量 x， 则当我在小卖部的时候， x的熵是多少？解答 1： 由于 8种情况的概率相等，所以：H(x)=f(1/8
3、,1/8,1/8,1/8,1/8,1/8,1/8,1/8)=log8问题 2： 我看一眼所得到的信息 y的熵是多少？解答 2： 由于猫的只数共有 0,1,2,3四种情况，概率分别为 (1/8,3/8,3/8,1/8)，所以：H(y)=f(1/8,3/8,3/8,1/8)=log8-6log3/8例 1：验证一下定理 1问题 3： 我看完之后， x的熵 H(x)是多少？解答 3： 此时猫的只数为 0,1,2,3的四种情况的概率依次是 (1/8,3/8,3/8,1/8)，而每种情况的熵分别为(0,log3,log3,0)， 所以此时 H(x)的数学期望为：H(x)=1/8*0+3/8*log3+3/8*log3+1/8*0=6log3/8可以发现 H(x)=H(y)+H(x)。定理 1得到了验证。例 2： Rods(IOI2002)一个 Rod是一个由至少 2个单位正方形连成的水平或竖直的长条。在一个 N*N的方阵中，放了水平和竖直两个 Rod。 如图 1，其中 Rod用 X表示。图 1例 2： Rods(IOI2002)两个 Rod可能有公共方格，比如在图 1中，方格（ 4， 4）无法确定是仅属于 1个 Rod还是同时属于两个 Rod。 因此，在这种情况下我们假定它同时属于两个Rod。 这样，图中竖直Rod的上端点是（ 4， 4）而不是（ 5， 4）。图 1
