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

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

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

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

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

我相信他們在接下來的區(qū)域賽能夠表現(xiàn)得很好。那也是能夠讓學(xué)校矚目的機(jī)會。實(shí)在不行就當(dāng)是次旅行也行吧？據(jù)說最近的賽區(qū)是在武漢。

以上是我們學(xué)校的比賽總結(jié)，下面看看本次冠軍隊(duì)伍的總結(jié)，轉(zhuǎn)自中大論壇逸仙時空：
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ā)信站: 逸仙時空 Yat-Sen Channel (Tue May 11 20:51:23 2010)

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

——ANALYSIS——

按照規(guī)矩，先來說下這次比賽的簡單題解：

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

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

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

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

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

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

F:給出A和B兩個序列，試找出一個最大的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被確定下來，接下來的事情就只是中國剩余定理了
。

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


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

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

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

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

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

——????——

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

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

拋開這個僵尸進(jìn)程不談，我們來說趙牛。

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

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

回頭看db這邊。

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

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

期間我們許久沒出題，甚至郭老師都忍不住送食物過來了。

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

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