摘要：
原題鏈接 解析 對于樹上任意一點 \(u\)，任意直徑的兩個端點中至少有一個在離 \(u\) 距離最大的點的集合中。 我怎么把這個給忘了？ 知道這個性質后，就可以構造操作讓每個點都取到最大值了 。具體地，先求出一條直徑，然后刪掉除該直徑端點以外的所有點，最后刪直徑，實現類似拓撲。 代碼 /* */ 閱讀全文
posted @ 2025-08-25 09:16
yuyce
閱讀(2)
評論(0)
推薦(0)
摘要：
題目鏈接 解析 考慮 dp。 設 \(dp_{i,j}\) 表示長度為 \(i\) 的以 \(a_j\) 結尾的合法序列個數，于是有： \[dp_{i,j} = \sum_{k=1}^n dp_{i - 1,k}[\operatorname{popcount}(a_j \otimes a_k) \b 閱讀全文
posted @ 2025-08-21 08:40
yuyce
閱讀(2)
評論(0)
推薦(0)
摘要：
原題鏈接 提供一種復雜度多一個 \(\log\) 的做法。 解析 我最初的想法是將詢問離線下來，將球按權值排序，對于每個球 \(i\) 維護一個指針指向滿足 \(a_i \cdot a_j \ge p\) 的第一個 \(j\)，然后在處理詢問的時候去移這個指針。 但是我們甚至無法接受在處理每個詢問時 閱讀全文
posted @ 2025-08-21 08:37
yuyce
閱讀(1)
評論(0)
推薦(0)
摘要：
其實從前往后做也是可以的。 解析 先不考慮 \(L\)。 一個很自然的想法是從前往后讓每個 \(\texttt{O}\) 跟一個在它前面的 \(\texttt{M}\) 配對。問題在于 \(K\) 的限制難以滿足。 所以先滿足 \(K\) 的限制，對于每個 \(\texttt{M}\)，在它后面預留 閱讀全文
posted @ 2025-08-20 06:41
yuyce
閱讀(2)
評論(0)
推薦(0)
摘要：
提供一種不一樣的狀態設計。 將所有區間按右端點排序后，設 \(dp_{i,j,k}\) 表示前 \(i\) 個區間中，選出的右端點最靠右的顏色為 \(k\) 的區間，其右端點位于 \(j\) 的方案數。 如果不選第 \(i\) 個區間，\(dp_{i-1,j,k}\) 對 \(dp_{i,j,k}\ 閱讀全文
posted @ 2025-08-20 06:40
yuyce
閱讀(0)
評論(0)
推薦(0)
摘要：
題意 有 \(N\) 頭奶牛圍成一圈，第 \(i\) 頭奶牛有一個容量為 \(a_i\) 的桶，初始時桶滿，每一時刻，每頭奶牛都會根據一個操作序列 \(s\) 來將自己桶中的 \(1\) 升牛奶倒給自己左邊或右邊的奶牛（如果桶里有牛奶的話），傳遞完之后，大于桶的容量那部分牛奶將會溢出，問 \(M\) 閱讀全文
posted @ 2025-08-20 06:36
yuyce
閱讀(5)
評論(0)
推薦(0)
摘要：
解析 注意到 \(a_i\) 很小，那就不妨讓它更小一點，從最簡單的情況出發。 當 \(1 \le a_i \le 1\) 時，顯然所有子數組都是”好數組“。 當 \(1 \le a_i \le 2\) 時，如果一個子數組中 \(1\) 的個數與 \(2\) 的個數不同，那么它是“好數組”，否則它不 閱讀全文
posted @ 2025-08-20 06:35
yuyce
閱讀(2)
評論(0)
推薦(0)
摘要：
前言 在這里提供運用 ST 表思想但又略不同于 ST 表的構造方法，能夠在 \(n=4000\) 時相比 ST 表少構造將近 \(4000\) 個區間。 解析 構造的思路是這樣的： 設 \(len\) 為詢問的區間的長度，從小到大考慮。 當 \(len=1\) 時，詢問區間必定只能是相同的長度為一的 閱讀全文
posted @ 2025-08-20 06:33
yuyce
閱讀(2)
評論(0)
推薦(0)
摘要：
題意 判斷能否取多集中若干個數使得它們的和等于 \(w\)。 解析 由于給的數都是 \(2\) 的冪，所以我們可以每次讓 \(w\) 減去不大于它的在集合中存在的二進制位數最多的數，如果能減完那么就說明可以，否則說明不可能。 怎么保證這種策略是最優的？ 假設 \(n=\lfloor log_2w\r 閱讀全文
posted @ 2023-12-19 12:40
yuyce
閱讀(55)
評論(0)
推薦(0)
摘要：
原題鏈接 此題是01背包的變形，與傳統01背包不同的是每件物品貢獻的計算方式 如果在 \(t\) 時刻完成第 \(i\) 樣食材則得到 \(a_i - t × b_i\) 的美味指數 這句話意味著食材的美味指數在不同的時間有著不一樣的數值，也就是說，烹調的先后順序會影響得到的美味指數 假設有兩樣食材 閱讀全文
posted @ 2023-09-03 17:54
yuyce
閱讀(0)
評論(0)
推薦(0)
浙公網安備 33010602011771號