參加程序設(shè)計(jì)大賽的須知資料

最負(fù)盛名的程序設(shè)計(jì)競賽程序設(shè)計(jì)競賽有著各種各樣的形式，在此，我們來介紹其中最負(fù)盛名的幾個。

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

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

1.2.3 歷史最悠久的競賽——ACM-ICPC ACM-ICPC是由美國計(jì)算機(jī)協(xié)會（ACM）主辦的、面向大學(xué)生的競賽，也是歷史最悠久的程序設(shè)計(jì)競賽。這是一個三人一隊(duì)的團(tuán)隊(duì)比賽，選手要在5個小時內(nèi)解決大約10道題。因?yàn)楸荣愔腥x手共用一臺電腦，題量又比其他賽事多，并且多是一些實(shí)現(xiàn)復(fù)雜的問題，所以團(tuán)隊(duì)配合顯得異常重要。想要從日本參加該項(xiàng)賽事，首先要參加在線進(jìn)行的國內(nèi)預(yù)選賽，勝出后才能參加亞洲區(qū)域賽，取得前幾名的好成績后才能夠參加世界總決賽。①

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

1.2.5 通過網(wǎng)絡(luò)自動評測——Online Judge（OJ）在互聯(lián)網(wǎng)上，有一些被稱為Online Judge的系統(tǒng)，它們能夠自動評測以往程序設(shè)計(jì)競賽中的題目。利用該系統(tǒng)就可以練習(xí)了。另外，其中一些Online Judge也會定期舉辦自己的比賽，不妨去參加一下。在此列舉幾個有名的Online Judge。? PKU Online Judge （POJ）——http://poj.org/ 題庫中有大量的題目。? 會津大學(xué)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，經(jīng)常舉辦比賽。? Codecorces——http://codeforces.com/ 與TopCoder一樣定期舉辦比賽，又同其他網(wǎng)站一樣不斷維護(hù)歷屆題庫。

1.3 本書的使用方法在此，就本書所涉及的內(nèi)容、使用方法及注意點(diǎn)做一下說明。

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

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

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

1.3.4 程序結(jié)構(gòu)在許多比賽中，程序都從標(biāo)準(zhǔn)輸入按指定格式讀入數(shù)據(jù)。輸入并非問題的關(guān)鍵，所以本書的程序