摘要：
復習：線性篩、ST 表、圖論連通性、最短路板子、差分約束、樹剖、KMP、Manacher、高斯消元、歐拉路徑相關、笛卡爾樹、平衡樹、同余最短路. 學習：bitset、exgcd、各種數論神秘定理. 復習 學習 bitset 內部通過壓位來大幅優化空間和位運算效率，常數為 \(O({1\over w} 閱讀全文
posted @ 2025-10-31 09:12
Ydoc770
閱讀(10)
評論(0)
推薦(0)
摘要：
2025.6.27 ST 表 可以做到 \(O(n\log n)\) 預處理， \(O(1)\) 回答詢問. 原理是預處理 \(f_{i,j}\) 維護每個左端點 \(i\) 開始長度為 \(2^j\) 的區間信息，把每個詢問區間拆成可能重疊的兩個區間來回答. 所以 ST 表使用的前提是查詢重復信息 閱讀全文
posted @ 2025-07-11 15:19
Ydoc770
閱讀(18)
評論(1)
推薦(1)
摘要：
惡補基礎 DP. 2025.10.22 CF1061C 多樣性 轉移是經典的子序列 DP，考慮前 \(i\) 個數，子序列長度為 \(j\) 的方案數. 轉移： \[f_{i,j}=\begin{cases} f_{i-1,j-1}+f_{i-1,j}&j\mid a_i\\ f_{i-1,j}&o 閱讀全文
posted @ 2025-10-22 21:45
Ydoc770
閱讀(10)
評論(1)
推薦(0)
摘要：
最短路 P5304 [GXOI/GZOI2019] 旅行者 Hint：考慮從暴力優化. 圖論建模，路徑最短的兩個關鍵點編號一定不同，按照二進制位劃分成兩個集合跑最短路. 最暴力的方法我們可以枚舉關鍵點對跑最短路，時間復雜度 \(O(k^2m\log m)\). 顯然有很多點對是沒有任何意義的，考慮圖 閱讀全文
posted @ 2025-10-11 17:28
Ydoc770
閱讀(7)
評論(0)
推薦(0)
摘要：
前言 我太菜了，如有沒寫清楚的地方大家輕噴. 爆搜 P4467 k短路 Hint：沿用次短路的思路（P1491）. 不能經過重復的點是一個很強的限制，直接搜無論怎么剪枝都會被卡爆. 由于沒有負權邊，最短路必然不會經過重復的點，所以我們可以通過每次從最短路的第一條邊開始，刪掉一條邊重新跑最短路，就可以 閱讀全文
posted @ 2025-10-09 18:43
Ydoc770
閱讀(24)
評論(1)
推薦(1)
摘要：
CF2115 Div1 B 比較人類智慧. 后面操作會覆蓋前面的，考慮對序列 \(b\) 構造一種具有必要性的操作使得滿足題目限制，因為一個重要事實是序列 \(a\) 并不唯一，只要對于任意位置，在被覆蓋前沒有覆蓋其他位置的操作，或者其他位置之后還可以被覆蓋的，都滿足題意. 根據上述思考，可以發現： 閱讀全文
posted @ 2025-10-05 21:34
Ydoc770
閱讀(17)
評論(0)
推薦(0)
摘要：
非常好 hfu 開發的神秘打一場比賽改兩場題，使我的國慶假期旋轉. CF2129 Div1 B 逆序對考慮在較小的數處統計貢獻，枚舉序列里面每個數，一并枚舉逆序對的另一個數. \(p_i\) 有貢獻當且 \(i>j\)，\(2n-p_i\) 有貢獻當且僅當 \(j<i\)，取較小值即可. C 構造交 閱讀全文
posted @ 2025-10-03 15:48
Ydoc770
閱讀(19)
評論(0)
推薦(0)
摘要：
這篇博客只會寫一些題解，基礎內容和另外一些題，見： 容斥基礎 反演基礎 P4492 [HAOI2018] 蘋果樹 Hint：相當于求所有形態二叉樹的路徑和，考慮一條邊 \((u,fa_u)\) 的貢獻. 記子樹 \(u\) 的大小為 \(sz_u\)，把所有路徑和拆成每條邊會貢獻到多少條路徑里面，發 閱讀全文
posted @ 2025-10-01 19:38
Ydoc770
閱讀(20)
評論(1)
推薦(0)
摘要：
到處亂找的. 用到的數據結構在 NOIP 考綱內，主要是學習、鍛煉各種處理思路. 代碼的實現都不算困難. 倍增思想 P10198 [USACO24FEB] Infinite Adventure P Hint：跳的步數明顯提示倍增. 根據 \(\sum T_i\) 的限制直接預處理是三只 \(\log 閱讀全文
posted @ 2025-09-22 21:07
Ydoc770
閱讀(15)
評論(0)
推薦(0)
摘要：
在做這個題單：https://www.luogu.com.cn/training/629645 題目按照獵奇程度排序. CF1016F Road Projects Hint：抽出 \(1\sim n\) 的鏈 \(L\) 之后鏈上每個節點有一棵子樹，考慮根據子樹的狀態分討，對子樹進行處理. 要使最短 閱讀全文
posted @ 2025-09-07 18:02
Ydoc770
閱讀(14)
評論(0)
推薦(0)
摘要：
點與向量 點與向量二者類似，在平面直角坐標系中都可以用二元組 \((x,y)\) 來精確刻畫. 通過一些代數運算，我們可以刻畫向量之間的位置、方向關系. 這是計算幾何的核心. 點擊查看代碼 struct pt{ double x, y; pt(double _x = 0, double _y = 0 閱讀全文
posted @ 2025-08-13 15:53
Ydoc770
閱讀(15)
評論(1)
推薦(1)
浙公網安備 33010602011771號