摘要：
概念 點分治用于解決有一定要求的鏈的計數。 對于點 $u$ 的子樹的問題，可以將答案分為： 經過點 $u$ 不經過點 $u$ 第一種可以用桶加暴力。枚舉一端的長度，用桶計算另一端長度；第二種分到子樹中解決即可。 注意到，在隨機選根的時候該算法表現不優秀，但若根為重心，因為每次子樹大小都減少一半，所以 閱讀全文
posted @ 2023-05-04 18:26
lizhous
閱讀(17)
評論(0)
推薦(0)
摘要：
概念 最大流: 在一個網絡圖上，每個邊有流量限制，假如起始點有無線流量，求最多能有多少流量流到終點。 增廣路: 一條從起始點到終點了路徑，可以流流量。 算法 Ford-Fulkerson算法 解決這個問題，可以用Ford-Fulkerson算法。 該算法的核心就是尋找增廣路。每找到一條增廣路，就給它 閱讀全文
posted @ 2023-05-04 18:26
lizhous
閱讀(21)
評論(0)
推薦(0)
摘要：
1.基本模型 數位dp，即以數的每一位作為狀態進行dp的算法。通常狀態為 $f_{i,0-9}$ 表示第 $i$ 為取 $0-9$ 時的dp值。通常時間復雜度為 $log_{10}n$ ，十分優秀。 2.套路 求區間合法類的題，使用容斥思想思想求解，即 $[1,r]-[1,l-1]$ dp式子一般很 閱讀全文
posted @ 2023-05-04 18:26
lizhous
閱讀(56)
評論(0)
推薦(0)
摘要：
概念 線性基是一個集合。 從原集合中選取任意數都能通過線性基中的數異或得到。 本質上是對集合的壓縮 性質 所有數字沒有最高位相同的 集合大小為 $\log_2$ 級別。 操作 排查：若線性基內有最高位相等的，讓其相異或，并繼續排查直到沒有可操作的數。 若原集合內有 $0$ 線性基無法實現。 實現 v 閱讀全文
posted @ 2023-05-04 18:25
lizhous
閱讀(18)
評論(0)
推薦(0)
摘要：
概念 莫隊是一種幽雅的暴力。用于處理區間問題。 核心思想就是把詢問離線下來，然后維護雙指針按一定順序處理每個詢問。精髓就在于一定順序。 首先確定一個塊長，然后將左端點的位置除以塊長，把詢問分成若干塊。在每個塊里按右端點排序。發現當塊長為 $\sqrt n$ 時兩個指針各移動 $n\sqrt n$ 次 閱讀全文
posted @ 2023-05-04 18:25
lizhous
閱讀(26)
評論(0)
推薦(0)
摘要：
一棵樹，支持： 路徑加 單點查詢 一般樹上鏈的問題使用樹鏈剖分解決。 重鏈剖分 前置知識 LCA，線段樹 定義 重兒子：所有兒子中子樹最大的兒子為重兒子 重邊：重兒子之間的連邊 重鏈：若干重兒子連成的鏈 性質 一棵樹可以被剖成若干重鏈。 優先遍歷重兒子，所有重鏈的dfs序連續。 重鏈數量不多于 $\ 閱讀全文
posted @ 2023-05-04 18:25
lizhous
閱讀(29)
評論(0)
推薦(0)
摘要：
概念 序列的母函數（生成函數）是一種形式冪級數。其每一項的系數可以提供關于這個序列的信息，使用母函數解決問題。 如：序列 $a$ 的生成函數為 $G(x)=\sum\limits_{i=1}^{n}a_if_i(x)$。其中 $f_i(x)$ 是無實際意義的，具體取值看題目要求。但有一些一般取值。 閱讀全文
posted @ 2023-05-04 18:25
lizhous
閱讀(60)
評論(0)
推薦(0)
摘要：
拉格朗日插值學習筆記 概念 拉格朗日插值用于擬合一個函數?？梢酝ㄟ^已知函數中的點擬合出函數。若為 $n$ 次函數，則需要多于 $n+1$ 個點。 做法 考慮構造 $n+1$ 個函數，第 $i$ 個函數 $f_i$ 對應點 $i$ 滿足 $f_i(X_i)=Y_i$ 且對于其他的點 $j(i\neq 閱讀全文
posted @ 2023-05-04 18:24
lizhous
閱讀(41)
評論(0)
推薦(0)
摘要：
1.矩陣乘法 設矩陣有 $H$ 行，$L$ 列，則兩個矩陣 $MatA,MatB$ 進行乘法，需要滿足 $MatA.L=MatB.H$。則結果矩陣 $MatR_{i,j}=\sum\limits^{n}{z=1}MatA{i,z}*MatB_{z,j}$。 性質： 結合律，但不滿足交換律。 mat 閱讀全文
posted @ 2023-05-04 18:24
lizhous
閱讀(25)
評論(0)
推薦(0)
摘要：
## 概念 多項式乘法時，我們發現暴力乘十分緩慢，但是點值乘十分快速?？紤]求 $A$ 和 $B$ 的卷積。 一個 $n$ 次多項式可以被 $n+1$ 個點確定。 設多項式 $A(x)$ 的系數為 $(a_0,a_1,\cdots,a_n)$ 對其奇偶分類得 $A(x)=\sum\limits a_{ 閱讀全文
posted @ 2023-05-04 18:23
lizhous
閱讀(28)
評論(0)
推薦(0)
浙公網安備 33010602011771號