列举贪心算法

A. kruskal算法的举例描述

克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程可以用一个图来表示。这里的图的选择借用了Wikipedia上的那个。非常清晰且直观。
首先第一步，我们有一张图，有若干点和边
第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择。
排序完成后，我们率先选择了边AD。这样我们的图就变成了
.
.
.
.
.
.
第二步，在剩下的边中寻找。我们找到了CE。这里边的权重也是5
.
.
.
.
.
.
依次类推我们找到了6,7,7。完成之后，图变成了这个样子。
.
.
.
.
.
.
下一步就是关键了。下面选择那条边呢？ BC或者EF吗？都不是，尽管现在长度为8的边是最小的未选择的边。但是他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以我们不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。
最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是下图：
.
.
.
.
.
.
到这里所有的边点都已经连通了，一个最小生成树构建完成。
Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。

B. 我不知道pascal一些算法的简称，例如动态规划等，希望得到一些算法的简称，有人能帮我列举出来吗谢谢了

枚举法： Enumeration

排序：Sort

贪心法：Greedy algorithm

递归：Recursion

分治：Divide and Rule

深度优先搜索：Depth First Search(DFS)

宽(广)度优先搜索：Breadth First Search(BFS)

动态规划：Dynamic Programming(DP) 也有人叫它 Dynamic Process

离散化：Discretization

栈：Stack Last in First out (LIFO)

队列：Queue First in First out(FIFO)

顺序表：Array Array-Based List

链表：Chain Linked List

广义表：Lists

串：String

集合：Set

树：Tree

二叉树：Binary Tree

完全二叉树：Complete Binary Tree

二叉搜索树：Binary Search Tree(BST)

堆：Heap

图：Graph

哈希表：Hash Table

并查集：Union-Find Sets 或 Disjoint Sets

最大匹配：maximal matching

线段树：Segment Tree

树状数组：Binary Indexed Tree

伸展树：Splay Tree

左偏树：Leftist Tree 或 Leftist Heap

斐波那契堆：Fibonacci Heap

后缀树：Suffix Tree

网络流：Network Flows

凸包：Convex Hull

叉积：Cross Function

高斯消元：Gaussian Elimination

匹配：Matching

矩阵：Matrix

C. 三个月内如何突破noip

1.确定你的语言 NOIP接受Pascal、C、C++三种语言的参赛者，在学习的开始，务必确定自己使用的语言。 在中途变更自己学习的语言，对学习NOIP来说是非常大的困难。若是初学者，对C、C++没有基础，我个人建议学习Pascal。Pascal可读性高，对于初学者来说，比起C和C++，Pascal应该是更容易上手的。如果有较长时间的准备，不妨试试看学C或者C++，在以后的大学学习中也会有帮助，而且需要网上搜索题解时，C和C++的题解往往较多，更加方便阅读参考。 （本人使用Pascal语言，所以后文回答可能涉及到具体程序的大多是Pascal思维。）

2.从排序入手 排序是信息竞赛基础中的基础，值得我划出整整一块来为排序进行说明。 快速排序是必备本领，在信息竞赛中，若是不会快排，其他的知识就是空中阁楼，学习其他各种优化方法，排序却丢了时间，是万万不可的。学习快排最简单的方法是背。而C和C++应当是自带快排的，所以快速排序很是轻松。 而个人认为，快速排序以外，必须掌握的排序知识还有多关键字排序以及稳定的O(nlogn)排序。 多关键字排序来说，我个人是引入比较函数，在确定两个数字顺序时不单纯比大小，而使用函数处理判断先后。 而稳定排序，我学习了归并排序。它不仅是一个稳定排序，而且可以进行求逆序对等操作，对程序学习的帮助也非常大。

3.贪心和穷举以及模拟——最简单的程序 想要快速获奖，必须熟练掌握贪心和穷举以及模拟。它们虽然不能帮你得到满分，但是可以帮助你从得不到分变为得到30分甚至60分，或者说，它是你想不出更好算法时的救命稻草。 所谓贪心，就是通过局部最优来达成整体最优。每一步都获得当前能取得的最优值，最终也能获得最优值。虽然看似是非常正确的思路，但由于贪心算法所能够考虑因素往往具有局限性，得出的答案常常不会是最优解。但是，仍然需要强调的是，贪心在NOIP这一类比赛中，是能够得分的。 所谓穷举，就是列出所有可能的情况，然后从中寻找最优解。虽然看上去是非常简单的操作方法，但是实际应用时，通过穷举和剪枝（程序运行到一定程度由于能判断必定不是最优解而不再继续），可以达到意想不到的效果。 所谓模拟，常应用于给定步骤时。我们通过逐步进行操作、逐步判断来推断是否符合题目中所给出的情况。这种方法常常是非常耗费时间的，所以一般都不可能是最优解。但是，仍然是可以得到部分分数的一种简单而粗暴的方法。

4.用动态规划来训练思维 动态规划，我偶然跟母亲说到这个的时候，母亲想起了大学时的课程，然后一脸苦笑的样子现在都令我印象深刻（笑）。 动态规划是非常难的一个部分，虽然解题上有一定的规律，但是对于思维的周密程度和逻辑要求非常高。所以我会建议先通过动态规划来训练自己的思维。特别是在短时间内的学习的话，动态规划可以帮助你快速进入编程状态。并且，动态规划的思考也可能帮你发现题目背后可能隐藏的更简便的算法。 动态规划主要的思考规律应该是如下： 定义函数（动态转移方程中转移量的定义） 建立方程 确定初值和边界 由于没有具体的题目，我也不能详细说明动态规划。动态规划千变万化，题目类型多种多样，动态规划的种类也多种多样，难以一一赘述了。 需要提醒的是，在NOIP的考场上，千万不要因为想不到动态转移方程而放弃一道题目，尝试使用贪心等看似并不完全正确的做法来做，能够得到部分分数；也不要在动态规划写出后发现答案不正确后耗费太多的时间，经验表明要找出动态规划的错误点可能可以浪费你整场考试的时间。

5.学习简单的图论 我认为简单图论中包括的有：（单源或多源）最短路和（最小）生成树。 最短路中需要学习的有Dijkstra算法和Floyd算法。Dijkstra算法有点像图论中的动态规划，而Floyd则是图论中的穷举法。但是由于近年来图论的题目越来越困难，加入的其他知识越来越多，没有长时间准备的话，这两种算法掌握即可。如果想再深入一点的话，可以学习SPFA，SPFA也是非常实用的一种算法。 最小生成树就不得不提Prim算法和Kruskal算法。最小生成树的算法中，这两种某种意义上都可以算是贪心的算法。Prim算法更适用于稠密图，而Kruskal算法更适用于稀疏图。如果要学习最小生成树的话，两者都学习并且对比是一种很好的方法，能够看到两种算法的优点和不足。

6.常用的数据结构——让程序更快一点 数据结构中想说的NOIP常常能够用到的是：堆（优先队列）、并查集。更加深入学习还可以提到树状数组 堆，这种数据结构只关注“直系亲属”之间的关系，而不关注“旁系”。常常能够配合贪心使用。例如NOIP的经典题合并果子，虽然能够想出是贪心，但是如果不明白堆的话，程序也不能够得到满分。 并查集，能够快速判断两个元素是否有关联，增加了其他手法之后还能够判断元素之间关系。比如说上面提到的Kruskal，一种非常常见的写法中就运用到了并查集来判断两个点是否已经被连接。 树状数组，能够查询和修改操作复杂度比较平衡的一种算法，正因如此常用来解决同时需要查询和修改的问题。

7.不知道该放在哪里说的搜索——和枚举很像 老师每次被要求讲解搜索都会非常无奈，因为每次讲解完搜索，同学们都会以一种“啊，原来是这样”的眼神看着他，而几个月后还会再重复这样的场景（笑）。 搜索大题来说分为深度优先搜索和广度优先搜索。深度优先搜索就是一条路走到死，撞墙了再回头，而广度优先搜索则是每一步就将下一步所有的可能性放入队列中，然后按照队列顺序来探测。 初赛经常会考深度优先遍历或广度优先遍历后是什么顺序，而复赛的搜索题会加入许多复杂的因素，所以也请好好学习一下这一部分。

8.最后的最后，一定要学习的数学基础知识 简单列举一下： 快速幂 高精度 筛法选素数 扩展欧几里得定理（辗转相除法） 这些在考前一定要重新再看一遍，因为难度并不大但是NOIP考到的几率并不小（会隐藏在第一题中）。