thspc-2024

前情提要

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

北市賽當天

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

以下是題目:

pA

給$N$個物品$(1 \le N \le 16)$，和一個容量限制$Q$，每個物品有$p_i,s_i,t_i$，要你把每個物品按照$p_i$排序之後，把排序後的序列拆分，使得拆分後的每個區間的$\sum s_i \le Q$，每個區間的cost是$\max t_i$，求每個區間的cost和最小值。

pB

你有一個$N \times M$大小的矩形$(1 \le N,M \le 500)$，還有$K$種太陽能板$(1 \le K \le 1000)$，第$i$種太陽能板長$h_i$寬$w_i$，每種都能無限用。你要把$N \times M$大小的矩形分割，第一次分割可以任意分割，第二次以後只能在分割後的區域分割，並在分割後的區域裝上大小不大於此區域的太陽能板，第$i$種太陽能板裝上去之後可以得到$p_i$的收益，求收益最大值。

pC

求長度為$N(1 \le N \le 10^9)$，由$\text{C,D,E,F,G,A,B}$七種字母組成，且符合以下規則的字串有幾種。

• $\text{D}$之後不能放$\text{A}$，但是可以有$\text{DAD}$，且$\text{DA}$可以是最後兩個字母。
• $\text{count(E)+count(G)}$必須為偶數。

pD

給一個$M(1 \le M \le 9 \times 10^5)$，和$N$個物品$(1 \le N \le 100)$，每個物品有$p_i(1 \le p_i \le 10^6)$，要你求出，所有物品的子集$S$使得$\sum_{i \in S} p_i \ge M$中$(\sum_{i \in S} p_i) -M$的最小值。

pE

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

pF

有$M$個山峰$(1 \le M \le 2 \times 10^5)$，每個山峰有位置$p_i$和高度$h_i$，保證所有人的$p_i$相異。然後有$N$筆詢問$(1 \le N \le 50000)$，每次詢問給$K$個人的起始山峰$(\sum K \le 2 \times 10^6)$，每個人都只能走到高度不低於他的山峰，而這$K$個人要走到同一個山峰去開會，從$i$山峰移動到$j$山峰的移動距離是$|p_i-p_j|$，求每個人移動距離和的最小值。

以下是大爆雷

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

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

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

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

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

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

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

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

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

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

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

感想

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

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

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

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