去年打完ICPC杭州站就想寫退役記了，但一直懶得寫。可以說的實(shí)在是太多了，而且無法按時(shí)間順序敘述，我盡量寫的有條理一些。

〇、雜談

算法競賽吸引我的點(diǎn)在于趣味性、專業(yè)性、公正性。

趣味性：學(xué)會某個(gè)算法后，非常具有成就感。每當(dāng)看到Accepted的那一刻我都會感到無比的喜悅，而這種喜悅我已經(jīng)體驗(yàn)過2000多次了。

專業(yè)性：學(xué)習(xí)內(nèi)容與專業(yè)強(qiáng)相關(guān)，競賽并非應(yīng)試，考察專業(yè)能力，需要重要的編碼能力和算法能力。

公正性：純機(jī)器判題，沒有任何主觀因素，賽場上所有選手處于完全公平公正的競賽環(huán)境，三個(gè)人一臺電腦，完全正確就是Accepted，部分錯(cuò)誤就是Wrong Answer，超時(shí)就算Time Limit Exceeded，超內(nèi)存就算Memory Limit Exceeded，運(yùn)行時(shí)錯(cuò)誤就算Runtime Error。這里就不提大家都知道的三人三機(jī)、獲取并提交逐字符相同代碼、廁所戰(zhàn)神等事件了。我校向來嚴(yán)格要求自己，對作弊行為零容忍，一旦發(fā)現(xiàn)任何作弊，開除出集訓(xùn)隊(duì)無商量余地（親眼見證三例了），同學(xué)互相之間也有監(jiān)督，哪場codeforces/比賽打得不正常，總會有學(xué)長學(xué)姐、教練的眼睛盯著你。

劉春英教練一開始就說，打ACM的結(jié)束了要叫退役，因?yàn)楹蛣e的競賽不一樣，XCPC需要你花的時(shí)間必然是用一年兩年三年來計(jì)算的，而不是幾個(gè)月參加一下。從入坑到退役，我向著ICPC區(qū)域賽獎(jiǎng)牌的目標(biāo)，一刻不停地學(xué)習(xí)。我為之付出的是我大一大二幾乎所有的課余時(shí)間，我不參加任何校內(nèi)的課余活動(dòng)，不參加任何社團(tuán)、學(xué)生工作，不出校玩耍，幾乎不聚餐。高考前都每天想玩一會兒游戲的我，也完全沒有了玩游戲的興趣。每天從早到晚只要有空，就在刷題，特別是大一上學(xué)期，為了快速入門，我每天上課（非重要的課）、下課、午休、晚自修都在刷題，周一到周五一天6小時(shí)起步，周末更是早8到晚10。

我只是想說明我是這樣的，并不是推薦大家都這樣，畢竟人是要休息和社交的，每個(gè)人的精力狀況都不一樣，一天內(nèi)的過度學(xué)習(xí)也會導(dǎo)致第二天的精神不足，大家要選擇適合自己的節(jié)奏。我的兩位隊(duì)友入坑沒有我這么快，也照樣能學(xué)的很好。

我之所以一上來就這么努力地學(xué)習(xí)，是因?yàn)槲夷芸吹阶约汉推渌说牟罹?。我的競爭對手不僅僅有校內(nèi)的幾十位OI省獎(jiǎng)、省隊(duì)、國家隊(duì)的選手，更多的是全國各大高校的強(qiáng)隊(duì)。試想一下，一場區(qū)域賽一兩百所高校，每所高校派出一支甚至多支強(qiáng)隊(duì)，賽場上有幾十個(gè)OI高手隊(duì)，數(shù)百個(gè)努力了1~3年的大學(xué)零基礎(chǔ)隊(duì)伍，ICPC金牌需要rank35，銀牌需要rank105，銅牌需要rank210，能報(bào)名的隊(duì)伍大多都你一樣經(jīng)過大量訓(xùn)練，你怎樣才能打出前排的rank？自我感覺良好的時(shí)候，一上賽場，看到別人遙遙領(lǐng)先的題目數(shù)和罰時(shí)，就能體會到自己和別人的差距。

我自認(rèn)為是很有競技精神的人，心態(tài)良好，不管是打電子競技還是算法競賽，比賽必堅(jiān)持到最后一秒。哪怕我知道你比我強(qiáng)很多，我也要盡全力咬緊比分，就算我們都正常發(fā)揮，我不可能戰(zhàn)勝你，我也絕不允許你有放松和大失誤的機(jī)會。而人不像機(jī)器，經(jīng)常會有失誤，一旦前面的人有一部分發(fā)揮失誤，那么機(jī)會就來到了我的手里。?

在暑假前，我認(rèn)識了我的隊(duì)友并組隊(duì)。老劉說組隊(duì)就像自由戀愛，互相要認(rèn)可對方的水平，比賽需要配合，但是沒有個(gè)人實(shí)力，就不要談配合。我們組隊(duì)前都不認(rèn)識，組隊(duì)后還算比較配合得不錯(cuò)。能夠和一群志同道合的同學(xué)一起向著目標(biāo)努力，簡直就是夢幻一般的幸福生活。

我們隊(duì)伍幾乎沒有過合照，幾乎沒有聚過餐，除了群里討論題目、VP、正式參賽，就沒有一起干過別的事情，除了上面這張退役后特意拍的，其他合照都是OMS監(jiān)考系統(tǒng)賽前認(rèn)證。。。

當(dāng)時(shí)我們討論了隊(duì)名，討論了風(fēng)格，是霸氣風(fēng)格（如“逆十字”、“殺戮降臨”），還是蒟蒻風(fēng)格（如“重生之我是菜狗”），后來選擇叫做”HDUNchar66“

隊(duì)名的解讀：HDU=杭電，Nchar=牛叉，66=玩得溜，char66='B'，Nchar66=NB。并沒有采用三人英文字母組合，是因?yàn)椴恢廊绾谓M合三人的字母。大小寫+數(shù)字整體形態(tài)較和諧。char66帶有專業(yè)性雙關(guān)，且隊(duì)名具有一定的娛樂性，符合比賽的風(fēng)格。

一、入坑過程

2020年9月14日報(bào)道杭電，第一周考進(jìn)計(jì)科實(shí)驗(yàn)班，認(rèn)識了ACM學(xué)長班助以及OI選手SGColin，被他們成功帶入坑。雖然從未參加過任何競賽，也一直都不喜歡競賽，但我剛接觸就對此非常感興趣，便開始快速入門。9月18日還是什么時(shí)候，我成功通過了hdoj的多測A+B（當(dāng)時(shí)還是記事本編輯C語言）。我加入了新生群，認(rèn)識到了校內(nèi)競爭的激烈，在入學(xué)第二周就從早到晚刷題上手。

9月28日，我第一次參加codeforces Div3，AC了兩道題

這是10月1日入學(xué)兩周的刷題量，我深知笨鳥先飛的道理，只有充分利用每一分鐘的時(shí)間，才有可能彌補(bǔ)我和OI基礎(chǔ)同學(xué)的差距。大一第一學(xué)期我沒有早八，我每天早上7點(diǎn)多起床，買了煎餅回來寫題，寫到9：40去上課，11：35或者12：25下課后，買了煎餅回來邊吃邊寫題，寫道1：15去上課，4：00下課了回來些題，吃個(gè)晚飯?jiān)偃ネ碜孕藿淌覍戭}，8：50晚自修下課回寢室繼續(xù)寫題。周末更是有可能早8到晚10。數(shù)學(xué)分析+高等代數(shù)正常聽，水課寫數(shù)學(xué)課作業(yè)，C語言課課上AC掉作業(yè)題邊聽課邊寫題。

國慶假期我學(xué)了背包DP和dfs/bfs，休息了一天。又過了一個(gè)月，下圖是截至11月1日的刷題量

新生ACM選拔賽3題rank28，教練要求4題進(jìn)隊(duì)，我成功落選，但我知道第二輪選拔必能進(jìn)，果然不出所料。下圖為第二次選拔賽，我給這張圖起名為《樹形充電》，我的插線板是圖右下角的根節(jié)點(diǎn)，好在質(zhì)量不錯(cuò)。

看到名單中的50人里有30信奧得獎(jiǎng)?wù)撸腋羌涌炝四_步。經(jīng)過了大一下半學(xué)期的多輪pk/淘汰賽，codeforces分?jǐn)?shù)以及校賽成績，這一屆留下了20多人，我作為零基礎(chǔ)僅剩的8人，成功留在了集訓(xùn)隊(duì)。而暑假集訓(xùn)過后，作為校內(nèi)排名10/14的隊(duì)伍，獲得了參賽資格。

二、學(xué)習(xí)過程

基礎(chǔ)：高中浙江選考技術(shù)，有VB基礎(chǔ)，會冒泡、選擇、插入排序，其他啥也不會。

大一9月：刷C語言基礎(chǔ)題、前綴和/差分、 線性DP

10個(gè)月：背包DP、dfs、bfs、棧、隊(duì)列、二分答案

11個(gè)月：并查集、kruscal最小生成樹、單調(diào)棧、單調(diào)隊(duì)列、歸并排序、floyd最短路、質(zhì)因數(shù)分解、埃拉托斯特尼篩、乘法逆元、快速冪、矩陣快速冪、組合博弈

12個(gè)月：樹狀數(shù)組、鄰接表、堆優(yōu)化dijkstra最短路、線段樹

寒假：LCA、Trie樹、可持久化線段樹、狀態(tài)壓縮DP

第二學(xué)期：01Trie、可持久化01Trie、輕重鏈剖分、擴(kuò)展歐幾里得算法、（擴(kuò)展）中國剩余定理、線性篩、歐拉函數(shù)、樹形DP、區(qū)間DP、二叉堆、ST表、二分圖最大匹配、平衡樹入門(Treap)、生成函數(shù)、差分約束、Tarjan（SCC/EDCC縮點(diǎn)）、2-SAT、高斯消元、KMP、數(shù)位DP、FFT、Dinic最大流、SPFA最短路、Edmond Karp最小費(fèi)用最大流、線性基、AC自動(dòng)機(jī)

暑假：計(jì)算幾何基礎(chǔ)、極角排序、凸包、線段樹優(yōu)化DP、cdq分治（其實(shí)現(xiàn)在都不會）、樹上啟發(fā)式合并、點(diǎn)分治、整除分塊、線段樹合并、splay

第三學(xué)期：樹套樹、旋轉(zhuǎn)卡殼、計(jì)算幾何更多的基礎(chǔ)，仙人掌圓方樹

寒假：后綴數(shù)組、長鏈剖分

第四學(xué)期：LGV引理、狄利克雷卷積、莫比烏斯反演、kruskal重構(gòu)樹、掃描線、笛卡爾樹、線段樹上二分、虛樹DP、（廣義）容斥定理、可持久化并查集、可撤銷并查集、字符串哈希、kruskal重構(gòu)樹

暑假-第五學(xué)期：后綴自動(dòng)機(jī)、manacher、回文自動(dòng)機(jī)、線段樹分裂、link-cut-tree、杜教篩、min25篩、矩陣樹定理、數(shù)學(xué)/計(jì)算幾何/博弈/數(shù)據(jù)結(jié)構(gòu)/圖論更多內(nèi)容

我整理了一份184頁7800行l(wèi)atex源碼的算法模板，總結(jié)了我們隊(duì)的所有科技，當(dāng)然這也只是表面的東西，真正重要的是我們大量訓(xùn)練后掌握的靈活的解題思路，算法模板只是偶爾需要抄一下的東西。

我的刷題量：codeforces、hdoj大量專題訓(xùn)練和杭電多校比賽沒有計(jì)入賬號、牛客41場比賽大多沒有記入賬號，還有PTA的很多題，總計(jì)大約2000題，現(xiàn)在看起來大部分是簡單題，但做的過程中，對當(dāng)時(shí)的我來說都是很有難度的。

做過的最難的幾個(gè)題（部分）：

1、洛谷P6292 區(qū)間本質(zhì)不同子串個(gè)數(shù) https://www.luogu.com.cn/problem/P6292?

詢問離線后link-cut-tree在SAM的parent tree上access，用線段樹更新、查詢區(qū)間貢獻(xiàn)

2、codeforces?487E tourists：?https://codeforces.com/problemset/problem/487/E

無向圖點(diǎn)雙連通分量縮點(diǎn)，建廣義圓方樹，multiset維護(hù)方點(diǎn)最值，樹剖線段樹維護(hù)/查詢鏈上最值，

3、#572. 「LibreOJ Round #11」Misaka Network 與求和 ： https://loj.ac/p/572?

莫比烏斯反演后整除分塊HashTable記憶化杜教篩套min25篩

在此還要特別感謝劉春英教練、SGColin、ZigZagK、Comld、DDosvoid，以及所有幫助過我的同學(xué)，沒有他們的幫助，我也很難有那么高的學(xué)習(xí)效率。我還沒寫過博客，因?yàn)橐环矫嬗X得不需要整理，記在腦子里才有意義，另一方面也沒時(shí)間和心情寫。有幾位同學(xué)的博客內(nèi)容非常豐富，在此附上他們的博客鏈接。

SGColin：http://blog.gyx.me/

ZigZagK：https://zigzagk.top/

Comld：https://www.cnblogs.com/ZH-comld/

DDoisvoid：https://ddosvoid.github.io/

三、參加過的訓(xùn)練賽和非XCPC比賽

codeorces round 116場，大一幾乎全勤，晚上22：3500：35是熟悉的時(shí)間，codeforces virtual participation三四十場各地區(qū)域賽，參加其他學(xué)校校賽若干

校內(nèi)比賽：自動(dòng)化學(xué)院新生賽（入學(xué)兩個(gè)月學(xué)了矩陣快速冪后剛好考到，喜題一等獎(jiǎng)）、校新生賽（三等獎(jiǎng)）、計(jì)算機(jī)學(xué)院debug杯、兩次校賽

多校集訓(xùn)：兩年各10場?？投嘈！?0場杭電多校，杭電多校在暑假的每周二、四，?？投嘈Ｔ谑罴俚拿恐芤?、六，兩個(gè)暑假實(shí)際放假時(shí)間大約一星期。大一暑假后，我們隊(duì)的校內(nèi)排名是10/14，大二暑假后，我們隊(duì)的校內(nèi)排名是4/14

團(tuán)體程序設(shè)計(jì)天梯賽：大一250，大二220，大三237（總分相等難度不等，大三打的最好），本想最后一戰(zhàn)搶下先鋒，賽前一周板刷了100多道天梯賽的題，賽場上前半段確實(shí)發(fā)揮的很好，20分鐘AK了L1，1小時(shí)AK了L1和L2，可惜L2沒有搶到一血，而L3又卡太久了。

藍(lán)橋杯C++軟件類大學(xué)A組：大一省一（國賽和校賽沖突，放棄參加國賽），大二國二，實(shí)力確實(shí)差點(diǎn)，現(xiàn)在看來的簡單題當(dāng)時(shí)都不會，國賽還是很難打的。

CCF CSP等級認(rèn)證：500分，杭電剛設(shè)立考場，我參加了第一場就AK了，運(yùn)氣真好，壓軸題考點(diǎn)恰好和我一周前訓(xùn)練過的HDOJ 6967（I love data structure，2021杭電多校集訓(xùn)）一樣，線段樹維護(hù)線性變換矩陣乘法tag先乘后加，花了一個(gè)多小時(shí)成功秒掉。

某個(gè)國家級的比賽：和室友一起參加的夏季賽，當(dāng)時(shí)確實(shí)實(shí)力不夠，樹上SAM板題不會做，又不搜題，差一題，喜提銀獎(jiǎng)。畢竟參賽的大部分人在群里討論、搜題、換題，反正沒有人管，div1E tourist大神都沒有做出來的困難網(wǎng)絡(luò)流原題被500多人AC了。

2023杭州師范大學(xué)校賽：這是我唯一參加過的線下賽，也是我們的省賽選拔，我們隊(duì)三線卡題，成功排名校內(nèi)倒數(shù)第一，正好也想退役了。我拍了一些視頻，但是一直沒空剪輯。

我們負(fù)責(zé)了2023年的校新生賽和計(jì)算機(jī)院賽的出題，我接下來估計(jì)會為今年的杭電多校集訓(xùn)貢獻(xiàn)兩道（不夠難的）題。

四、參加過的XCPC正式賽

2021年CCPC威海站銅獎(jiǎng)：

大二第一次參賽，感覺差距非常大，好在簽到成功簽上，KMP成功簽上，驚險(xiǎn)地拿下銅獎(jiǎng)。

2021年ICPC澳門站銅獎(jiǎng)：大二下學(xué)期教練又給了我們一次機(jī)會，可惜極角排序精度炸了（使用了atan2沒用整數(shù)向量叉積）、FFT精度也炸了（沒有預(yù)處理單位根，或者沒有改用大模數(shù)NTT），兩題卡死?？梢哉f是學(xué)得不夠精，網(wǎng)上找學(xué)習(xí)資源需謹(jǐn)慎，遺憾獲得銅獎(jiǎng)。

2022年浙江省大學(xué)程序設(shè)計(jì)競賽金獎(jiǎng)：成功簽到6題后，兩個(gè)金牌題主席樹+計(jì)算幾和構(gòu)造，我各寫出一個(gè)驚天bug，好在隊(duì)友一人幫忙debug出一個(gè)，最后半小時(shí)AC兩題驚險(xiǎn)拿下金獎(jiǎng)

2022年CCPC威海站銀獎(jiǎng)：

前期找規(guī)律題卡太久，罰時(shí)過高，時(shí)間也不夠，最后一題差一口氣，但就算AC也是銀，感覺CCPC太難啦

2022年ICPC西安站金獎(jiǎng)：

輪流上機(jī)切簽到題，一小時(shí)一發(fā)AC了6個(gè)題，再花3小時(shí)通過2個(gè)題，罰坐一小時(shí)后喜題金獎(jiǎng)。特產(chǎn)很香！

2022年ICPC杭州站銀獎(jiǎng)

簽到過的穩(wěn)健，可惜中檔題卡了兩道，考到了我們都不會的東西，喜題銀獎(jiǎng)。知味餅禮真的很好吃！

五、經(jīng)驗(yàn)分享

1、保持良好的健康狀態(tài)，才能有力氣高強(qiáng)度學(xué)習(xí)。保持陽間作息，多運(yùn)動(dòng)。

2、多刷題，刷題量是最能代表水平的。感覺沒有提升？一定是沒好好刷題。不知道怎么快速上手？先刷50題吧。學(xué)了感覺不會用？再刷到到感覺會了為止。建議一開始廣泛學(xué)基礎(chǔ)算法，有一定基礎(chǔ)后可以繼續(xù)深入。當(dāng)然一直刷簡單題沒有任何幫助，必須不斷地AC自己原先不會做的題。

3、參加各種訓(xùn)練賽，可以挑選喜歡的參加，例如codeforces、atcoder、牛客訓(xùn)練賽、洛谷訓(xùn)練賽、各大高校校賽等。通常來說正式ACM訓(xùn)練賽的考點(diǎn)較廣，質(zhì)量高，能幫你找到盲區(qū)。賽后一定要補(bǔ)題，哪怕補(bǔ)一題或者只看個(gè)思路，不補(bǔ)題就沒收獲，等于沒參加，浪費(fèi)時(shí)間。

4、建立抽象思考能力，學(xué)習(xí)某個(gè)新的算法時(shí)，通常需要舉個(gè)具體的例子，但是你需要從例子中獲得算法的抽象思維，即對于任意的情況，該算法均能處理。算法可視化也是很有助于理解的，可以看一下網(wǎng)上的視頻，但也不能依賴于別人做得很好的可視化，你可以嘗試在腦子里“可視化”。例如：考慮使用線段樹時(shí)，我的眼前仿佛出現(xiàn)了一棵線段樹，需要處理更新操作的時(shí)候，眼前的這顆線段樹從根節(jié)點(diǎn)向下的兩條鏈不斷地在變?yōu)楦吡?；考慮到拓?fù)渑判驎r(shí)，我的眼前仿佛出現(xiàn)了一個(gè)具有一般性的DAG，且眼前的這張DAG正在進(jìn)行拓?fù)渑判颍Y(jié)點(diǎn)上的數(shù)據(jù)正在從一個(gè)傳向另一個(gè)；考慮使用splay樹時(shí)，眼前的一棵二叉平衡樹正在把一個(gè)結(jié)點(diǎn)伸展到根。

5、掌握算法的通用性。學(xué)習(xí)一個(gè)算法并做了一個(gè)題時(shí)，你學(xué)會了用算法解決這個(gè)問題，刷了5個(gè)或者10個(gè)題后，你應(yīng)該學(xué)會的是對于相似的問題，可以考慮用這個(gè)方法解決，而非僅僅用該算法解決這5個(gè)題。講一個(gè)反面教材，我的一個(gè)室友思考問題的方式是這樣的：“這題能不能用LCA解決？這題能不能用拓?fù)渑判蚪鉀Q？這題能不能用最短路解決？”這是非常錯(cuò)誤的思考方式，對于一個(gè)特定的問題，你如果不能直接聯(lián)想到一些可能有關(guān)的算法，那就說明你并沒有真正掌握這些算法。

6、鍛煉自學(xué)能力，打ACM幾乎完全靠自學(xué)，網(wǎng)上資源很豐富，題解、博客等優(yōu)質(zhì)學(xué)習(xí)資料應(yīng)有盡有，足夠?qū)W習(xí)的。

7、算法競賽需要你對算法有足夠的興趣。別人學(xué)習(xí)ACM是吃苦，我學(xué)習(xí)ACM是享受，別人學(xué)完需要玩游戲，我學(xué)習(xí)就是玩游戲。學(xué)弟跟我說“學(xué)ACM痛并快樂著”，我覺得是這樣子。一開始確實(shí)學(xué)的比較吃力，但有一定成效后，你就會覺得這些付出都是非常值得的，而且訓(xùn)練到后面，參加訓(xùn)練賽/正式賽，就像是打了一把游戲，非常有娛樂的感覺。