參加程序設計大賽的須知資料

最負盛名的程序設計競賽程序設計競賽有著各種各樣的形式，在此，我們來介紹其中最負盛名的幾個。

1.2.1 世界規模的大賽——Google Code Jam（GCJ）它是Google公司幾乎每年都會舉辦的世界規模的程序設計競賽，參賽者要在2~3小時內解決大約4 道題。一旦從在線（Online）進行的幾輪預選中勝出，就能夠參加現場（Onsite）總決賽。該賽事的特點是，每道題都備有Small和Large兩組輸入數據。即便是難度系數較大的問題，只要輸入規模足夠小，依然可以簡單地求解，這一形式深受廣大參賽者的喜歡。另外，GCJ并不在服務器上自動執行程序，而是要求將源代碼和本地執行的結果一同提交。

1.2.2 向高排名看齊！——TopCoder TopCoder公司是一家策劃并舉辦程序設計競賽的公司，它舉辦的比賽涉及多個領域。其中之一就是算法（Algorithm）比賽，該賽事大致每周都以SRM（Single Round Match）的形式舉辦一場，其具有以下特點。 （1） 在 1 小時 15 分鐘的短時間內挑戰 3 道題。 （2） 提交的結果在比賽結束前是不知道的，整個過程中稍有失誤，就會變成 0 分。 （3） 在編碼階段（coding phase）結束后，還有一個挑戰階段（challege phase）。該階段可以查找別人代碼中的漏洞。如果能夠提供一組輸入數據，使別人的程序返回錯誤的結果，就能得到額外的分數。其中第3條是該賽事獨一無二的特點①，也是閱讀別人代碼的好機會。TopCoder還有一個深受大家喜歡的等級分系統（rating system），它會依據SRM的結果給參賽選手排名。另外，TopCoder還會舉辦一年一度的TCO（TopCoder Open）公開賽。一旦從在線進行的幾輪預選中勝出，就能夠參加在拉斯維加斯②舉辦的總決賽。

1.2.3 歷史最悠久的競賽——ACM-ICPC ACM-ICPC是由美國計算機協會（ACM）主辦的、面向大學生的競賽，也是歷史最悠久的程序設計競賽。這是一個三人一隊的團隊比賽，選手要在5個小時內解決大約10道題。因為比賽中三名選手共用一臺電腦，題量又比其他賽事多，并且多是一些實現復雜的問題，所以團隊配合顯得異常重要。想要從日本參加該項賽事，首先要參加在線進行的國內預選賽，勝出后才能參加亞洲區域賽，取得前幾名的好成績后才能夠參加世界總決賽。①

1.2.4 面向中學生的信息學奧林匹克競賽——JOI-IOI 信息學奧林匹克競賽是學科奧林匹克競賽的一種，是以初中生和高中生為參賽對象的程序設計競賽。在日本，首先要參加日本信息學奧林匹克競賽，取得優異成績后，才能作為日本國家隊選手參加國際信息學奧林匹克競賽。②其他比賽都需要盡可能快地解決盡可能多的問題，而信息學奧林匹克競賽只要在規定時間內求解問題即可，成績與所用時間無關，但是它相對其他比賽而言，求解每道題所花的時間要長得多。雖然是面向中學生的比賽，每年所出問題的難度卻是非常高的。

1.2.5 通過網絡自動評測——Online Judge（OJ）在互聯網上，有一些被稱為Online Judge的系統，它們能夠自動評測以往程序設計競賽中的題目。利用該系統就可以練習了。另外，其中一些Online Judge也會定期舉辦自己的比賽，不妨去參加一下。在此列舉幾個有名的Online Judge。? PKU Online Judge （POJ）——http://poj.org/ 題庫中有大量的題目。? 會津大學Online Judge（AOJ）——http://judge.u-aizu.ac.jp/onlinejudge/ 還包含日語題。? Sphere Online Judge（SPOJ）——http://www.spoj.pl/ 允許使用各種各樣的編程語言。? SGU Online Contester——http://acm.sgu.ru/ 具有模擬參加歷史比賽的虛擬賽功能。? UVa Online Judge——http://uva.onlinejudge.org/ 老字號Online Judge，經常舉辦比賽。? Codecorces——http://codeforces.com/ 與TopCoder一樣定期舉辦比賽，又同其他網站一樣不斷維護歷屆題庫。

1.3 本書的使用方法在此，就本書所涉及的內容、使用方法及注意點做一下說明。

1.3.1 本書所涉及的內容本書主要講解程序設計競賽中的經典問題和基礎算法，并介紹便捷的實用技巧。如果僅僅是死記經典問題和基礎算法，遇到難解的應用問題或是需要靈活想象力的問題時，仍然會難以下手。因此，為了加深理解，我們通過選自POJ的經典題和部分原創題來介紹實踐中的例子。另外，每章末尾都備有挑戰GCJ中實戰題目的小欄目，里面都是精選出來的題目。盡管要找到正確的解法恐怕不太容易，還是建議讀者先自己試著多思考一下。在此基礎上再閱讀題解，能夠得到更深刻的理解。當然，在本書所介紹的解法之外，還會有更簡潔或更高效的解法。大家不妨多試著去思考一下別的解法。

1.3.2 所用的編程語言比賽中可用的編程語言各色各異，而C++在幾乎所有比賽中都可用。它的運行速度快，庫函數豐富，因而人氣很高。本書選擇C++作為所用的編程語言，并基本按照g++的規范來編寫源代碼。

1.3.3 題目描述的處理在世界規模的大賽中，理所當然是用英語來描述題目的。不過，因為題目描述中的英語不那么難，所用的單詞往往也非常有限，所以很快就能習慣。當然，這不是英語考試，字典也是允許自由使用的。另外，其中有些比賽會針對日本選手提供日語版的題目描述。英語的閱讀理解不是題目的關鍵，因此本書的題目都與最開始的例子一樣用中文概述①。

1.3.4 程序結構在許多比賽中，程序都從標準輸入按指定格式讀入數據。輸入并非問題的關鍵，所以本書的程序