【遊記】CSP-S-2021

CSP2021

有關時間表示

不存在 Day 0, CSP 考試當天是 Day 1, 前一天是 Day -1

Day -5

如果有空閑的話, 希望能夠熟悉一下基環樹的處理, 打一打樹剖, 做點容斥

大坑: 8級的原根、BSGS、網絡流、SA、Manacher、AC 自動機

Day -1

想着考前好好打一次闆子，結果寫了并查集和最小生成樹之後，負環就開始卡了，于是滾去頹廢了。

與以往不同的是，我爹我媽這次一起送我。中午吃過飯後出發，下午到了飯店。安頓下來後，我們去了萬平口。

“海浪拂過的地方，送上來些許貝殼，那裡的沙子被撫平了。海擁有如此強大的力量，是因為它是無數個水分子的融合。”我這麼想着，想到了自己的小團體。

“為什麼沙灘是沙灘而不是石灘？石灘都堆成陸地和島嶼了。大陸已經這麼久沒有變遷了啊。”我這麼想着。

我在海邊留下了腳印，也許代表了我來過，來過這裡，來過日照，來過山東外國語職業技術大學。

飯店對面的街邊有幾家飯館，我們在那裡解決了晚飯，包括 Day1 的早飯和午飯也是在這幾家店解決的。

晚上沒有複習。

Day1

上午寫了寫FHQ。

下午，來到校門口，與大家見面，合影。

入場。

CSP2021 場上

T1讀了7min，覺得仿佛是單峰。

讀T2，麻煩的DP。

讀T3，麻煩的DP。

20min+ 過去了。

讀T4，啊網格圖啊附加點，難道是斯坦納樹？可是我已經忘記闆子怎麼寫了。啊反正不可做。

30+min 過去了。

想T1。對于國内，廊橋停放機次肯定關于國内廊橋單調不降；國外同理。不妨拟合成單調遞增的一次函數 \(y1=k1*x\)，\(y2=k2*x\)，設 \(\rm y\) 表示最終的答案，\(\rm x\)表示配置設定給國内的廊橋，\(n-x\) 就是配置設定給國外的，是以 \(y=k1*x+k2*(n-x)=k2*n+x*(k1-k2)\) 。呵呵，這玩意有個P的單調性。

先去給T1寫個暴力。

不知道怎麼回事寫挂了，瞪了一會眼之後我果斷重構，換了換 if 嵌套的順序就沒問題了。

90min 過去了。

這個時候，通過第三個資料，我發現答案不是關于配置設定給一方的單峰函數，然後我就蒙了。考慮增量？用(配置設定的廊橋數量)個連結清單維護停進廊橋的飛機？算了算了，我還是先去打剩下題的暴力吧。

根據題面的勸退程度，我選擇了T3。T3寫完之後就隻剩下 30min 了，也就是說我 T3 一共花了 120min，而我僅僅是打了爆搜、手玩 1 組 \(n=5\) 樣例和一組 \(n=20\) 樣例，寫DP，扔DP，用隊列寫DP，然後過了樣例，由于暴力隻會寫 \(2^n\) 并且不會造合法資料，我沒法拍。于是把STL隊列改成手寫隊列，扔。

估計腦電波最死的一段時間就是思考 T3 怎麼DP的時候了...我總是這樣，一次次走到死胡同，然後退回去，然後再走一次...無論是題目、是遊戲、是學習方式、還是生活态度...T3 的思考角度，我是考慮回文中心還是首位？是考慮由給定序列推回文序列還是考慮回文序列如何構造出一個給定序列？\(T=100, n=1e5\) 這看起來像是誘人的 \(O(n)\)，然後我大概發了 20min 的呆，才想起來去看多項式複雜度的部分分，這個 \(n=100\) 大概寫個三次方四次方的DP吧。但是我腦子裡沒有一個簡單的狀态設計蹦出來。想起校内試機賽，别人一眼的DP，到我這裡也是發呆。

考慮我前面取了連續的一部分，後面取了連續的一部分，取出來的數字一定對應在原序列中間連續的一段。用這個來DP，記錄前面取了 [1, l]，後面取了 [r, 2*n]，中間取了 [i,j] 滿足前後數字集合等于中間數字集合。\(O(n^3)\) 枚舉狀态，\(O(1)\)轉移。這樣看來DP過程就挺簡單了，但是寫起來繁瑣。我寫了一半就不想寫了，而且感覺開 \(f[l][r][i]\) 浪費空間，于是就打算拿 BFS 寫，開個隊列放已知狀态，每次往外擴張。

具體地，我寫一個結構體：

struct Op{
    int l, r, i, j, tp;
}
           

一開始我把單個結構體塞進隊列裡，一個狀态 pop 掉之後就沒了。但是我忘記考慮輸出方案了，是以我給所有狀态存下來，也就是這樣子：

struct Op{
    int l, r, i, j, tp, pre;
}P[10000010];
           

給所有狀态一個編号，然後把編号塞進隊列裡，pre記錄轉移過來的狀态用于回溯答案。由于我 BFS 内的轉移時先考慮 L 操作再考慮 R 操作是以我第一次找到的結束狀态就是答案。結束狀态就是 l+1=i,j+1=r 的狀态。

唉就是這裡的代碼寫的很爛，寫了改改了寫，讓我覺得“我廢了”。

210min 過去了。

給T2打一個爆搜。

CSP2021 送走我...

讀完題，我向自己确認"廊橋是一樣的對吧，隻需要知道目前空出來能用的廊橋數量即可吧，不需要區分每一個廊橋。"賽時腦子裡關于 T1 ， 蹦出來了大概有"取模（即分組）"、"連結清單"雲雲的關鍵詞，意思是把廊橋視作不同的，考慮一個廊橋上停放了哪些飛機。但是每當這個想法升起時，"廊橋沒有差別"的聲音就會把那些想法打消... 賽後我看民間題解，考慮每一個廊橋的停機情況卻是解體的關鍵... 怎麼說，是自己限制了自己的思考。

Day After

Else