浅谈NOIP策略.pdf

浅谈NOIP策略 算法：快速排序、堆排序、多关键字快排、高精度、递推、递归、 有哪些信誉好的足球投注网站（BFS、DFS、ID- DFS、双向DFS、记忆化有哪些信誉好的足球投注网站、剪枝）、贪心、分治、Dynamic Programming动态规划（线型、区间、坐标、背包、树形、特殊） 数据结构：链表、队列、栈、普通树、二叉树、堆、图、Hash表、 并查集、图论算法、网络流、拓扑排序、关键路径、字符串匹配 其他：计算几何、建模、数论 必背代码：二分查找、快速排序、堆排序、多关键字快排、高精度 、分治框架、有哪些信誉好的足球投注网站框架（BFS、DFS、ID- DFS、双向DFS、记忆化有哪些信誉好的足球投注网站、剪枝）、DP框架、背包DP、链表（ 建立、插入、删除）、入队、出队、POP （退栈）、PUSH （进栈 ）、树（存储、遍历）、二叉树（存储、遍历、建立、删除、插入 、查找、输出、已知先序和中序求后序、扩展二叉树、树的计数、 普通树森林转换成二叉树）、get （插入堆）、put （从堆中删除） 、建堆、图的存储、哈密尔顿环、欧拉回路、Hash表、并查集、图 论算法（最短路径：Floyd、Dijkstra、Ford ；MST ：Kruskal、Pri m；求强连通分量：Kosaraju ；拓扑排序；关键路径；最小环；二 分图匹配:Hopcroft- Carp、匈牙利算法）、字符串匹配：（KMP、AC 自动机）、网络 流（最短增广路、最小费用最大流、最小割最大流、上下界网络流 、预流推进、Ford-Fulkerson、Edmonds- Karp、ISAP、Dinic、Push-Relabel、Relabel-to-Front、Preflow- Push ） 如何选择最完美的数据结构 可否工作？ 如果数据结构不能正常工作，这是完全没有用的。对于一个问题，什么样的算法决定什么 样的数据结构，你要确保数据结构可以处理算法。否则，要么在数据结构中继续添加一些 必要的数据，要么你需要找到另外的数据结构来构建这个算法。 可否编码？ 如果您不知道或不记得如何编写一个给定的数据结构，选择其他的数据结构。确保你有一 个清醒的认识，知道每一个操作对数据结构的影响。在此，另一个要考虑的是内存。这个 数据结构能在适当大小的内存空间里运行吗？如果不能就简化它，或选择一个新的数据结 构。否则，从一开始就注定了它不能正常工作。 按时完成？ 由于比赛是限定时间的，5小时内解决3至5道题。如果你在第一题上为了数据结构就花了一 个半小时，那么你基本上已经悲剧了。 可否调试？ 在选择数据结构的时候很容易忘掉调试这部分。请记住一点，一个程序除非它能正常工作 ，否则它就是无用的。不要忘记，在整个比赛的时间中，调试占的比例是很大的，因此必 须把调试时间考虑到写程序的时间中。一个数据结构是否容易调试取决于下面两个属性。 静态的数据结构更易于检查通常来说，规模更小、更紧凑的表达形式更容易检查。此外， 静态分配的数组比链表甚至于动态数组更容易检查。静态的数据结构更容易被显示对于更 复杂的数据结构，最简单的检验方法是写一个小例子来输出数据。可惜，由于时间的限制 ，你可能想限制自己的文本输出。这意味着，像树和图的结构将难以检查。 是否快速？ 很奇怪，速度是在选择数据结构的时候是最后一个要考虑的。一个慢的程序很容易发现是 什么导致了慢，但是一个快速的错的程序却不容易发现什么导致了错，除非运气很好。 结论 总的说来，遵循KISS原则: “使其简单，傻瓜化。”(Keep It Simple, Stupid.) 有时候一定的复杂度是有必要的，但请确保它值得。请牢记：在开始的时候花时间去确保 你选择了一个合适的数据结构，比之后不得不用另一个数据结构去替代它，要划算得多。 避免动态内存 通常情况下，你应当避免使用动态内存，因为： 使用动态内存会很容易犯错误！！ 重写已分配的内存，忘记释放内存，忘记分配内存，只是使用动态内存时引入的一点错误 。此外，这些错误的出错代码很难告诉我们发生错误的位置，因为它可能发生在一个（可 能更晚）内存操作时。 检查数据结构的含义太难了！！ 集成开发环境不能很好地操作动态内存，尤其对于C语言更是一塌糊涂。尝试考