列舉貪心演算法

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考到的幾率並不小（會隱藏在第一題中）。