摘要：
2025年我新學的東西 DP 05-19 Slope Trick 08-07 Knuth 決策單調性優化。 字符串 04-06 SAM 后綴自動機。 04-17 \(O(n\log n)\) 后綴排序。 04-19 擴展 KMP。 04-19 Manacher。 07-09 回文自動機（回文樹） 0 閱讀全文
posted @ 2025-03-06 22:18
dengchengyu
閱讀(34)
評論(0)
推薦(0)
摘要：
10-31 題 目錄10-31 題G - Minimum PermutationG - P-smooth numberG - Dream TeamP14254 分割（divide） - 洛谷 G - Minimum Permutation 可以用一個棧維護當前選了哪些數，從前往后考慮，首先檢查 \( 閱讀全文
posted @ 2025-11-03 22:36
dengchengyu
閱讀(4)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-11-03 22:26
dengchengyu
閱讀(0)
評論(0)
推薦(0)
摘要：
CSP-S 2025 題解 club 先貪心，每個數都選取 \(\max\)?？紤]調整法解決 \(n/2\) 的限制，找到超過 \(n/2\) 的集合，按照次大值減去最大值的大小，從小到大把它們調整成次大值即可。復雜度 \(O(n\log n)\)（需要排序）。 road 先把初始 \(m\) 條邊 閱讀全文
posted @ 2025-11-03 22:19
dengchengyu
閱讀(8)
評論(0)
推薦(0)
摘要：
CF Pinely Round 5(#2161) 總結 A~D A：每次都取到盡量?。▽?\(0\) 取 max）即最優。 B：特判掉 2*2 的情況，剩下的情況只能是一條不斷轉彎的「斜線」，此時所有點都在兩條相鄰的斜線上，只需判斷 \(x+y\) 的最值，或 \(x-y\) 的最值即可。 C：猜想 閱讀全文
posted @ 2025-11-03 22:03
dengchengyu
閱讀(9)
評論(0)
推薦(0)
摘要：
CSP-S 2025 總結 中午沒有睡著，但是影響不大。 前兩題 50 分鐘過完，T2 寫了一個 \(O(2^Kn(\log n+\alpha(n))\) 的做法，賽后發現可以歸并把排序的 log 去掉。 然后先想 T3，考慮對 \(s_1,s_2\) 建 AC 自動機，然后枚舉 \(t\) 中替換 閱讀全文
posted @ 2025-11-02 19:23
dengchengyu
閱讀(1)
評論(0)
推薦(0)
摘要：
10-29 題 目錄10-29 題abc248_g G - GCD cost on the treeProblem - 1842G - Codeforcesabc231_g G - Balls in BoxesP2455 [SDOI2006] 線性方程組 - 洛谷abc249_g G - Xor C 閱讀全文
posted @ 2025-10-31 16:34
dengchengyu
閱讀(4)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-31 15:52
dengchengyu
閱讀(0)
評論(0)
推薦(0)
摘要：
10-30 題 目錄10-30 題Joke - 題目 - QOJ.ac\(k\)-coloring - 題目 - QOJ.acPermutation Recovery - 題目 - QOJ.acExcluded Min - 題目 - QOJ.acAngle Beats 2.0 - 題目 - QOJ. 閱讀全文
posted @ 2025-10-31 15:52
dengchengyu
閱讀(4)
評論(0)
推薦(0)
摘要：
AtCoder AGC074 總結 A 賽時一個多小時通過?？紤]特殊點。由于是有向無環圖，考慮入度為 0 的點?？紤]怎么區分多個入度為 0 的點，由于這些點中一定有一個點取到當前可選值域的最小值，所以想到 select 除了最小值以外的點，此時自然可以確認最小值所在的點，即對答案的貢獻為零度點個數減 閱讀全文
posted @ 2025-10-27 21:00
dengchengyu
閱讀(18)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-27 20:40
dengchengyu
閱讀(0)
評論(0)
推薦(0)
摘要：
樹狀數組 區間加 & 區間和 小記 考慮差分數組的變化，即 \(d_i=a_i-a_{i-1}\)。 那么區間加時，會使 \(d_l\gets d_l+val,d_{r+1}\gets d_{r+1}-val\)。 考慮求區間和，轉化為求前綴的和，即求 \[\begin{aligned} \sum 閱讀全文
posted @ 2025-10-25 22:43
dengchengyu
閱讀(3)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-25 22:29
dengchengyu
閱讀(0)
評論(0)
推薦(0)
摘要：
CF Round 1046(#2135) 總結 A 可以 DP，用 vector 存下這個數出現的位置。 B 考慮移動到無限遠處，如果移到左下角，容易發現離的最近的點就是離 \((-10^9,-10^9)\) 最近的點。這樣就能確定一條直線（確定 \(x+y\)）。 同理移動到左上角又確定一條直線（ 閱讀全文
posted @ 2025-10-24 21:45
dengchengyu
閱讀(3)
評論(0)
推薦(0)
摘要：
10-23 好題選講總結 目錄10-23 好題選講總結P13779 「o.OI R2」試機題 - 洛谷P8861 線段 - 洛谷P10322 高潔（Purity） - 洛谷ABC242 Ex - Random PaintingYet Another 偉大的數據結構問題 - 云斗學院【UR #32】王 閱讀全文
posted @ 2025-10-24 21:00
dengchengyu
閱讀(7)
評論(0)
推薦(0)
摘要：
10-20 Extra-Problem 總結 AtCoder abc280_g 發現點 \((x,y)\) 的距離實際上是 \(\max(|x|,|y|,|x-y|)\)。由于坐標是可平移的，所以 \((x_1,y_1),(x_2,y_2)\) 的距離為 \(\max(|x_1-x_2|,|y_1- 閱讀全文
posted @ 2025-10-20 22:45
dengchengyu
閱讀(7)
評論(0)
推薦(0)
摘要：
AtCoder AGC047 總結 A 由于小數位最多九位，我們先乘 \(10^9\)，轉化為求 \(10^{18}\mid a_ia_j\) 的個數。 考慮分解質因數，要求 \(2,5\) 的次數都至少為 \(18\) 即可。時間 \(18^2\times n\)。 B 一個串可以變成的串形如，選 閱讀全文
posted @ 2025-10-20 16:55
dengchengyu
閱讀(9)
評論(0)
推薦(0)
摘要：
CF Global Round 29(#2147) 總結 ? A void solve() { int x,y; cin>>x>>y; if(x<y) return cout<<"2\n",void(); --x; if(y<x&&y>1) return cout<<"3\n",void(); co 閱讀全文
posted @ 2025-10-17 22:47
dengchengyu
閱讀(7)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-17 19:20
dengchengyu
閱讀(0)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-17 19:15
dengchengyu
閱讀(0)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-17 18:34
dengchengyu
閱讀(0)
評論(0)
推薦(0)
摘要：
AtCoder arc208 總結 A 猜想 SG 是 \(a_1\oplus a_2\oplus \cdots \oplus a_n \oplus (a_1 \lor a_2 \lor \cdots \lor a_n)\)。然后發現過了。 B 發現當 \(a_i=\lfloor\dfrac{a_{ 閱讀全文
posted @ 2025-10-17 18:34
dengchengyu
閱讀(15)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-17 18:33
dengchengyu
閱讀(0)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-17 18:32
dengchengyu
閱讀(0)
評論(0)
推薦(0)
摘要：
最小割樹 小記 算法 問題如下：給定一張無向圖（\(n\le 500,m\le 1500\)），點有點權，\(Q\) 次（\(Q\le n^2\)）詢問兩點 \(S,T\) 之間的最小割。 可以建出最小割樹，建樹過程如下： 對于給定的點集，隨便找兩個點 \(S,T\) 求出 \(S,T\) 在原圖上 閱讀全文
posted @ 2025-10-16 21:55
dengchengyu
閱讀(3)
評論(0)
推薦(0)
摘要：
CF Round 1055(#2152) 總結 VP 時過了 ABCE。 A. Increase or Smash 對于每一種數字都要操作兩次，先把小于自己的清零，然后再加操作。 第一次不用清零，因此答案為 \(2\times 種類數-1\)。 復雜度 \(O(\sum n)\)。 B. Catch 閱讀全文
posted @ 2025-10-13 22:43
dengchengyu
閱讀(5)
評論(0)
推薦(0)
摘要：
CF Round 1058(#2159) 總結 A 從左到右掃一次，維護一個待詢問集合 \(S\)，若 \(q(S\cup i)=v\ne 0\) 則 \(a_i=v\) 第二次出現，否則將 \(i\) 加入 \(S\)，這樣所有 \(1\sim n\) 都確定了一個位置。 對于沒有被確定的位置，用 閱讀全文
posted @ 2025-10-13 22:42
dengchengyu
閱讀(6)
評論(0)
推薦(0)
摘要：
AtCoder ARC207 總結 B 構造題。觀察樣例，發現 \(i\) 恰好三步到達 \(n-i\)，其他點都是兩步到達，這使我們想到 \(n\) 為偶數時的解法：分成 \(\le n/2\) 和 \(>n/2\) 的兩部分點，對于其中一部分，我們讓一個點恰好兩步到達恰好一個或兩個點。而對于兩部 閱讀全文
posted @ 2025-10-07 21:52
dengchengyu
閱讀(41)
評論(0)
推薦(0)
該文被密碼保護。 閱讀全文
posted @ 2025-10-07 17:13
dengchengyu
閱讀(0)
評論(0)
推薦(0)
摘要：
網絡流復雜度 小記 記 \(E\) 為邊數，\(V\) 為點數，\(F\) 為流量。 Dinic 最大流：\(O(V^2E)\)。 單位容量網絡下 Dinic 最大流：\(O(E\sqrt V)\)。 二分圖匹配下 Dinic 最大流：\(O(E\sqrt V)\)。 最小費用最大流：\(O(FEV 閱讀全文
posted @ 2025-10-05 19:58
dengchengyu
閱讀(6)
評論(0)
推薦(0)
摘要：
上下界網絡流小記 每條邊有流量的上下界，記下界為 \(L\)，上界為 \(R\)。 無源匯上下界可行流 要求給每條邊標定一個范圍內流量使得每個點流量平衡。 考慮先給每條邊流 \(L\)。對于一個點記入度減出度為 \(d\)，若 \(d>0\) 則從源點向它連容量 \(d\) 的邊；否則從它向新建匯點 閱讀全文
posted @ 2025-10-05 19:57
dengchengyu
閱讀(9)
評論(0)
推薦(0)
摘要：
無向圖三元環計數 先給每條邊定向：由度數小的點連向度數大的點，若度數相等則按編號。 這樣一個合法的三元環 \((x,y,z)\) 一定形如 \(x\to y,x\to z,y\to z\)。 考慮枚舉 \(x\)，把所有 \(z\) 打上標記，再枚舉 \(y\) 與 \(y\) 的出邊 \(w\)， 閱讀全文
posted @ 2025-10-05 19:04
dengchengyu
閱讀(8)
評論(0)
推薦(0)
摘要：
歐拉路徑 & 歐拉圖 小記 P7771 【模板】歐拉路徑 歐拉路徑：一個圖中經過每條邊恰好一次的路徑，允許經過重復點。 歐拉回路：起點與終點相同的歐拉路徑。 對于連通圖，歐拉路徑有如下判定： 對于無向圖，恰好有兩個點度數為奇數時，存在起點與終點不同的歐拉路徑，且起點與終點就是這兩個奇度數的點。 對于 閱讀全文
posted @ 2025-10-05 17:24
dengchengyu
閱讀(8)
評論(0)
推薦(0)
浙公網安備 33010602011771號