摘要：
你好 閱讀全文
posted @ 2023-01-18 20:36
ChiFAN鴨
閱讀(363)
評論(4)
推薦(1)
摘要：
理論 我們需要一個數據結構維護樹上的問題，仿照序列上的問題，我們需要一個方法快速的刻畫出信息。 比如說線段樹就通過分治的方式來通過將一個區間劃分成 \(\log n\) 個區間并刻畫出這 \(\log n\) 個區間的信息。 然后我們考慮把這個東西放到樹上類比。你發現線段樹上每個非葉節點都有兩個兒子 閱讀全文
posted @ 2024-07-05 15:10
ChiFAN鴨
閱讀(869)
評論(0)
推薦(4)
摘要：
前言 如題。 值域分塊 顧名思義，就是在桶上分塊。 它的用處是把區間修改和區間詢問中某一種操作變成 \(O(1)\)，另一種變成 \(O(\sqrt n)\)。 所以經常用來輔助維護兩種操作數量嚴重不對等的數據結構。 典型代表有莫隊和根號分治。 這里看一個莫隊的例子。 如我們要維護一個二維數點。 那 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(46)
評論(0)
推薦(0)
摘要：
Part 1 求證：\(\frac{n}{\sum_{i=1}^{n}\frac{1}{y_i}} \leq ({\prod_{i=1}^{n}y_i})^{\frac{1}{n}}\) \(y_i\) 為正實數 \(n \geq 3\) 證明： 令 \(x_i\) = \(y_i^{\frac{1 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(579)
評論(2)
推薦(1)
摘要：
調了一小時結果發現爆 long long 了。 考慮數位 dp，具體來說，設計狀態 \(dp_{i,r_1,r_2,r_3,mx_1,mx_2,mx3_,c_1,c_2,c_3}\) 表示當前考慮到第 \(i\) 位，\(x_1,x_2,x_3\) 模 \(a_1,a_2,a_3\) 等于 \(r_ 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(38)
評論(0)
推薦(0)
摘要：
考慮一顆樹怎么染色。 每個子節點染成邊的顏色，如果與父親節點相同，就隨便染色（這條邊的限制已經被父親節點滿足）。 那么一定可以染色。 所以把原圖跑最小生成樹再按上述方法染色即可。 倘若原圖不連通，那么無解。 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(18)
評論(0)
推薦(0)
摘要：
后向差分 對于函數 \(f(x)\) 定義等距節點 \(x_k = x_0 + k \Delta x\)。 有： \[\Delta f(x_k) = f(x_{k}) - f(x_{k-1}) \]下文簡稱差分。 高階差分 一般來說，\(k\) 階差分的定義如下： \[\Delta^k a_n = 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(302)
評論(0)
推薦(0)
摘要：
先考慮這個式子： \[\sum_{j=1}^{M} |C_{k_{j}} - C_{k_{j+1}}| \]一定是在 \(C\) 有序時取到，具體證明很簡單各位讀者自己證明。 那么現在式子變成： \[\sum{V} + 2 \times({C_{\max} - C_{\min}}) \]這個時候一個 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(26)
評論(0)
推薦(0)
摘要：
首先這個查詢操作很迷，考慮先化簡查詢操作。 不難發現由于每次是加上一個逆的等差序列，因此一次操作完每個數與它的前驅之差一定會減少，因此加上等差序列的次數就等于全局每個數與它的前驅之差最大值。 又因為會排序去重，所以最后剩下來的數一定是最開始的數一路加過來的，至此我們發現答案就是全局每個數與它的前驅之 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(24)
評論(0)
推薦(0)
摘要：
做這個東西有兩個用處，一是初賽會考，二是考場上用 windows 哪里數組越界你都不知道直接 RE 爆炸。 sudo -s 輸入后填寫密碼獲得管理員權限。 cd 打開文件或者目錄，用法是 cd 目錄名。 cd / 退回到根目錄。 mkdir 創建一個目錄，使用方法為 mkdir 目錄名。 ls 顯示 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(55)
評論(0)
推薦(0)
摘要：
其實我們發現很多博弈論的動態規劃都是從后往前的，比如過河卒和本題。 這是因為從某種角度上來說這些動態規劃有后效性而無前效性。 所以設計狀態 \(dp_{i,j}\) 表示第 \(i\) 次操作 \(T\) 模 \(7\) 的余數為 \(j\) 的情況下能否走到 Takahashi 的勝利狀態。 然后 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(22)
評論(0)
推薦(0)
浙公網安備 33010602011771號