算法竞赛入门经典
最新书摘：
-
hao2013-06-01在编写枚举递归需要深入分析，对模型精雕细琢。如果在回溯法中使用了辅助的全局变量，用完之后，请恢复原状。
-
hao2013-06-01子集生成算法：给定一个集合，枚举它所有可能的子集。一般有3种思路：增量构造，位向量法，二进制法。用二进制表示子集，其中从右往左第i位（从0开始编号）表示元素i是否在集合中（1表示“在”，0表示“不在”）。当用二进制法表示子集时，位运算中的&， | ，^对应集合的交，并，对称差。
-
hao2013-06-01如果某问题的解可以由多个步骤得到，而每个步骤可以由若干种选择，且可以使用递归枚举，工作方式可以用解答树来描述。
-
hao2013-06-01暴力求解，一般用在排列枚举之类的方面。
-
hao2013-06-01关于图，考虑DFS,BFS，拓扑排序。
-
hao2013-06-01二叉树的一般三种遍历：先序遍历，中序遍历，后序遍历如下：PreOrder（T）=T的根节点 + PreOrder（T的左子树） + PreOrder(T的右子树)InOrder（T）= InOrder（T的左子树） + T的根节点 + InOrder(T的右子树)PostOrder（T）=PostOrder（T的左子树） + PostOrder(T的右子树)+ T的根节点
-
hao2013-06-01对比测试，随机生成大规模随机数据量。考虑srand , time,rand rand生成闭区间的[0,RAND_MAX],RAND_MAX至少为32767.
-
hao2013-06-01排序的话，数据规模小的话，冒泡排序很管用的，比快排好。快排有时候分割不好，速度很慢。stdlib.h中的qsort速度就很快。
-
hao2013-06-01有些题考虑建立常量表，打表的方式可能会更简单。用状态变量来辅助字符串读入对于大数高精度运算，请考虑数组存储大数，模拟手工计算。考虑万进制提高效率。
-
hao2013-06-01记住为递归函数编写终止条件，否则无限递归，导致栈溢出。在运行时，程序会动态创建一个堆栈段，里面存放着栈帧，因此保存着调用关系和局部变量。在可执行文件中，文本段储存指令，数据段存储已初始化的全局变量，BSS段存储未赋值的全局变量
-
hao2013-06-01C语言用调用栈（call stack）来描述函数之间的调用关系。调用栈由栈帧（stack frame）组成，每个栈帧对应着一个未运行完成的函数。
-
hao2013-06-01编写函数时，尽量保证它能对任何合法参数都能得到正确结果，如若不然，应在显著位置标明函数的缺陷，以避免使用。编程时，合理的利用assert宏，将给调试带来很大的方便。（assert.h）
-
hao2013-06-01建议用来判断某事物是否具有某种特殊性质的函数命名成“is_xxx”的形式。返回非0数为真，0为假。
-
hao2013-06-01为了方便使用，往往用typedef struct {域定义；}类型名；的方式定义一个新类型名。这样，就可以像原生数据类型一样使用这个自定义类型了。
-
hao2013-06-01字符还可以直接用ASCII码来表示。如果用八进制o,十六进制就是xh（h为16进制数字串）
-
hao2013-06-01使用fgetc可以从打开的文件读取一个字符。一般情况下应当检查不是EOF后再将其转换成char值。getchar等价于fgetc（stdin）。fgets会读取完整的一行。就是说，它一旦读取到‘ ’，就会停止读取工作，然后在buffer后加‘ ’结束符。头文件ctype.h中定义的isalpha，isdigit,isprint,等可以判断字符的属性，toupper,tolower等用来转换大小写。
-
hao2013-06-01可以用sprintf把格式化信息输出到字符串，保证buffer足够大。由于字符串的本质是数组，只能用strcpy，strcmp，strcat来执行“赋值”，“比较”，“连接”操作。不能用=，==，<=,+等运算符。它们在string.h中。
-
hao2013-06-01C语言中的字符型用关键字char表示，实际储存的是字符的ASCII码。字符常量可以用单引号法表示。在语法上可以当做int型使用。
-
灵魂机器2013-04-27有趣的是，如果把状态定义成“d(i)表示以节点i为终点的最长路径长度”，也能顺利求出最优值，却难以打印出字典序最小的方案。想一想，为什么？你能总结出一些规律吗？
-
灵魂机器2013-04-21现在讨论最坏情况下也是O(n)的方案，把所有的数分为5个一堆，那么总共会有n/5堆，对于每堆我们可以很快的找到中位数（因为只有5个所以很容易嘛），之后调用当前算法找到这n/5个中位数的中位数，用这个数来做pivot，所以这个算法被叫做Median of Medians algorithm。把中位数的中位数作为pivot的话，那么原数组中便会有3/5*1/2个也就是3/10个小于等于这个pivot的，同理会有3/10大于这个pivot的，所以最坏情况下，数组被分为30%，70%或者70%，30%的两部分。T(n)<=T(n/5)+T(7/10*n)+O(n)<=c*n*(1+9/10+(9/10)^2....)所以T(n)=O(n)也就是最坏情况下是O(n)。