樓天城樓教主的acm心路歷程(作為勵志用)

/利用假期空閑之時，將這幾年GCJ,ACM，ＴoｐＣｏｄer參加的一些重要比賽作個?回顧。昨天是ＧＣJ20０６的回憶,今天時間上更早一些吧，我現(xiàn)在還清晰記得3年

前，我剛剛參加ACM時參加北京賽區(qū)２005和杭州賽區(qū)2005的情況。

２00５年AＣM－ＩCPC——酸甜苦辣

我進入清華大學(xué)開始本科學(xué)習(xí)的時間是2００4年8月，在進入清華大學(xué)的第一

年里,由于基礎(chǔ)課學(xué)習(xí)比較緊張,再加上計算機系不允許大一學(xué)生自帶電腦，我沒

有參加200４年的ＡCM比賽.不過在大一一年中沒有停止這方面的練習(xí)，對ACＭ?還是熱情高漲.

大概在2005年７月底，與同班同學(xué)shell（貝小輝）和superzn(張寧)一起

決定組隊參加AＣM比賽.對于隊名沒有太多的想法,就隨便取了一個字典序靠前?一點的bｏmbeｒ.隨后進行的幾場訓(xùn)練中,我的編程狀態(tài)一直保持得很好，訓(xùn)練比?賽的主要方式都是：我主寫程序,ｓhell和supeｒｚn負責(zé)翻譯題目，思考算法和測試。?這種組隊模式一直沿用到我們后面的所有比賽中。

20０5年底，我們報名參加了２005年的北京賽區(qū)和杭州賽區(qū)的比賽。順利通過

了預(yù)賽進入了現(xiàn)場決賽。記得當(dāng)時北京賽區(qū)預(yù)賽的時候，我和superｚｎ一起在參加?百度之星程序設(shè)計大賽，shell依靠一人之力過了6題，最后以第二名的資格參加?北京賽區(qū)現(xiàn)場比賽。

北京賽區(qū)：?２00５年的北京賽區(qū)地點設(shè)在隔壁的北京大學(xué)，由于交通非常方便,我們沒有?和大部分選手住在一起，不過也沒有參加Java－Challｅｎge和晚上的表演。?練習(xí)賽之前，說到比賽位置抽簽,本身意義不是很大，可是鄔老師神奇的RP?把兩只清華的隊伍抽在一起,結(jié)果練習(xí)賽進行了一半，另一只清華的隊伍THU1?(隊員是：吳景岳，栗師和金凱，好像后來隊名改成了DreaｍCatcheｒ,不是很確

定)被要求換到一個比較遠的地方，理由是有些學(xué)校覺得這樣不合理。后來很多賽

區(qū)也出現(xiàn)過隊伍座位在一起的情況,鄔老師的RP果然不是蓋的。

記得練習(xí)賽時和復(fù)旦的ＬeｍonTrｅe(盛城)一起在場地里閑逛,結(jié)果果然不到?10分鐘就被要求回座位了.還有當(dāng)時比賽場地是一個體育館，有些隊伍把氣球放?飛之后氣球就飄在天花板下了，總裁判李文新老師還威脅我們說,如果明天正式比?賽把氣球放飛,就不算通過相應(yīng)的題目,除非有辦法把氣球取下來。?然后就是比賽的過程了，下面有底紋的文字是我找到的當(dāng)時留下的比賽總結(jié)：?Ｅ：快速排序。５分鐘1Y.?我想5分鐘的時間可以爭取這幾年ACM國內(nèi)賽區(qū)的最快出題記錄了吧。?G:二分答案+最小生成樹.25分鐘1Y。?這題就是經(jīng)典的最優(yōu)比例生成樹問題,我們一致認為這題比較簡單。不過后來?被李文新老師批評了,說法是誤導(dǎo)其他的隊伍。不過說到最優(yōu)比例生成樹問題,

ＴCＯ2006的時候ｆwｊ和tomｅk竟然都沒有見過這道題目，這題可是源于PＯI呀。我?想我們認為這道題目簡單的主要原因是我們都在冬令營上見過這到題目，如果第一?次看見，想出算法可能確實需要一些時間.在這里向被我們影響的隊伍的道歉,最

終G提交了200多次,但是只有8個隊伍AC。?Ｃ：二分圖最大匹配。42分鐘1Y?題目要求計算一張圖的最小覆蓋集，可能唯一的trｉcky是發(fā)現(xiàn)圖是二分圖.

D:遇到了一定的困難，發(fā)現(xiàn)A很簡單,于是先放一下?D是一道比較綜合的題目，設(shè)計一些簡單的計算幾何和字符串處理的知識。

Ａ:簡單的幾何問題，出現(xiàn)了一個低級錯誤，提交了3次均為WA。

A是北京賽區(qū)最簡單的題目,我的程序里犯了一個很低級的錯誤,可能也是經(jīng)

驗不足造成的吧。?D:重新寫,但是沒有考慮一種情況，ＷA了1次.?8７分鐘,復(fù)旦的Abuacus過了4題占據(jù)了Ｒanｋ１。由于隊伍模式的原因,我們

在還有很多簡單題目的情況下卡住了長達30分鐘。

A：ｓhell突然發(fā)現(xiàn)了A程序中的低級錯誤,１0５分鐘AC，重新奪回Raｎｋ1。?這是很重要的一步，現(xiàn)在想來如果沒有這個發(fā)現(xiàn),后果可能不堪設(shè)想。

B：二分答案+2SAT.1２9分鐘AC。

B是一道明顯的2ＳAT問題，由于題目比較長，我們沒有很早發(fā)現(xiàn)這道簡單題。?D：發(fā)現(xiàn)了D的沒有考慮的情況，140分鐘AC。?看了一個boａrｄ，那時Abuacuｓ，Eccentｒic都只有4題,能夠在第一次參加正

式比賽就做到6—4的領(lǐng)先，當(dāng)時心情很激動，不過由于缺少經(jīng)驗，也影響了接下來

的發(fā)揮。其實,現(xiàn)在回想起來，這次比賽其實是一個很好的ＡK的機會。?F：DP。程序比較復(fù)雜，WA了4次.?Ｆ是一道比較復(fù)雜的動態(tài)規(guī)劃的題目,其實ＷＡ的原因是一個應(yīng)該用ｉnt64的?地方，我們使用了inｔ,這個地方的確很難發(fā)現(xiàn).

H：F一時無法AC,只好轉(zhuǎn)功Ｈ.H就是普通的模擬題。開始沒有考慮坦克和?炮彈可能在1/3秒相遇，WA了1次。

比賽還有一個小時，封板.?H：ｓhell發(fā)現(xiàn)了坦克和炮彈可能在１/3秒相遇的情況,250分鐘左右AC.

對于我們這種組隊模式，當(dāng)主寫程序的選手狀態(tài)不好的時候，很容易出現(xiàn)連續(xù)?卡題的情況，這種情況的出現(xiàn)很不利于水平的正常發(fā)揮。在北京賽區(qū)的比賽中,我?們很有幸沒有出現(xiàn)連續(xù)卡處的情況.

記得,當(dāng)時北京賽區(qū)的Ｊudgｅ的半自動的，就是說如果結(jié)果是AC，速度就會非??？?，否則由于人的介入,不能AC的提交往往需要等一段時間。我們第2次提交

H之后,沒有得到很快的回復(fù),以為已經(jīng)WA了，于是我和sｕｐeｒzn繼續(xù)測試一些

數(shù)據(jù)。但此時,突然有一個mm從左邊走過來插氣球,這個氣球也成為了全場唯?一的藍色氣球，這個意外之喜最后成就了第一個分區(qū)賽冠軍。?F:下面就是痛苦地提交Ｆ，一直戰(zhàn)斗到最后一刻，WA了14次，留下了北京

賽區(qū)最大的遺憾。

在最后時刻我們似乎發(fā)現(xiàn)了那個int64的錯誤，不過當(dāng)時思路已經(jīng)比較混亂了,?沒能改對。F的問題也導(dǎo)致沒有時間寫I，當(dāng)時如果直接重寫后者換suｐerzn來寫Ｆ,?完全可以在比賽結(jié)束前AC。?比賽的大致過程如上所述，那個神奇的氣球，我現(xiàn)在仍然記憶猶新。最終有4?個隊伍攻破7題,Abacus的組成應(yīng)該是盛城，ｔiｍegreen和sｕzhan吧，Ecｃｅntrｉｃ中?我只記得辛韜，ZＳU_Paｎｋｕ中我記得Savior（陳實).上述的老朋友之后見面的機

會就很少了，分區(qū)比賽也成為了我好需要老同學(xué)重要的交流機會了.?我ACRｕsｈ的ID估計就是那時開始使用的吧，轉(zhuǎn)眼就已經(jīng)3年多了。

比賽前后還記得經(jīng)常與復(fù)旦大學(xué)的吳永輝老師聊天,在那之后的每次比賽我都

能見到他年輕的身影。

現(xiàn)在回想起北京的分區(qū)賽,很有幸能夠在第一次參加ACM正式比賽就獲得分

區(qū)比賽的冠軍。我想是由于現(xiàn)場氣氛對許多隊伍都有不小的影響吧,當(dāng)時許多隊伍

都卡在幾道比較繁瑣的題目上了，題目的算法性都不是很強。我大概從那時才剛剛

接觸TopCｏder，如果能夠早一些，相信會更適應(yīng)這樣的比賽。?杭州賽區(qū):?２005年的AＣM杭州賽區(qū)比賽在浙江大學(xué)舉行，杭州賽區(qū)的時間就在北京賽區(qū)?結(jié)束后一周,最初選擇杭州賽區(qū)的原因很飄逸：我自己家在杭州.實際上也差不多，?我隨隊伍(當(dāng)時ＴHU派了3只隊伍參加杭州賽區(qū)的比賽，除了我們隊之外，?b14２857（侯啟明),zhy（周源)，ｙｓy（楊思雨)組隊,另外一只由汪汀，王俊

和黃源河組成）一同抵達杭州車站之后就馬上回家休息了，直到比賽前才趕回。在?北京到杭州賽區(qū)之間的一周中,我的狀態(tài)就在不斷下滑，在家中完全失去了比賽?的氣氛,回到賽場再也找不到感覺了。一場悲劇即將上演。我們先看看比賽過程吧，

下面有底紋的文字是我找到的當(dāng)時留下的比賽總結(jié):

G：初看很簡單，但是調(diào)試了30分鐘沒有結(jié)果。

G是一道數(shù)學(xué)問題，其實《具體數(shù)學(xué)》書上有明確的公式,不過我們使用的遞

推方法應(yīng)該也可以得到正確的結(jié)果。程序中犯了一些低級的錯誤,由于實在不在狀

態(tài)，調(diào)試了30分鐘還沒有找到錯誤.這里還暴露了一個組隊模式的問題,在后來

的組隊模式中,如果像這樣沒有想清楚算法的題目隊友是一定不允許我去寫的。?A：模擬.41分鐘ＡC，當(dāng)時肯定沒有想到這是唯一一道1Y的題目。?Ａ是一道模擬題，1Y的時候已經(jīng)很晚了，排名也很靠后。?C：圖論.但是由于堆棧逸出RTＥ了5次,浪費了大量的時間。

C的問題關(guān)于樹中祖先關(guān)心的判定,題目很簡單，實現(xiàn)的方法也很容易，就是

通過一遍DFS來計算。但是我們忽視了一個從來沒有遇到過的問題：堆棧溢出。

而且,堆棧在本地機器上運行過程中，Eｃlｉｐse提供了8MB左右的堆棧,所以沒有?溢出,但是在提交之后的環(huán)境下運行就溢出了.而且每次RTＥ之后，我們一直在

嘗試修改數(shù)組的大小,一直沒有找到根本原因。調(diào)試Ｃ的同時，我也嘗試修改G，?結(jié)果Ｇ也錯了8次之多,并且始終都是WＡ。?I:sheｌl在我郁悶地調(diào)試C和Ｇ中AＣ了，之前ＷA了一次。

I是動態(tài)規(guī)劃問題，WＡ一次可能是忽視了一些邊界情況.?Ｄ：網(wǎng)絡(luò)流，沒有想到先貪心進行優(yōu)化。TLE了５次最終沒有通過。

Ｄ就是計算最小割,我們事先準(zhǔn)備了先流推進算法，不過根據(jù)這道題目的模型,?先流推進算法遇到最壞情況：二分圖。由于當(dāng)時dinic還不是很流行，我們ＴLE了

5次還沒有通過。?郁悶地調(diào)試D和G。

Ｅ，B：都嘗試過，但是都出現(xiàn)了不明的問題。

在隨后的時間里,不斷調(diào)試D和Ｇ，但是始終不能AC。之后又嘗試Ｅ和B，E?通過分段的方法可以處理，Ｂ是數(shù)學(xué)題目。正常的話E和B并不是很困難的題目,?但是當(dāng)時已經(jīng)非?；靵y，連樣例都沒有通過。

最終我們只過了3題,排在21名,經(jīng)歷了我參加ACＭ以來最慘痛的失敗。

這次失敗主要歸過與我狀態(tài)太差，基本上什么題目都不能順利通過。當(dāng)然題目的選

擇也有很大的問題:G確實不是難題，但是由于未知的原因始終不能通過，后來我

把紙上的程序敲在ZJU上就AＣ了，至于現(xiàn)場為什么不能AC我現(xiàn)在還是不能明白。?如果說第一題的選擇直接影響了我們的信心,那么D的堆棧溢出則完全打亂了我

們的節(jié)奏。對于我們的組隊模式,卡出2題已經(jīng)超出了極限，我們不可能再嘗試?其他題目。

Ａｂacus也來到了杭州,他們前期體現(xiàn)了強勁的先期優(yōu)勢，在2小時就達到了6?題；ｂ142857（侯啟明），ｚhy(周源)，ysｙ（楊思雨)的隊伍表現(xiàn)得相當(dāng)神勇，

在最后一小時超越了Abａｃus,奪得了冠軍.

杭州賽區(qū)的失敗至今仍是心中痛苦的回憶，不過這個教訓(xùn)也是對我今后的學(xué)?習(xí)生活的一種警示。?總結(jié)：?2005年是我第一年參加ACM—ＩＣPC的比賽,兩場ACM分區(qū)賽,我們經(jīng)歷了奪

冠的興奮,也經(jīng)歷了環(huán)顧四周等待比賽結(jié)束的無奈。2004年清華沒有獲得任何分

區(qū)賽的冠軍，2005年清華打了個漂亮的翻身仗，先后在成都,北京和杭州奪得冠

軍,而且是三支不同的隊伍。?兩個賽區(qū)的G都是有傳奇色彩的題目。北京賽區(qū)中，我們25分鐘1Y了Ｇ，?導(dǎo)致許多隊伍跟風(fēng)失敗,最終達到了208提交8AC的低通過率。但是,杭州賽區(qū)

中,G從比賽一開始就占用了我們大量的時間，直到最后都沒有通過,估計至少浪

費了兩個小時左右.真所謂成也在Ｇ，敗也在Ｇ。?北京賽區(qū)后,PＯJ的論壇上傳聞?wù)f我曾經(jīng)說過“起身去廁所，不許碰鍵?盤。。?！?，很敬仰那些同學(xué)搞笑和扯淡的功底，我們雖然定下了以我主寫程序的?組隊模式,但是也非常重視配合和每個人在隊伍中的重要作用。

當(dāng)時清華沒有組織校內(nèi)PK

選拔，選擇了成都賽區(qū)的冠軍隊THU1參加全球總

決賽，當(dāng)時總決賽隊伍是以參考第二賽區(qū)的成績決定的，現(xiàn)在回想起來也是很合理?的。由于最終我們未能得到機會參加全球總決賽，接下來幾個月我們情緒低落,?boｍber從那時也就宣布解散了吧。

2005年的比賽過程中,我見到了許許多多的老朋友.用吳永輝老師的話,?ＡCM

競賽可以看作一些老朋友一起進行的一場智力游戲。

附北京賽區(qū)前5名:

１TｓinｇhｕaUniversiｔy=>boｍｂerFirstPlａｃe７788?2ＦｕｄａnＵniversiｔy＝＞ＡbａcusSecｏｎｄＰl(wèi)aｃe798３?２SｈanｇhaiJiaoTongUniｖerｓitｙ=＞EcceｎtriｃＳeｃondPlace71084?3ZhoｎgSｈaｎ（ＳｕnＹaｔ－ｓｅn）Univｅｒsity=>ZSＵ＿PaｎkuＴhiｒｄＰl(wèi)ace７１１９4?4PekｉngUniveｒsity=〉ＭｏnｋeｙKingFｏｕrｔhＰl(wèi)ａｃe6７６８?找不到杭州賽區(qū)的排名了，只發(fā)現(xiàn)了這個：

２1THU*bombｅｒ35011/４10/—－6/19７5/-－0/-—０／——8／-－0/--2/14322?謝謝韓家龍同學(xué)的熱心幫助，找到一個排名的鏈接是：??利用假期空閑之時,將這幾年GCJ,AＣM，ToｐCoder參加的一些重要比賽作個?回顧。GCJ200６，ACＭ２005和TCCC20０６之后,2００6年對于我來說是一個大豐收，?今天晚上先回顧MobilｅRoboｔ成立先期的事情吧,明天再總結(jié)驚心動魄的ACM上?海200６和ACM西安2006吧.?2006年ACM—ICPC（上)—-MobileRobot的成立初期?回憶到200５年清華沒有組織校內(nèi)PK選拔，選擇了成都賽區(qū)的冠軍隊TＨＵ1參

加全球總決賽，ｂombｅr從那時也就宣布解散了。?早在20０6年初,THU1準(zhǔn)備參加ＡCM-IＣPC２00６

世界總決賽的訓(xùn)練時,我們的

隊伍就已經(jīng)成立了。隊伍其他兩名選手是一起參加IOI2０0４的geworm(鬲融）和?wd.ｈ（胡偉棟)。?MoｂileRobot的組隊比賽：

至于MoｂileRｏboｔ的隊名,我們是為了紀念2004年4名參加IOI的選手第一?次合作的時候使用的帳號，如果回到2０04年的PKU月賽,也許可以看到thｍr3１91?的身影，這個ID最初是我們4人共同使用的。其中thmr就是TｓinghuaＭobiｌe

Rｏｂｏt的縮寫。當(dāng)然我們覺得ＭobiｌｅＲｏbot讀起來也比較容易上口。?MｏbiｌeＲｏｂot成立之后做的第一件事情就是配合TＨU1準(zhǔn)備WorｌdＦiｎaｌ20０6的?訓(xùn)練,先后模擬比賽了兩次NｏrtｈeasternEurope(NEERC）的題目。這兩次訓(xùn)練中,?我們隊伍的主要模式都是：?（１）geworｍ全程負責(zé)讀題，思考算法和出數(shù)據(jù)；

（2）wｄ。ｈ和我在比賽前2個小時一起攻簡單的題目;

(3)２小時后ｗｄ。h就開始死磕難題,我主寫程序一直到3個半小時左右，結(jié)

合wd。h對難題的把握，大家開始合攻難題。

這種拖后中衛(wèi)的打法,對于NEEＲＣ的題目難度非常合適，兩場比賽我們都做?到了AＫ(全過1１題）。這種組隊模式也一直沿用至總決賽。當(dāng)時wd.h的狀態(tài)很

好，對于ＮEERC的題目難度，我覺得世界上很難有隊伍能夠有信心做到AＫ。

隊伍成立初期的順利使我們更有信心,我們利用署假時間進行了一些必要的訓(xùn)?練以迎接２006年下半年的ACM分區(qū)比賽。

北京賽區(qū)預(yù)賽——網(wǎng)絡(luò)賽賽網(wǎng)絡(luò)：

2０06下半年有3個國內(nèi)賽區(qū),包括北京，上海和西安,其中北京賽區(qū)最先舉

行。2006年北京賽區(qū)的地點設(shè)在了清華大學(xué)，這也是我唯一一次參與組織ACM分?區(qū)比賽的機會.

1０月中旬舉行了北京賽區(qū)網(wǎng)絡(luò)預(yù)賽，網(wǎng)絡(luò)預(yù)賽的參與者是所有報名參加北京?賽區(qū)的隊伍，以決定哪些隊伍擁有參加現(xiàn)場比賽的資格。那段時間,我們隊伍主要?精力放在了準(zhǔn)備比賽上，我們都沒有參與網(wǎng)絡(luò)預(yù)賽的命題和測試平臺工作。由于?清華距離上次承辦分區(qū)比賽已經(jīng)相隔很多時間,直接導(dǎo)致網(wǎng)絡(luò)比賽過程中出現(xiàn)了嚴

重的網(wǎng)絡(luò)問題,在這里作為清華ＡCM隊的一員向受到影響的隊伍道歉。

不過,我也是作為“局外人"來了解這次網(wǎng)絡(luò)阻塞的，因為我確實沒有參加?任何與網(wǎng)絡(luò)賽有關(guān)的活動?，F(xiàn)在回想起來,我認為平臺的穩(wěn)定性是一個不可推卸的?原因，但是主要應(yīng)該歸咎于題目描述和樣例的設(shè)計，當(dāng)然還有測試數(shù)據(jù)的錯誤。?設(shè)想這樣一種情況，如果一個比賽過程中,從某一時刻起,突然增加100０個提交?需要rｅｊudgｅ，然后所有隊伍還都在這一時刻起嘗試提交，我想現(xiàn)有的大部分ＯJ都

很難在1小時之內(nèi)平息這些提交吧。再舉一個更夸張的例子,如果OJ準(zhǔn)備的測試?機器的測試速度已經(jīng)完全跟不上提交的速度，那么卡住是不可避免的。我們通過網(wǎng)?絡(luò)預(yù)賽的教訓(xùn)總結(jié)出一些網(wǎng)絡(luò)預(yù)賽題目的重要經(jīng)驗:

(1)對于容易上手的題目，測試樣例一定要足夠強。

（２）對于簡單的題目,必須仔細確保測試數(shù)據(jù)是正確的。

（3）題目描述必須沒有任何歧義,避免選手通過提交來不斷嘗試各種理解。

如果題目能夠很有效控制提交數(shù)目,對于測試系統(tǒng)的要求其實不是很高。例

如復(fù)活賽和現(xiàn)場決賽的時候，測試系統(tǒng)會大部分時間處在空閑階段。反之，如果提?交處在上述病態(tài)的情況下，只有非常專業(yè)的測試系統(tǒng)才能勝任這樣的挑戰(zhàn)，當(dāng)然不

包括我們的測試系統(tǒng)。?總之，對于網(wǎng)絡(luò)問題我作為清華AＣM隊的一員深表歉意，如果還有下一次的?機會，我們一定努力做得更好.?北京賽區(qū)驗題賽:

如果說網(wǎng)絡(luò)預(yù)賽過程中,網(wǎng)絡(luò)出了一些問題，那么,決賽則是結(jié)果更出乎我

們的意料之外。在北京賽區(qū)現(xiàn)場賽之前幾天,我們3支隊伍進行了驗題賽，比賽?雖然不正式,但是過程仍然很激烈.?先列一下決賽的9道題目吧:

A．Robot?B．ＡnimalRun

C。AnoｔhｅｒMinｉｍumSｐanningTreｅ?D。ConｎectIt，IfYouCaｎ！?Ｅ.Guess

Ｆ。XAR?G。Ｗhａt(yī)aSpecialGraｐh?H。Ｒuler?I.AＦunnyStoｎeＧamｅ

現(xiàn)場賽只有BEHI這４道題目有隊伍成功通過,可是在驗題賽中我們隊伍的進?程完全不是這樣，下面是我們的做題情況：?2２分鐘A題，數(shù)學(xué)方法,1Y?首先，我們3支隊伍在30分鐘之內(nèi)都１Y了A題。A題是一道中等難度的數(shù)學(xué)

題，可能A題需要明確高次等差數(shù)列的求和公式,而且通過枚舉來代替一些假設(shè)

可以大大簡化問題?，F(xiàn)場比賽時有些隊伍做了不正確的假設(shè)導(dǎo)致始終WA。

記得當(dāng)時ｚｈuzeｙｕan使用了一個奇怪的貪心方法，后來被OpenGL找到一個反

例,這個測試用例被添加到正式比賽的測試數(shù)據(jù)之中，這個反例也成為了現(xiàn)場賽中

使得許多提交WA的重要數(shù)據(jù)之一。?3０分鐘E題，貪心,1Y?E是２006北京賽區(qū)最簡單的題目，只需要直接的貪心法就可以解決。?5２分鐘Ｈ題，深度優(yōu)先搜索,1Y?Ｈ是一道搜索題，題目時限不是很緊，不需要太多的優(yōu)化就可以通過。

7５分鐘I題,標(biāo)準(zhǔn)的博弈ＳG問題，1Y?I是標(biāo)準(zhǔn)的博弈問題，通過計算SG就可以得到結(jié)果。這題其實有一個陰險的

地方，就是當(dāng)某位置石子為大于0的偶數(shù)時,也需要考慮以保證結(jié)果的字典序最?小，好在我們及時避開了這個陷阱?，F(xiàn)場很多隊伍調(diào)入這個陷阱中,耽誤了一些時

間。?１２9分鐘B題，最短路徑問題,3Y

B是一張平面圖的最大流問題，由于圖形比較有特點,所以可以建圖來計算最?小割。但是這張圖有106個點,2＊１06條邊,最短路徑需要用堆來輔助實現(xiàn),首先?由于數(shù)組開小了RTE了一次，然后由于用map實現(xiàn)TLE了一次。這題浪費了許多?時間。?Ｇ題,實現(xiàn)和調(diào)試了30分鐘,超時?G是2006北京賽區(qū)最困難的題目之一，題目描述很簡單，判斷一張圖是否為

cｏ—graph。我們算法的復(fù)雜度是O（ｎ＊m/32）的,不過由于數(shù)據(jù)個數(shù)比較多,程序運

行時間遠超過了時限。

C題,貪心法實現(xiàn)50分鐘，ＷA

C題是計算平面圖曼哈頓最小生成樹,直接計算是O(n2)的,但是題目中n接?近1０0０００。我使用了一個貪心算法，其實和標(biāo)準(zhǔn)算法差距不大，不過還是導(dǎo)致

ＷＡ。其實提前寫C不是很合理的選擇，當(dāng)時沒有注意到D。C和Ｇ難度相差無幾。?23０分鐘F題,構(gòu)造,1Y?F題是很變態(tài)的構(gòu)造問題，這題完全是wd.ｈ做的，我至今還不是很清楚算法.

2５0分鐘D題，計算幾何,2Y

D題是一道比較復(fù)雜的計算幾何,當(dāng)判斷一條直線是否穿過一個多邊形的時候

忘記考慮了一種情況，ＷA了１次?，F(xiàn)場許多隊伍其實都只忘記考慮了這一種情況，?但是可惜沒有隊伍該正確。

這場比賽最終我們隊伍以7題結(jié)束，另外兩隊也都通過了７題。我們因此也?沒有修改題目難度,隨后讓大家沒有想到的是:一場極低通過率的比賽即將開始了。?北京賽區(qū)現(xiàn)場賽:

現(xiàn)場比賽中，我負責(zé)在某一個房間為參賽選手送打印資料，比賽60分鐘左右?由于技術(shù)問題到Ｊuｄge室處理一些問題.經(jīng)過5個小時的比賽,最終中科大?Ｓｔuｄent隊通過４題獲得冠軍,廈門大學(xué)ｂtALＴ通過3題獲得亞軍，北京大學(xué)

RPWT，浙江大學(xué)gogｏgo和合肥工業(yè)大學(xué)LoｖeWisdom也都通過3題分列3－5位。

最終Stｕｄｅnｔ，ｂtＡLT和LoveWisdoｍ進軍總決賽。

回顧比賽現(xiàn)場過程,首先讓我們出乎意料的是Ｅ,E是2００6北京賽區(qū)中最簡?單的題目，貪心法的方法參加比賽的同學(xué)都想到了，可是有一個小小的細節(jié)，對于?實數(shù)比較大小時，需要加入一個微小量eps來控制精度。E題沒有加ｅps的提交占

到總提交的50％以上，我們稱之為“經(jīng)典提交”。這個小tｒｉcky不慎導(dǎo)致很多隊伍

遲遲不能通過第一題，對許多隊伍的狀態(tài)有不小的影響。?其次是A，A題收到了很多隊伍的提交,但是最終都沒有隊伍通過A。原因是?大家做了一些不保證正確的假設(shè),當(dāng)時我們都通過枚舉的方法避免了這些假設(shè).?另外，有一些隊伍提早接觸了F和G,并深深地陷入其中.中科大早在2４０分

鐘就通過了第4題，可是之后他們在G上花費了不少精力，我們甚至想跑到他們

那里告訴他們Ｇ是最難的.

記得18０分鐘到２40分鐘，我們只接收到了不超過10次提交，每次大家聽到?提交的聲音,所有Ｊｕdｇe一起點鼠標(biāo)搶測試權(quán)。后來，在TCＣC２0０6上和Yiｎg說起

此事,據(jù)他說和２004年的廣州賽區(qū)有許多相似之處.

總結(jié)：?祝賀所有獲得好成績的隊伍,恭喜Sｔｕdent，ｂtALT和LoveＷisｄｏm進軍總決

賽.并再次對網(wǎng)絡(luò)賽給大家?guī)淼牟槐愕狼?。后來清華舉行了名為復(fù)活賽的比賽,

我想復(fù)活賽應(yīng)該就是從那時開始出現(xiàn)的吧？?當(dāng)年清華一共有6支隊伍，但是只參加兩個賽區(qū)的比賽,造成每個賽區(qū)之前

都要進行小規(guī)模PＫ，最終只有４支隊伍有機會參加AＣM分區(qū)賽.MobilｅRoｂot建?立之初比較順利,獲得了參加兩個賽區(qū)比賽的機會，迎接MobiｌeRｏｂot的將是上?海和西安賽區(qū)的挑戰(zhàn)。

我們3人能夠走在一起,要感謝吳文虎老師的支持，組隊初期雖然沒有經(jīng)歷

大戰(zhàn)，但是那些快樂的時光至今都很難忘懷。

附北京賽區(qū)排名?１UniversitｙofＳcieｎceanｄＴeｃｈnｏｌoｇyofChinａ＝〉StudｅntFirstPlａce4628?２XｉaｍenUnｉvｅrsitｙ=>ｂtALTSeｃｏndPlace3４1７?3PｅkｉngUniveｒsｉｔy=＞ＫUＲPWＴThirｄPlace3460

4ZhejiaｎgUnivｅｒsｉｔy=〉gｏgogoFouｒthPlａce347１

5HeｆeiUnｉversityofTecｈnｏlogy＝＞LovｅWisdomFifthPlace３４77

６FuｄａnUniversｉty=>Ｙin－ＹangSｉxthPlａｃe2204?7TianjinＵｎｉverｓiｔｙ=＞TJU＿RhyｔhmSevenｔhＰｌace2２1２?8ＢeiｈａngUniversity=＞L3EighthＰｌacｅ2254?9PekingUｎiveｒsity=＞ＫU4NｉntｈPlaｃe2２75?9HａrｂinＩｎｓtituｔｅｏfTeｃｈnｏloｇy=〉IACNiｎtｈPlace2282

10ZhｏｎｇShan(ＳｕnＹａt(yī)-sen)Unｉverｓｉty＝〉ZSU_PyrｅｎeaｎTenthPlace2288

1１ZhejiangUniversity=＞hｏebusElevｅnｔhPlａcｅ２311

11UniversiｔyofEleｃtronｉｃＳcｉencｅａｎｄＴechnolｏｇyofＣhinａ＝〉GryffｉnｄorElｅveｎthＰl(wèi)ace

2３19

12ZhongＳhaｎ(SuｎYat－sｅn）Uｎｉｖersity=〉ＺSU＿HｉmalaｙaｓＴwelftｈPlace2324?12FｕzhouUniｖｅrsity=〉OrOrzTｗｅlfthPlａｃe2412?13ＢeijingUｎｉｖersityofPoｓｔｓａｎdTｅlｅcoｍmunicationｓ=>ＶitaｍinＴhirteenthPlace2432

14ＮingboＩnｓｔitutｅofＴechnology,ZhejiａngUniversity＝＞iｍpａcｔＦourｔeenthPlace2４35?15HuazhoｎgＵniveｒsityｏｆＳcｉｅnceandＴechnology＝〉roｄimusFifｔｅentｈPｌａce244２?16NanｊｉngＵｎiverｓitｙ=>ＨOEＮIXSｉxｔeｅnｔhPlaｃｅ２459

17ＦuｚhouUｎｉｖｅｒｓiｔy=>ＬaｐlａcianSｅventeenthPｌａce２467

1７FuｄanUｎｉverｓitｙ=＞ShuaｎgwａiwaiSｅveｎteeｎthPlace25０0?１７Ｎａt(yī)ionalＵnivｅrsｉｔyoｆDeｆｅnseＴeｃｈｎology=>RobｕｓtSｅｖenteeｎtｈPlace25１７

１8ＦudａnUniversity=〉ＦｒｅeWinｇs，Ｙｅah!EｉｇhteenｔｈPｌace2518

18HoｎgKｏｎgＵnｉversityoｆScienceandTeｃhnoloｇy=＞HKUST1EiｇhｔeentｈPｌaｃｅ２6９2?利用假期空閑之時，將這幾年GCJ，ACＭ，TｏpCoｄｅr參加的一些重要比賽作

個回顧。GCJ200６,ACM2005和TCCＣ2006之后,2006年對于我來說是一個大豐

收，昨天晚上回顧了MobｉｌｅRｏbot成立先期的事情吧，今天先發(fā)驚心動魄的AＣM?上海２0０6吧。

2００６年ACM-ＩCＰＣ（中）-—MｏbiｌeRｏboｔ上海對決

回憶到，當(dāng)年清華一共有6支隊伍，但是只參加兩個賽區(qū)的比賽,造成每個賽

區(qū)之前都要進行小規(guī)模PＫ，最終只有４支隊伍有機會參加ACM分區(qū)賽。Mｏbｉｌe

Ｒoｂot建立之初比較順利,獲得了參加兩個賽區(qū)比賽的機會,迎接MｏbｉlｅＲobｏt的

將是上海和西安賽區(qū)的挑戰(zhàn)。

比賽前:空前的豪華陣容

記得清華大學(xué)出發(fā)上海賽區(qū)的時間是10月20日晚上，至于為什么能記得如此?精確,是因為在那之前我經(jīng)歷了真正意義上的“趕火車”。1０月18日TCCC２006?在圣地亞哥落下帷幕，1９日從舊金山機場起飛會北京，飛機著陸時間是20日下午

2點半,進海關(guān)之后已經(jīng)快4點了，我立即乘坐機場大巴直奔火車站與大部隊會合,?之間都沒有時間回寢室.?來到中亞飯店報道拿到參賽隊伍名單的時候，就赫然發(fā)現(xiàn)上海20０6的參賽隊

伍實力達到了幾年來一個不可逾越的巔峰。上海交大的1２34隊都出現(xiàn)在了名單中,?還有浙大和北大的Ｆinａl隊都來了，這些還不夠,蕪湖一中的Loner（周冬)，上海微?軟AＴC的lyｍpanda也參加比賽.上海交大一直是這幾年來清華國內(nèi)最強勁的對手，?如今交大又占據(jù)主場優(yōu)勢,實力深不可測。上海微軟ＡTC雖然是旅游隊，但是

lympaｎda憑借在TｏｐCoder上的表現(xiàn)，沒有人敢輕視這位無冕之王的實力。

對于上海賽區(qū),清華也派出了華麗的陣容，參賽的有３支隊伍，除了Ｍoｂile

Rｏboｔ(我，ｇｅwoｒm（鬲融）和ｗd。h(胡偉棟））之外,還有鼎盛時期的Shanｇrｉ－Lａ

（b14285７（候啟明）,lxd(林希德）和zｈuzeyｕaｎ(朱澤園））以及后來的西安賽區(qū)亞軍

GｏtoFly（zｃgzcgzcg(朱晨光)，wａngjun（王俊),teｄcn(龍凡)）。記得練習(xí)賽之前，

大家一起圍圓桌吃飯，朱晨光突然和旁邊的王俊說，好像就我們兩個沒有參加過?IOI,然后另一邊林希德補了一句，就我們?nèi)齻€不是金牌。?我第一次有機會敬仰候啟明的時候，是自己第一次參加ＮＯI——NＯI200２天津，

候啟明以滿分的成績獲得冠軍，當(dāng)時的亞軍就是林希德。之后的冬令營,我以非正?式營員參加測試神奇得獲得第三名，但更重要的是冬令營測試的冠亞軍就是候啟明?和林希德，之后我再沒有和兩位前輩在OI上交過手.時光飛逝，我代表bｏmbeｒ?隊參加2005年的杭州賽區(qū)，被候啟明領(lǐng)軍的LegendａｒyTeａm打得一敗涂地。隨后?2０0６年初的GoogleCodｅＪａmChinａ(GＣJC）200６上，我獲得第三名,記得當(dāng)天與獲?得亞軍的候啟明同住在總統(tǒng)套房。其實在上海賽區(qū)之前我沒有在正式比賽中戰(zhàn)勝過

他們.Shanｇrｉ－Ｌａ的另一人zhｕzeyuaｎ現(xiàn)在是我的隊友，記得他當(dāng)時在ＴopＣｏdｅr仍

然是Taｒｇet（你可是早點在今年Finaｌ之前把Taｒget拿回來呀，幾次漲停就可以

了），實力也不在前二人之下。

面對知根知底的Shａngｒi—Ｌａ，大家都知道一場大戰(zhàn)在即，從實力上分析，我覺

得MobｉleRｏbot略弱,不過賽前我們都沒有信心一定能夠在比賽中占據(jù)優(yōu)勢。而

且我們心里深知,上海賽區(qū)的結(jié)果將很有可能直接決定清華大學(xué)當(dāng)年的總決賽隊伍。?面對這種殘酷的現(xiàn)實，我們都無可奈何,有時一些有實力進軍總決賽的隊伍在清華?都沒有機會參加分區(qū)比賽。

個人的經(jīng)驗看來，我認為在勢均力敵的時候,最重要一點是明白自己的優(yōu)勢和?劣勢所在,要用自己最強的方面來對抗對手,避免暴露出自己的劣勢。我想在這一

點上Shanｇｒi—La可能沒有我們做得好.Ｓhａngｒｉ-La的優(yōu)勢是三人的總體實力很強，

他們完全可以采用三大高手的組隊模式；我們組隊時間長，配合默契,而且當(dāng)時自

己剛剛從TCCC20０6以100%正確率回國，保持了良好的狀態(tài).從單人比賽上講,?當(dāng)時我的狀態(tài)即使有Ｐeｔｒ和Tomek在場,我都并不認為自己一定會有明顯的劣勢。

比賽場地是上海大學(xué)的一個大體育館，現(xiàn)場氣氛很熱烈，想到我們用4個機房

辦的北京賽區(qū)的現(xiàn)場比賽，不由地覺得有些寒酸。?在場外碰到了lympanda，他向我了解剛結(jié)束的TCCC２0０6的情況，我于是給

他描述了一下幾道現(xiàn)場比賽過程中1000分的題目,結(jié)果全部都被panｄa秒殺了,

無限敬仰呀!同時也第一次見到了周冬。?提一件飄逸事情，記得當(dāng)時練習(xí)賽有3題，封版時沒有隊伍通過B題，但是其

實在封版后我們通過了這題，我們應(yīng)該是當(dāng)時唯一在練習(xí)賽中AK的隊伍。記得之?后好像還和中山大學(xué)的郭老師交流過這題。不過至于Ｂ為什么能夠AC：B題是一

道需要SPJ的題目，可是練習(xí)賽的時候沒有ＳＰＪ，而我又堅信自己的程序是正確的，

于是我不斷提交。可能是由于Juｄgｅ不耐煩了，才用Ｙｅs的方法讓我們停止。

比賽之前的晚上我們都休息得很好，第二天早上以充足的精力迎接史詩般的上?海賽區(qū)決戰(zhàn)。?比賽過程:40０米賽跑

我中學(xué)是很喜歡參加400米比賽，400米比賽從起跑姿勢角度應(yīng)該認為是短跑，?但是400米已經(jīng)遠遠超過了沖刺極限。所以４00米跑中，要求我們從發(fā)令槍響起的

時候就加速啟動,直到拼盡全力為止.?我們回顧一下比賽的過程吧，上海賽區(qū)比賽之后，我們寫下了詳細的比賽過程：

按照一貫的方法,鬲融從A開始讀,胡偉棟從Ｊ開始讀，我準(zhǔn)備編程的環(huán)境,?然后從中間選擇題目讀.鬲融讀完A后，發(fā)現(xiàn)A是一道簡單題.于是選擇先寫A?題。

A:給定ACM網(wǎng)上預(yù)選賽的比賽晉級規(guī)則,求每所學(xué)校的晉級隊伍數(shù)。?簡單模擬題，時間復(fù)雜度O（N)。本題題目有一個疑問:一個學(xué)校出線的隊伍

數(shù)目可能比該學(xué)校參加預(yù)選賽的隊伍數(shù)目還多，但是題目描述和樣例表明不需要考

慮這種情況。?AＣM比賽的第一題的選擇對比賽的進程影響很大,當(dāng)沒有優(yōu)先選擇比賽中最?簡單的題目時,更需要保持冷靜。?在我寫A的過程中,鬲融看了B和C，發(fā)現(xiàn)C也非常簡單，于是馬上做Ｃ。?Ｃ：將一棵節(jié)點帶權(quán)的樹劃分成兩半，使兩半的權(quán)值和的差最小。

枚舉或者樹的遍歷，時間復(fù)雜度O（N）.去年有一個深刻的教訓(xùn)：當(dāng)遍歷樹的?時候,很容易造成堆棧溢出(杭州賽區(qū)留下的疙瘩）.對于本題的范圍，保險起見沒

有使用DＦＳ，而是使用BFS。使用BFS略微增加了編程量,但是可以在一定程度?上避免不必要的麻煩。

鬲融發(fā)現(xiàn)D是一道經(jīng)典的統(tǒng)計題，在不到3分鐘的討論后,我們得出了可行的

算法,于是下面寫了D。在寫D的時候，鬲融和胡偉棟把題看完了，經(jīng)過討論，?決定胡偉棟開始想一道數(shù)學(xué)題I,而鬲融繼續(xù)看題義不是很清楚的G和J兩題。?D：給出平面里的一系列點,要找一個矩形，使矩形邊上的點最多.?離散化后，先判斷一條直線的情況。枚舉兩條橫邊，然后枚舉豎邊,一旦一條?右邊的邊比左邊的邊好,左邊的邊就不會再有作用。因此,枚舉豎邊的過程很容易

做到O（N)，總的復(fù)雜度是O(Ｎ3)?這題其實存在O（N2ｌｏｇN)的算法，我想出題人也應(yīng)該沒有在第一時間想到吧。?做出D后寫了B，原因是B的算法相對簡單。但是意想不到的是:B的樣例不?合法，而且Clarificａt(yī)ioｎ的速度非常慢，于是只好先把B放在一邊。這個過程浪費

了不少寶貴時間.?隨后看到ｔeam10９(Ｓhａngri－La)過了一道紅色氣球,感覺是G,于是鬲融給我講

了G，但是發(fā)現(xiàn)G實在不像算法簡單或程序簡單的題目。?此時,胡偉棟推出了Ｉ的一個很簡明的公式.而且我們發(fā)現(xiàn)I的氣球也是紅色

的。剛才看G很可能是被誤導(dǎo)的。于是寫了I.?寫I的過程中，由于鬲融看的題基本已經(jīng)被做完了，胡偉棟給鬲融講了H的題?意,鬲融想出了一個可行的做法,不過由于還有更簡單的題并沒有馬上做。

I：求楊暉三角形第N＋1行不能被質(zhì)數(shù)整除的數(shù)的個數(shù)。

可以找出規(guī)律，然后寫出公式，時間復(fù)雜度Ｏ(logN）。我在并不知題目意思的

情況下寫過了I,依靠胡偉棟的公式,我們度過了此次比賽第一段艱難的時期。?從過D題到過I題，大概有4０分鐘的時間。這段時間我們主要的失誤有:

（１)B的樣例不合法，這其實不是我們的錯誤。?（２)受氣球顏色的誤導(dǎo),過早思考一道很難的題目。?(3）后來聽朱澤園的建議：由于一個人的問題導(dǎo)致卡住，應(yīng)該一個人解決，不

應(yīng)該讓全隊都陷入混亂中.?我認為我們直接選擇寫另外一道題目主要有兩個原因：一是B卡住的原因比較

特殊，不是我們花時間就能克服的;二是I的算法比較清楚，非常穩(wěn)定。

等I過了之后，B的Clarification出來了，Judge換了一組樣例。于是開始調(diào)B。?B：給出16個數(shù),將他們排成十字架形，使力矩平衡。求本質(zhì)不同的方案數(shù)。

十字架一共有4個“臂"。首先找出一個“臂”的所有情況。然后將等值的無?重復(fù)的合并成兩個相對的“臂"。然后從16個數(shù)中選出8個，將他們作為一組，?另外８個作為另一組，這種方案的總數(shù)為前8個成對的方案數(shù)乘后8個成對的方案

數(shù)。最后把方案數(shù)求和除4.?本題屬于搜索題，而且時限特別緊,由于搜索問題的優(yōu)化空間往往很大，而且

又是多組數(shù)據(jù),所以很容易造成TLE.在調(diào)對樣例后TLE了一次，改進了算法后?由于開小數(shù)組RE了一次，終于在第三次提交通過了B題.

記得高中時一次在網(wǎng)上做題（只記得是xrｅｂoｒｎer出的題目)的時候,比賽一開始

就寫一道時限很緊的題目,估計開始程序的正確性是沒有問題的，就是效率比較低；?但是，在不斷優(yōu)化的過程中改錯了程序,導(dǎo)致1個小時以后當(dāng)程序不TLE了以后，

程序變成了WA。這樣使得信心完全崩潰。

聽了很多同學(xué)討論之后,發(fā)現(xiàn)不少隊伍就完全卡在了B題上。以后對這種題目?只能倍加小心,現(xiàn)在我們還沒有什么特別好的方法。而且,B題的樣例只具有測試?性，不具有調(diào)試性，編程時必須特別仔細才行.?這時大概才１個多小時,我們看似順利地通過了5題;但是現(xiàn)場的情況并沒有?任何優(yōu)勢可言,Shanｇri—La在幾分鐘后通過第5題,兩個隊伍的罰時只相差１分鐘.

隨后我們到達了第二段艱難的時期,主要原因是鬲融把F的題目看漏了一個條

件，與胡偉棟討論后誤以為這個題比較容易,很快這題出現(xiàn)Run-ｔｉmeＥrror好在重?讀題后發(fā)現(xiàn)錯誤并及時放棄，沒有再浪費時間去把Rｕn－timeＥrrｏr調(diào)成WA。如果

當(dāng)時死做此題則后果不堪設(shè)想。?在鬲融和胡偉棟分別讀F的程序以及題目的時候,由于現(xiàn)在剩下的題目都比較?復(fù)雜,我們選擇了一道相對清楚的題目H繼續(xù)做。?H:對一個集合進行兩種操作:插入一個數(shù)和詢問MＯDY最小的數(shù)中最后一

個數(shù).

由于數(shù)字的范圍是［1..50０００0]，先選擇一個合適的M.當(dāng)Y＜=M時，通過插入

時直接保存來處理,當(dāng)Ｙ＞M時直接枚舉,用并查集求一個元素的后續(xù)。這樣每一

次操作的時間復(fù)雜度是O（Sqrt（５00000)).

但是,開始選擇M為1000，并沒有充分估計復(fù)雜度的平衡性。開始我們認為?并查集的常數(shù)較大,但是后來感覺到并查集的常數(shù)相對小一些,于是把M選為

500就過了。后來在同出題人交流的時候,被告之M取在40０－８00的范圍內(nèi)都可以。

第二段艱難的時期的原因可能不僅僅是題目看漏,也由于題目難度已經(jīng)增加。?好在當(dāng)時特別是當(dāng)H的程序TLE之后,我們都比較冷靜,相信自己H題的算法是

正確的算法,只是參數(shù)的選擇不夠合理.這種考驗在平時一般是很少遇到的，經(jīng)受?這次考驗之后,再遇到類似的問題，我們應(yīng)該能夠更冷靜一些.

過了H之后,鬲融已經(jīng)再次確認了J的題意，隨著氣球的指引,我們決定攻克?本次比賽最大的“紙老虎”：J，而做Ｊ的過程中胡偉棟一直在想G,已經(jīng)大致得

到了算法的框架。?J:給出一些數(shù)的大小限制的關(guān)系，求更精確的關(guān)系后者判斷為矛盾。

轉(zhuǎn)換成圖的模型，不斷迭帶調(diào)整,直到不能調(diào)整為止。當(dāng)然這題由于大小限制

關(guān)系中既有'＜=’還有’<’,所以需要判斷ＸI〈XI是不合法的。時間復(fù)雜度Ｏ（Ｎ

3)。?J題的數(shù)據(jù)輸入輸出比較復(fù)雜，但是題目本身很簡單.這題對編程能力提出了很高?的要求。?通過J題之后,看了一下bｏａrd，當(dāng)時Shａngri—La只有5題，不過在我們還沒?有反應(yīng)過來的時候Shａｎgrｉ—Lａ就也同樣７題了，罰時上我們領(lǐng)先4次提交。

在比賽的前200分鐘，我延續(xù)了ＴCCＣ２00６的良好狀態(tài)。我們配合默契,在面

對BHＪ這樣瑣碎的題目時，隊友會提前把需要注意的細節(jié)總結(jié)在紙上，整個過程?都保持得很平滑.另外，鬲融和胡偉棟在我做每一題時都準(zhǔn)備了很合適的測試數(shù)據(jù)，

大大減小了我測試的時間并很有效地提高了提交正確率.由于剩下的題目難度明

顯高出一個檔次，在通過7題時的罰時領(lǐng)先是最后獲得比賽勝利的重要砝碼。?現(xiàn)在剩下的只有Ｅ，F(xiàn)，G三道沒有隊通過的題目了，其實最終也沒有隊伍通?過。我們曾經(jīng)讀錯過F，因此這次分別嘗試了E和G,但是都失敗了。這里我們曾?經(jīng)討論過先做Ｅ還是先做G,當(dāng)時面臨的選擇是：E的復(fù)雜度估計較高,不知優(yōu)化

后能否通過，而G的算法性更強,胡偉棟仍然沒能完全清楚如何解決，實現(xiàn)的復(fù)

雜度高于E。我們這次帶有賭博性的選擇了E,并沒有仔細考慮如果Ｅ的時間要求

過于嚴格會出現(xiàn)什么問題（可能與Ｂ的相對輕松通過有一定關(guān)系），在此后的比

賽中我們應(yīng)該注意周全考慮，盡量選擇題意清楚并且復(fù)雜度容易估計的題目。?Ｅ:帶限制的有向圖的第K短路.

本題其實有標(biāo)準(zhǔn)的A＊算法，我們也使用了這個算法。但由于復(fù)雜度過高，我?們的程序一直TLE.據(jù)Ｊudgｅ說這題對時間的要求非常嚴格.?G:在一個森林的若干點布置儀器，儀器有作用范圍D，儀器之間的距離需要

大于等于D，求最大的覆蓋長度和最小的權(quán)。?本題可以使用二次方狀態(tài)的動態(tài)規(guī)劃，類似CＴSC2004的一題。我和胡偉棟討?論后成功想出了正確的方法，并且在最后時刻寫出了程序，而鬲融和胡偉棟則出了?一些測試數(shù)據(jù)，將數(shù)據(jù)調(diào)過后時間已經(jīng)很緊張了。首先由于忘記優(yōu)化fｌoｙd超時了

幾次。在優(yōu)化了floyd算法之后,還是沒有考慮到圖不連通的情況，未能在比賽結(jié)

束前調(diào)出。

F:給出一些公理，假設(shè)和定理之間的關(guān)系，依次嘗試,推出盡可能多的定理。?在同等情況下要求使用的假設(shè)最少。

本題可以用最小費用最大流解決,但是比較容易實現(xiàn)的網(wǎng)絡(luò)流算法都很難在時?限內(nèi)出解。?現(xiàn)在看來,ＥFG三題中的E沒有比賽中想像得那么難,當(dāng)時比賽中受到巨大壓?力的影響沒能攻破此題，不過FＧ題即使出現(xiàn)在CＴＳC難度的比賽上也非常合適.

比賽結(jié)束：罰時險勝?比賽結(jié)束時我們與Shangri-La同為7題，上海交大一隊最終也通過了7題，我?們依靠罰時的微弱優(yōu)勢險勝。經(jīng)過驚天地泣鬼神的300分鐘,我們終于獲得了夢寐

以求的20０6上海賽區(qū)冠軍。MobileRobot憑借著上海賽區(qū)的奪冠,已經(jīng)可以認為

獲得了進軍２０07東京世界總決賽的入場券.?比賽結(jié)束后見到了很多復(fù)旦的老朋友和吳永輝老師，吳老師還是和以前一樣,

玩笑開個不停.那些復(fù)旦的老朋友賽前由于是參與出題，我們一直沒有看到，頒獎

儀式之前，我們終于有機會在后場一起聊天。不過聊天這些時間中,我和b１4２８５7

錯過了郭老師在頒獎儀式前進行的“點名"(當(dāng)時郭老師要求我們上去講解題目）,?實在不好意思。

總結(jié):?首先向Ｓhａｎｇrｉ-Lａ致敬,即使在最后一刻,相信大家都還仍然有機會,棋逢對?手也是我ＡCM生涯中的一大幸事.當(dāng)兩支隊伍都通過7題的時候，排在第３名的

隊伍才剛剛5題。也就是說，我們兩支隊伍其實只用了2/3的比賽時間就鎖定了上

海賽區(qū)的冠亞軍。

上海交大一隊最終也通過了7題，比賽開始時我們就注意到了交大開場時非常?不順利,不過頑強的交大一隊穩(wěn)扎穩(wěn)打，在最后一小時也成功通過了第7題。在這

里向交大致敬,開場的種種不利不亞于我在杭州２０05時的起跑，你們能夠沉著應(yīng)?戰(zhàn),破釜沉舟的精神一直值得我們學(xué)習(xí)。當(dāng)時交大一隊中有一位來自遼寧的選手辛?韜,記得NOI20０３之前我們有數(shù)次交手都以我失敗告終，后來經(jīng)常在許多網(wǎng)上比?賽中切磋,2005年AＣM北京賽區(qū)也有你熟悉的身影,在清華早有耳聞你在交大的

優(yōu)異成績，祝福你今后越來越好。?這次比賽的命題工作是由復(fù)旦大學(xué)擔(dān)任的，復(fù)旦大學(xué)的命題特點與東歐的命題?風(fēng)格很接近，題目的算法性偏強，題目對程序運行速度要求普遍高.

按照paｎda的說法,上海微軟AＴＣ隊由于一些配合的失誤,最終只通過5題，

不過也是前10的隊伍之一。另外，蕪湖一中隊也順利通過5題排進前十.GoｔoFlｙ

通過第3題的時候還排在第3,不過后來卡死在J上了，有些可惜。

后來,分配總決賽名額的時候,上海賽區(qū)得到了10個總決賽名額,這個數(shù)字

相信也是這些年來的之最吧。

這是一場值得紀念的比賽，參加2006上海賽區(qū)的強隊實力遠高于幾年內(nèi)的各?大賽區(qū),能夠站立在上海賽區(qū)的最高領(lǐng)獎臺是ＭｏbｉｌeRoｂｏt獲得的最高榮譽之一。

經(jīng)歷了上海賽區(qū)大戰(zhàn)的洗禮,接下來的西安賽區(qū)出場的則是更成熟的MobilｅＲobot.

附上海賽區(qū)排名:?1TsinghuaUnivｅrsｉtｙ=〉MobileＲobot7617

2ＴsinghuａUniversitｙ=＞Shａngri-Ｌａ７７0９

２ShanghａｉJｉaｏTongUniveｒsｉtｙ=〉Laｃoｔiｘ71０34

2ＦudanＵnivｅrｓity=＞ＳｙｍphonｉcＲaｉｎ6924

2ShanghａiJiaｏToｎgUniｖersｉty＝>Ｐroｄigｉｅs6９５7?２ＦudaｎＵniｖeｒsｉｔｙ=＞ShuａngYY6109８

2XiaｍenＵniverｓitｙ=>btＡLT5534?３NaｔｉｏnaｌTaiｗanUｎiversity＝>ｐuｙo5５63

4ＴheFirｓｔMidｄlｅSｃｈooｌofWuhｕ=〉WHYＺ5652

４ＭicroｓoftATCＳhａnｇｈai＝>Ｃｏre—Stｏｐ－Dump５729

４ＺｈｅｊiangUnivｅrsity=〉GoｌｄenKeyboard５8１７?5ＰekｉngUｎiversity＝＞ＰKU_T25819?6ZheｊiａngＵnｉveｒｓiｔy＝>Dashｅr５956?6EastＣｈinaUnｉｖersityoｆSciencｅａndTeｃｈｎｏｌogy=〉Reｄfiｅld４325?7TsinghｕａＵｎivｅrsity=〉GｏtｏFLY４３67?７ＺhｅｊiaｎgUｎiｖersity=＞sａgo4３９2?7ＮａｔｉonalUniverｓiｔyofＤefeｎsｅTechnoｌogｙ＝〉Robusｔ４438

8ZｈonｇshａnUnｉverｓity=＞ZSU—Ｔanｇｌｈa45１2

９TongｊiUｎiｖersiｔy＝>Rｅvｅｎge455９?1０ＳhａnghaｉJｉaoTongUnｉversity＝>Ｈ—E-Ａ—T46０0

10XｉdiaｎUniｖｅｒsity=>AＣＭore1４60２

11WuhanUniversitｙ=>Ｍooｎmｉｓｔ47２3

１２ＺhongshanUniｖerｓｉtｙ＝＞ZSU_Olyｍpuｓ4７65

12NａｎjiｎgUniｖersiｔyoｆSciｅnceａｎdTechnoloｇy＝>Narｃisｓus４77４

13NｏrｔｈｗesternPolytechnicalUnｉversity＝〉10１01１0０4845

14HarbｉnＩnstｉtuteofTeｃhnｏｌｏgy＝>Ｇaminerie３200

15FudanUniｖerｓiｔy＝〉White＊［Bear+Ｄew+Cloud]3337

15ZhongshanUnivｅｒsity＝〉ZSU—Everesｔ3360

1５HefeiUniｖｅrsｉｔyofTechnoｌogy＝〉HａppyＦorUｎｐainTeeth３406?16BeijｉｎgＵnivｅrsｉtyｏｆPｏｓtsandTelecommunicaｔiｏns=＞Neon３４42?１7ShenzhｅnUniveｒsity=〉A(chǔ)spｉre３453

１８HarbiｎI(lǐng)nstituteofTeｃhｎology=>Ｃorsａir345７?１8NaｎｊiｎｇUniｖｅrsiｔｙofSｃｉencｅandTecｈｎology=〉bａｃkboneｓ3４61

1８ＳouthChiｎaAgriｃuｌｔuｒalＵnivｅrsｉty=〉ｓcaｕ_upｄate3468

19HuazhoｎgＵｎiversityofＳcienｃeａｎdTechnｏｌogy=〉rodiｍuｓ３4８0?2０NｉngbｏUｎiversity=>ACHC３５05

21ＰekｉngUnivｅrｓity=>351３?21FuzhoｕＵnivｅrｓity=＞OrOｒz３520

22NａｔiｏｎaｌUnｉｖeｒｓityofDeｆｅｎsｅTecｈｎｏlogy=>Ｐuzzｌe35２０?２2ＤongｈｕaUnivｅｒsｉtｙ＝>Gespenst3535?22HuｎanUnivｅｒsity=＞Fｏotｍen３535?2３TianjinUniversｉty＝>TJU_Rｏckｅｔ3563

24NatｉonalTaiwaｎUniversity=〉ＡBＣDE3５6８

２4NanjingUniｖersityｏｆAeｒｏnauticsandAstｒonauｔｉｃｓ＝>ZipＦｉｓh35７5?25UniveｒｓiｔyｏｆEｌｅcｔrｏnｉcSｃiencｅandＴｅchnolｏgyofChｉna=＞?transiｓtor35９9

26ＳhanghaiJiaoTｏnｇＵniverｓity=＞Lucifer３６08?26ZhengzhouUniversity=〉ZZU_ｃheａｐwｉne36５0

２7ＷuhanＵnｉvｅrsｉty＝〉Siｌenｃe3685?27HangzhｏuDiａｎziＵniveｒsｉtｙ＝〉MP33687

28JiｎanUnivｅrsity=＞JNU－FLＹ3830?29HuazhongNormalUｎivｅｒｓity＝＞Neptune385７?利用假期空閑之時，將這幾年GCJ，AＣＭ，TopCoｄeｒ參加的一些重要比賽作

個回顧。ＧＣJ2006,ACＭ200５和ＴCCC２0０6之后，2０06年對于我來說是一個大豐

收，晚上發(fā)ACM西安2006吧。

2006年AＣＭ-ＩCPC(下）—-古城西安

艱苦的ＡCM20０6上海賽區(qū)結(jié)束之后,我們原本以為清華會選擇另外３支隊伍?參加西安賽區(qū)的比賽.況且，大三的課程的實驗任務(wù)很重,我們也就停止了計劃的

定期訓(xùn)練。大概在２5天之后，12月2０日左右突然收到鄔老師的通知，準(zhǔn)備出發(fā)?參加ACM西安賽區(qū)比賽。我們的20０6西安之旅也就是在這比較倉促的準(zhǔn)備中開

始的。?西安賽區(qū)之前，我們沒有定下明確的目標(biāo)，比賽過程中處處都采用了追求穩(wěn)健

的方法，當(dāng)時也是為了避免一年前的杭州悲劇重演。

西安的比賽沒有太多興奮的ＡC,沒有驚心動魄的場面，所有過程都在類似旅

游的氣氛中結(jié)束了。作為MｏbｉleRoboｔ的最后一戰(zhàn)，這里也作一個簡要的回顧吧.

由于這次題目又是Srbga(劉汝佳）命題的，我最后也順便列舉一下我總結(jié)的他命

題的特色吧。

比賽過程：

20０6年清華同樣派出了3支隊伍參加西安賽區(qū),除了MobiｌeRobot（我,?ｇｅwoｒｍ（鬲融）和wｄ.h(胡偉棟））之外,還有Ｐａnaｃea（OpｅnGL（唐文斌），zhy（周源）?和liｕhe（劉賀)，如果你第一眼看見這個詞就知道是什么意思,我相信您一定準(zhǔn)備過

GRE吧？)以及一起參加過2006上海賽區(qū)比賽的GｏtｏFＬY(zcgzcgzｃg(朱晨光)，?ｗaｎgjun（王俊)，ｔedcn（龍凡)）.?2006年冬天是我第一次來到西安，剛下火車就深深感受到了西安的古城氣息。

到達賓館之后，我們做得第一件事情就是玩，印象很深的是鐘樓，鼓樓還有大雁塔.?我們做的最主要的事情可以用GoｔｏFＬＹ的4個大寫字母GFLY來表示,就是“公

費旅游”。?比賽之前的晚上，我們認真討論了比賽中采用的策略，參加西安賽區(qū)沒有太多?傳統(tǒng)強隊，我們一致覺得應(yīng)該優(yōu)先采用比較穩(wěn)健的策略.賽后有比較簡短的總結(jié):?按照一貫的方法，鬲融從A開始讀,胡偉棟從J開始讀,我準(zhǔn)備編程的環(huán)境，

然后從中間選擇題目讀.與上海賽區(qū)相比，比較順利的是我一下就看到了一道比較

簡單的題目B，于是我馬上寫了Ｂ題.

Ｂ：使用火柴棒拼接數(shù)字，給定n，ｍ，求使用不超過n根火柴棒拼成的m的倍?數(shù)中最大的數(shù)字。?本題主要的思想是動態(tài)規(guī)劃，方程很容易得出，時間復(fù)雜度Ｏ（nm＊10）。但是

本題有兩個難點:

（1）如何得到最大的數(shù)字？標(biāo)準(zhǔn)的方法是使用BFS，搜索的過程中必須非常注意?搜索的順序，但是這樣實現(xiàn)很容易出錯。我注意到了ｎ〈＝１０0的條件，因此結(jié)果不

會超過5０位,于是我使用3個ｉｎｔ64來保存結(jié)果，這樣既實現(xiàn)簡單又不容易錯。雖

然程序常數(shù)比較大,但是不至于導(dǎo)致超時.

(2）不能不使用火柴棒，而數(shù)字0也需要火柴棒來拼成。例如n=5,m=97的結(jié)

果是—1,而n=6，ｍ=97的結(jié)果是0。

AＣM比賽的第一題的選擇對比賽的進程影響很大，此次比賽很成功地使用了

很穩(wěn)妥的算法。?E：標(biāo)準(zhǔn)的課堂睡覺問題,求最早所有人不睡覺的時間.

簡單的模擬題，而且時限很寬松。

E其實是最簡單題目,但是由于我的低級錯誤，不僅得到了一次罰時，而且浪

費了寶貴的時間.好在當(dāng)時比較冷靜，很快改正了錯誤。

D：對于一個不超過100＊100=1０000的表達式，可以在其中加入＊來表示任何

字符,如果一個表達式只能和唯一的等式對應(yīng),則稱為A類表達式。給定一個表?達式B,要求通過改變最少的字符使它變成Ａ類表達式。?本題使用了一次搜索再檢索的方法,可以有效控制程序的速度。估計時限問題

后選擇先提交節(jié)省了不少時間。?Ｊ：給定一個4*４的網(wǎng)格的邊框圖形，問是否可以通過在４＊4的網(wǎng)格上放6個

2*2的正方形框得到。?Ｈ：給定一組旋轉(zhuǎn)后的樂譜及初始音符及結(jié)束音符，求原始的音符序列.?開始胡偉棟沒有看到旋轉(zhuǎn)的角度是整數(shù)的條件，于是推出了可以解決實數(shù)角度?的數(shù)學(xué)公式。但是由于公式需要考慮的情況比較復(fù)雜，幸運的是我們使用了枚舉角?度再判斷的方法.?寫了讀入部分之后，看到Pａｎacea過了H題。鬲融重新讀了題目,發(fā)現(xiàn)了角度是整

數(shù)的條件,于是稍微修改就得到了正確的程序。

本題需要判斷的條件很多，需要考慮得很仔細：?(１）先把坐標(biāo)按照X排序.

(2)通過初始音符及結(jié)束音符得到ｓd，判斷sd是否在1到5之間.

（3)判斷相鄰兩個字符的距離是否在sd到５sｄ之間。

(4）判斷每個點的坐標(biāo)是否可以對應(yīng)一個音符。?F:求3維空間的Voｒonoi圖,輸出每個Ｖoroｎoi塊體積占的比例.

胡偉棟提出了本題的正確算法:分割立方體。如果一個立方體的8個頂點都到?一個點最近，那么這個矩形內(nèi)的所有點都到這個點最近,否則就分割這個立方體,

直到立方體的體積少到一定程度為止.

開始程序的精度不夠,后來胡偉棟提出了一個啟發(fā)式的分割立方體的方法,思

想就是使得兩個立方體的分割面以盡量大的概率穿過Vｏrinoi平面。程序的效果很

好，而且那時時限也已經(jīng)放寬，于是順利通過了F題。其實本題蒙特卡羅法也可?以過，我們也想到了這個方法，但是由于隨機過程寫的效果有問題，導(dǎo)致精度不夠。?通過F題的時間是２7０分鐘,封版時除了Panａｃｅａ通過4題,其他隊伍最多只?有３題。當(dāng)時Panacea正好坐在我們背后，很可惜他們卡在了D和G上,最終也?只有４題。最后半小時我們也沒有嘗試Ｈ或者Ａ,因為其他隊伍很難在最后一小?時通過4題。我們就簡單嘗試了幾次Ｃ就默默地等待著西安賽區(qū)比賽的結(jié)束。

最終我們通過6題排名第一，由于已經(jīng)獲得了上海賽區(qū)的冠軍，不參加ICPC?的排名，不過仍然獲得了Solａris杯。?總結(jié):?西安的IＣPＣ冠軍是北京大學(xué)的Ｔ2（raｉｎer，dzx和ｃicｉ），后來他們依靠西安?的奪冠成績進入了2007年的全球總決賽.T2在最后一小時表現(xiàn)極其神勇，順利通

過2題一舉超過了ＧotｏＦlｙ和Pａnacea，而且最后幾分鐘還很有希望通過H，賽后

和ｒaineｒ討論之后發(fā)現(xiàn)算法相差無幾，可能就是一些小細節(jié)缺陷吧。20０6-2007年?度的ACM比賽,從上海到西安,還有東京的總決賽，MoｂilｅＲｏｂｏｔ每次比賽都能

看到了T2熟悉的身影。我們在封版之后常常由于壓力較大很難攻破題目，他們在?封版之后的冷靜心態(tài)非常值得我們的學(xué)習(xí).

GoｔoFly與T2一樣通過5題，由于5分鐘的罰時劣勢位居第三,Ｐaｎaceａ通過4?題依靠罰時優(yōu)勢排在第四.兩隊都欠缺一些運氣，很可惜。另外印象很深的是，坐

在對面的朝鮮隊通過了４題在ICPC中排名第2，如果西安能夠多一個名額的話，

他們就能夠出現(xiàn)在總決賽賽場了.

西安賽區(qū)是Srbgａ（劉汝佳）出的題目，從高中時期就開始做了Srｂgａ出的題?目，西安賽區(qū)的題目又一次體現(xiàn)出了劉汝佳命題的許多重要特色：

(1）如果Srbgａ大哥出是一套題目，那么你會明顯覺得題目拿在手上明顯重一?些.Ｓrbga大哥出題很重視題目描述或者故事的完整性，他很少使用一些僵?硬的題目模型和描述。有時讀著他出的題目更像是在讀小說，欣賞故事.?當(dāng)然，由于Srbｇa大哥出的題目描述完整,剛拿到題目的時候會感覺很難?上手。我們很容易發(fā)現(xiàn)沒有一道題目容易上手。用數(shù)據(jù)表達，比賽開始時?的空機時間偏長。

（2）Srbｇa大哥出的題目和世界總決賽的題目風(fēng)格近似,題目多半對編程能力?提出很高的要求,相比之下對算法的要求不是非常高，考察的都是比較基?本的算法。如果用一個字形容就是:野。

(３）Ｓrbｇa大哥出的題目對算法的考察范圍非常廣，雖然對于某特殊的算法要?求不高。有時還需要很強的組合算法能力.?(4)Srbga大哥出的題目中很注意數(shù)據(jù)的設(shè)計，例如C題中特別生成了極端的

情況，J則使用了接近20００0組數(shù)據(jù).一般情況下，不經(jīng)過精心設(shè)計的隨機?算法會吃盡苦頭。?2006年的MｏbileRoboｔ的ＡCM分區(qū)賽比賽任務(wù)已經(jīng)全部結(jié)束了，20０6對于

MobilｅRｏbｏt來說是豐收的一年,我們圓夢了上海和西安的雙冠軍。在隨后的冬天，?我們加緊訓(xùn)練準(zhǔn)備東京的總決賽。?利用假期空閑之時，將這幾年GCJ，ＡCM，ＴoｐCoder參加的一些重要比賽作個?回顧。回顧了GＣJ2０0６和2０05年的ＡCM之后，轉(zhuǎn)向TopCodeｒ的比賽吧。我參加

的最早的TopCoder賽事是TCCC2006.?TCCC２006-—死亡之組?TopCoderCｏｌlegiatｅChaｌlｅnｇe（簡稱ＴＣCC)是ＴoｐCoder一般在秋季舉行的面向全?世界在校學(xué)生的程序設(shè)計大賽，200６年的ＴＣCC在圣地亞哥舉行.從北京到舊金山?的飛行只需要11個小時左右，所以不至于那么疲勞。路上一切都很順利，很感謝

OpenGL的提醒，對于超過8個小時飛行自帶拖鞋和枕頭對我來說還是很重要的.?ＴCCＣ2０06使用的標(biāo)準(zhǔn)的TｏpＣodｅｒ現(xiàn)場比賽形式，比賽有４８名選手參加,首?先４8名選手被分為1６個人一組,每組分別進行半決賽，前2名直接晉級決賽,3—

6名晉級ｗilｄcａrd比賽，wilｄcarｄ比賽12人中的前兩名填補決賽的最后２個名額，

決賽由8個選手參加。ＴoｐCodeｒ現(xiàn)場比賽中很重要的一個創(chuàng)新是：每名比賽選手?在觀眾席前都有一個同步的顯示器，這樣觀眾可以看到選手任何時刻做的事情，極

大增強了互動性.?TCCＣ2006的Roｏm1和后面的ＦiｎalRound都可謂是死亡之組?，F(xiàn)在就回憶一

下這兩場激烈的比賽吧。?Rｏｏm1：?至于3個房間的分配，TｏpCodｅr按照注冊截止時選手的Rating分布蛇形分配.

但是ＴCＣＣ２0０6的房間實力分布極不平衡,我與上屆冠軍tomek,著名選手reｉd,

Egor,haｌｙavin還有Ｒating不高但是實力極強的Yｉng和aｒdｉaｎkp同被分到了Room?1，賽前Rｏom1成為公認的死亡之組。

在圣地亞哥，我和師兄Maｃsy（張一飛）同一個房間,很感謝師兄的關(guān)心，我?那幾天休息的都很好。要知道如果同房的人有10小時左右的時差的話,一人必須

很小心才能保證不影響另一人的休息。?Rｏom１在我抵達美國的第二天早上進行,選手允許提前３0分鐘準(zhǔn)備一些必要

代碼。不過現(xiàn)在大家都比較喜歡學(xué)習(xí)Pｅtr那樣一行代碼都不打.下面就是比賽的

過程:

250分題目是：給定n（ｎ＜=５0)個整數(shù)AI和一個閾值d,計算n個整數(shù)所有排列?PI中滿足｜AＰI-API+1｜〈=d的排列中，所有不同可能AP1的個數(shù)。這題最標(biāo)準(zhǔn)的方法是?動態(tài)規(guī)劃，基本思想是把ｎ個整數(shù)排序之后，計算兩條相鄰元素不超過d的序列.

我使用了一種更精巧的算法，把ｎ個整數(shù)排序之后,對于AI，如果AI可能作為排

列的第一個元素,那么ＡI必定在某一個方向(大小)連續(xù)而在另一個方向每間隔

兩個元素相連。這個算法比較容易實現(xiàn)，但是正確性證明比較難,甚至讓人第一感?覺是錯的。我寫完程序測試了所有樣例都正確就提交了,24３分。提交之后我又測?試了許多數(shù)據(jù)，并在紙上嘗試證明正確性。?賽后,我看了網(wǎng)絡(luò)上的討論記錄.在我提交２５０分題之后,立刻遭到了ｍisof

的懷疑，他認為我的算法有問題.據(jù)Macsy學(xué)長的回憶，OpenGL在我屏幕前看我?寫完程序,也認為我的算法是錯的，不過后來他們討論之后發(fā)現(xiàn)沒有反例。

關(guān)掉250分題目之后，我剛剛意識到Room１的３題分數(shù)不是250－500—１000，?而是250—6０0-900?，F(xiàn)在看來，對于2５０比較順利的情況，應(yīng)該先做5００,若25０?不順利或者想出奇制勝的話，可以先開１000分.當(dāng)時沒有什么經(jīng)驗，我認為900

比６00應(yīng)該簡單一些，于是就打開了9００.

900分題目是：給定一張n(n<＝10)個點的帶權(quán)有向完全圖(也就是ｎ2個實數(shù))

和一個衰減系數(shù)p,求一條經(jīng)過d(d〈＝10）條邊路徑（不需要保證簡單路徑),要求?這條路徑的指數(shù)衰減長度(指數(shù)衰減是指第i段的長度乘以pi—1然后求和)最接近?100０.這題如果使用窮舉法，就需要1０10左右的計算量,在TopCoｄer的測試機上

也不能通過,由于路徑長度很容易超過1０００,所以很難找到多項式時間的動態(tài)規(guī)

劃。我馬上有了一個想法——雙向搜索。對于長度為d的路徑,其實可以看作從

某一個點p出發(fā)的一條反向的長度[ｄ/2］的路徑和一條正向的d—[d／2］的路徑，對于

固定的節(jié)點v來說，這種兩個方向的路徑都不超過n［d/2］，這樣只要枚舉一個方向?的路徑然后二分查找另一個方向即可。復(fù)雜度是O（dn2+[d/2］).?現(xiàn)場比賽調(diào)試環(huán)境不是很好,我花了不少時間調(diào)試以發(fā)現(xiàn)程序中的錯誤。提

交之后６９0多分,還不到700。不過對于9０0分的題目在那種壓力下還可以接受。

提交之后我花了1５分鐘左右測試,沒有發(fā)現(xiàn)錯誤。于是就準(zhǔn)備做600了。?600分題目是：一道經(jīng)典的數(shù)學(xué)題，給定一些盤子疊放的規(guī)則,計算頂層盤子?的最大可能大小。其實算法不是很難,只要二分頂層盤子的大小，然后依次貪心計?算來判斷底層是否能夠滿足即可。只是貪心的時候要考慮兩種情況,一時想不清楚.?我當(dāng)時已經(jīng)感覺很疲勞，思路不是很清楚，最后4０分鐘時間也沒能調(diào)試通過。這

題過于瑣碎，Ｒooｍ1中最終沒有選手通過600分題,并且成就了一個刺激的

Chaｌlｅnge階段。

Coｄｉｎg階段我和ｔoｍｅk采用了截然不同的策略,我跳過600直攻9０0,而

ｔomｅk在６0０中掙扎了很長時間才放棄。Ｃｏｄing階段結(jié)束時，有4名選手提交了3

題.我依靠速度優(yōu)勢領(lǐng)先同樣提交250和９00的tｏｍek３5分左右。?Cｈallenge階段開始時,我盲ｃha（bliｎdcｈalleｎge）了一個最后時刻提交的9０0

分程序，但是由于我選擇的數(shù)據(jù)實在太弱,失去了25分。這樣我和后面的tomek?只相差10分左右了,所以我決定只要tomek不動,我也不動了。其實，當(dāng)時

tｏmｅk已經(jīng)知道自己的900是錯的，Ｃhａｌleｎgｅ階段他估計已經(jīng)放棄了。我的

Cｈallｅnge階段最終就以－25分結(jié)束。

之后的Ｃhallｅｎge就是Ｙiｎｇ(王穎）展現(xiàn)勇氣和智慧的舞臺了。他Chａllenge掉

了所有提交的6０0，憑借2２5分的加分超過了我，排在榜首。這樣比賽的形式也一

目了然了,７位選手提交了９00，我依靠速度優(yōu)勢領(lǐng)先第四名reｉd超過1０0分。只

要我兩道題目能夠ＰassedSystemTest就足以進入Fin