不給大樣例還是太壞了。

?

鏈接：link
題解：紙質版

時間：4h (2025.10.30 07:30~11:30)
題目數：4
難度：

估分：100 + 50 + [40,60] + 20 = [210,230]
得分：100 + 30 + 60 + 0 = 190
Rank：3/6

場祭

讀題。

怎么不給大樣例，這么壞。

A 簽。

B 考慮拆貢獻但是發現很難處理，一坨特判，復雜度也不好保證，于是打了 30pts 的暴力跑路了。

開 C，發現可以枚舉 \(b_i\)，然后對于不同的 \(a_j\) 統計答案，但是這樣就要枚舉 \(\ge a_i\) 的所有 \(a_j\) 可能值，考慮推式子，推出來的時候手玩了一下樣例發現漏情況了，加上之后就推不動了，所以果斷打了個 \(O(nV)\) 的暴力走人了，不過會有一點常數，不知道 \(V \le 1000\) 的部分分能不能卡過去。

在做 C 的時候忽然發現了 B 的一個 \(c_i \le 20\) 的特殊性質做法，枚舉每個 \(c\) 然后單步容斥一下就可以算了。

不過還是先開 D，是區間 dp 嗎？好像不怎么好轉移，于是只打了暴力。

回去把 B 的特殊性質寫了。

還剩 0.5h，因為沒有大樣例，所以拍了拍 BC，只拍 BC 是因為 A 暴力不是很好寫而且不怎么可能掛，然后 D 本來寫的就是暴力還拍個毛線（

沒拍出任何錯誤，最后 10min+ 擺了。

……賽后忽然注意到 D 的暴力掛掉了，因為忘判單調性了！不給大樣例還是太壞了。

補題

B 掛了 20pts 是因為數據根本不符合數據范圍啊。。經過 assert 發現所有測試點都不滿足 \(c_i \le 20\)，糖。

補 B，考慮擴展 \(c \le 20\) 的那個做法，然后發現非常容易，記一個 \(f_{u,v}\) 表示節點 \(u\) 的子樹中，刪掉所有和 \(u\) 顏色相同的點之后，包含 \(u\) 的兒子 \(v\) 的連通塊大小，發現記錄每個顏色的最近祖先 就可以在子樹內同色節點處更新子樹的根了，做完了?；蛘咴俜奖阋稽c，直接記 \(f_u\) 表示刪掉 \(fa_u\) 后的結果，也是可以的。

但是這樣掛了一個點不知道為啥。

補 C，注意到上面（賽時做法）那個東西，可以被刻畫成區間 \(\times 2\) 和區間求和，直接上線段樹就做完了。具體地，還是從小到大枚舉 \(b_i\)，并對每個可能的 \(\max a_j\) 算方案數，考慮維護所有可以被選的 \(a_j\) 的一個有序序列，那么在加入一個 \(b_i\) 對應的 \(a_i\) 之后，\(\ge a_i\) 的所有 \(\max a_j\) 對應的可選元素就會多一個，也就相當于方案數 \(\times 2\)。而對于每個 \(b_i\) 算貢獻就是全局求和再乘上一個 \(3^{b_i}\)。那么直接對所有 \(a_i\) 開動態開點權值線段樹即可。

天依寶寶可愛！