16 Webb.S
· 640K 确实是苛刻的内存限制。幸运的是，1999-2000 赛季将是这个限制的最后一次
起作用。
· 210 约等于10 3
· 如果有k 重嵌套的循环，每重大约循环N 次，该程序的复杂度为O(N k)。
· 如果你的程序有l 层递归，每层递归有b 个递归调用，该程序复杂度为O(b l)。 · 当你在处理有关排列组合之类的算法时，记住N 个元素的排列有N!个，N 个元素的 组合或N 个元素组成的集合的幂集的有2 n 个。 · 对N 个元素排序的最少时间是O(NlogN)。
· 进行数学计算！将所有的数据加起来。（Plug in the numbers.）
解决方案的范例
产生器vs. 过滤器
产生大量可能的答案然后选择其中正确的（比如8 皇后问题的解答），这样的程序叫做过滤 器。那些只产生正确答案而不产生任何错误节点的叫做产生器。一般来说，过滤器较容易（较 快）编程实现但是运行较慢。通过数学计算来判断一个过滤器是否足够好或者是否你需要尝 试制作一个产生器。 预先计算
有时生成表格或其他数据结构以便快速查找结果是很有用的。这种方法叫做预先计算（在这 里用空间换取时间）。你可以将需要预先计算的数据和程序一起编译，在程序开始时计算； 也可以干脆记住预先计算出的结果。比如说，一个程序需要将大写字母转化为小写字母，可 以不需任何条件地利用一个表格进行快速查找来实现。竞赛题经常要用到素数——生成一长 串素数在程序中某处使用通常是很实用的。 分解（编程竞赛中最困难的事）
虽然在竞赛中经常使用的基本算法不超过20 种，但是某些需要将两种算法结合才能解决的 组合型问题却是很复杂的。尽量将问题不同部分的线索分离开来以便你可以将一个算法和一 个循环或其他算法结合起来以独立地解决问题的不同部分。注意，有时你可以对你的数据的 不同（独立）部分重复使用相同的算法以有效地改进程序的运行时间。 对称
许多问题中存在着对称（例如，无论你按哪一个方向，一对点之间的距离通常是相同的）。 对称可以是2 路的（？？原文是2-way），4 路的，8 路的或是更多的。尽量利用对称以减少
运行时间。
例如，对于4 路对称，你只需解决问题的四分之一，就可以写下4 个结果，这四个结果和你 所解决的一个结果是对称的（注意自对称的解答，他当然只应该被输出一次或两次）。 正向vs. 逆向 令人惊讶的是，许多竞赛题用逆向法解决比正面突破要好得多。以逆序处理数据或构造一种 基于某种非明显的方式或顺序检索数据的突破策略时，要特别小心。 简化
某些问题可以被改述为一个有点不同的其他问题，这样你解决了新问题，就已经有了原始问 题的答案或者容易找出原始问题的答案；当然，你只需解决两者之中较容易的那个。另外， 像归纳法一样，你可以对一个较小的问题的解答作一些小小的改变以得到原问题的完整答 案。
16
17 Webb.S 十六、（纲）NOIP常用知识点列表
那些最最基本的内容我就不赘述了。。。
感觉这些应该是NOIP难度的知识点，尽量掌握吧。。。前面的数字分别是难度系数和重要度(1---5)
1、排序：
(1,5)冒泡/选排(这个很常用，一定要保证正确性)
(2,5)快排(Pascal选手可以去FPC文件夹里找代码,C/C++选手注意sort的正确性)
(3,4)归并排序(最好要会，因为有可能有题要卡快排)
2、数据结构：
(2,2)循环队列(节省空间用) (2,4)单调队列(DP里经常用) (1,3)完全二叉树的数组存储 (2,5)并查集(一定要会路径压缩) (3,4)图的前向星存法
(4,2)Trie树，后缀数组(这些学过的就再复习一下，没学过就不用看了，估计考的概率不大)
(3,2)森林转二叉树(树状DP常用)
3、动态规划：
(1,5)基本的背包问题(一定要熟练写出方程，尤其注意边界的取值)
(3,4)多线程DP(二取方格数) (3,2)LIS的二分优化
(2,4)DP的队列优化(LCIS，单调队列很常用的) (3,4)树状DP(其实就是记忆化搜索，很好理解)
4、图论：
(1,5)最短路(dijkstra,floyd,spfa) (2,5)最小生成树(prim,kruskal) (2,5)拓扑排序
(2,3)floyd求最小环
(3,4)求(有向/无向)图的强连通分量 (1,3)判断图中是否有环 (3,2)图的关键路径
(4,1)差分约束系统(就是求最长路，用spfa)
5、其他：
(2,4)RMQ问题的ST算法(LCA问题也可以转化为RMQ问题)
(4,5)高精度的加减乘除开方(开方一般情况下直接二分比较方便)
(3,4)表达式求值(栈或并查集皆可，一般来说并查集比较容易实现)
(2,2)扩展欧几里得算法(解同余方程用) (1,5)乘法转加法神器：log
(1,4)求最大子序列和的备忘录算法
(2,3)位运算优化搜索(N皇后问题，建议去USACO做一下) (4,2)搜索剪枝(推荐做USACO的fence rail那题)
17
18 Webb.S NOIP常用基础知识点列表
I.高精度
a.加法 b.减法 c.乘法 d.高精度除单精 II.排序算法 a.选择排序 b.插入排序 c.hash排序 d.归并排序 e.堆排序 f.快排
III.字符串匹配算法 a.蛮力法 b.KMP IV.数论
a.欧几里德算法
b.扩展欧几里德算法(ax+by=c的正整数) c.素数测试 {O(sqrt(n))} d.筛法求素数
e.快速乘方(请用高精) V.树论
a.二叉搜索树 b.优先队列
c.线段树 (RMQ问题建议使用st算法) d.平衡树一种(建议学习SBT) VI.图论
a.拓扑排序
b.割顶，割边(桥) {O(n)} c.强连通分支 {O(n)}
d.有向无回路图的最长路径(罕见用上的) e.欧拉回路 f.最小生成树
1.Prime 2.Kruskal (这个个人觉得挺重要的) g.次小生成树 {简单的删除最大边是不对的} h.最短路径
1.Dijkstra
{推荐单源使用spfa，同样可以通过设上2.Bellman-ford
限发现图中是否有负权回路，而且这个思3.spfa
想在去除dp中的暂时后效性非常有用} 4.flyod
VII.计算几何学 {noip不是不考几何} a.判断两条线段是否相交 b.凸包算法 {O(n)} VIII.其他算法 a.并查集
b.RMQ问题(通解：线段树，st算法)
18
19 Webb.S 十七、（图论）Kruskal和SPFA
用Kruskal算法求最小生成树的思想如下：
设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。最后的T即为最小生成树。
Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？
我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内，求出源点到其他所有点的最短路径，可以处理负边回路（某一个顶点入队超过n次）。SPFA的实现比Dijkstra或者Bellman_Ford还要简单。
设dist代表s到i点的当前最短距离，fa代表s到i的当前最短路径中i点之前的一个点的编号。开始时dist全部为+∞，只有dist[s]=0，fa全部为0。
维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。
SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。
设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右。
19
20 Webb.S 十八、（图论）匈牙利算法
所谓二分图，简单的来说就是满足可以把图中的所有点分成两堆使得任意一边的两个顶点均不在同一堆中这一条件的图；而二分图的匹配则是指原图中的边集的一个子集并且这个子集满足其中任意两条边均不共顶点；至于最（极）大匹配，顾名思义就是说边数最多的匹配。
根据这些定义，我们可以很明显的发现，这个题实在是一个典型的不能再典型的二分图的最大匹配：
人：一堆点
传送点：另一堆点 建图：
有些人能够在规定时间跑到某些传送点：点与点之间有边，且任意一边的两个顶点的不在同一堆点中。
一个传送点只能传送一个人：任意一个点只能使用一次，即一种逃跑方案对应一个匹配。 求最多有多少个人能够逃脱：求最大匹配含有多少条边。 匈牙利算法实现思想
现在有一群人要逃跑，他们按照编号大小（一定顺序即可）逐个选择目的地，但是这样就会产生一些矛盾，即有可能两个人选择了同一目的地，于是他们就可以协商一下，如果后选者能为先选者找到另一个传送点，那么先选的人就同意放弃这个点，转而走后选者帮他找的那个传送点（当然可能后来选的传送点也已经被占用，这时我们可以采用递归的方式进行判断是否能为后选的传送点的原主人再找另一个传送点），如果后选者找不到另外一个可以让先选者逃生的路线，那么对不起，先选的人不会放弃自己逃生的机会，后选者只有另寻出路了。
匈牙利算法其实是一个类似于贪心的过程，其主体思想就是若让某个人逃生可以让逃生的总人数加一的话，那么让他走，否则就把他留下。首先我们可以为依次为每个人寻找传送点（显然若某个点一条边都没有那么他肯定是跑不出去的，所以对于这样的人我们可以不做考虑），当然这样可能会出现某个人的目的地已经被前面的人占用了，考虑到如果仅仅是更换这个传送点的归属的话，逃生的总人数并未发生改变，即未产生有意义的变化，所以我们约定必须要能够为传送点原先的主人找到另一个穿送点才能把这个这个传送点让给他，即要使得逃生的总人数增加，产生有意义的变化。如此，对每个人都判断一下让他逃跑是否会产生有意义的变化即可得到最终结果。
这个题目的需要注意的几个地方
1：注意输入格式，多读，一定要多读。
2：需要开一个数组保证不会与同一个人协商两次，以免产生无限递归导致栈溢出（如果不开数组判断的话有可能产生如下问题：1要占2的传送点，2要占3的传送点，3要占2的传送点，2又要占3的传送点??）
十九、心得
* memset 因为memset是以字节为单位就是对array指向的内存的4个字节进行赋值，每个都用ASCII为1的字符去填充， 转为二进制后，
1就是00000001,占一个字节。一个INT元素是4字节，
合一起就是00000001000000010000000100000001，就等于16843009， 就完成了对一个INT元素的赋值了。 memset 127 = max (int)
20