寫下這行字的時候是 2025.11.17 8:10，比賽在一個小時十分鐘前完全結束了。

隊名 Endless Dream，rk256 搞笑排名。

C

簽到。奇數無解，偶數輸出 n/2 n/2 即可！！1

K

也是簽到，但是做了三個小時！！1

一直在猜結論，最後發現直接把博弈圖畫出來套有向圖博弈是能過的/cf

F

沒那麼簽到的簽到，最開始一直在想這題然後發現 K 好像更為簡單！！1

首先考慮 -1 怎麼判，發現並查集直接做。

然後考慮，詢問的時候，我們可以貪心從高到低位選，那我就需要維護的是，所有滿足 \(x\) 是邊權的一個子集的邊保留，其餘刪去後 \(u,v\)

如果直接枚舉每一個子集連上，是 \(O(qV\log n)\)，顯然過不去，考慮一個小小的剪枝，即已經聯通的就不用連了，然後過了。

？？？這就過了

證完複雜度才敢寫出來交。

考慮一個並查集最多有效合併 \(n-1\) 次就會聯通，總共有 \(V\) 個並查集，所以至多 \(O(nV)\)

時間複雜度 \(O((nV+q\log V)\log n)\)，可以優化掉那個 \(\log\)，不過完全沒必要！！1

G

這題為啥過的比 F/K 少？

唐題，每個詢問二分一下就過了。

---

I

考慮設 \(dp_{i,j}\) 為前 \(i\) 個花費 \(j\)

upd：沒判 -1，naomale

H

\(O(n^8)\)

聰明一點的暴力是 \(O(n^7)\)，更聰明一點的是 \(O(n^6)\)

設 \(f_{i,j,k}=1\) 表示 \(s_{[i,i+k-1]}=s_{[j-k+1,j]}\)，把這個東西給預處理出來（枚舉 \(i\) 和 \(j-k+1\)

對 \(k\) 做一個累加，得到 \(g_{i,j}\)。

然後你枚舉兩邊的 pen 是什麼，然後枚舉 apple 是什麼，你發現事實上我們就是要在 \(i\times g_{i,j}\) 和 \(g_{i,j}\) 上做一個矩形和，然後二維前綴和優化一下就可以做到 \(O(n^3)\)。

我們現在預處理 \(f\)

先看求答案吧，我們事實上是可以 \(O(1)\) 求助每個區間的 pineapple-apple 的答案，我們只需要計算兩邊可能的 pen 的數量就行。

我們注意到，這就是 \(g_{i,j}\)！不過是 \(i>j\)

我們先考慮記錄 \(dp_{i,j}\) 表示 \(i\) 開頭的後綴和 \(j\)

那麼我們對於 \(dp_{i,j}\)，需要將 \(g_i\) 這個數組進行一個 \(j\sim j+dp_{i,j}-1\) 的區間加 \(1\)，差分前綴和即可。

做完了，時間複雜度 \(O(n^2)\)。