原來(lái)沒想著能去觀摩比賽的，比賽前幾天，才被告知能夠隨大隊(duì)一起去。

周六去注冊(cè)報(bào)名試機(jī)和做阿里巴巴的PK，我沒事做，在教練室閑著。其他高校很多人留在那里做阿里巴巴的PK，我們懶得做，跑去玩和吃雪糕了，等到鐘了就去吃自助餐，吃得好飽，據(jù)郭老說(shuō)，人均標(biāo)準(zhǔn)是60元。總的來(lái)說(shuō)，我們不是去吃東西，我們是去學(xué)習(xí)、進(jìn)步、交流的，我根本不記得我吃了七八個(gè)肉丸、十多只茶葉蝦、四五塊鮮嫩雞肉、四個(gè)小蛋糕、一碟拉皮、豬骨玉米湯、紅棗蓮子湯、一碗豆芽豬紅、牛腩、香蕉西瓜番茄若干、可樂兩杯、雪碧一杯、紫番薯兩塊，我只記得人山人海以及阿里巴巴PK比賽的趣味性。

第二天比賽，早早過(guò)去，在教練室一邊看他們比賽，一邊記錄下現(xiàn)場(chǎng)報(bào)告，可惜3個(gè)小時(shí)后電腦沒電了，所有插座都被老師用光了~~只能看起題目來(lái)，發(fā)現(xiàn)我自己來(lái)做，也是只能做出3道。。。囧

很可惜的是，79名就能夠拿到三等獎(jiǎng)，良智他們隊(duì)85名，主要是在K題提交了幾次，或者說(shuō)E題沒做出來(lái)。其他隊(duì)更是在120名之后~

事后評(píng)判長(zhǎng)的題目分析是這樣的：
A題：水題，全場(chǎng)都過(guò)。
B題：水題，僅有幾支隊(duì)伍沒過(guò)。
C題：網(wǎng)絡(luò)流+二分答案。
D題：
E題：右上角開始搜索。
F題：中國(guó)剩余定理變型+高精度。
G題：博弈，判斷兩端端點(diǎn)或者用SG理論。
H題：
I題：
J題：枚舉、DP都行。
K題：BFS、智權(quán)的最長(zhǎng)路徑、DP都能過(guò)。
椰子的弟弟他們隊(duì)伍拿到了十六名。看著場(chǎng)上那些拿獎(jiǎng)的牛人，我覺得我們更應(yīng)該覺得熱血沸騰，想方設(shè)法超越他們。難道我們只想著看著別人在我們面前打機(jī)而看不過(guò)別人在我們面前拿獎(jiǎng)？

我相信他們?cè)诮酉聛?lái)的區(qū)域賽能夠表現(xiàn)得很好。那也是能夠讓學(xué)校矚目的機(jī)會(huì)。實(shí)在不行就當(dāng)是次旅行也行吧？據(jù)說(shuō)最近的賽區(qū)是在武漢。

以上是我們學(xué)校的比賽總結(jié)，下面看看本次冠軍隊(duì)伍的總結(jié)，轉(zhuǎn)自中大論壇逸仙時(shí)空：
http://argo.sysu.edu.cn/bbscon?board=ACMICPC&file=M.1273582283.A

發(fā)信人: litexavier (Xavier), 信區(qū): ACMICPC
標(biāo)  題: GDCPC 2010 Summary @ SYSU_Stellation
發(fā)信站: 逸仙時(shí)空 Yat-Sen Channel (Tue May 11 20:51:23 2010)

自blog截出來(lái)的，砍掉了一大段東西，將就著看吧。
另外已將題解劇透，有想明年做GDCPC2010的忽略此文好了。

——ANALYSIS——

按照規(guī)矩，先來(lái)說(shuō)下這次比賽的簡(jiǎn)單題解：

A: 在n x n x n的盒子中，放m x m x m的木塊，問最多放多少塊木塊。
答案應(yīng)該很顯然吧。

B:一開始序列S={1..N}，P={}，然后每次P = P + S，S刪掉最小的M個(gè)元素，如此循環(huán)，直
到S={}，問P中第K個(gè)元素是什么。
簡(jiǎn)單的計(jì)數(shù)問題。等差數(shù)列解之即可。

C:給出M種產(chǎn)品，以及每種產(chǎn)品的個(gè)數(shù)。給出N個(gè)檢查員，每個(gè)檢查員能檢查給定種類中若
干產(chǎn)品的一個(gè)，但是每個(gè)產(chǎn)品只能由一個(gè)檢查員檢查。并且檢查每個(gè)產(chǎn)品的時(shí)間是一樣的
。問最少花費(fèi)多少時(shí)間才能檢查完所有產(chǎn)品。
構(gòu)造一個(gè)流量圖：如果檢查員A能夠檢查產(chǎn)品B，那么在A,B間連一條流量為無(wú)窮大的邊，所
有產(chǎn)品到匯點(diǎn)連一條以產(chǎn)品個(gè)數(shù)為流量的邊。那么，如果已知最少花費(fèi)時(shí)間為T，那么就從
源點(diǎn)連一條流量為T的邊到每個(gè)檢查員上。這個(gè)圖的意義很明顯：“所有檢查員在T時(shí)間內(nèi)
檢查完所有產(chǎn)品”的充分必要條件為“該圖的最大流等于產(chǎn)品總數(shù)”。那么，接下來(lái)只要
二分T即可。

D:給出N個(gè)點(diǎn)，試確定兩個(gè)正方形，滿足：（1）所有給定點(diǎn)都在某個(gè)正方形內(nèi)；（2）正方
形的中心（對(duì)角線連線的交點(diǎn)）必須在某個(gè)給定點(diǎn)上；（3）最大的正方形的面積最小。

二分正方形的邊長(zhǎng)L。然后根據(jù)鬼才知道的某個(gè)單調(diào)性掃描判斷出用兩個(gè)長(zhǎng)度為L(zhǎng)的正方形
能不能滿足題設(shè)。

E:楊氏矩陣上的一些操作。
做法都固定了吧。

F:給出A和B兩個(gè)序列，試找出一個(gè)最大的Y和最小的X，滿足X = Ai ( mod Bi * Y )，for
each i。
首先因?yàn)?X = Ai + Ki * Bi * Y = Aj + Kj * Bj * Y，于是必有 Ai = Aj ( mod (Bi,B
j)*Y )，即 (Bi,Bj)*Y | Ai-Aj。于是Y被確定下來(lái)，接下來(lái)的事情就只是中國(guó)剩余定理了
。

G:給定一個(gè)無(wú)向圖G。問經(jīng)過(guò)G中給定的X個(gè)點(diǎn)和Y條邊的最小花費(fèi)是多少。
由于X和Y很小（X+Y<16），于是一個(gè)簡(jiǎn)單狀態(tài)壓縮動(dòng)態(tài)規(guī)劃即可。注：別忘了做預(yù)處理。


H:給出N個(gè)總長(zhǎng)度不超過(guò)300,000的關(guān)鍵字。并且，給出M個(gè)文本，每個(gè)文本的長(zhǎng)度為L(zhǎng)。對(duì)
于每個(gè)文本，求出該文本出現(xiàn)的關(guān)鍵字個(gè)數(shù)S，然后用S替代下一個(gè)文本的"0"，并輸出S。

經(jīng)典自動(dòng)機(jī)。需要注意的是要延遲處理關(guān)鍵字個(gè)數(shù)的統(tǒng)計(jì)，總之，是個(gè)細(xì)節(jié)題，要仔細(xì)分
析每步的復(fù)雜度。

I:無(wú)愛的博弈題啊。
SG值可以搞定，大概。不知道SG值是何的可以搜Game Theory這書。

J:給出N個(gè)二元組(v,c)，從中選出K個(gè)，并確定順序，使得給定函數(shù)的值最大。注意：c <
 1。
按照 v / (1-c) 排序。然后順序就確定了，之后就是一個(gè)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問題了。

K:打地鼠游戲。已知地鼠出現(xiàn)的時(shí)間，并且規(guī)定錘子每單位時(shí)間只能移動(dòng)到相鄰的地洞上
，并且擊打操作是不需要時(shí)間的。問最多打到幾只地鼠。
簡(jiǎn)單的動(dòng)態(tài)規(guī)劃題目。

——????——

開場(chǎng)后，老樣子，db從A開始，我從K開始，趙牛中間。db第一時(shí)間讀完A題，并很快開始c
oding。我讀完了K，算了下復(fù)雜度，剛好的樣子。于是又一道水題到手了。db交A了之后，
我開始敲K。不久之后A返回Yes，然后db的B就在隊(duì)列中了。敲完的K的代碼沒過(guò)樣例，離線
debug了下，發(fā)現(xiàn)是初始化狀態(tài)搞錯(cuò)了。改之，返回第二個(gè)Yes。再來(lái)db連續(xù)開了B,E,C三題
，都是很順利的過(guò)掉了。

我下來(lái)之后，趙牛扔了D給我。這時(shí)候看了下時(shí)間——才過(guò)了一個(gè)半小時(shí)。比賽的時(shí)候還未
知這是一個(gè)大坑來(lái)著。就這樣，我一直想，一直想，一直想……頭腦各種混亂……

拋開這個(gè)僵尸進(jìn)程不談，我們來(lái)說(shuō)趙牛。

趙牛在閱遍大半版的題目后發(fā)現(xiàn)了第一個(gè)看起來(lái)能做的題目——I。才推了不到一會(huì)，趙牛
很堅(jiān)定的說(shuō)：“我來(lái)敲I ”。I就這樣accepted了。再之后看時(shí)間還有好久，我就直接把一
個(gè)看起來(lái)像是動(dòng)態(tài)規(guī)劃的題目J（不過(guò)有個(gè)序的問題需要證明）扔給了趙牛。他看后沒等我
反應(yīng)，直接上去搶機(jī)器了。不過(guò)很詭異的是，直到趙牛敲完J，還沒人過(guò)這個(gè)所謂的簡(jiǎn)單題
。到趙牛剛要交時(shí)，才發(fā)現(xiàn)第一個(gè)accepted這題的隊(duì)伍。然后，不出所料，J一次提交即返
回Yes。

因?yàn)檫@時(shí)我們隊(duì)伍已經(jīng)8題，領(lǐng)先第二名2題之多。所以剩下的時(shí)間就交給趙牛研究他的F。
雖然趙牛英勇無(wú)比地再次在現(xiàn)場(chǎng)推導(dǎo)出中國(guó)剩余定理的公式，但是難奈BigCowZhang的陰險(xiǎn)
的數(shù)據(jù)使然，趙牛陷入了苦戰(zhàn)。

回頭看db這邊。

db投出的超高速直線球三好一壞不僅起到了穩(wěn)定軍心的作用，同時(shí)我們也確立的巨大的罰
時(shí)上的領(lǐng)先優(yōu)勢(shì)。他下來(lái)之后，我將 H題的題意說(shuō)給他看，并說(shuō)了下大概做法。當(dāng)然，我
相信他也是會(huì)的——畢竟雅加達(dá)那次比賽我們就栽倒在一道差不多的題目上面。在三次TL
E之后，H終于順利返回Yes。3個(gè)小時(shí)之后的第8道題終于accepted。

然后也不知是我們太放松還是如何，我們一直堅(jiān)信G是一個(gè)節(jié)點(diǎn)規(guī)模為100的TSP問題。于是
我便拉db來(lái)跳火坑（D 題）。

期間我們?cè)S久沒出題，甚至郭老師都忍不住送食物過(guò)來(lái)了。

最后半個(gè)小時(shí)，雖然db回過(guò)頭看了下G發(fā)現(xiàn)我們?nèi)x錯(cuò)題了，然則為時(shí)晚矣。趙牛的F也被
完美的卡到死。

至于D題？……（……（……））