一念行空の幻想空間

摘要： 突然發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)太菜了，這里記錄一些數(shù)據(jù)結(jié)構(gòu)題。 CF1085F Rock-Paper-Scissors Champion 一排的人，玩石頭剪刀布，預(yù)先設(shè)定好手型。 你可以做局，讓某相鄰兩個(gè)人比，平局做局一個(gè)勝者。 問有多少人可以被你做局成冠軍。帶修。 以石頭為例，一個(gè)人可以被做局的充要條件：左右兩 閱讀全文

摘要： 復(fù)習(xí)筆記當(dāng)然主要是做題了。 主要是我當(dāng)時(shí)也沒記什么筆記，只能從我做過的題復(fù)習(xí)了。 容斥 總計(jì) 不管什么題都先想容斥?。。?交集并集嘗試容斥！??！ 條件嘗試反面去容斥！?。?條件嘗試去掉去容斥！??！ 哪怕是數(shù)據(jù)范圍看著不能直接容斥的題，如果有一些特殊性質(zhì)保證容斥層數(shù)不多也是可以容斥的?。?！最常見的就是 閱讀全文

摘要： 概率論 基本概念 樣本空間 $\Omega $：隨機(jī)現(xiàn)象所有可能出現(xiàn)的結(jié)果。元素稱之為樣本點(diǎn)。 隨機(jī)事件：樣本空間的一個(gè)子集。稱一個(gè)隨機(jī)事件發(fā)生了當(dāng)且僅當(dāng)其內(nèi)部的某一樣本點(diǎn)發(fā)生了。 隨機(jī)事件是子集，我們稱 \(A\) \(B\) 兩事件的交是 \(AB\)，意指同時(shí)發(fā)生；并是 \(A+B\) 意指分 閱讀全文

摘要： 主要參考了 oi-wiki。 線性方程組 首先搞清楚線性方程組的本質(zhì)?；蛘哒f是搞清楚矩陣的本質(zhì)。 \[\left\{\begin{matrix} A_1x+B_1y+C_1z = S_1 \\ A_2x+B_2y+C_2z = S_2 \\ A_3x+B_3y+C_3z = S_3 \end{mat 閱讀全文

摘要： 這應(yīng)該是我學(xué)習(xí)的最后一個(gè)還在我舒適圈的算法了。后面那一些和數(shù)學(xué)強(qiáng)相關(guān)的算法都很沒意思。 建議閱讀。推薦閱讀。 圖源皆是上面的，侵刪。 簇（cluster） 基于分治思想將樹分成可以遞歸合并的結(jié)構(gòu)，稱之為簇。 類比區(qū)間，我們希望一個(gè)簇可以只有兩個(gè)出點(diǎn)。稱向外出的點(diǎn)為界點(diǎn)。 簇體現(xiàn)在樹上就是一個(gè)子樹（無 閱讀全文

摘要： 可以說幾百年沒去練過的東西了。但事實(shí)證明還挺有用的。 Meet in the Middle 以前一直沒想通過雙向搜索是怎么優(yōu)化復(fù)雜度的。 例題 1 我稱其為合法子集計(jì)數(shù)問題。 雙向搜索就是把集合劈成兩半，兩邊分別枚舉子集，然后再記兩兩匹配的合法關(guān)系。 當(dāng)后者可以快速統(tǒng)計(jì)時(shí)，雙向搜索就優(yōu)化了復(fù)雜度。 閱讀全文

摘要： 差分約束 處理一類不等式限制諸如 \(x_i - x_j\le c_{i,j}\) 的限制。 移項(xiàng)過后就是 \(x_i\le x_j+c_{i,j}\)，與最短路的松弛類似。于是建圖，連邊，然后跑最短路，有負(fù)環(huán)就退出。不保證有解的情況下使用 SPFA，否則使用 Dij。 同余最短路 同樣是將一類問題 閱讀全文

摘要： 2023 國(guó)家集訓(xùn)隊(duì)論文 xtq《一類基礎(chǔ)子串?dāng)?shù)據(jù)結(jié)構(gòu)》閱讀筆記。 主要借鑒了 crashed 的學(xué)習(xí)筆記 和 127 的學(xué)習(xí)筆記，侵刪。 雖然但是這個(gè)名字是真的樸素。明明可以取一些好聽的名字的。按照翻譯應(yīng)該叫做 \(\text{BSS}\)（Basic Substring Structure）。 閱讀全文

摘要： 感覺都挺好玩的。 不會(huì)都寫。會(huì)都不寫。 Border 論做法 border 可以被劃分成 log 個(gè)等差數(shù)列。配合 dbf 表等性質(zhì)可以存儲(chǔ)下整個(gè)子串的 border。 復(fù)雜度 \(O(n\log n)\)，是最優(yōu)的做法。不建議在沒對(duì) SA 和 border 論有充分理解的情況下使用。 鏈分治做法 閱讀全文

摘要： 推薦扶蘇的 FFT 題解，講得很不錯(cuò)。 一些記號(hào) 變量、數(shù)組會(huì)使用小寫字母。 多項(xiàng)式會(huì)使用大寫字母。一般大小寫對(duì)應(yīng)，如 \(A\) 是 \(a\) 的普通生成函數(shù)。\(A(x)\) 表示 \(x\) 代入后的取值。一般來說，生成函數(shù)會(huì)表示成關(guān)于 \(x\) 的冪指數(shù)形式。 多項(xiàng)式間的計(jì)算分為卷積（\ 閱讀全文