摘要：
有時候見過的 trick 還是想不起來，感覺還是有必要做這個啊。 數據結構 時間相關的操作，可以： 考慮換維掃描線，即對序列維掃描線。例題：P7560，P3863，P8955。 考慮維護時間戳。例題：P13129，P7735。 區間問題有時可以僅利用線段樹結構維護信息。例題：P11536。 歷史版本 閱讀全文
posted @ 2025-10-12 16:29
P2441M
閱讀(10)
評論(0)
推薦(0)
摘要：
引入 支配對通常用來解決一類點對貢獻問題。具體來說，任意兩個對象構成一個點對，我們做一定范圍內的信息查詢時，就相當于查詢范圍內的點對的信息并。但是這樣點對的數量是 \(\mathcal{O}(n^2)\) 量級的，無法接受。 支配對優化這類問題的思想，就是只保留有效點對，通常題目中有性質使得有貢獻的 閱讀全文
posted @ 2025-09-24 15:58
P2441M
閱讀(45)
評論(0)
推薦(0)
摘要：
多項式基礎 為了與冪次相對應，下文中系數均采用 \(\text{0-based}\) 下標計數。 多項式的表示方法 我們習慣于將一個 \(n\) 次多項式 \(f(x)\) 表示為 \(f(x)=\sum_{i=0}^{n-1}a_ix^i\)。那么有沒有其他表示方法呢？ 我們不妨考慮代入 \(n\ 閱讀全文
posted @ 2025-03-01 21:53
P2441M
閱讀(89)
評論(0)
推薦(0)
摘要：
游記 Day -? 初賽獲得了 \(95\text{pts}\)，喜提 S > J。 Day -? 不報 J 組了。 Day -1 獲得了 \(0(100)+10+0+0=10(110)\) 分。 感覺自己 \(rp\leftarrow rp+\infty\) 了，這就是信心賽嗎?。。?！111。 D 閱讀全文
posted @ 2025-11-03 12:41
P2441M
閱讀(15)
評論(0)
推薦(0)
摘要：
建議讀者可以先去學習邊三連通分量，因為本題的做法很大程度上與邊三相關。 題意 給定一張 \(n\) 個點 \(m\) 條邊的無向簡單連通圖和 \(k\) 個二元組 \((a_i,b_i)\)。初始時所有邊權為 \(0\)，你需要選擇兩條不同的邊，將它們的邊權置為 \(1\)，使得 \(\sum\op 閱讀全文
posted @ 2025-11-01 09:35
P2441M
閱讀(2)
評論(0)
推薦(0)
摘要：
題意 對于兩個排列 \(p,q\)，定義它們的距離為將 \(p\) 變成 \(q\) 的最小操作次數，其中每次操作可以交換 \(p\) 中兩個元素的位置?，F在給定兩個長度為 \(n\) 的排列 \(p,q\)，其中一些位置被替換成了 \(0\)。對于每個 \(0\leq k\leq n-1\)，求補 閱讀全文
posted @ 2025-10-29 22:00
P2441M
閱讀(6)
評論(0)
推薦(0)
摘要：
題意 給定長度為 \(n\) 的排列 \(p\)，\(q\) 次詢問 \(l,r\)，求 \(p[l,r]\) 的 LIS 長度。\(1\leq n,q\leq 10^5\)。 題解 挺牛的題。 考慮如何刻畫 LIS。感覺上 DP 沒有什么前途，考慮另一種經典的 \(\mathcal{O}(n\lo 閱讀全文
posted @ 2025-10-20 22:11
P2441M
閱讀(14)
評論(0)
推薦(0)
摘要：
題意 給定 \(n\)，對于所有 \(0\leq x,y<n\) 求有多少長度為 \(n\) 的排列 \(p\) 滿足 \(\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]=x\) 且 \(\sum\limits_{i=1}^{n-1}[p^{-1}_i<p^{-1}_{i+ 閱讀全文
posted @ 2025-10-20 22:10
P2441M
閱讀(4)
評論(0)
推薦(0)
摘要：
題意 給定 \(n,m\)。對于 \(n\times m\) 的網格 \(a\)，定義 \[c_{i,j}=\left\lvert \sum_{k=1}^{n}a_{k,j}-\sum_{k=1}^{m}a_{i,k} \right\rvert \]現在給定 \(c\)，構造一組合法的 \(a\)。 閱讀全文
posted @ 2025-10-20 22:09
P2441M
閱讀(8)
評論(0)
推薦(0)
摘要：
題意 給定長度為 \(n\) 的字符串 \(s\) 和權值序列 \(v\)。求所有子串 \(s[l,r]\) 使得 \(s[l,r]\) 在所有子串去重后的字典序降序排名，恰好等于 \(v[l,r]\) 的區間和。\(1\leq n\leq 10^5\)。 題解 注意到固定左端點 \(l\) 后，隨 閱讀全文
posted @ 2025-10-20 22:09
P2441M
閱讀(4)
評論(0)
推薦(0)
摘要：
題意 給定長度為 \(n\) 的序列 \(a\) 和值域 \(V\)。有 \(m\) 次操作： 給定 \(l,r,x\)，將 \(a[l,r]\) 中 \(=x\) 的數改為 \(0\)。 給定 \(x\)，在序列末尾添加 \(x\)。 給定 \(l\)，查詢最小的 \(r\) 使得 \(a[l,r 閱讀全文
posted @ 2025-10-20 22:08
P2441M
閱讀(7)
評論(0)
推薦(0)
摘要：
題意 給定 \(C,X\)，構造一個 \(n(1\leq n<2^{60})\) 使得 \((n\oplus C)\bmod{n}=X\)，或報告無解。多測，\(1\leq T\leq 2\times 10^5\)，\(1\leq C,X<2^{30}\)。 題解 神人構造題。 顯然要有 \(n>X 閱讀全文
posted @ 2025-10-20 22:07
P2441M
閱讀(2)
評論(0)
推薦(0)
摘要：
題意 給定長度為 \(n\) 的序列 \(a\) 和一個數 \(X\)，求有多少種 \(a\) 的重排 \(b\) 使得 \(\sum\limits_{i=1}^n\max(b_i-i+1,0)\leq X\)。\(1\leq n\leq 100\)，\(1\leq a_i,X\leq 10^9\) 閱讀全文
posted @ 2025-10-20 22:04
P2441M
閱讀(17)
評論(0)
推薦(0)
浙公網安備 33010602011771號