2021CSP-S游記

從國慶過后就開始停課，確實面對的壓力和挑戰(zhàn)很大。

這段時間真的就是完全沒有去想文化課那邊的事。

越接近考試時間，模擬賽就越密集，最近大家都在互測。

蠻清楚自己的水平的，而且偶爾還是能考得不錯，但是因為一些常見錯誤爆分的情況也不少。

在考試前一天晚上 $10:40$ 就早早上床，直接睡了個爽。

下午試機，我那個 $5$ 機房配置超級差，$32$ 位不說，$\text{VScode}/\text{MinGW9.3.0}$ 都用不了，雖然老師說會去交涉，但也有可能因為各種因素就這樣了。所以還是蠻擔(dān)心的。

考試當(dāng)天中午也放的挺早，老實說下午我的狀態(tài)至少不是迷迷糊糊的那種。

但是之前模擬賽大部分都是早上，后面才改成下午考，我能很明顯感受到自己早上的思維狀態(tài)要優(yōu)于下午的，雖然我也不知道為啥。

因此考試的時候還是有點點沒把握的。

心里挺矛盾的，不想再像上次 $2h$ 做大模擬，又不想第一題都想不出來。

最后——懷著模擬賽就像平時一樣打的心，我進(jìn)入了考場。

---

考試開始，我先花了十分鐘左右通讀了一遍題目，第四題晃晃就過了（因為我清楚自己不一定能做到第四題）。

最有感覺的應(yīng)該算是第二題了，但是我還是先從第一題開始的，因為我覺得第一題應(yīng)該是簽到類型的吧，認(rèn)真想想就出來了。。。然而——

---

T1

再次細(xì)讀了一遍題目，明白大意后，暴力的 $40^{\prime }$ 就出來的：枚舉國內(nèi)機場的廊橋數(shù)量，然后模擬一遍。

但是我還沒忙著打上去。

接著就是想正解，很明顯我應(yīng)該是要優(yōu)化這個模擬過程的，嗯？有點貪心的意思了。

我的想法是如何從 $i?1$ 個轉(zhuǎn)移到 $i$ 個，的確沒想到用桶來裝廊橋，所以就卡住了。

到最后我懷疑是不是這個思路有問題，我就開始手玩樣例，自己也弄了幾組小樣例。

好巧不巧這些小樣例都是有凸性的，我就以為這是道三分的題目。

迅速就碼完了，連大樣例也過了。

耗時四十分鐘左右。

后面寫 $T_2$ 的時候，想了想先跑回來寫了個暴力程序就開始對拍。結(jié)果對拍到最后都沒拍出錯，我就以為自己是正解了。

誰想到根本就是個錯解。最后只能聽天由命，看官方數(shù)據(jù)怎么出了。

害，我應(yīng)該寫兩段式把暴力嵌進(jìn)去，分就能騙高一點。

---

T2

再次細(xì)讀一遍題后，明顯就是個 $dp$ 。而且狀態(tài)和轉(zhuǎn)移非常好想。

我懷疑了一下，莫非 $T1,T2$ 放反了？？

但我覺得不可能，所以我就再讀了一遍題目，終于在不合法的舉例中明白了不能兩邊都放 $?$ 。

頓時感覺難度上來了，順次轉(zhuǎn)移的 $dp$ 似乎就不起作用了，根本記錄不了前面是否放了 $?$ 的狀況，無法轉(zhuǎn)移。

但我堅信，這一定是個 $dp$ 題。

然后我就想到強制 $l,r$ 括號匹配，然后枚舉 $l+1$ 開始的左邊連續(xù)一段 $?$ 和 $r?1$ 開始的右邊連續(xù)一段 $?$，在這之前還預(yù)處理了一下 $g_{l,r}$ 看 $[l,r]$ 段能否全為 $?$ ，作為系數(shù)。

這就是個區(qū)間 $dp$ ，目前已經(jīng)是 $n^3$ 了。

迅速碼完，測試樣例：第一組過了，第二組呃……就掛了，看一看算少了。

這時我再次回到題目，順便看看第一組樣例解釋。

仔細(xì)想了想，發(fā)現(xiàn)自己忘了 ()**() 的情況，也就是 $l,r$ 雖然是左右括號但不一定要匹配。

具體操作是我得枚舉 $k,t$ 分別與 $l,r$ 括號匹配，$(k,t)$ 中間就得是連續(xù)的 $?$，但這已經(jīng)是 $n^4$ 了。

顯然后面需要優(yōu)化，但是我想還是先把暴力轉(zhuǎn)移碼出來再說，至少得保證自己是對的，要能過大樣例，超時都是其次。

挺好寫的，再測試樣例，然后第二組還是不對——又大了。

后面就開始一堆亂改，修了幾個字符敲錯，枚舉長度少了點的鍋。

測試樣例，還是第二組！！！

我就有點無語了(⊙﹏⊙)。

這時候已經(jīng)過去一個小時二十分鐘左右了。

我后面兩道題還沒有開。我就先放了一下 $T_2$。

---

T3

我感覺是有點偏向結(jié)論后的模擬構(gòu)造類型的，因為沒有想到選了一個端點后再選一個，相當(dāng)于中間某兩個字符連續(xù)。

看了一下部分分，發(fā)現(xiàn)指數(shù)級的只有 $28^{\prime }$，還有特殊性質(zhì)的 $12^{\prime }$，當(dāng)時簡單想了下特殊性質(zhì)，因為考慮漏掉了一種情況，所以我以為非常簡單，權(quán)衡一下我應(yīng)該能拿到 $40^{\prime }$。

迅速碼完調(diào)了一些小錯誤，大小樣例均過。

時間又過去了二十分鐘。

最后我簡單看了下自己的暴力過程，發(fā)現(xiàn)對于數(shù)據(jù)而言，有了剪枝，自己的程序應(yīng)該是能跑過 $40^{\prime }$ 的指數(shù)部分分。

所以本題我的預(yù)估是 $52^{\prime }$。

到這里我看了眼 $T_1$ 的對拍還在繼續(xù)，所以此時在考場上的我，以為已經(jīng)拿到了 $152^{\prime }$。

---

T4

細(xì)讀一遍題目后又讀了一遍，我發(fā)現(xiàn)毫無思路。

果斷看部分分，先思考了一下指數(shù)級別的暴力，蠻好打的，但是我發(fā)現(xiàn)還有多組數(shù)據(jù)的時間復(fù)雜度，一下子乘起來就還是會超時。

我就看 $k=2$ 的部分，發(fā)現(xiàn)就是黑白染色，但當(dāng)時沒有聯(lián)想到網(wǎng)絡(luò)流的最小割。

腦子已經(jīng)有點發(fā)熱了，我就迅速寫了個雙向 $\text{bfs}$，調(diào)了一下，時間又過去了半個小時左右。

小樣例又能過，大樣例第一組就掛了。

隨便一想就把自己 $\text{hack}$ 掉了。

我馬上明白這道題自己應(yīng)該是拿不到一分了。

果斷棄掉，回到 $T_2$ 的調(diào)試。

---

T2

此時時間大概是過去了兩個小時二十分鐘左右。

我就開始分布調(diào)試代碼，輸出中間結(jié)果，然后人腦模擬第二個樣例。

發(fā)現(xiàn)有一個中間轉(zhuǎn)移的是錯的，我就單獨摳出來將樣例縮小跑。

因為長度為 $10$ 人腦模擬起來就已經(jīng)很吃力了。

我就縮小到了 $8$ 再縮小到 $7$。

發(fā)現(xiàn)一旦超過 $5$ 就會算出問題，但是當(dāng)時沒仔細(xì)管是算多還是算少。

突然我就反應(yīng)過來，$k$ 的枚舉會算重。

我枚舉了 $k,t$ 必須強制 $l?k,t?r$ 強制匹配，為了解決這個情況我就再定義了一個二位數(shù)組，強制匹配和不要求強制匹配之間互相轉(zhuǎn)移。

小調(diào)了一下，大小樣例全過，此時時間大概過去了三小時不到。

$n^4$ 只有穩(wěn)的 $65^{\prime }$，考慮優(yōu)化。

明顯我能感覺到是前綴和的優(yōu)化，但是因為我自己 $g$ 的限制，就影響了我的前綴和優(yōu)化，沒有想到優(yōu)化的實現(xiàn)。只能遺憾放棄。

后面又花了半個小時左右在 $T_4$ 上無謂的掙扎，真的一點分都拿不到。

---

檢查

此時的時間還剩下最后半個小時，我的四道題基本上已經(jīng)做完，預(yù)估分在 $205$ 左右。

我猶豫了一下是繼續(xù)思考四道題進(jìn)一步拿分，還是點到為止開始檢查。

我想起了吳老師前一天晚上說可以莽一點，又想起了吳老師反復(fù)叮囑低級錯誤的檢查。

最后我選擇了檢查。

將文件輸入輸出注釋掉，本地測試小樣例，先保證中間調(diào)試結(jié)果都已經(jīng)注釋了。

然后我靜態(tài)查錯了所有代碼。

接著看了一下 #define int long long 和 數(shù)組范圍是否開小。

因為很顯然的沒有大空間的使用，我就沒有計算空間復(fù)雜度。

緊接著解開文件輸入的注釋，本次測試大樣例。都沒有問題。

最后解開文件輸出的注釋，再次測試大樣例。

問題出現(xiàn)了——$T_2$ 一開始就直接輸出 $0$ 了，沒有文件輸出。

我就看了一下寫的 freopen 。

原來我將輸出的 stdout 錯寫成了 stdin。

迅速改正，大樣例再次過掉。對著這個錯誤我再次檢查了其余代碼的 freopen 問題。

我又打開了題目上面的文件名，因為不能直接復(fù)制，我害怕自己敲錯。

就又對著一個字符一個字符的檢查了一遍。

我瘋狂 ctrl+s ，關(guān)掉 dev。在自己準(zhǔn)考證所在的文件夾里再次打開所有題目的代碼，再次文件運行，看 .out 是否成功。

做完這些后只剩寥寥無幾的時間。

沒一會，“保持安靜”，我的屏幕不再能動，CSP-S 就這么拉下了帷幕。

出考場后，我很慶幸自己檢查了代碼，保全了 $T_2$ 的暴力。

非常不想聽，卻又聽到了別人的討論，聽到他們 $T_1$ 的 “線段樹二分“,”是貪心吧。” 我就意識到自己的 $T_1$ 假掉了。

然后塵埃落定，我無力回天。

---

總結(jié)

老實說我大部分時間都在前兩題，尤其是第二題。

因為考試前我就做好了騙三四題分然后做一二題的準(zhǔn)備。

如果我能很快做出一二題，還有時間我就再慢慢想后面的難題。

但是今年確實前兩題，我都沒有做出來。

后面大家討論后，第四題網(wǎng)絡(luò)流我也沒有復(fù)習(xí)，就算想到了我可能也得調(diào)一會。第三題，我如果能多手玩幾組認(rèn)真想想，還是有可能做出來的。

但因為自己心態(tài)上就是想的騙三四題的分，主要先把一二題過掉，所以在考場上三四題的思維深度投入不及一二題。

雖然吳老師一再強調(diào)這只能算得上全真模擬賽，但是還是應(yīng)該好好反思。短時間內(nèi)思維是不可能有質(zhì)的飛躍的，我能做的就是把自己能拿到的分?jǐn)?shù)緊緊抓住。

所以對于本場表現(xiàn)，我對自己能夠在最后檢查出致命細(xì)節(jié)錯誤；也沒有出現(xiàn)平時模擬賽過了一半代碼敲完才發(fā)現(xiàn)自己題目讀錯的悲劇，反而通過樣例和題面迅速理解題意；在第二題第一次沒調(diào)出來也沒有影響心態(tài)，相信自己后面能成功調(diào)出來（可能是平時調(diào)試多了，已經(jīng)很相信自己分布調(diào)試的能力了(●’?’●)），這幾點很滿意。

希望下一次 $\text{NOIP}$ 自己能正常發(fā)揮，全力以赴，至少得超過一年前的自己吧！！

---

你再快都有比你快的，你再慢也有比你慢的！——《三體》

前進(jìn)！前進(jìn)！不擇手段的前進(jìn)！ ——《三體》

總結(jié)

以上是生活随笔為你收集整理的2021 CSP-S 游记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。