yuyc

摘要： 原題鏈接 解析 Solution 1 由題意得，能替換的位置一定是 \(s_1\) 能匹配上 \(t_1\) 且 \(s_2\) 能匹配上 \(t_2\) 的位置。替換是否有效就取決于 \(t_1\) 替換掉的子串左右兩邊的串是否和 \(t_2\) 相同。所以可以處理出 \(t_1\) 與 \(t_ 閱讀全文

摘要： 原題鏈接 解析 設 \(f_i\) 表示取完了編號為 \(a_i\) 的車，最后取出的是第 \(i\) 個格子上的車所需的最少操作次數。枚舉上一層終點 \(j\) 進行轉移： \[f_i=\min(f_j + \operatorname{dis}(pre_i,j) + \operatorname{A 閱讀全文

摘要： 原題鏈接 解析 注意到對于一個起點站 \(x\)，必定有另一個站 \(y > x\) 使得所有以 \(x\) 為起點站，終點站編號小于 \(y\) 的路線均處于停開狀態，而所有終點站編號大于等于 \(y\) 的路線均不處于停開狀態。 故考慮對于每個站 \(i\)，維護 \(a_i\) 表示以 \(i 閱讀全文

摘要： 原題鏈接 解析 首先可以想到區間 dp。 設 \(f_{l,r}\) 表示分裂出 \(T[l,r]\) 所需的最少 \(\texttt{S}\) 個數，其中 \(T\) 是目標串。 但是仔細思考后發現根本沒有辦法轉移，于是倒閉。 正難則反，考慮怎么合成。 設 \(f_{l,r}\) 表示合成 \(T 閱讀全文

摘要： 原題鏈接 解析 題意等價于問有多少個位置 \(k\)，使得其對于所有 \(1 \le i \le n\)，右移 \(a_i\) 后不屬于任何一個區間。 發現有一個區間長度互不相等的限制，不知道有什么用。 發現 \(a_i \le 5 \times 10 ^ 5\)，但是區間和 \(k\) 的值域非常 閱讀全文

摘要： 原題鏈接 解析 如果你還不會利用哈希 \(O(n)\) 找循環節，那么你應該先去做 P4391。 由于我們要求的是完整周期，所以循環節長度必定為所選片段長度的因子，于是可以很輕松地得到一個 \(O(q \sqrt n)\) 的做法。 設查詢的字符串為 \(a\)。觀察到若字符串 \(b\) 是一個完 閱讀全文

摘要： 原題鏈接 解析 首先將直徑長度轉換為深度，那么要求的就是： \[\max_{1 \le i \le n,1 \le j \le n}(dep_i + dep_j - 2dep_{\operatorname{lca}(i,j)}) \]修改邊權啟發我們在 DFS 序上考慮，因為修改邊權影響的是子樹內結 閱讀全文

摘要： 原題鏈接 分享圖片 解析 首先小心不要把“總跳躍次數”看成“總跳躍長度”。 如果你做過前一場的 E，那么你應該很快能想到要把 \(\lceil \frac{3n}{2} \rceil\) 變成 \(n + \lceil \frac{n}{2} \rceil\)。 手玩一下，發現如果設 \(s_i\) 閱讀全文

摘要： 原題鏈接 解析 先考慮 \(K = 1\) 的情況，加一條邊會連出一個環，環上所有邊只需經過 \(1\) 次，這個可以利用無向圖歐拉回路的判定來證明。巡邏距離最小就是要讓環盡量大，所以連直徑端點即可。 再來看 \(K = 2\)，由于有公共邊的存在，兩個環的貢獻無法通過直接相加來計算。畫個圖發現一般 閱讀全文

摘要： 原題鏈接 解析 不難發現對于一條鏈，直接從一個端點 check 到另一個就可以。進而發現如果要保證找到，那么每個點都需要 check 一次。結合操作次數的限制，問題變成了用不超過 \(\lfloor \frac{n}{4}\rfloor\) 次操作 2 把樹分割成若干條鏈。 于是就會有一個想法，對于 閱讀全文