摘要：
通用 模板記憶 Trick 代碼易錯點 雜題： 構造/交互 雜題 雜題2 雜題3 貪心 IOI題目合集 NOI題目合集 Math 同余代數 數論函數和篩法 組合 計數 概率與期望 容斥 多項式 計算幾何 博弈論 線性代數 集合冪級數 DS 數據結構以及應用 分治類數據結構 DS 綜合做題筆記 Gra 閱讀全文
posted @ 2024-01-06 18:51
Mirasycle
閱讀(267)
評論(0)
推薦(1)
摘要：
基本技巧 01 串轉化為走網格圖。如果是 \(1\) 向右，\(0\) 向上的話，順序對數就是面積大小。 括號序列轉折線圖。可以和反射容斥結合。 區間包含/不交關系：樹。括號串也可以看成一堆區間。 走若干步回到自己，考慮置換環相關。\(i\to a_i\) 構建基環樹。 逆序對和偏序信息可以放到二維 閱讀全文
posted @ 2025-07-09 10:00
Mirasycle
閱讀(34)
評論(0)
推薦(0)
摘要：
模擬賽考了這題的加強版，我被肘飛了。模擬賽那題除了要判定是否合法之外，還要求構造。感覺還是有跡可循的啊。 這題一個很重要的 Trick 就是 LIS 的分層，我們設 \(f_i\) 表示以 \(p_i\) 結尾的 LIS 的長度。然后按照 \(f_i\) 進行分組，值相同的在一組。可以發現 \(f_ 閱讀全文
posted @ 2025-07-01 19:57
Mirasycle
閱讀(25)
評論(2)
推薦(1)
摘要：
模擬對數空間的圖靈機 基本概述 問題一般分類為判定型，構造型，計數型 \(\dots\) 可以構造模擬對數空間的圖靈機。\(M(x,y)\)，其中 \(x\) 是輸入，\(y\) 是需要判定的東西。計數題就是判定有多少個 \(y\) 合法，或者是統計 \(y\) 的容斥系數。比如說我們在統計序列數量 閱讀全文
posted @ 2025-06-19 09:56
Mirasycle
閱讀(31)
評論(0)
推薦(1)
摘要：
IOI2025 P13535 [IOI 2025] 紀念品 souvenirs 有意思的題目。但是不難，因為這題的約束太強了，導致你在每種情況下基本只能進行一種操作（有一些可能合法但是顯然無意義的操作就不去考慮了），所以順著這個模擬就可以 AC 了！ 記 \(co_i\) 表示 \(i\) 的價格。 閱讀全文
posted @ 2025-06-15 17:29
Mirasycle
閱讀(221)
評論(3)
推薦(0)
摘要：
NOI2024 P10785 [NOI2024] 集合 很牛的一道哈希題。不過感覺隨便試一試就能猜出結論，不太難。 首先嘗試刻畫一個條件來判定合法，經過我們手玩+嘗試/從集合大小為 \(1\) 開始思考并推廣，之后可以發現條件是 \(a\) 和 \(b\) 在 \([l,r]\) 內每個數的出現位置 閱讀全文
posted @ 2025-04-18 22:52
Mirasycle
閱讀(106)
評論(5)
推薦(0)
摘要：
P8095 [USACO22JAN] Cereal 2 S 顯然有一個二分圖匹配 \(+\) 拓撲排序的做法，這里記錄另一個巧妙的貪心線性做法。 考慮經典建圖模型，我們對于一頭奶牛建立一條邊，邊的兩個端點分別為它最喜歡的麥片和次喜歡的。 每條邊要去貪心地匹配其某個端點。多條邊可能共端點，所以我們需要 閱讀全文
posted @ 2025-04-01 22:36
Mirasycle
閱讀(47)
評論(1)
推薦(1)
摘要：
LOJ575 不等關系 考慮只有 \(<\) 和 \(？\)的時候的做法，直接就是集合劃分了，也就是 \(\dfrac{(n+1)!}{\prod len_i!}\)。 于是直接把大于號容斥掉就行了，替換成 \([?]-[<]\)，每次替換成 \(?\) 有一個 \(-1\) 的系數。 考慮帶著容斥 閱讀全文
posted @ 2025-03-30 21:07
Mirasycle
閱讀(56)
評論(0)
推薦(0)
摘要：
UOJ424. count 對于區間最大值位置本質不同的序列計數，可以直接轉化為笛卡爾樹計數。 考慮如何判定合法的笛卡爾樹，左子樹的值需要 \(<\) 根，右子樹需要 $\le $ 根。上述約束需要滿足左子樹深度 \(\le m\)，笛卡爾樹是二叉樹，可以轉化為括號序列計數。 首先 \(n<m\) 閱讀全文
posted @ 2025-02-23 20:18
Mirasycle
閱讀(66)
評論(0)
推薦(0)
摘要：
CF2062C Cirno and Operations 由于差分的特性，所以要么反翻轉一次，要么不翻轉。翻轉更多次效果是等效的。 翻轉一次就等價于最后差分出來的取相反數。于是直接暴力模擬即可。 QOJ9980. Boolean Function Reconstruction 有解的充要條件是對于 閱讀全文
posted @ 2025-02-23 20:18
Mirasycle
閱讀(26)
評論(0)
推薦(0)
摘要：
Meta Hacker Cup 2024 R1C Substantial Losses 初始 \(x=y=m\)。每過一秒 \(x\) 會等概率變成 \(x-1\) 或 \(x+1\)，并更新 \(y\gets \min(x,y)\)。特別地，如果此時 \(x=y+n\)，則 \(x\) 一定會變成 閱讀全文
posted @ 2025-02-21 00:45
Mirasycle
閱讀(33)
評論(0)
推薦(0)
浙公網安備 33010602011771號