1、1,高等程式設計與實做,PG Tsai TFcis2011/06/09,2,我是誰,蔡宗翰 a.k.a. PG台南一中 20042007中山大學資訊與工程學系 20072011交大資研所 網路與工程組 2011ACM題數 500題三次ACM國內 region 兩次ACM國外region,大綱,Part I.程式庫(比賽用小抄)介紹Part II.程式比賽經驗分享Part III.千里之行，始於足下,3,4,Part I 競賽用程式庫,PG Tsai TFcis2011/06/09,競賽用程式庫,a.k.a. 比賽用小抄核心精神： 快 有效常用語法備忘常用演算法提示高等演算法的實做,5,比賽過一
2、個小時連warshall都袧不出來,小抄分類,1.比賽IO操作 檔案讀寫(C freopen sscanf / C+ fstream sstream )2.PG嚴選 STL必備容器與演算法3.比賽常見的初階演算法,6,比賽技巧,資料流重新導向方法：C: test.exe out.txt效果：將in.txt的文字當成鍵盤輸入 餵給程式將程式輸出寫入到檔案,7,IO處理 檔案讀寫,無腦版 （將螢幕鍵盤的IO改為從檔案IO）freopen(“file”,”r”,stdin);freopen(“file”,”w”,stdout);C+ 正常版（fin fout 操作同cin cout）ifstream
3、 fin(“file”);ofstream fout(“file”);,8,IO處理 字串資料流,使用時機：遇到不定量輸入，且資料用換行結尾時#includestring tmp;getline(cin,tmp); istringstream cin2(tmp) ;while(cin2 data) ,9,STL必備容器與演算法,1.map (關聯式陣列)2.sort (排序)3.priority_queue （優先權佇列）4.queue / stack （佇列 / 堆疊）,10,關聯式陣列,#include 宣告: map 變數名稱;Ex: map PG;操作 ：可直接使用操作Ex: PG“t
4、est”=123; PG“test”+ ;若型態1的資料不存在則會初始化一個型態1的資料必須提供比較函數,11,範例,12,Sort,#include int data = 2,4,5,1,3;sort ( data , data + 5）;自訂比較函數 bool cmp（int a , int b）return ab;如果需要穩定排序: stable_sort,13,14,15,Priority Queue,16,Queue / Stack,Queue:宣告 queue 變數名稱;push()插入 front()讀取 pop()移除Stack:宣告 stack 變數名稱;push()插入 t
5、op()讀取 pop()移除,17,範例,18,範例,19,常用演算法,Floyd-Warshall最小生成樹暴搜 / BFS最短路徑遞迴+剪支+記憶動態規劃網路流,20,質數相關拓樸排序Union-and-Find計算機幾何,21,Part II 個人心得分享,PG Tsai TFcis2011/06/09,個人ACM歷程分享,一切的一切：台南一中 資訊社契機：高二上南市賽失利，開始衝ACM自由學風：高二整學年，公假超過一半TOI選訓營：這輩子最充實的時光,22,個人ACM歷程分享,高三沈迷於ACM ，成績(44/45)遭約談高三下：大夢初醒，重拾荒廢已久的學業,23,反思,基本功的鍛鍊，大
6、量練習的重要性環境：在強者雲集的情況下，容易思考本身的不足，與方便詢問問題學業：強健的數學底子才是解題的根基未知旅程：永無止境的程設之路,24,25,Part III 實踐！,PG Tsai TFcis2011/06/09,從哪開始練習ACM解題,來修”高等程式設計與實做”在 Lucky貓的ACM園地 找中譯題目Zerojudge 高中生解題系統,26,練習方式,“可”重複實做已經會的演算法“盡量別”重複利用以前的程式碼不排斥白爛題“不要”在徹底思考前翻閱解答卡關？ 找助教/問同學/爬討論版/google校內資源：高程網頁/校內ACM培訓實踐：校內賽/大專盃/ACM region/南城盃,27,關於題數,題數不代表實力，但代表你曾經花多少時間在ACM上面ACM百題才開始ACM千題才開始追求神乎其技的程式設計之道,28,29,30,Thank You,PG Tsai TFcis2011/06/09,
