harmisyz

摘要： 容易發現每年都在考這玩意。每年都不會。 AT_abc213_g [ABC213G] Connectivity 2 顯然刪邊可以變成保留邊。 定義狀態函數 \(f_s\) 表示保留邊，使得 \(s\) 中的點聯通的方案數。那么對于 \(k=k0\) 來說，答案應該就是 \(\sum f_{s}[1 \ 閱讀全文

摘要： P4340 [SHOI2016] 隨機序列 記 \(s_i\) 為前 \(i\) 個的和。發現 \(+,-\) 抵消。有：\(s_i=3s_{i-1}+g_{i-1}(a_i-1)\)。其中 \(g_i\) 為連續 $\times $ 的值的和。且 \(g_i=g_{i-1}\times a_i\) 閱讀全文

摘要： 游記 CSP2025。 已知我 CSP-S 2022 有 \(0\) 分，CSP-S 2023 有 \(45\) 分。 前一天 頹廢。 下午。 打了套 S 組模擬賽。T1 不會，是最小生成樹，啊？T2 是前后綴優化建圖，T3 是折半警報器，T4 是李超樹合并板子。 T1 寫的 \(O(n^2)\)， 閱讀全文

摘要： 省流：abc 沒質量；cf 沒實力。 AT_abc420_f kirinuki 你早說你是 \(O(NM)\) 的不就行了嘛。 一眼感覺不太好計數，但是 \(NM \le 5\times 10^6\) 就很有意思。直接上分治，我們去分治列，則現在只需要解決 \(l_y \in [l,mid]\lan 閱讀全文

摘要： 【不會計數，要吐了】 AT_arc174_e Existence Counting 考慮容斥。答案等價于：總的方案數 - 比 \(P\) 大的方案數 - 不包含 \(x\) 的方案數 + 比 \(P\) 大且不包含 \(x\) 的方案數。 第一個東西是 \(A_{n}^k\)，第二個是 \(\sum 閱讀全文

摘要： 貓樹 概述：類似于 ST表，可以支持快速查詢大部分靜態區間問題。 實現：考慮將詢問分治，對于每次分治到的區間 \([l,r]\)，處理出 \([l,mid]\) 中每個后綴的信息與 \((mid,r]\) 中每個前綴的信息。那么對于一個詢問 \([L,R] (L \le mid < R)\)，就可以 閱讀全文

摘要： 『我從來沒有會過任何串串科技。』 AC 自動機 相當于多個 KMP。也就是多個模板字符串上搞某種匹配問題。 建 AC 自動機 假設我有 \(n\) 個字符串為 \(abc,bcd,bd,c\)（\(n=4\)）。 首先我們對 \(n\) 個字符串建立 Trie 樹。長這樣：【圖】。 如果我們有個匹配 閱讀全文

摘要： 『我從來沒有會過任何數據結構。』 李超線段樹 這玩意是一個可以支持插入直線 \(y=kx+b\)，查詢 \(x=x_0\) 時 \(y\) 的最值的數據結構。 很簡單，我們記 \(f_x\) 為 \(x_0=x\) 時 \(y\) 的最值對應直線的下標。那么對于插入的一條直線 \(p\)，在位置 \ 閱讀全文

摘要： 第一次打省選。 CQ-148，你怎么知道我的考號是倒數第 \(3\) 個。 2025.2.28 住酒店，很唐的。這酒店貴在哪里。350 一晚，感覺和 100 一晚的沒區別。 打 div2。開場做 D1，感覺可以打表。然后并沒有看出什么明顯的規律，結果發現是弱智暴力。切了 A 之后收電腦。rk1400 閱讀全文

摘要： 點分治 額，就是你每次去找一棵樹的重心，然后將這棵子樹變成以這個重心為根的樹，再在這個樹上進行某些操作，就可以在 \(O(n\log n)\) 的時間復雜度遍歷到任意兩個點 \(u,v\) 在 \(P(u,v)\) 上某個點 \(x\) 為根時候的貢獻了。那么對于類似于求點對 \((u,v)\) 的 閱讀全文