CQOI2021游自家學校記

”我們趨行在人生這個亙古的旅途，在坎坷中奔跑，在挫折里涅槃，憂愁纏滿全身，痛苦飄灑一地，我們累，卻無從止歇；我們苦，卻無法回避，“

2020noip 得知成績那天

那是個周四體育課之前的課間

dmy跑過來說：“楊姐楊姐，noip成績出了你知道嗎，我T1掛成了60哎呀，都是那個先乘后除，”

完了，我就是先乘后除，掛成60？完了完了完了完了這波不會是要退役了吧

于是翹了體育課，去機房，給教練打電話

潘老師說了一堆東西，說每道題都有掛分，說關于我的對手，說關于要不要退役，

確實，我聯賽分數 181 ，估分 250 ，掛了70，

潘老師：“第一是南開的女生比你高14分，第二是育才的比你高9分…”

“你的目標從來都不是女隊，你要進B類，”

沒說話，迷茫，絕望…

回寢室給媽媽打了電話，淚水逐漸模糊眼眶，

我后來知道了，這種時候不要給媽媽打電話，越說越委屈根本繃不住，

“整理好心情，重新出發，”

2021.4.3 周六 清明節

離省選還有一周，育才中學的選手來西附交流感情，順便一起考了兩天，

他們來的前一天晚上我才知道這件事情，育才也有一個女選叫cyj，

我挺無語的，重慶市真的已經夠卷了，

到省選這個階段就這幾個學校卷卷了，今年女隊就前面幾個女選爭一個名額，

就無語啊就無語，一定要爭個第一出來，明明都是志同道合的人，

育才來的第一天，刻意沒有那個姐妹說話，畢竟目前是競爭對手，

然而她卻很熱情主動，上來跟我搭話，是個很自來熟很開朗的女生，

好吧，其實還是可以做朋友的，

和育才一起的模擬賽兩天加起來 rank2，還行，沒怎么掛分，

“遺憾是自己給自己留的，你不想，”

省選就在我們學校，

考前一天沒給寢室的同學說明天我要省選，因為她們給我加油我會更緊張，

考前一天晚上凌晨的時候還是看到 yyq 學長發來的加油，

開心，一夜好夢，

DAY1

破天荒起了個大早，到食堂吃早飯，

碰到了 hd 和 dmy ，

我：“我好慌啊啊啊，好慌啊，嗚嗚嗚嗚嗚嗚嗚嗚嗚嗚嗚嗚，好緊張咋辦啊嗚嗚嗚，”

hd：”你慌啥…”

dmy：“附議…”

行吧，

8:30 開考

看 T1，呃呃呃？？？

啥啊，簽到題，

直接雙指標掃兩遍就線性做了啊，為啥資料只有 1e6 ？

不太理解，害怕自己想假了就又看了好幾遍題面，

淦，真是簽到題，不管了，先寫了再拍上，寫完T1有 100 100 100 分就不怎么慌了，

9:20了

開 T2，

emmm，沒啥思路，看上去是個構造，

不會吧，不會真是構造吧，我對這玩意過敏啊，

giao giao giao心想我要是jly就好了，直接就秒了，

突然，

天黑了（bushi

我去！停電了！我去！我去！

活久見，四年OI考試一次都沒有見過停電的，

不是吧不是吧，西附好不容易承辦省選，別關鍵時刻掉鏈子吧，

我抬頭望了望 wx 老師，他也一臉懵，

不管了再想想T2，

這個限制有點像差分啊，這個資料范圍又有點迷，

呃呃呃，

來電了，

有自知之明的小楊知道自己是想不出正解的了，于是開始扣部分分，

n , m ≤ 3 n,m\le 3 n,m≤3 先把四個角的填上盡量大，然后再貪心往中間填， 20 20 20 分直接貪心應該沒啥問題，

m = 2 m=2 m=2 意思是就只有一列的限制，如果我定了最后一個數的多少那么總的方案就出來的，然后對于最后一個數只有 n ? 1 n-1 n?1 個限制，還是充要條件，掃一邊然后找出一個合法的就行了，另外 30 30 30 分到手，

0 ≤ b i , j ≤ 1 0\le b_{i,j}\le1 0≤bi,j?≤1 這個意思是每四個方框最多有一個為 1 ，然后稍微構造一下就能找到合法解，很有道理的樣子，又 25 25 25 分搞定，

拼拼湊湊 75 75 75 分了，部分分就拿完了，

看了看了這題多測要注意清空，嗯清了的，

11:30了

開 T3！

額，T3 肯定不會簡單吧，

給你一張有向圖，求你每洗掉前 i i i 條邊后，多少對點可以互相到達，且不能經過比這兩個點編號都小的點，

額額額，好蠢的限制，

就是求每一個點不經過編號比它小的點和前 i i i 條編號的邊，能到達且能回傳的點的數量，

如果暴力的話，能到哪些點好解決，

能回傳的點就可以將每條邊反向再建一個新圖，就能知道哪些點是到了之后能回傳來的，

考慮 dp ， d i s 1 [ i ] [ j ] dis1[i][j] dis1[i][j] 表示正常建圖，從 i i i 出發不經過編號 < i <i <i 的點走到 j j j 路徑上最小編號的邊最大編號是多少， d i s 2 [ i ] [ j ] dis2[i][j] dis2[i][j] 就是反向建圖的 dp 值，

然后跑 n n n 遍 spfa，對每一對點算貢獻，時間復雜度 O ( n m ) O(nm) O(nm) ，

看了看資料范圍，這個復雜度 80 80 80 分很穩，

12:40

不放心T3，寫了個 O ( n 2 m ) O(n^2m) O(n2m) 的暴力拍上了，

T1也不太放心，那就多拍一會兒，

這滑鼠怎么突然不靈了呢？

咦？

咦？

咦？

淦，對拍把電腦拍死機了，我淦，

于是叫來老師，（來的是我的教練和副教練，

老師剛走過來電腦就好了，

突然就不死機了，

于是他倆一臉看豬的表情看我…

13:30

考試結束，

估分 100+75+80=255

出考場，和隊友交流了一下，發現這個分還不低，發揮的還不錯，

整個下午都在劃水，

不敢相信自己能考這么好，按以往的經驗，考這么好一定也同時會掛很多分，

慌，

對，有種會掛分的預感，

（事實證明女人的第六感真的準

看了一下午的日常，晚上吃飯也沒什么胃口，

晚自習

我關系最好的一個一中的oier朋友，day1似乎跪了，

晚上和他聊qq，他好死不活去洛谷測了民間資料，發現真跪了…

淦，心疼他，

于是我也開始害怕，

細想今天哪里會不會掛分，

多測清空了嗎，嗯清了，我在輸入的時候順便清了，

嗯，輸入的矩陣是 ( n ? 1 ) × ( m ? 1 ) (n-1)\times(m-1) (n?1)×(m?1) 的，所以我清了，清…，等一下？？！

輸出矩陣是 n × m n\times m n×m 的啊，

完了啊我的天，沒清干凈啊我去，多測不清空，爆零兩行淚，

第六感真沒錯，果然掛分了嗚嗚嗚嗚嗚嗚嗚嗚嗚，

于是就悄悄早退了，離開積建樓，回寢室了，

晚上和前一天一樣收到了 yyq 學長的加油，還有叫我放輕松好好考，

喜歡，又是一夜好夢，

DAY2

8:00

早早到了競賽教室，

潘老師走進來奶了我一波：“你這兩天考得挺開心吧，聽說昨天最差的分都很高，“

我：”教練你別把我奶死了啊嗚嗚嗚，“

8:30

開始考試了，

看T1，

淦啊資料結構！樹上路徑上的問題，

emm，兩個 l o g log log 的做法挺顯然的，2e5 的范圍怕是要一個 l o g log log 才行吧，

2s的話，二分一下答案然后倍增來check應該沒什么問題，

此時我的心理OS：話說我編碼能力不太行，萬一調不出來咋辦，而之前做這種題要調一晚上，

算了，先看T2，

T2 n ≤ 13 n\le13 n≤13 ， n n n 好小，

可以按求一個排列最小花費的構造方法來狀壓dp，時間 O ( 2 n n 2 m ) O(2^nn^2m) O(2nn2m) ，

m m m 只有 500 500 500 ，這個且復雜度遠遠跑不滿，

所以就切了？

寫了暴力拍上了，

激動，以為 100 分到手，（然而我忘記long long 掛成了 90 ）

10:30

開T3，

艸啊支配樹，

完了，

不是吧不是吧，考前才壓了一波絕對不會考支配樹，

復習的時候支配樹看都沒看，我只會求DAG上的支配樹啊，

？

那只能亂搞了，

先暴力求出支配關系，然后再每個點來check支配它的點的點集變了沒變，

集合就用bitset吧，反正不會寫支配樹，反正都是亂搞，

等一下， O ( m n 2 / ω ) O(mn^2/\omega) O(mn2/ω) 的時間+樹上情況特判似乎能過掉 75 分，

我愿稱之為亂搞出奇跡，

大樣例一遍過，但是我不太懂它的正確性2333，

12:00

開始肝 T1 ，

我深知我大概率調不出來，所以把暴力先寫好，

然后慢慢悠悠寫二分,倍增,還有挺多細節，

12:30

寫完T1了，測樣例，

額，一個都沒過，意料之中，

那就調唄，

然而等到快結束了我還在調，

13:00

啊，結束了！！！

估分 25+100+75=200

T1最后還是沒調出來，好在沒有耽擱其他題，

附中的選手一起到門口拍了合照，

被強制拉到 C 位，有點害羞，

話說在自家學校考試留影這感徑訓挺奇妙的，

“月色微醺，比是比不過太陽，不過，只要照得了前路，就耽誤不了你的行程，“

DAY2 下午

教練請客去嘉陵江邊放松了一下，烤肉真好吃，

這可能是散伙飯吧，不知道，

省選一百多個人，刷掉九十多個，

bs bz 強到窒息，看得出來我的幾個隊友很焦灼，

這時候無比慶幸自己是個女生，不然我省選掛的這接近 100 分足以讓我退役，

現在想想大家真的一起學了好久的 oi 了，

而這一次注定會有人抱著遺憾離開，

是這樣的，成王敗寇，愿賭服輸，

我曾問過一位成都學姐，當年沒進省隊甘不甘心，

”甘心，“

意義不是成功學上的，而是青春學上的，

哪怕有些事情難以啟齒，有些事情還沒有開始就夭折，

也許此時會有遺憾，也許那是一條千萬人走過卻與自己將來截然不同的道路，

那是一條好且讓人羨慕但未來你也許并不想選擇走上的路，

一切都是有預兆的，那注定的對手，注定的結局，

愛有時也是強求不來的，是有緣無份的，

愛中要學會放手，寄以永久的凝視，

省選結束，沒有進隊的隊友，也是解脫了，

”我輸掉的本就不屬于我，”

放下沉重的擔子，告訴自己，從吾心，盡吾力，

足夠了，

致我從初一就認識的好朋友 konjacq dmy，還有機房里我最尊重的隊友 wzhh xzh，

無論走那條路，都希望你們披荊斬棘，前程似錦，

我們各自努力，未來后會有期，

“一步一個腳印，努力追光，”

省選結束后的周四發了成績，

100+50+52+25+90+0=317

d1t2多測沒清空掛了25分，t3手賤寫了拼盤大資料過了小資料T了掛了28分，

d2t1沒開longlong掛了10分，t3暴力的部分沒接進主函式掛了44分

淦，加起來 107 分了，怎么這么慘，

感謝爹媽，幸好是個女的，

又茍進cq省隊了，幸好當前cq女選水平還是不太高，

自己還是菜，

去年說希望今年要不靠女選優勢進隊也沒有實作，

不管了，

新的征途已經開始，新的挑戰正在臨近，

一步一個腳印，努力變強，努力追光，

noi2021 浙江見，