happybob

摘要： 1 P14363 問題等價于給若干字符串二元組，\(q\) 次詢問每次給兩個字符串，問有多少二元組使得第一個是詢問的第一個的后綴，第二個是詢問的第二個的前綴。建 Trie 等價于查詢兩棵 Trie 上到根路徑交，變成 DFN 序后隨便維護。 不保證 \(|t_1|=|t_2|\)，神經病。 2 P1 閱讀全文

摘要： 1 NFLS 模擬賽 T1 每個點處理一些信息，選好枚舉哪個點就行。 2 NFLS 模擬賽 T2 首先，所有 \(x_i+y_i\) 奇偶性相同是必要條件。其次，其也是充分條件。 觀察大樣例可以看出其給的是 \(1,2,4,8,\cdots\)，對這個東西構造即可。大概是你嘗試歸納證明用 \(2^0 閱讀全文

摘要： 1 煉石 NOIP R2T1 不講。 2 煉石 NOIP R2T2 \(f_{i,j,0/1}\) 表示，\(i\) 子樹內選點，相鄰點數最大為 \(j\)，點 \(i\) 是否取到這個 \(j\) 時的方案數。轉移容易背包，復雜度 \(O(n^3)\)。 3 煉石 NOIP R2T3 \(a_0, 閱讀全文

摘要： 1 NFLS 訓練賽 T3 2025 山東省隊一輪集訓 D5T1，懶得說了。 2 NFLS 訓練賽 T4 / QOJ4914 \(fa_i \geq fa_{i-1}\)，所以 \(dep_i \geq dep_{i-1}\)。 對于每個 \(i\)，令 \(g_i\) 為最大的 \(j\) 使得 閱讀全文

摘要： 1 P12152 一個序列是好的當且僅當其可以被劃分為 \(m\) 個子段，使得每個子段都完整覆蓋 \([1,k]\)。這暗示著 \(n \geq mk\) 答案才非 \(0\)。 所以考慮一個關于段的 DP，考慮這個 DP 需要記錄什么狀態(tài)。首先肯定需要 \(i,j,x\)，表示目前到了 \(i\ 閱讀全文

摘要： 1 P12462 \(q=1\) 是經典貪心問題，先建立區(qū)間 \([l,r]\) 虛樹，找出直徑以某個直徑端點為根做長剖，取前 \(k-1\) 大路徑長度求和即為答案，證明顯然。 考慮原題，我們有以下兩個引理： 對于任意 \(k\)，存在選 \(k\) 個點的最優(yōu)策略使得這 \(k\) 個點是選 \ 閱讀全文

摘要： 廣東省集 Day11 T1 考慮詢問本質上能獲得什么信息，發(fā)現當你詢問 \(p\) 后，交互庫會告訴你假幣的 \(p\) 值為多少。 考慮什么時候 \(W=1\)，發(fā)現必然是存在方案使得 \(p_i \leq a_i\) 且 \(p_i\) 互不相等，這等價于對于所有 \(i\) 都有 \(a_i 閱讀全文

摘要： P11920 將一個數字數位任意排列，其 \(f\) 值不變。 注意到有很多 \(f(x)=0\)，考慮先求出 \(1\) 到 \(9\) 的答案，\(0\) 的答案即可算出。 枚舉所有 \(f(x) \neq 0\) 且 \(x\) 數位單調不降的 \(x\)，每個 \(1 \leq y \leq 閱讀全文

摘要： D1T1 若前 \(r\) 行和前 \(c\) 列已經確定，則剩下的格子全都確定。 考慮怎么判定前 \(r\) 行和 \(c\) 列確定的格子符合條件，有一些形如和相等的限制。可以發(fā)現左上角的 \(r \times c\) 的網格的每個格子要么一列等差數列編號都相同，要么一行等差數列編號都相同。可以 閱讀全文

摘要： P6292 考慮建出 SAM 后掃描線。 考慮目前一個等價類集合長度區(qū)間為 \([l,r]\)，顯然我們掃到每個位置的時候只需要維護每個等價類的 \(\operatorname{Endpos}\) 集合中最靠右的位置。我們考慮右端點增加 \(1\) 的時候，會被修改的等價類為目前前綴對應的等價類 F 閱讀全文