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

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

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

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

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

我相信他們在接下來的區域賽能夠表現得很好。那也是能夠讓學校矚目的機會。實在不行就當是次旅行也行吧？據說最近的賽區是在武漢。

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

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

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

——ANALYSIS——

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

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

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

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

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

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

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

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

G:給定一個無向圖G。問經過G中給定的X個點和Y條邊的最小花費是多少。
由于X和Y很?。╔+Y<16），于是一個簡單狀態壓縮動態規劃即可。注：別忘了做預處理。


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

經典自動機。需要注意的是要延遲處理關鍵字個數的統計，總之，是個細節題，要仔細分
析每步的復雜度。

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

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

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

——????——

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

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

拋開這個僵尸進程不談，我們來說趙牛。

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

因為這時我們隊伍已經8題，領先第二名2題之多。所以剩下的時間就交給趙牛研究他的F。
雖然趙牛英勇無比地再次在現場推導出中國剩余定理的公式，但是難奈BigCowZhang的陰險
的數據使然，趙牛陷入了苦戰。

回頭看db這邊。

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

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

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

最后半個小時，雖然db回過頭看了下G發現我們全讀錯題了，然則為時晚矣。趙牛的F也被
完美的卡到死。

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