Astar隊(duì)成立已經(jīng)一個(gè)多月了，還記得我們集體參加的第一場(chǎng)比賽是8.8號(hào)南航的官方練習(xí)賽，由于正值暑假期間，各大OJ都沒有正式的比賽，所以這個(gè)比賽吸引了眾多的大牛參加。我認(rèn)為這次比賽對(duì)于我們隊(duì)的意義倒不是比賽的結(jié)果，而是通過這場(chǎng)比賽我們有了初步的磨合，隊(duì)員與隊(duì)員之間開始達(dá)成默契。最后通過幾個(gè)小時(shí)的努力，我們AC了6題，排名大概在15左右。這是我們隊(duì)參加的第一次正式比賽^_^。
當(dāng)時(shí)是計(jì)劃暑假至少參加兩次練習(xí)比賽的，第二次的比賽本來想選擇天大，后來聽說8.23號(hào)有北大的月賽，于是便堅(jiān)定地再戰(zhàn)POJ了.比賽前我們分好了題，開始的時(shí)候先各自看了一會(huì)題，我時(shí)不時(shí)盯一下board,比賽開始不久我發(fā)現(xiàn)A題已經(jīng)有人過了，于是大家一起商量了下，決定dfs暴力這道題，并且由沸騰來寫這個(gè)題，其它人看別的題，過了沒多久，A題AC了。我們開的第二道題是一道概率題，求安全通過不踩到雷的概率，我初步分析了下，這道題可以轉(zhuǎn)化成一個(gè)遞推數(shù)列的問題，我直接敲了一個(gè)遞歸的算法，交上去，TLE了，于是不得不考慮其他的算法。其實(shí)這道題可以用差分方程直接算出來，這樣可以跳過中間的遞推，大家商量后，由張俊華推公式，開始Wa了1，2次，最終AC了，由于有公式，代碼非常短。這道題也提醒了我差分方程的重要性，尤其在對(duì)數(shù)列方面的題上。最終我們隊(duì)AC了兩題，大致排在前100位左右，比賽完后很以外的看到了“another crazy man"隊(duì) ，神奇的是，和我們隊(duì)貼在一起了 呵呵。
再來看網(wǎng)絡(luò)賽的情況，第一場(chǎng)合肥網(wǎng)絡(luò)賽。題目比較“友好”，和平時(shí)做的題目，銜接度比較大，但是也有所創(chuàng)新，我覺得說它完全是陳題是不恰當(dāng)?shù)摹７趾妙}之后，大家各自開始看題，我首先看到了上升子序列那道題，和阿義商量了一下，很熟悉，不過暫時(shí)沒有想法，所以直接跳過看別的題，于是看到了那道計(jì)算幾何，由于暑假在家里做了計(jì)算幾何的專題，這樣的題目做了很多，主要是叉積的運(yùn)用，不過由于早已總結(jié)出模板，直接套用模板，處理了一下輸入輸出就過了。等過了第一題，貌似開始覺得有希望的題已經(jīng)被別的隊(duì)做出來了，只好開始看另外的題。這時(shí)候注意到了已經(jīng)有很多人過的A題，壓力比較大，剛開始的時(shí)候大家都沒有什么想法，后來我想到了背包問題，大家一起討論，阿義突然說他有想法，貌似是他見過的一道題，航電上面的，當(dāng)時(shí)聽到很多隊(duì)說它們用N^3的算法超時(shí)了，阿義說他用的是N^2的算法，敲好了之后處理了一下模除，順利AC.這時(shí)剩下的只有兩道同構(gòu)的題目還有一道通過率為0的題目，由于同構(gòu)的題目以前從來沒有接觸，圖的同構(gòu)更是NP問題，幾乎沒有什么想法，只能上網(wǎng)搜索資料，后來聽說竇煜峰組過了，問了一下，原來用充分條件巧妙地AC了那道題，思路并不復(fù)雜，數(shù)據(jù)比較弱而已。這次比賽給我們的啟示主要出自同構(gòu)的那兩道題，其實(shí)有的時(shí)候并不需要使用標(biāo)準(zhǔn)算法，比賽亦有技巧可用的。像圖的同構(gòu)本為NP問題，既然標(biāo)程都不可能使用絕對(duì)正確的算法，那么這題肯定可以使用做題技巧來解的。
接下來，第二場(chǎng)網(wǎng)絡(luò)賽，剛開始的時(shí)候非常郁悶，網(wǎng)絡(luò)不是很好，等真正拿到題目開始做題，幾乎半個(gè)小時(shí)過去了，然后看到了那道通過率比較高的hello,world,看到題目我的第一反應(yīng)是匯編，不過顯然不可能，后來看到每一行代表一個(gè)字符，每一行有5個(gè)16進(jìn)制數(shù)，而每一個(gè)字符由5個(gè)豎行表示，應(yīng)該是一個(gè)16進(jìn)制數(shù)代表一列的信息，數(shù)進(jìn)制轉(zhuǎn)換無疑。不過正準(zhǔn)備敲的時(shí)候，有同學(xué)發(fā)消息說這題已經(jīng)過了，于是只好放棄看其他的題目。之后的1個(gè)小時(shí)，大家在看題，互通每道題目的意思，前兩個(gè)小時(shí)大致弄明白了沒道題目的意思，這一點(diǎn)我們做得很好。沸騰說題目難的話就做一道模擬題，于是他著手做了A題，我和阿義兩個(gè)人同時(shí)寫一道點(diǎn)線關(guān)系的題目。
關(guān)于那道計(jì)算幾何題，我們使用的是掃描+hash，可惜一直TLE，優(yōu)化了很多次，還是TLE，直到比賽結(jié)束。賽后問了下中山大學(xué)的ACMer，它們用的也是hash判重的方法，過了，不過為什么我們的一直TLE？至于沸騰的那道題，應(yīng)該是很有希望過的，不過由于時(shí)間原因，最后沒有寫完，略微有些遺憾。
哈爾濱網(wǎng)絡(luò)賽，寫總結(jié)之前，忽然聽說了現(xiàn)場(chǎng)賽要推遲的消息，原因是為了控制流感疫情，哈爾濱的幾所大學(xué)要采取應(yīng)急措施，取消近期一切室內(nèi)活動(dòng)。不知道比賽究竟會(huì)被推到哪天進(jìn)行。。。BTW，比賽開始以后，還是按照慣例，先分好題，阿義看的是后面，發(fā)現(xiàn)很快就有人AC了J題，我們想會(huì)不會(huì)是一個(gè)模擬題呢？于是我首先去模擬這個(gè)題，用了數(shù)組模擬然后優(yōu)化，可惜TLE了，后來聯(lián)想到樹，不過好像已經(jīng)被其他組過掉了，只好放棄，做別的題目。等大家把題目都看的差不多了，我們開了一道數(shù)列的題，我們很直觀的想到了差分方程求解數(shù)列的通項(xiàng)公式，然后再求位數(shù)。張俊華負(fù)責(zé)推出公式，可是后來我發(fā)現(xiàn)發(fā)現(xiàn)這個(gè)想法無法實(shí)現(xiàn)，因?yàn)橛?jì)算中會(huì)出現(xiàn)小數(shù)，大數(shù)模板沒法處理小數(shù)。。。一時(shí)陷入了僵局。最終我們決定放棄這道題，不過時(shí)間已經(jīng)所剩無多。賽后有人說這道題可以用模擬科學(xué)計(jì)算器的方法來做，這才恍然大悟。這次網(wǎng)絡(luò)賽對(duì)大家的啟示在于對(duì)題目的靈活轉(zhuǎn)換上面，有的問題并不是你不能，而是你沒有意識(shí)到。 愛因斯坦說的對(duì)，想象力比知識(shí)更重要。
總結(jié)就到這里，所說的一切只屬于過去，我相信，我們還會(huì)繼續(xù)不斷地向前走，不斷地超越自我，我們的集訓(xùn)隊(duì)也會(huì)變得更加強(qiáng)大。