摘要：
概率論 APIO 2024 講課內(nèi)容 基礎(chǔ) 樣本空間：隨機(jī)實(shí)驗(yàn)的所有結(jié)果構(gòu)成集合 \(\Omega\)。 \(e.g.\) 拋硬幣 \(\Omega=\{H,T\}\)，拋 \(n\) 次就是 \(\{H,T\}^n\)。 事件：是 \(\Omega\) 的子集。 概率空間：為 \(\Omega\) 閱讀全文
posted @ 2024-01-06 23:59
Mirasycle
閱讀(45)
評(píng)論(0)
推薦(0)
摘要：
樹(shù)的直徑 兩次 \(\operatorname{bfs}\) 可以記錄路徑，但邊權(quán)必須非負(fù)。 \(\operatorname{dp}\) 邊權(quán)任意，但不方便記錄路徑。 性質(zhì): 樹(shù)的直徑不唯一，所有直徑必定相交于中心處（可以為一條邊或者為一個(gè)點(diǎn)）。 維護(hù)動(dòng)態(tài)加點(diǎn)直徑，可見(jiàn) QOJ8235，只需要在可能 閱讀全文
posted @ 2024-01-06 23:56
Mirasycle
閱讀(78)
評(píng)論(0)
推薦(0)
摘要：
P9743 「KDOI-06-J」旅行 先寫(xiě)出來(lái)一個(gè) \(O(n^7)\) 計(jì)數(shù)方程 \[dp_{x,y,c,la,lb}=\sum\limits_{ca=0}^{la}\sum\limits_{cb=0}^{lb}dp_{x-1,y,c',la-ca+1,lb-cb}+dp_{x,y-1,c',l 閱讀全文
posted @ 2024-01-06 23:55
Mirasycle
閱讀(189)
評(píng)論(1)
推薦(2)
摘要：
P5309 [Ynoi2011] 初始化 修改次數(shù)與修改周期乘積 \(\le n\) 。啟發(fā)我們使用根號(hào)分治。修改次數(shù) $ \le T$ 時(shí)候直接暴力修改，修改次數(shù) \(\ge T\) 時(shí)候說(shuō)明每次修改的間隔很短。 可以維護(hù)每一個(gè)修改周期下的修改位置。其實(shí)題目本質(zhì)上就是在 \(mod\) \(x = 閱讀全文
posted @ 2024-01-06 23:53
Mirasycle
閱讀(39)
評(píng)論(0)
推薦(0)
摘要：
CDQ分治： 理解：用一個(gè) \(\log\) 的代價(jià)去掉一個(gè)維度/一層分治可以代替一個(gè)數(shù)據(jù)結(jié)構(gòu)。 應(yīng)用：三維偏序：第一維排序，第二維分治，第三維數(shù)據(jù)結(jié)構(gòu)。 細(xì)節(jié)：分治遍歷順序與數(shù)組何時(shí)排序 ？ 一般三維偏序采取后序遍歷，這樣可以保證在劃分區(qū)間前后兩段的時(shí)候，是依據(jù) cmp1 劃分的。下面演示一下其他 閱讀全文
posted @ 2024-01-06 23:51
Mirasycle
閱讀(77)
評(píng)論(2)
推薦(0)
摘要：
基本概述 對(duì)于原樹(shù)進(jìn)行實(shí)鏈剖分，原樹(shù)上每一個(gè)節(jié)點(diǎn)僅向其中一個(gè)兒子連實(shí)邊，向其他兒子連虛邊。 根據(jù)我們維護(hù)信息的需求，邊的虛實(shí)是可以動(dòng)態(tài)變化的，我們對(duì)于每條實(shí)邊構(gòu)成的鏈用一個(gè) DS 維護(hù)。而輕邊相當(dāng)于連接了兩個(gè)相鄰的 DS。實(shí)鏈剖分之后用平衡樹(shù)來(lái)維護(hù)一條鏈，而由于平衡樹(shù)正好是樹(shù)的形態(tài)，所以我們可以直接 閱讀全文
posted @ 2024-01-06 23:49
Mirasycle
閱讀(50)
評(píng)論(0)
推薦(0)
摘要：
普適做題思路總結(jié) 先嘗試簡(jiǎn)化版，再擴(kuò)展至復(fù)雜版 UVA1437 string painter 先考慮 空串 $\to $ B串，再計(jì)算出上述結(jié)果后在此基礎(chǔ)上，解決A串 $\to $ B串。 Acwing146. 序列 多個(gè)序列操作化簡(jiǎn)為兩個(gè)，最后數(shù)學(xué)歸納法證明 \(n\) 個(gè)成立，并且可以通過(guò)兩兩處 閱讀全文
posted @ 2024-01-06 23:41
Mirasycle
閱讀(181)
評(píng)論(1)
推薦(1)
摘要：
P1360 [USACO07MAR] Gold Balanced Lineup G 咋一看挺難轉(zhuǎn)化為一個(gè)有效狀態(tài)供后面查詢(xún)的。這里有兩種思路可以引導(dǎo)至正解。 最樸素的列式子，\(sum_{i,k_{1}}-sum_{j,k1}=sum_{i,k2}-sum_{j,k2}=......\) 的時(shí)候方能 閱讀全文
posted @ 2024-01-06 19:29
Mirasycle
閱讀(59)
評(píng)論(2)
推薦(1)
摘要：
通用 模板記憶 Trick 代碼易錯(cuò)點(diǎn) 雜題： 構(gòu)造/交互 雜題 雜題2 雜題3 貪心 IOI題目合集 NOI題目合集 Math 同余代數(shù) 數(shù)論函數(shù)和篩法 組合 計(jì)數(shù) 概率與期望 容斥 多項(xiàng)式 計(jì)算幾何 博弈論 線性代數(shù) 集合冪級(jí)數(shù) DS 數(shù)據(jù)結(jié)構(gòu)以及應(yīng)用 分治類(lèi)數(shù)據(jù)結(jié)構(gòu) DS 綜合做題筆記 Gra 閱讀全文
posted @ 2024-01-06 18:51
Mirasycle
閱讀(267)
評(píng)論(0)
推薦(1)
浙公網(wǎng)安備 33010602011771號(hào)