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

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

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

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

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

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

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

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

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

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

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

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