崔添翼 § 翼若垂天之云

第10章 变量，显然是程序里最多使用的东西。我认为这是在OI中改善程序清晰度最重要的一个环节。 声明应该尽量靠近变量第一次使用的位置，初始化靠近声明。尽量减少变量的作用域（存活时间），能局部就不要全局，循环变量不在循环体外部使用的话就声明在内部。能采用const的不要采用神秘数值，如果保证只出现一次的话可以例外。不要采用节省一两个字节的奇怪技巧，比如说同一个变量会先后代表两个不同的事物。确保所有声明的变量都有被使用。 并不像伪代码编程过程之类的方法学，这些软件工程技巧都是“零代价”的。所以为何不将它们引入到OI中呢？ 第11章 在OI中，关于变量的命名，唯一的目的是保证你自己能够在整个过程中都能完全清晰的理解。可能的情况下让它尽量自描述可以帮助理解。更值得称道的是你自己养成的从不会搞错的根深蒂固的命名规则。“何时采用命名规则”的清单里，没有OI能对上号的。变量名字没有意义(i,j,k)不要紧，值得担心的是变量名字的字面意义和实际用途不一致。 第12章 避免使用神秘数值，说过好多遍了。事实上，一般使用const声明的原因是因为你可以方便地改动它。 整数需要关注的问题是除法和溢出。除法的规则已经了解，溢出的问题需要加强估算。（我还是记不住2 147 483 647这个神秘数……还是(~0)>>1好了。） 浮点数的加减运算也会出问题，在数量级相差巨大的数之间。等量判断的常识应该是众所周知的。 数组中，需要关心的是下标的溢出，以及嵌套循环中的“下标串话(cross-talk)”。 第13章 结构体可以明确数据的关系。例如几个看上去无关的数组其实是在表示一组元素的多个不同属性。这时若定义一个struct，并使用这个struct的数组可以使代码清晰一些，但也会加大代码长度。值得权衡。当它们可能被作为一个整体来使用时，例如交换甚至排序，那么毫无疑问应该用struct了。 指针是令人亦爱亦恨的东西。它的确很方便，能简化一些东西，但也是很多很多错误的源泉。至于指针的理解，呵呵，每一个真正的C程序员都理解的。 把指针操作限制在子程序或类里面我是同意的。不过若一个名为NextLink()的函数的唯一一行就是i=i->next的话，也太形式主义了点。 应该把指针看作更“易碎”的变量来看待。对待变量的原则——声明与初始化与首次使用尽量接近之类——应该更加严格地施加于指针之上。指针的运用还是应该尽量减少，但决不应该“惧怕”到自己用数组模拟一种指针出来，那会能使强类型变弱。当指针仅仅是为了使接受它为参数的子程序能够修改此变量的时候应该使用引用。 全局变量在OI中的地位有点微妙。由于一个OI程序本身研究的是一个很“局部”的问题。所以所有和整个问题相关的变量（比如说输入进来的数据）都可以全局。真正需要避免的是把确实“局部”的东西，例如循环中的i、j、k都弄成全局的。

第6章 加法原理的应用条件是分类后的集合是不相交的，但如果这个条件不满足呢？这就是容斥原理隆重登场的时候了。容斥原理是这样的A_1到A_n是对于需计数的集合分类后的集合，它们之间能有相交，总的元素个数就是|A_1∪A_2∪… ∪A_n| = ∑|A_i| – ∑|A_i∩A_j| + ∑|A_i∩A_j∩A_k| + …+ (-1)^m |A_1∩A_2∩…∩A_n|。它可以这样解释：首先加上所有集合的大小，然后减去每两个的集合并的大小，然后加上每三个集合的并的大小，然后减去每四个集合的并的大小，……，最后加或减所有集合的并的大小。它的证明可以通过计算某一元素对于等式每一项的贡献的方法来得到。 值得注意的是，如果和式中的每一项都需要直接计算的话，那么利用容斥原理的计算的复杂度关于n是指数级的。例如它用来计算一般的多重集的r-组合的个数就是如此。所以多重集的r-组合个数当元素的种数较多时似乎还是后面介绍的生成函数的方法更高效，它是伪多项式的。 错位排列（即元素i不在第i个位置上的排列）问题很有意思，它的特点是公式右边每一个和式里面的每一项是相同的，可以简化推导过程。最后的公式是：Dn = n! (1- 1/1! + 1/2! – … + (-1)^n 1/n!)。它有一个递推关系：D_n=(n-1)(D_(n-2) + D_(n-1)），可以组合推导。然后这个关系可以进一步简化为D_n = n D_(n-1) + (-1)^n，这个关系就不好组合推导了。 对于更一般的带有禁止位置的排列，就用一般的容斥原理就好了。 （墨比乌斯反演暂无） 第7章 算术序列就是等差数列，几何序列就是等比数列。顺便说一下，这里用a0（第0项）定义通项公式可比数学课本上用a1定义的公式优美多了。 求解递推关系是一门学问。比如说Fibonacci数的通项公式的样子很容易令第一次看到的人感到困惑。（八卦一下，我初中的时候曾经“证明”过 Fibonacci数不可能存在通项公式。呃……天才少年也有小的时候嘛……）现在的考试中似乎Fibonacci数的直接应用不多了。不过线性递推关系还是要看的。 一般的求解线性齐次递推关系的方法在此略过。 生成函数这个名字看上去有点神秘。但其实它就是将一个数列转化成一个函数的方法，定义函数的i次项的系数为a_i，就是数列a的生成函数了。将数列用这种方法表示出来可以方便处理和计算。比如说常数数列1,1,…的生成函数是1+x+x^2+……，但是利用无穷级数的求和，它同时可以表示成1/(1-x)这个很紧凑的形式，就方便接下来的处理了。 生成函数的首要用途是用来解元素的取法有限制的组合问题。比如说某元素只能取偶数个、某元素至多取b个最少取a个之类。对于每个元素的取法写成一个生成函数，就是如果能取i个x^i的系数就是1，否则为0。把所有元素的生成函数乘起来，得到的函数中x^i的系数就是取i个元素的方法数。 利用生成函数可以求解所有的常系数线性齐次递推关系。但目前还没有看到OI上的应用，所以在这里略过。 可以说，生成函数是一个模型，一个数学概念，就像“关系”“集合”这种数学上定义出来的东西一样。灵活的运用生成函数可以求解很多递推关系，比如Catalan数，还有后面讨论的很多数列。 指数生成函数是另一种生成函数。数列a的指数生成函数中x_i的系数是a_i / i!。常数列1,1,…的指数生成函数是Σx^i/i!=e^x。一般的，几何序列a_i=a^i的指数生成函数经化简是e^(ax)。它是用来解决和排列有关的问题的，典型的就是集合划分（更好理解的表达方式是涂色），例如某集合要被划分成若干个（有序的）集合，满足第一个集合的元素数是偶数，第二个集合不能少于a……这样就可以把每个集合的要求写成一个指数生成函数，然后分别化简以后乘起来就得到了通项公式。 可以看到，不管是常规生成函数还是指数生成函数，之所以用途很大就在于它可以被转化为很简单的形式方便运算（特别是乘法），还表达了原来数列的本质信息。