⑴ c/c++ 最大流演算法ford-fulkerson
你的問題是用C/C++寫最大流演算法ford-fulkerson演算法。頂點就是節點。
void maximum_flow(int n, int s, int t, int *capacity, int *flow)
可以參考:演算法模板-最大流(Ford-fulkerson演算法)
⑵ 如何准備互聯網公司面試(演算法相關)
書籍: 《演算法導論》 這本是大部頭,很多人都看不完。我本人也並沒有看完,它跟了我這么多年,完全是屬於常看常新的牛書。每一次看,都發現會有新的收獲。比如,以前並不知道求K位數或者中位數有平均為O(n)復雜度的演算法。看到了別的地方的參考資料,才知道,原來《算導》上專門有一小節講這個內容。我基本上是本科比較集中的看了一遍,研一的時候又集中的看了一遍,才算是粗略的看完。但是其實,很多理論性的,以及圖論一部分依然還是沒有看完。個人推薦,先從簡單的開始,挑選比較熟悉的一些偏重與數據結構方面的知識作為起點。這本書的習題非常重要,要是有時間,能夠全部做完,那絕對是能夠神功在手了。其實,集中把,第二部分(排序),第三部分(數據結構),第四部分(高級設計,我基本主要看動態規劃和貪心),第五部分(高級數據結構,B樹和二項堆,並差集),第六部分(圖演算法,最大流部分較難,自己可以看情況掌握)。這些部分可以先從演算法本身開始,偽代碼全部看懂。因為演算法導論講的很詳細,而且有來龍去脈,基本不會有太大難度。數學證明,推薦大家掌握,但是,突擊或者第一次,可以選擇性的看看。我自己是重復看,才把證明看掉的。第一次看的時候,基本都跳過了。不過,證明和習題是精髓!希望如果有時間,一定要補回來。 《編程之美》《挑戰編程》 這本書絕對是將全中國企業,或者說是一部分懶惰的企業面試題庫提升了一個檔次的一本神書。網路面我師兄的時候,我師兄直接把有一道題的最優解答出來了。但是,那個面試官顯然是不知道最優解,一直在引導我師兄答出,這本書裡面的第四個解。呵呵。書很不錯。全部看一遍並不難。說個不好聽的,可以背下來,而且相信我,基本上絕對有用!比如說,n!後面有多少個0。我相信,你們今年面試或者筆試,一定會碰到這道題。《挑戰編程》大家可以自行考慮一下吧,這個完全是針對acm競賽的,不過,看看題也不錯。 《編程珠璣》 業界神書嘛。習題全部做完就是了。其實都是些小東西,但是,基本上一步步考察你的解決問題的能力。個人覺得,最常用的就是bit map做排序或者去重,拓展一下就是bloom filter,我當時都是在這本書裡面看到的。 《演算法技術手冊》 這本書貌似出鏡不多。書很薄,代碼寫的非常好,其實基本上全部都是基礎演算法和數據結構的實現。但是,它牛逼就在於,代碼寫的太好了,基本上,看一遍,絕對能背下來。面試基礎很重要。基本上每個筆試或者面試,都會考一個100行以內的小程序。比如,給定一棵樹,以及其中一個節點x,要求出這棵樹的中序遍歷序列中,x的後續節點,非遞歸實現。這種題非常簡單,但是,真正寫對的,其實並不多。《STL源碼剖析》《C標准庫》 都不厚。挑著看一遍非常舒服。特別是,看看STL每個數據結構迭代器類型啊,紅黑書如何實現啊。C標准庫,最常見的,比如strcpy()和memcpy()有什麼區別啊。特別是,STL,看過之後,對泛型還是能有一定了解的。《C專家編程》《Effective c++》《深度探索C++對象模型》 第一本比較簡單,可以當八卦書看。後兩本其實也沒啥好說的,其實都是些業界公認的牛書。我再重復一遍也沒什麼意義。但是,的確,考察基本上也就都是這么幾本書上面的東西。基本上後兩本主要側重看c++對象方面的一些指示,特別是多態相關的。 《具體數學》《組合數學》 這兩本其實可以看作修身養性的書。我當時是時間比較充裕的時候看完的。純突擊,大家就可以跳過了。但是,看完真的很有用。比如說,你們就可以跟面試官扯約瑟夫環的構造解了(這道題我覺得80%會遇到),直接推推公式,就不用寫模擬代碼了。《組合數學》也是,很多筆試一般會有些小智力題。不過,其實一般的題目,不看這本書也可以搞定。所以,這兩本僅供參考。大家有興趣的時候,可以翻翻。《Linux內核源碼剖析》《Linux環境高級編程》…… 要是有機會,能看看最好。因為很多公司都會考察Linux相關的知識。最少要會點腳本,一些簡單的Linux命令,以及正則表達式什麼的。要是能聊聊內核源碼或者驅動開發什麼的東西,面試官肯定更加喜歡了。 知識: c & c++ 首先要知道c和c++的區別。常考的有const的用法,一些生僻關鍵字比如extern,static的用法。 結構體與類的差別。類裡面的字對齊問題,也就是說一個類到底有多大。以及一個空的類有多大。 虛函數以及多態相關的顯然是重點。比如析構函數什麼時候需要寫成虛函數,構造函數是否可以是虛函數。 int a[10]; a 和 &a的區別。 java java我並不熟。但是基本上肯定會考一些虛擬機相關的,以及GC等知識。然後,一般招聘的java程序員都會問到很多多線程編程的東西,以及hadoop!這個絕對是重點,淘寶絕對就是問這個的。 操作系統 這個看工作崗位的實際要求。基本的進程線程區別==肯定是會問到的。要是要求高一些,就會問很多多線程編程的問題。一些競爭死鎖等基礎知識,一些進程調度的演算法,最近的kernel好像用的是CFS調度演算法。shell編程,如何讀取程序堆棧,寫一些core mp的讀取程序等等的。 數據結構 基本上所有的排序都要會寫。與樹有關的操作都要會些非遞歸版本。圖一般考的不多。Flood-Fill演算法等等。查找中位數。B樹和紅黑書最好要掌握,不用會寫,能扯扯基本就行。KMP,這個很有可能考!而且的確真的不好懂。要是實在不行,背下來吧。哈哈。 網路 這個其實比較基礎了。我個人網路方面的知識並不好。但是各種協議的基礎,幾次握手啊,一些操作系統的api實現到底是單工還是雙工用的是TCP還是UDP。我個人網路純粹靠拼RP。 資料庫 資料庫非常重要。基本的SQL肯定是要會的。最常見有一道題,inner join和out join的區別。MySQL是重點,基本上很多企業都是問這個。然後,網路扯多了會跟你扯MySQL引擎 的一些東西。這些我就不太懂了。要是能准備的話,或者說的確是做這方面的,就可以著重多准備下。 大規模數據處理這一塊絕對是重點!而且本身不是一個系統的學科分支。但是,基本上幾家大公司都會問這方面的。推薦先讀讀google那幾篇論文。Page Rank那一篇,然後Map Rece好像有幾篇吧。Big Table什麼的。推薦一個網址。這篇貌似是轉載的,我以前找到的源地址現在找不到了。處理這一類問題基本上思路都是,哈希,map rece以及bit map等等的。對了,推薦看一下外排序以及相關的敗者樹。這些都是大規模數據處理的一些典型問題。掌握了這些其實也就夠了。這塊有點屠龍之技的感覺,特別是對於學生,基本沒有誰能有機會把這些代碼實現出來。但是,沒辦法,這些公司就是喜歡考。看完那篇博客的,然後再自行查找一些資料,基本就夠了。萬變不離其中,而且,這些東西,沒辦法考那麼難的。 推薦一個博客吧,作者收集了100+道面試題,並且全部給出了代碼。把這個全部看完,基本上很多面試筆試,都是這些原題。 推薦Top Language裡面的今天我們思考系列,好幾年前的了。看大牛的思考過程,非常有幫助。希望自己能多想想再看答案。注意,google group好像有時被牆。 我把發芽網的題庫版塊也掃了一遍。 還有好多一時想不起來了。
⑶ 演算法導論的作品目錄
目錄(Table of Contents)
前言(Preface)
第一部分(Part I) 基礎(Foundations)
第一章 計算中演算法的角色(The Role of Algorithms in Computing)
第二章 開始(Getting Started)
第三章 函數的增長率(Growth of Functions)
第四章 遞歸(Recurrences)
第五章 概率分析與隨機化演算法(Probabilistic Analysis and Randomized Algorithms)
第二部分(Part II) 排序與順序統計(Sorting and Order Statistics)
第六章 堆排序(Heapsort)
第七章快速排序(Quicksort)
第八章 線性時間中的排序(Sorting in Linear Time)
第九章 中值與順序統計(Medians and Order Statistics)
第三部分(Part III) 數據結構(Data Structures)
第十章 基本的數據結構(Elementary Data Structures)
第十一章 散列表(Hash Tables)
第十二章 二叉查找樹(Binary Search Trees)
第十三章 紅-黑樹(Red-Black Trees)
第十四章 擴充的數據結構(Augmenting Data Structures)
第四部分(Part IV) 高級的設計與分析技術(Advanced Design and Analysis Techniques)
第十五章 動態規劃(Dynamic Programming)
第十六章 貪婪演算法(Greedy Algorithms)
第十七章 分攤分析(Amortized Analysis)
第五部分(Part V) 高級的數據結構(Advanced Data Structures)
第十八章 B-樹(B-Trees)
第十九章 二項式堆(Binomial Heaps)
第二十章 斐波納契堆(Fibonacci Heaps)
第二十一章 不相交集的數據結構(Data Structures for Disjoint Sets)
第六部分(Part VI) 圖演算法(Graph Algorithms)
第二十二章 基本的圖演算法(Elementary Graph Algorithms)
第二十三章 最小生成樹(Minimum Spanning Trees)
第二十四章單源最短路徑(Single-Source Shortest Paths)
第二十五章 全對的最短路徑(All-Pairs Shortest Paths)
第二十六章 最大流(Maximum Flow)
第七部分(Part VII) 精選的主題(Selected Topics)
第二十七章 排序網路(Sorting Networks)
第二十八章矩陣運算(Matrix Operations)
第二十九章 線性規劃(Linear Programming)
第三十章 多項式與快速傅里葉變換(Polynomials and the FFT)
第三十一章 數論演算法(Number-Theoretic Algorithms)
第三十二章 字元串匹配(String Matching)
第三十三章 計算幾何學(Computational Geometry)
第三十四章 NP-完備性(NP-Completeness)
第三十五章 近似演算法(Approximation Algorithms)
第八部分(Part VIII) 附錄:數學背景(Mathematical Background)
附錄A 求和(Summations)
附錄B 集合,等等。(Sets, Etc.)
附錄C 計數與概率(Counting and Probability)
參考文獻(Bibliography)
索引(Index)
⑷ 為什麼《演算法導論》中的數組序號是從1開始的
c語言下標從零開始是個錯誤,並且 index 也是一個有誤導性的名詞,它表示的是偏移量,明明應該用 offset。
然後 c 的徒子徒孫都學了它,導致現在很多人都誤以為下標應該從 0 開始。
早期蠻荒時代,很多東西都不科學,演算法導論作者致力於與落後文明作斗爭,然而卻遭到了樓主你的不理解,實乃編程屆一大憾事。
我再說一遍,C 是結構化的匯編,下標基 0 是受到了 PDP-11 指令集的影響,更老的語言(比如 Fortran)都是基 1 的。
另外用 0/非 0 代表 false/true 也是 PDP-11 中 TST 指令和 Z 位的行為。
可能是這本書強調演算法的求學思想,所以從一更加符合數學的數組規定。
但是編程的時候,指針這個東西會經常用到,如果用a(o)作為第一個元素 那麼*a+n就等同於a(n) 比較方便
演算法導論上的這個問題呢,我覺得我比較同意樓上的看法,這個書上面的很多的程序並不是可以敲上去直接運行的,他只是偽代碼,思想而已,給人看的,人類的普遍思維是從1開始,那麼書頁就是從1開始了
說編程語言是給機器看而偽代碼是給人看的簡直是逗大家笑吧...編程語言設計出來就是給人看的....
另外從0開始在很多方便都極好....我覺得寫多代碼都能體會到吧..
幫算導洗地:
演算法導論通篇用的是偽代碼 是給人類閱讀理解的 不是設計給機器去運行的
而絕大多數情況下, index 從 1 開始更符合人類直覺(如果你對這點有異議請參考的答案 )
但少數情況下, index 從 0 開始更符合人類直覺。例如書中 hashing 還有 FFT 那塊內容, index 是從 0 開始的。
其實寫幾天 Pascal 你就適應啦。。
⑸ 什麼是最大流演算法
最大流不是一個演算法,是一個問題。關於這個問題有很多演算法。比如找增廣路的,預留推進的。。。時間效率各有不同。
最大流問題,你可以這樣想像:源點是工廠,匯點是客戶,工廠到客戶間有很多條有運貨量限制的道路,問工廠到客戶最多可以運多少貨。
這些都可以通過程序實現~至於為什麼要用MATLAB,我就不清楚了~~
⑹ NOIP 如果想得全國一等獎的話需要學習那些知識
必備:【模擬】高精度加、減、乘
【圖論】圖的表示:鄰接矩陣,鄰接表,邊表
傳遞閉包和floyd
最小生成樹演算法(至少會一種)
單源最短路dijkstra(O(n2))或者bellman(spfa優化,O(km))
拓撲排序
【樹】 樹的先序、中序、後序遍歷
樹中的最長路(兩遍bfs或者dfs)
並查集
【搜索】深搜、寬搜
【排序】冒泡排序、快速排序 選擇排序 記數排序(又稱「桶排」)
【動態規劃】
01背包,無限背包
【數論】
最大公約數和最小公倍數,進制轉換
需要:【模擬】
表達式求值(中綴轉後綴,棧的操作)、前綴表達式、中綴表達式、後綴表達式之間的相互轉化
【樹】線段樹 字母樹
【搜索】迭代深搜
【動態規劃】
樹形動態規劃、最長不下降子序列、最長公共子序列和最長公共子串
【排序】歸並排序、堆排序
【串】 KMP(字串匹配)
【數論】 判斷質數(sqrt式與篩法求素數)
【有序表】順序表、鏈表、線段樹及其基本操作
【圖論】
Dijkstra演算法的堆優化、求割點、求割邊、強連通分量、歐拉路(邊一次)、漢密爾頓迴路(點一次)、差分約束系統
【動態規劃】
狀態壓縮的動態規劃
【分治】二分查找、二分答案、最近點對
【樹】 歸並樹(逆序對)
【其他】
Hash、矩形切割(與線段樹的比較)
【數論】歐拉函數
【幾何】線段相交
【有序表】樹狀數組
【樹】 Lca(最近公共祖先)與rmq(區間最值)
【圖論】匹配演算法(最大匹配,最小點覆蓋,最小路徑覆蓋,最大獨立集)
網路流演算法(最大流dinic,最小費用流spfa)
【動態規劃】動態規劃的優化(快速冪,改變狀態,優化轉移,單調性,四邊形不等式)
【串】 Kmp擴展、AC自動機
【數論】 中國剩餘定理、概率與期望
【幾何】 最遠點對(旋轉卡殼) 、凸包(水平序和極角序)
、半平面交
【有序表】平衡樹(sbt、treap、splay)後綴數組
【其他】隨機化演算法、高斯消元
書:演算法導論
《Free Pascal語言與基礎演算法》(第三版)
《全國青少年信息學奧林匹克競賽輔導叢書(中學高級本)》
《青少年信息學奧林匹克競賽實戰輔導叢書》系列(《數學與程序設計》和《數據結構與應用》)
⑺ 計算機科學與技術相關書籍
就計算機科學與技術而言,我知道的《演算法導論》這本書挺合適的,這裡面涵蓋了計算機的幾乎所有的演算法,對於學習計算機編程的人而言十分重要。學懂了這本書,就可以應付很多的考試和比賽。
附:
目錄(Table of Contents)
前言(Preface)
第一部分(Part I) 基礎(Foundations)
第一章 計算中演算法的角色(The Role of Algorithms in Computing)
第二章 開始(Getting Started)
第三章 函數的增長率(Growth of Functions)
第四章 遞歸(Recurrences)
第五章 概率分析與隨機化演算法(Probabilistic Analysis and Randomized Algorithms)
第二部分(Part II) 排序與順序統計(Sorting and Order Statistics)
第六章 堆排序(Heapsort)
第七章 快速排序(Quicksort)
第八章 線性時間中的排序(Sorting in Linear Time)
第九章 中值與順序統計(Medians and Order Statistics)
第三部分(Part III) 數據結構(Data Structures)
第十章 基本的數據結構(Elementary Data Structures)
第十一章 散列表(Hash Tables)
第十二章 二叉查找樹(Binary Search Trees)
第十三章 紅-黑樹(Red-Black Trees)
第十四章 擴充的數據結構(Augmenting Data Structures)
第四部分(Part IV) 高級的設計與分析技術(Advanced Design and Analysis Techniques)
第十五章 動態規劃(Dynamic Programming)
第十六章 貪婪演算法(Greedy Algorithms)
第十七章 分攤分析(Amortized Analysis)
第五部分(Part V) 高級的數據結構(Advanced Data Structures)
第十八章 B-樹(B-Trees)
第十九章 二項式堆(Binomial Heaps)
第二十章 斐波納契堆(Fibonacci Heaps)
第二十一章 不相交集的數據結構(Data Structures for Disjoint Sets)
第六部分(Part VI) 圖演算法(Graph Algorithms)
第二十二章 基本的圖演算法(Elementary Graph Algorithms)
第二十三章 最小生成樹(Minimum Spanning Trees)
第二十四章 單源最短路徑(Single-Source Shortest Paths)
第二十五章 全對的最短路徑(All-Pairs Shortest Paths)
第二十六章 最大流(Maximum Flow)
第七部分(Part VII) 精選的主題(Selected Topics)
第二十七章 排序網路(Sorting Networks)
第二十八章 矩陣運算(Matrix Operations)
第二十九章 線性規劃(Linear Programming)
第三十章 多項式與快速傅里葉變換(Polynomials and the FFT)
第三十一章 數論演算法(Number-Theoretic Algorithms)
第三十二章 字元串匹配(String Matching)
第三十三章 計算幾何學(Computational Geometry)
第三十四章 NP-完備性(NP-Completeness)
第三十五章 近似演算法(Approximation Algorithms)
第八部分(Part VIII) 附錄:數學背景(Mathematical Background)
附錄A 求和(Summations)
附錄B 集合,等等。(Sets, Etc.)
附錄C 計數與概率(Counting and Probability)
參考文獻(Bibliography)
索引(Index)
⑻ 網路流的最大流演算法
1、augment path,直譯為「增廣路徑」,其思想大致如下:
原有網路為G,設有一輔助圖G',其定義為V(G') = V(G),E(G')初始值(也就是容量)與E(G)相同。每次操作時從Source點搜索出一條到Sink點的路徑,然後將該路徑上所有的容量減去該路徑上容量的最小值,然後對路徑上每一條邊<u,v>添加或擴大反方向的容量,大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個演算法會陷入死循環,但事實上不是這樣的。我們只需要注意到每次網路中由Source到Sink的流都增加了,若容量都是整數,則這個演算法必然會結束。
尋找通路的時候可以用DFS,BFS最短路等演算法。就這兩者來說,BFS要比DFS快得多,但是編碼量也會相應上一個數量級。
增廣路方法可以解決最大流問題,然而它有一個不可避免的缺陷,就是在極端情況下每次只能將流擴大1(假設容量、流為整數),這樣會造成性能上的很大問題,解決這個問題有一個復雜得多的演算法,就是預推進演算法。
2、push label,直譯為「預推進」演算法。
3、壓入與重標記(Push-Relabel)演算法
除了用各種方法在剩餘網路中不斷找增廣路(augmenting)的Ford-Fulkerson系的演算法外,還有一種求最大流的演算法被稱為壓入與重標記(Push-Relabel)演算法。它的基本操作有:壓入,作用於一條邊,將邊的始點的預流盡可能多的壓向終點;重標記,作用於一個點,將它的高度(也就是label)設為所有鄰接點的高度的最小值加一。Push-Relabel系的演算法普遍要比Ford-Fulkerson系的演算法快,但是缺點是相對難以理解。
Relabel-to-Front使用一個鏈表保存溢出頂點,用Discharge操作不斷使溢出頂點不再溢出。Discharge的操作過程是:若找不到可被壓入的臨邊,則重標記,否則對臨邊壓入,直至點不再溢出。演算法的主過程是:首先將源點出發的所有邊充滿,然後將除源和匯外的所有頂點保存在一個鏈表裡,從鏈表頭開始進行Discharge,如果完成後頂點的高度有所增加,則將這個頂點置於鏈表的頭部,對下一個頂點開始Discharge。
Relabel-to-Front演算法的時間復雜度是O(V^3),還有一個叫Highest Label Preflow Push的演算法復雜度據說是O(V^2*E^0.5)。我研究了一下HLPP,感覺它和Relabel-to-Front本質上沒有區別,因為Relabel-to-Front每次前移的都是高度最高的頂點,所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的演算法是使用隊列維護溢出頂點,每次對pop出來的頂點discharge,出現了新的溢出頂點時入隊。
Push-Relabel類的演算法有一個名為gap heuristic的優化,就是當存在一個整數0<k<V,沒有任何頂點滿足h[v]=k時,對所有h[v]>k的頂點v做更新,若它小於V+1就置為V+1。
cpp程序: #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#;inttt,kase;intnn,m;intH[45],X[1004],P[1004],flow[1004],tot,cap[1005];intd[45];intS,T;voidadd(intx,inty,intz){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;cap[tot]=flow[tot];}queue<int>q;boolbfs(){memset(d,0,sizeof(d));d[S]=1;intx;q.push(S);while(!q.empty()){x=q.front();q.pop();for(inti=H[x];i;i=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1;q.push(P[i]);}}}returnd[T];}intdfs(intx,inta){if(x==T||a==0)returna;intf=a,tmp;for(inti=H[x];i;i=X[i]){if(flow[i]>0&&d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a));flow[i]-=tmp;a-=tmp;flow[i^1]+=tmp;if(!a)break;}}if(f==a)d[x]=-1;returnf-a;}intDinic(){intf=0;while(bfs())f+=dfs(S,inf);returnf;}intmain(){/**輸入過程省略**/intmaxflow=Dinic();printf(%d
,maxflow);return0;}
⑼ 程序員如何學好演算法
一.基本演算法:
枚舉. (poj1753,poj2965)
貪心(poj1328,poj2109,poj2586)
遞歸和分治法.
遞推.
構造法.(poj3295)
模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
圖的深度優先遍歷和廣度優先遍歷.
最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)
二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
串 (poj1035,poj3080,poj1936)
排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
簡單並查集的應用.
哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)
堆
trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
背包問題. (poj1837,poj1276)
型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
幾何公式.
叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)
中級(校賽壓軸及省賽中等難度):
一.基本演算法:
C++的標准模版庫的應用. (poj3096,poj3007)
較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
差分約束系統的建立和求解. (poj1201,poj2983)
最小費用最大流(poj2516,poj2516,poj2195)
雙連通分量(poj2942)
強連通分支及其縮點.(poj2186)
圖的割邊和割點(poj3352)
最小割模型、網路流規約(poj3308)
三.數據結構.
線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
靜態二叉檢索樹. (poj2482,poj2352)
樹狀樹組(poj1195,poj3321)
RMQ. (poj3264,poj3368)
並查集的高級應用. (poj1703,2492)
KMP演算法. (poj1961,poj2406)
四.搜索
最優化剪枝和可行性剪枝
搜索的技巧和優化 (poj3411,poj1724)
記憶化搜索(poj3373,poj1691)
五.動態規劃
較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
坐標離散化.
掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)
幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級(regional中等難度):
一.基本演算法要求:
代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
保證正確性和高效性. poj3434
二.圖演算法:
度限制最小生成樹和第K最短路. (poj1639)
最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)
最小樹形圖(poj3164)
次小生成樹.
無向圖、有向圖的最小環
三.數據結構.
trie圖的建立和應用. (poj2778)
LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).
後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索
較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.
較難的狀態DP(poj3133)
六.數學
組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
半平面求交(poj3384,poj2540)
可視圖的建立(poj2966)
點集最小圓覆蓋.
對踵點(poj2079)
⑽ acm初學者要准備什麼 看什麼書啊
剛剛接觸信息學領域的同學往往存在很多困惑,不知道從何入手學習,在這篇文章里,我希望能將自己不多的經驗與大家分享,希望對各位有所幫助。
一、語言是最重要的基本功
無論側重於什麼方面,只要是通過計算機程序去最終實現的競賽,語言都是大家要過的第一道關。亞洲賽區的比賽支持的語言包括C/C++與JAVA。筆者首先說說JAVA,眾所周知,作為面向對象的王牌語言,JAVA在大型工程的組織與安全性方面有著自己獨特的優勢,但是對於信息學比賽的具體場合,JAVA則顯得不那麼合適,它對於輸入輸出流的操作相比於C++要繁雜很多,更為重要的是JAVA程序的運行速度要比C++慢10倍以上,而競賽中對於JAVA程序的運行時限卻往往得不到同等比例的放寬,這無疑對演算法設計提出了更高的要求,是相當不利的。其實,筆者並不主張大家在這種場合過多地運用面向對象的程序設計思維,因為對於小程序來說這不旦需要花費更多的時間去編寫代碼,也會降低程序的執行效率。
接著說C和C++。許多現在參加講座的同學還在上大一,C的基礎知識剛剛學完,還沒有接觸過C++,其實在賽場上使用純C的選手還是大有人在的,它們主要是看重了純C在效率上的優勢,所以這部分同學如果時間有限,並不需要急著去學習新的語言,只要提高了自己在演算法設計上的造詣,純C一樣能發揮巨大的威力。
而C++相對於C,在輸入輸出流上的封裝大大方便了我們的操作,同時降低了出錯的可能性,並且能夠很好地實現標准流與文件流的切換,方便了調試的工作。如果有些同學比較在意這點,可以嘗試C和C++的混編,畢竟僅僅學習C++的流操作還是不花什麼時間的。
C++的另一個支持來源於標准模版庫(STL),庫中提供的對於基本數據結構的統一介面操作和基本演算法的實現可以縮減我們編寫代碼的長度,這可以節省一些時間。但是,與此相對的,使用STL要在效率上做出一些犧牲,對於輸入規模很大的題目,有時候必須放棄STL,這意味著我們不能存在「有了STL就可以不去管基本演算法的實現」的想法;另外,熟練和恰當地使用STL必須經過一定時間的積累,准確地了解各種操作的時間復雜度,切忌對STL中不熟悉的部分濫用,因為這其中蘊涵著許多初學者不易發現的陷阱。
通過以上的分析,我們可以看出僅就信息學競賽而言,對語言的掌握並不要求十分全面,但是對於經常用到的部分,必須十分熟練,不允許有半點不清楚的地方,下面我舉個真實的例子來說明這個道理——即使是一點很細微的語言障礙,都有可能釀成錯誤:
在去年清華的賽區上,有一個隊在做F題的時候使用了cout和printf的混合輸出,由於一個帶緩沖一個不帶,所以輸出一長就混亂了。只是因為當時judge team中負責F題的人眼睛尖,看出答案沒錯只是順序不對(答案有一頁多,是所有題目中最長的一個輸出),又看了看程序發現只是輸出問題就給了個Presentation error(格式錯)。如果審題的人不是這樣而是直接給一個 Wrong Answer,相信這個隊是很難查到自己錯在什麼地方的。
現在我們轉入第二個方面的討論,基礎學科知識的積累。
二、以數學為主的基礎知識十分重要
雖然被定性為程序設計競賽,但是參賽選手所遇到的問題更多的是沒有解決問題的思路,而不是有了思路卻死活不能實現,這就是平時積累的基礎知識不夠。今年World Final的總冠軍是波蘭華沙大學,其成員出自於數學系而非計算機系,這就是一個鮮活的例子。競賽中對於基礎學科的涉及主要集中於數學,此外對於物理、電路等等也可能有一定應用,但是不多。因此,大一的同學也不必為自己還沒學數據結構而感到不知從何入手提高,把數學撿起來吧!下面我來談談在競賽中應用的數學的主要分支。
1、離散數學——作為計算機學科的基礎,離散數學是競賽中涉及最多的數學分支,其重中之重又在於圖論和組合數學,尤其是圖論。
圖論之所以運用最多是因為它的變化最多,而且可以輕易地結合基本數據結構和許多演算法的基本思想,較多用到的知識包括連通性判斷、DFS和BFS,關節點和關鍵路徑、歐拉迴路、最小生成樹、最短路徑、二部圖匹配和網路流等等。雖然這部分的比重很大,但是往往也是競賽中的難題所在,如果有初學者對於這部分的某些具體內容暫時感到力不從心,也不必著急,可以慢慢積累。
競賽中設計的組合計數問題大都需要用組合數學來解決,組合數學中的知識相比於圖論要簡單一些,很多知識對於小學上過奧校的同學來說已經十分熟悉,但是也有一些部分需要先對代數結構中的群論有初步了解才能進行學習。組合數學在競賽中很少以難題的形式出現,但是如果積累不夠,任何一道這方面的題目卻都有可能成為難題。
2、數論——以素數判斷和同餘為模型構造出來的題目往往需要較多的數論知識來解決,這部分在競賽中的比重並不大,但只要來上一道,也足以使知識不足的人冥思苦想上一陣時間。素數判斷和同餘最常見的是在以密碼學為背景的題目中出現,在運用密碼學常識確定大概的過程之後,核心演算法往往要涉及數論的內容。
3、計算幾何——計算幾何相比於其它部分來說是比較獨立的,就是說它和其它的知識點很少有過多的結合,較常用到的部分包括——線段相交的判斷、多邊形面積的計算、內點外點的判斷、凸包等等。計算幾何的題目難度不會很大,但也永遠不會成為最弱的題。
4、線性代數——對線性代數的應用都是圍繞矩陣展開的,一些表面上是模擬的題目往往可以藉助於矩陣來找到更好的演算法。
5、概率論——競賽是以黑箱來判卷的,這就是說你幾乎不能動使用概率演算法的念頭,但這也並不是說概率就沒有用。關於這一點,只有通過一定的練習才能體會。
6、初等數學與解析幾何——這主要就是中學的知識了,用的不多,但是至少比高等數學多,我覺得熟悉一下數學手冊上的相關內容,至少要知道在哪兒能查到,還是必要的。
7、高等數學——純粹運用高等數學來解決的題目我接觸的只有一道,但是一些題目的敘述背景往往需要和這部分有一定聯系,掌握得牢固一些總歸沒有壞處。
以上就是競賽所涉及的數學領域,可以說范圍是相當廣的。我認識的許多人去搞信息學的競賽就是為了逼著自己多學一點數學,因為數學是一切一切的基礎。
三、數據結構與演算法是真正的核心
雖然數學十分十分重要,但是如果讓三個只會數學的人參加比賽,我相信多數情況下會比三個只會數據結構與演算法的人得到更為悲慘的結局。
先說說數據結構。掌握隊列、堆棧和圖的基本表達與操作是必需的,至於樹,我個人覺得需要建樹的問題有但是並不多。(但是樹往往是很重要的分析工具)除此之外,排序和查找並不需要對所有方式都能很熟練的掌握,但你必須保證自己對於各種情況都有一個在時間復雜度上滿足最低要求的解決方案。說到時間復雜度,就又該說說哈希表了,競賽時對時間的限制遠遠多於對空間的限制,這要求大家盡快掌握「以空間換時間」的原則策略,能用哈希表來存儲的數據一定不要到時候再去查找,如果實在不能建哈希表,再看看能否建二叉查找樹等等——這都是爭取時間的策略,掌握這些技巧需要大家對數據結構尤其是演算法復雜度有比較全面的理性和感性認識。
接著說說演算法。演算法中最基本和常用的是搜索,主要是回溯和分支限界法的使用。這里要說的是,有些初學者在學習這些搜索基本演算法是不太注意剪枝,這是十分不可取的,因為所有搜索的題目給你的測試用例都不會有很大的規模,你往往察覺不出程序運行的時間問題,但是真正的測試數據一定能過濾出那些沒有剪枝的演算法。實際上參賽選手基本上都會使用常用的搜索演算法,題目的區分度往往就是建立在諸如剪枝之類的優化上了。
常用演算法中的另一類是以「相似或相同子問題」為核心的,包括遞推、遞歸、貪心法和動態規劃。這其中比較難於掌握的就是動態規劃,如何抽象出重復的子問題是很多題目的難點所在,筆者建議初學者仔細理解圖論中一些以動態規劃為基本思想所建立起來的基本演算法(比如Floyd-Warshall演算法),並且多閱讀一些定理的證明,這雖然不能有什麼直接的幫助,但是長期堅持就會對思維很有幫助。
四、團隊配合
通過以上的介紹大家也可以看出,信息學競賽對於知識面覆蓋的非常廣,想憑一己之力全部消化這些東西實在是相當困難的,這就要求我們盡可能地發揮團隊協作的精神。同組成員之間的熟練配合和默契的形成需要時間,具體的情況因成員的組成不同而不同,這里我就不再多說了。
五、練習、練習、再練習
知識的積累固然重要,但是信息學終究不是看出來的,而是練出來的,這是多少前人最深的一點體會,只有通過具體題目的分析和實踐,才能真正掌握數學的使用和演算法的應用,並在不斷的練習中增加編程經驗和技巧,提高對時間復雜度的感性認識,優化時間的分配,加強團隊的配合。總之,在這里光有紙上談兵是絕對不行的,必須要通過實戰來鍛煉自己。
大家一定要問,我們去哪裡找題做,又如何檢驗程序是否正確呢?這大可不必擔心,現在已經有了很多網上做題的站點,這些站點提供了大量的題庫並支持在線判卷,你只需要把程序源碼提交上去,馬上就可以知道自己的程序是否正確,運行所使用的時間以及消耗的內存等等狀況。下面我給大家推薦幾個站點,筆者不建議大家在所有這些站點上做題,選擇一個就可以了,因為每個站點的題都有一定的難易比例,系統地做一套題庫可以使你對各種難度、各種類型的題都有所認識。
1、Ural:
Ural是中國學生對俄羅斯的Ural州立大學的簡稱 ,那裡設立了一個Ural Online Problem Set,並且支持Online Judge。Ural的不少題目演算法性和趣聞性都很強,得到了國內廣大學生的厚愛。根據「信息學初學者之家」網站的統計,Ural的題目類型大概呈如下的分布:
題型
搜索
動態規劃
貪心
構造
圖論
計算幾何
純數學問題
數據結構
其它
所佔比例
約10%
約15%
約5%
約5%
約10%
約5%
約20%
約5%
約25%
這和實際比賽中的題型分布也是大體相當的。有興趣的朋友可以去看看。
2、UVA:
UVA代表西班牙Valladolid大學(University de Valladolid)。該大學有一個那裡設立了一個PROBLEM SET ARCHIVE with ONLINE JUDGE ,並且支持ONLINE JUDGE,形式和Ural大學的題庫類似。不過和Ural不同的是,UVA題目多的多,而且比較雜,而且有些題目的測試數據比較刁鑽。這使得剛到那裡做題的朋友往往感覺到無所適從,要麼難以找到合適的題目,要麼Wrong Answer了很多次以後仍然不知道錯在那裡。 如果說做Ural題目主要是為了訓練演算法,那麼UVA題目可以訓練全方位的基本功和一些必要的編程素質。UVA和許多世界知名大學聯合辦有同步網上比賽,因此那裡強人無數,不過你先要使自己具有聽懂他們在說什麼的素質:)
3、ZOJ:
ZOJ是浙江大學建立的ONLINE JUDGE,是中國大學建立的第一個同類站點,也是最好和人氣最高的一個,筆者和許多班裡的同學就是在這里練習。ZOJ雖然也定位為一個英文網站,但是這里的中國學生比較多,因此讓人覺得很親切。這里目前有500多道題目,難易分配適中,且涵蓋了各大洲的題目類型並配有索引,除此之外,ZOJ的JUDGE系統是幾個網站中表現得比較好的一個,很少出現Wrong Answer和Presentation error混淆的情況。這里每月也辦有一次網上比賽,只要是注冊的用戶都可以參加。
說起中國的ONLINE JUDGE,去年才開始參加ACM競賽的北京大學現在也建立了自己的提交系統;而我們學校也是去年開始參加比賽,現在也有可能推出自己的提交系統,如果能夠做成,到時候大家就可以去上面做題了。同類網站的飛速發展標志著有越來越多的同學有興趣進入信息學的領域探索,這是一件好事,同時也意味著更激烈的競爭。
看看這篇文章對你有什麼幫助!我也是ACM初學者!