thspc-2024

前情提要

雖然複賽打得有夠爛(rank 8)，總之進校隊了。
從複賽到北市賽之前有差不多一個月的時間，在這期間我看了很多題，還有北市賽的考古題，然後學了一些字串演算法，還玩了一下Hopcroft Karp常數比較小的寫法(雖然他要shuffle但是真的很好玩)
北市賽前一周和顏巨砲和詹哲崴vir了BOI 19，然後d2心態炸了打爆炸爛，心態穩的話有機會打得更好。還好BOI 19 d2打太爛沒有影響到我打隔天北市模擬賽，拿了一個rank 2，好爽。
北市賽前兩天連上北市賽的CMS系統測試，然後他的judge只有C++17的選項，不知道在幹嘛。

北市賽當天

早上就先去報到然後聽個規則就準備開打了。

以下是題目:

pA

給個物品，和一個容量限制，每個物品有，要你把每個物品按照排序之後，把排序後的序列拆分，使得拆分後的每個區間的，每個區間的cost是，求每個區間的cost和最小值。

pB

你有一個大小的矩形，還有種太陽能板，第種太陽能板長寬，每種都能無限用。你要把大小的矩形分割，第一次分割可以任意分割，第二次以後只能在分割後的區域分割，並在分割後的區域裝上大小不大於此區域的太陽能板，第種太陽能板裝上去之後可以得到的收益，求收益最大值。

pC

求長度為，由七種字母組成，且符合以下規則的字串有幾種。

• 之後不能放，但是可以有，且可以是最後兩個字母。
• 必須為偶數。

pD

給一個，和個物品，每個物品有，要你求出，所有物品的子集使得中的最小值。

pE

給你一個只有加法的運算式，加號數量最多，每個數字用一個大寫英文字母代表，之後給你每個加號的執行順序，要你加上括號讓這條運算式加號的順序和他給你的順序一樣。
例如運算式是A+B+C+D，順序是2 3 1，那輸出要是(A+((B+C)+D))。

pF

有個山峰，每個山峰有位置和高度，保證所有人的相異。然後有筆詢問，每次詢問給個人的起始山峰，每個人都只能走到高度不低於他的山峰，而這個人要走到同一個山峰去開會，從山峰移動到山峰的移動距離是，求每個人移動距離和的最小值。

以下是大爆雷

比賽一開始我先登入CMS系統，然後調整一些vscode的設定之後打default code。
我在vscode點了好幾次open folder都沒反應，但其實我已經打開desktop這個folder了，然後我去調code runner的run in terminal，結果跑了很久都沒跑出來，我就乾脆直接打指令編譯了，反正我沒差，是說我的vscode的IntelliSense也是爛的。

處理好這些之後我開始看題目，大概看了一下之後發現字好多，所以就從A開始實作。
pA的，一開始我以為他可能是的子集枚舉dp，結果他說那些東西要照排，然後他就變了，不知道在幹嘛，打完才知道他應該是想出枚舉切在哪的位元枚舉。

然後去看pB，看完發現我還不會，所以跳pC。pC一臉矩陣快速冪，稍微推了一下狀態之後就先跳pD了。
pD是裸的可行性背包，看完就寫掉了。

pE看完之後發現沒想法，然後pF題敘好長喔，看完之後發現我不能對每個詢問暴力驗，但我會三分搜，可是這樣要離線還要砸pb_ds，丟到後面再寫好了。

這時回去看pB發現我會一個的dp，一開始寫了一個dp，交上去只有15分，發現漏狀態了，改一改交上去發現我寫遞迴的dp被卡常，改成迭代的變WA了(49分)，雖然不會溢位但是我把dp陣列改long long再交一發還是49分，我認真畫了轉移之後才發現我漏了不放太陽能板上去的case，複雜度應該是，改好之後就過了。

回去好好看pE，發現他每次加法操作就是把相鄰兩個人併起來而已，然後在最左邊加一個左括號，最右邊加一個右括號，所以我用一個dsu維護一個區間的最左和最右，然後好好寫就過了。

之後去寫pC，我很快的把Mat operator*(const Mat&, const Mat&)寫完，然後把矩陣推好，結果測的時候一直少一，我盯著我的矩陣很久才發現我打錯了，然後少的那一個字串是。

這時候我500分了，然後我去了一次廁所，準備把pF寫掉，結果我發現我沒有背pb_ds的node update policy(tree_order_statistics_node_update)，我本來想說靠賽看看我會不會猜對，結果編譯了很多次都沒過，所以我就花了一點時間把pb_ds的標頭檔找出來看。

pF實作的時候寫得蠻快的，不過bug有點多，然後好幾個iterator忘記dereference，本機吃:eight:次CE。在本機測完範測都過了之後傳上去，跑得有點久但是一發就過了。

這時候大概兩小時二十分鐘左右，因為我喉嚨有點乾所以我先去裝水，然後我就耍廢了40分鐘。

我是四個破台的裡面第三個破台的，施竣耀..真的..好強..

感想

比賽規則講的C++14和兩分鐘上傳間隔都是假的，有夠好笑，看到CMS上有C++17我就爽爽開用了，不過兩分鐘上傳間隔可能是因為傳上去之後要跑兩分鐘以上，然後你就真的可以等兩分鐘。

然後聽說有些人pD爆搜+剪枝拿100分，北市賽很會生測資。

負責北市賽的教授說他們預期一等獎的人都可以破台，什麼鬼。而且這場北市賽有4題dp，連一題圖論都沒有，本來我考前猜會考DAG最小路徑覆蓋和高斯消，結果這場有夠簡單==

總之有TIOJ管理員了，然後要負責出明年的校內賽。然後我希望我全國賽打好一點，我不想打TOI初選。