記2020年(第16屆)湖南ACM省賽

記2020年(第16屆)湖南ACM省賽

寫在前面

我很喜歡《龍族》裡那個叫路明非的衰小孩。雖然我也不知道為什麼要說這個，逃

這個世界有多大，取決於你認識的人，你每認識一個人，世界對你來說就會變大一些

——路明非

熱身賽

今年藍橋杯和熱身賽衝突了，搞完藍橋杯都1點了，急忙趕去長理簽到一下~哈哈

外市的參加完藍橋杯就不太方便過來，就現得熱身賽異常冷清了，沒多少隊伍。

開啟題目一看，好傢伙。是去年省賽的原題。

cjm：我不想寫了

我：？？（原來大佬都是這樣子的）

lb：？？（大佬啊）

我看到簽到題A就想到上次wa了無數發的場景（簽到題wa那真的…）…就直接上手過了（洗涮屈辱並沒有什麼用）

cjm就盯上了K（伸展樹題）然後就掏出了板子。伸展樹幾乎所有操作，幾頁的程式碼…全給打了上去。

打完才想怎麼用伸展樹解題。我看時間不多，我記得list就可以過，幾番折騰（WA了幾發）用list過了

然後就差不多到時間了。

出了機房cjm突然想出來解法…本來時間多點能一展身手的

然後（奢侈地）打的回府

正式賽

這回是校車接送···（專車->打的->校車 出行的逼格漸漸降低）哈哈

一波等待後就發題目了，沒辦法，只有一份紙質答案（難受啊），直接拆開。老規矩前中後，每人一部分。

一開始的密碼好像有點問題，一直上號不成功…長理臨時列印的正確密碼

lb看了一下A，發現是簽到題。

跟我講了一下意思，這第一題那是士氣題啊！一頓操作，一發過。

三人相視一笑，可以可以~

看了看榜，還挺前面的~

lb發現B也是水題，看似很複雜其實只需要巧妙地簡單判斷一下…

隨便搞搞，還是一發過。

又康了康榜~已經金牌區了，瞬間三人激動起來!!!

然後我們就決定跟榜了，更穩一些，發現有人過G，馬上轉戰G題。

cjm看了G題，然後就一起討論思路，還好，沒多大阻礙，一番亂打，順利通過~

太順利了，沒有太大的阻礙，嘿嘿（那時候確實有點小飄）lb~yyds

老規矩，開心地開啟榜單，看看待在金牌區的我們…

I過得挺多，lb正好看了題。跟我和cjm解釋題意。

趕緊一頓分析，許久，應該是判斷點在兩條直線夾角內，不過具體不太好處理。

然後準備先敲再說…剛打輸入，發現不太對，再仔細一看。wc，發現題意理解錯了。直線都是水平的…

然後趕緊回爐重造，算簡單計算幾何吧，cjm推了一下公式，直接通過！cjm~yyds

lb又掏出了D，跟我們講感覺是週期的字串才符合。

三人討論了一會，感覺是最小回圈節，cjm馬上說可以用kmp求~

快快快！直接操作~

cjm噠噠噠，提交一點，一發入魂~

然後我看H過的也不少，我一看，矩形面積並，不就是掃描線演演算法嗎？

不管了，直接操作再說

鍵來！

直接打上輸入，發現有點不太對…

再仔細一看發現理解錯了

兩次沒看清題意了

還是要推公式~

我畫了一通~推出公式。畫得太醜了，字寫得也不太好看，cjm在看我的圖的時候。我感覺沒啥問題就直接寫了。

莽了一發~然後…WA了，第一發WA。我仔細想了想，應該思路沒錯。

cjm突然發現我有一種情況沒有考慮進去~

確實有點衝動了，哈哈哈哈

然後又看了看榜，發現我們還是在金牌區的，不過還有兩個小時多點結束，其他隊也會過題，要拿金感覺還是需要再過一題

這個時候午餐來了（麵包+牛奶+香蕉）不過都沒什麼心思吃

看了看通過人數，只有C可以搞了。

初略一看，沒什麼思路，暴力求解肯定超時。

只能在至少模擬樣例，沒看出什麼~~然後又看變化情況，好像有跡可循。

但又不太清晰，只能在紙上各種亂搞，草稿紙都不夠用了，要了一次草稿紙，紙質題面都用來寫了（衰~~）

很久很久，我好像發現變化規律（也不知道是不是對的）…

跟隊友討論

我：先這樣，再那樣，然後這樣，最後再這樣，應該也許可能大概沒錯

cjm：？？

lb：？？

然後又是一頓畫圖

我：阿巴阿巴~

cjm：阿巴阿巴

lb：？？

這個時候已經封榜了，我們發現我們掉到金尾，這不過肯定就沒得了啊

一直在金牌區，可不能最後掉鏈子啊

我只能硬著頭皮先寫

一波操作，TLE

左看右看，時間複雜度上不太可能超時，那應該只可能是memset了

改成迴圈清空，WA~

改一下遞迴情況，WA~

再修改變化情況，還是WA~

WA得心態有點爆炸了。

時間不多了，還有幾十分鐘，沒什麼辦法了，搏一搏，單車變摩托！

然後一頓亂改，什麼陣列開大，取模的時候先加模，看起來不太舒服的都一頓猛改~

一點提交，我都準備提東西滾粗了（本來三人都沒抱什麼希望）

不知道是不是錯覺，感覺判題都變慢了。

》》》》》》》》》》》》》》》》然後螢幕上單詞突然跳了一下Accepted~

我：臥槽

cjm：臥槽，臥槽

lb：臥槽，臥槽，臥槽

感覺就差跳起來了！

然後就是比較舒服的收東西環節，記得封榜也會送氣球的來著，我們還想等送最後一個氣球過來過過癮…

然而並沒有…那隻能先溜了

…

頒獎環節

兩點結束比賽，4點半頒獎（不得不吐槽一下，這真的煎熬，太久了！！！！！）

然後我們各種分析，排名獲獎概率多大多大~，然後偉帥說中南有隊過了題…（好的，名次-1）

6題再過一題能超過我們的也少，畢竟前面的題目罰時還是可以的，

就是看少數幾個A的快的6題隊能否再過第七題了，連過兩題…那應該可能大概沒有了把（別吧，那真的…枯了）

然後叫隊伍派代表等待，竟然先頒三等獎…這個懸念就很致命啊

三等獎還好，肯定不會有我們…

報二等獎的時候那真的是，湖南…（心頭一緊）…XXX大學（送了一口氣，還好不是我們），湖南…（心頭再緊）…

一頓過山車後，誒，沒有！！！！

穩了穩了，哈哈哈

最後~（金尾…倒數第二 >> 銀首終究是銀，金尾終究是金啊）

經驗之談

付出和所得終將在某個點到達平衡！ —— 佚名

如果覺得自己的付出沒有獲得等價的回報，那只是說明你的付出不夠多，並沒有到達那個平衡點（亂說的）

對於初學者：沒有一個比賽是簡單的，ACM更是如此。ACM之所以有比其他學科競賽更高的含金量，是因為需要更多的付出，每一次WA都是給一次找出自己問題的機會，誰不是在一個個WA和TLE中走來的呢（萬事開頭難…是不是像極了初學C語言的時候）

對於刷題數：這個並不是說刷得多就一定更厲害，當然這隻代表一方面…其實我只是想說不用太執著於自己一共刷了多少題，一直學就是了~（有時候進步並不能馬上看到，所以也不用糾結於自己寫了一天的題目有沒有提高…）

對於刷題：比較推薦codeforces。首先是英文題，其次，題目程式碼都偏短，考察的更多的是思維，而且還有題目難度評級，可以挑合適自己的題目寫。唯一美中不足的就是比賽都很晚（實在不行克隆下來寫嘛），或者單刷題。

對於題目選擇：不要一直寫簡單題（就是一看就馬上出思路的），這並沒有太多的意義（除了能夠碼得快點之外），碰到不會的演演算法，那就學唄~

對於看演演算法書：這…個人感覺不如看部落格來的快，單看書容易睡著，也容易勸退，最經典的莫過於劉汝佳的白書/紫書了…雖然不錯，但是很多題還是太勸退，不是天賦異稟不太推薦。寫題就是了，開局一條狗，裝備全靠撿

對於比賽：一般都是團隊的努力，當然獨自carry…也不得不服（想想那些亂殺的中學生），考慮陣容嘛，三個肉一般打不過輸出+控制+前排…所以隊友也比較重要

以上僅為個人的片面看法和cjm/lb大佬無關~哈哈哈

cjm大佬登場：

字串那道題最具戲劇性。當時我們推出一個結論：把所有字串的最小週期串求出來，然後放在map裡累加求和。我對週期字串特別敏感，立馬想到KMP，敲出KMP演演算法~~（板子）~~，一發入魂。可能因為這個，讓我們在第5名穩定了近一個小時。

計算幾何那道題最考驗配合。當時h神敲程式碼，然後我推直線方程，我推完之後就看著h神寫程式碼，幫他糾正bug。最後我還指出了h神幾個沒有考慮的地方。當時要交的時候h神還向我反覆確認（我也不敢確定有沒有問題），提交之後立馬A。

矩陣求交那道題最考驗心態。h神推出公式直接交了一發，WA了~~（心態有點崩了）~~。我用我自己的思路推了一下公式，發現需要求整數平方和，但是h神說他那樣做沒有問題，我也沒想太多，就直接去理解他的思路了，儘管當時有點蒙，但是隱隱約約能感覺到哪裡不對------突然發現如果範圍沒超過矩陣可能會出錯（h神構造了一組資料，發現真是這麼回事）。處理之後直接A了，不過WA了一發還有有點惋惜。

C題（收官之題）最考驗運氣。h神想出了一個遞迴解法，就直接上手了。由於直接memset，T了一發。改掉memset之後，又wa了（心態幾乎炸裂）。零零散散各種改，又wa了兩發。最後，比賽只剩10分鐘，希望很渺茫了，h神一通亂改，交了一發，莫名其妙地就A了。。。我們直接從椅子上跳了起來（金有希望了）。

總之，比賽既考驗知識儲備，又考驗配合，還考驗運氣（也就是天時地利人和）。所以，首先把自己磨練好，然後一切都交給天意吧。。。

lb大佬登場：

緊緊抱住隊友的大腿，做一個合格的划水怪

ACM很難，但堅持定會讓你收穫不一樣的驚喜，可能它相較於應用開發成就感並沒有那麼強，甚至是經常自閉（打ACM自閉難道不是常事？），但那AC的快感是隻有在ACM賽場上才能感受到的獨有刺激（貌似wa or tle更是家常便飯）

日常刷題請務必靜下心來，獨立思考和敢於嘗試，切勿沒思路立馬看題解，這樣思維永遠也提升不了（當然如果幾天啃一道題那也大可不必）；真正地理解自學or請教學長老師的演演算法，日常儘量不依賴於模板，h神一些常用演演算法基本上都是信手拈來；刷題同時水水比賽可以去牛客（https://ac.nowcoder.com/acm/contest/vip-index） or CF（https://codeforces.com/contests）打打比賽，提升做題速度和能力（當然更重要的是補題，補題不必全部都補，但是比賽中看了的題，覺得自己可以過的一定得補）。

很喜歡這樣一句話：如果不累，那你的夢想豈不是很廉價？（熬了波好雞湯）。弱雞被h神強拉過來寫總結，必須得附上h神領獎的圖和得知我們省一穩了的圖。

hyh yyds

(左3 h神)

最後

無論如何~~願大家都有遠大的前程ヽ(✿ﾟ▽ﾟ)ノヽ(✿ﾟ▽ﾟ)ノ

哇，作業還沒寫！！！！