经验分享与竞赛程式库（蔡宗翰.ppt

《经验分享与竞赛程式库（蔡宗翰.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1高等程式設計與實做PGTsai@TFcis2011/06/092我是誰蔡宗翰a.k.a.PG台南一中2004~2007中山大學資訊與工程學系2007~2011交大資研所網路與工程組2011~ACM題數500題三次ACM國內region兩次ACM國外region大綱PartI.程式庫(比賽用小抄)介紹PartII.程式比賽經驗分享PartIII.千里之行，始於足下34PartI競賽用程式庫PGTsai@TFcis2011/06/09競賽用程式庫a.k.a.比賽用小抄核心精神：快有效常用語法備忘常用演算法提示高等演算法的實做

2、5比賽過一個小時連warshall都袧不出來…小抄分類1.比賽IO操作檔案讀寫(Cfreopensscanf/C++fstreamsstream)2.PG嚴選STL必備容器與演算法3.比賽常見的初階演算法6比賽技巧資料流重新導向方法：C:>test.exeout.txt效果：將in.txt的文字當成鍵盤輸入餵給程式將程式輸出寫入到檔案7IO處理檔案讀寫無腦版（將螢幕鍵盤的IO改為從檔案IO）freopen(“file”,”r”,stdin);freopen(“file”,”w”,stdout);C++正常

3、版（finfout操作同cincout）ifstreamfin(“file”);ofstreamfout(“file”);8IO處理字串資料流使用時機：遇到不定量輸入，且資料用換行結尾時#includestringtmp;getline(cin,tmp);istringstreamcin2(tmp);while(cin2>>data){…}9STL必備容器與演算法1.map(關聯式陣列)2.sort(排序)3.priority_queue（優先權佇列）4.queue/stack（佇列/堆疊）10關聯式陣列

4、#include

5、ityQueue16Queue/StackQueue:宣告queue<型態>變數名稱;push()插入front()讀取pop()移除Stack:宣告stack<型態>變數名稱;push()插入top()讀取pop()移除17範例18範例19常用演算法Floyd-Warshall最小生成樹暴搜/BFS最短路徑遞迴+剪支+記憶動態規劃網路流20質數相關拓樸排序Union-and-Find計算機幾何21PartII個人心得分享PGTsai@TFcis2011/06/09個人ACM歷程分享一切的一切：台南一中資訊社契機：高二上南

6、市賽失利，開始衝ACM自由學風：高二整學年，公假超過一半TOI選訓營：這輩子最充實的時光22個人ACM歷程分享高三沈迷於ACM，成績(44/45)遭約談高三下：大夢初醒，重拾荒廢已久的學業23反思基本功的鍛鍊，大量練習的重要性環境：在強者雲集的情況下，容易思考本身的不足，與方便詢問問題學業：強健的數學底子才是解題的根基未知旅程：永無止境的程設之路2425PartIII實踐！PGTsai@TFcis2011/06/09從哪開始練習ACM解題來修”高等程式設計與實做”在Lucky貓的ACM園地找中譯題目Zerojudge高中生

7、解題系統26練習方式“可”重複實做已經會的演算法“盡量別”重複利用以前的程式碼不排斥白爛題“不要”在徹底思考前翻閱解答卡關？找助教/問同學/爬討論版/google校內資源：高程網頁/校內ACM培訓實踐：校內賽/大專盃/ACMregion/南城盃27關於題數題數不代表實力，但代表你曾經花多少時間在ACM上面ACM百題才開始ACM千題才開始追求神乎其技的程式設計之道282930ThankYouPGTsai@TFcis2011/06/09