摘要：
前言 如題。 值域分塊 顧名思義，就是在桶上分塊。 它的用處是把區(qū)間修改和區(qū)間詢問(wèn)中某一種操作變成 \(O(1)\)，另一種變成 \(O(\sqrt n)\)。 所以經(jīng)常用來(lái)輔助維護(hù)兩種操作數(shù)量嚴(yán)重不對(duì)等的數(shù)據(jù)結(jié)構(gòu)。 典型代表有莫隊(duì)和根號(hào)分治。 這里看一個(gè)莫隊(duì)的例子。 如我們要維護(hù)一個(gè)二維數(shù)點(diǎn)。 那 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(46)
評(píng)論(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\) 為正實(shí)數(shù) \(n \geq 3\) 證明： 令 \(x_i\) = \(y_i^{\frac{1 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(579)
評(píng)論(2)
推薦(1)
摘要：
調(diào)了一小時(shí)結(jié)果發(fā)現(xiàn)爆 long long 了。 考慮數(shù)位 dp，具體來(lái)說(shuō)，設(shè)計(jì)狀態(tài) \(dp_{i,r_1,r_2,r_3,mx_1,mx_2,mx3_,c_1,c_2,c_3}\) 表示當(dāng)前考慮到第 \(i\) 位，\(x_1,x_2,x_3\) 模 \(a_1,a_2,a_3\) 等于 \(r_ 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(38)
評(píng)論(0)
推薦(0)
摘要：
后向差分 對(duì)于函數(shù) \(f(x)\) 定義等距節(jié)點(diǎn) \(x_k = x_0 + k \Delta x\)。 有： \[\Delta f(x_k) = f(x_{k}) - f(x_{k-1}) \]下文簡(jiǎn)稱差分。 高階差分 一般來(lái)說(shuō)，\(k\) 階差分的定義如下： \[\Delta^k a_n = 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(302)
評(píng)論(0)
推薦(0)
摘要：
考慮一顆樹(shù)怎么染色。 每個(gè)子節(jié)點(diǎn)染成邊的顏色，如果與父親節(jié)點(diǎn)相同，就隨便染色（這條邊的限制已經(jīng)被父親節(jié)點(diǎn)滿足）。 那么一定可以染色。 所以把原圖跑最小生成樹(shù)再按上述方法染色即可。 倘若原圖不連通，那么無(wú)解。 閱讀全文
posted @ 2024-02-27 18:13
ChiFAN鴨
閱讀(18)
評(píng)論(0)
推薦(0)
摘要：
先考慮這個(gè)式子： \[\sum_{j=1}^{M} |C_{k_{j}} - C_{k_{j+1}}| \]一定是在 \(C\) 有序時(shí)取到，具體證明很簡(jiǎn)單各位讀者自己證明。 那么現(xiàn)在式子變成： \[\sum{V} + 2 \times({C_{\max} - C_{\min}}) \]這個(gè)時(shí)候一個(gè) 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(26)
評(píng)論(0)
推薦(0)
摘要：
首先這個(gè)查詢操作很迷，考慮先化簡(jiǎn)查詢操作。 不難發(fā)現(xiàn)由于每次是加上一個(gè)逆的等差序列，因此一次操作完每個(gè)數(shù)與它的前驅(qū)之差一定會(huì)減少，因此加上等差序列的次數(shù)就等于全局每個(gè)數(shù)與它的前驅(qū)之差最大值。 又因?yàn)闀?huì)排序去重，所以最后剩下來(lái)的數(shù)一定是最開(kāi)始的數(shù)一路加過(guò)來(lái)的，至此我們發(fā)現(xiàn)答案就是全局每個(gè)數(shù)與它的前驅(qū)之 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(24)
評(píng)論(0)
推薦(0)
摘要：
做這個(gè)東西有兩個(gè)用處，一是初賽會(huì)考，二是考場(chǎng)上用 windows 哪里數(shù)組越界你都不知道直接 RE 爆炸。 sudo -s 輸入后填寫(xiě)密碼獲得管理員權(quán)限。 cd 打開(kāi)文件或者目錄，用法是 cd 目錄名。 cd / 退回到根目錄。 mkdir 創(chuàng)建一個(gè)目錄，使用方法為 mkdir 目錄名。 ls 顯示 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(56)
評(píng)論(0)
推薦(0)
摘要：
其實(shí)我們發(fā)現(xiàn)很多博弈論的動(dòng)態(tài)規(guī)劃都是從后往前的，比如過(guò)河卒和本題。 這是因?yàn)閺哪撤N角度上來(lái)說(shuō)這些動(dòng)態(tài)規(guī)劃有后效性而無(wú)前效性。 所以設(shè)計(jì)狀態(tài) \(dp_{i,j}\) 表示第 \(i\) 次操作 \(T\) 模 \(7\) 的余數(shù)為 \(j\) 的情況下能否走到 Takahashi 的勝利狀態(tài)。 然后 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(22)
評(píng)論(0)
推薦(0)
摘要：
發(fā)現(xiàn)一個(gè)神奇的事實(shí)：顯然不限制交換次數(shù)可以實(shí)現(xiàn)交換任意字符。 因此可以直接判斷字符集是否相等。 在考慮哪些地方可以交換。 根據(jù)題意可知可以交換的區(qū)間為 \([1,n - k]\) 以及 \([k + 1,n]\)。 不能交換的區(qū)間是靜態(tài)的，所以判斷是否相等即可。 代碼實(shí)現(xiàn)很簡(jiǎn)單，就不給出了。 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(14)
評(píng)論(0)
推薦(0)
摘要：
寫(xiě)了一小時(shí)結(jié)果被卡常了（笑。 考慮新加入一個(gè)數(shù)什么時(shí)候會(huì)產(chǎn)生貢獻(xiàn)，或者什么時(shí)候不會(huì)產(chǎn)生貢獻(xiàn)。 發(fā)現(xiàn)當(dāng)一個(gè)數(shù)的位置與他前一次出現(xiàn)時(shí)的位置所構(gòu)成的區(qū)間內(nèi)假若有一個(gè)比它小的數(shù)那么就不得不對(duì)這個(gè)數(shù)新進(jìn)行一次操作而不能共用。 又因?yàn)樵儐?wèn)一個(gè)值域范圍內(nèi)的貢獻(xiàn)，所以考慮把這個(gè)范圍內(nèi)最大的小于這個(gè)數(shù)本身的數(shù)找出來(lái)就 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(23)
評(píng)論(0)
推薦(0)
摘要：
既然是求最大值而且有收益有代價(jià)，所以考慮建立一個(gè)最大權(quán)封閉子圖模型。 收益 正的美味值是收益，所以假若 \(d_{i,j} \geq 0\) 則建邊 \((s,pos_{i,j},d_{i,j})\)。 代價(jià) 負(fù)的美味值是代價(jià)，所以假若 \(d_{i,j} < 0\) 則建邊 \((pos_{i,j 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(22)
評(píng)論(0)
推薦(0)
摘要：
其實(shí)很簡(jiǎn)單，把之前隨機(jī)數(shù)據(jù)的解法中維護(hù)塊內(nèi)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)換成約束 RMQ，這樣子復(fù)雜度 嚴(yán)格 單點(diǎn)修改 \(O(\sqrt n)\)，區(qū)間查詢 \(O(1)\),線性空間。 唯一的問(wèn)題是常數(shù)太大了，有 \(4\) 倍常數(shù)。 #include <bits/stdc++.h> using namespa 閱讀全文
posted @ 2024-02-27 18:12
ChiFAN鴨
閱讀(59)
評(píng)論(0)
推薦(1)
摘要：
\(x = 2^k\) 是好做的，每次以 \(2^{k-1}\) 為因數(shù)即可。 對(duì)于其他情況，考慮每次讓 \(x\) 減去其二進(jìn)制下最低位的 \(1\) 直至變成 \(2^k\)。 這種策略下顯然每個(gè)數(shù)只會(huì)在以上兩個(gè)大步驟下取到，故每個(gè)數(shù)使用不超過(guò) \(2\) 次。 同時(shí)操作次數(shù)在 \(O(\log 閱讀全文
posted @ 2024-02-27 18:11
ChiFAN鴨
閱讀(19)
評(píng)論(0)
推薦(0)
摘要：
考慮把每個(gè)字符串的前 \(k\) 位和后 \(k\) 位看成點(diǎn)，字符串看成邊，那么一個(gè)字符串前綴后綴至少有一個(gè)是相似群體的前綴后綴，看成這條邊的兩個(gè)端點(diǎn)至少有一個(gè)被選中。 那么這就變成了一個(gè)最小點(diǎn)覆蓋問(wèn)題。 考慮匈牙利算法算出答案，然后考慮如何構(gòu)造答案。 考慮右邊沒(méi)有被匹配的點(diǎn)，選中這些點(diǎn)向左邊連的 閱讀全文
posted @ 2024-02-27 18:11
ChiFAN鴨
閱讀(47)
評(píng)論(0)
推薦(0)
摘要：
考慮把貢獻(xiàn)攤到每個(gè)點(diǎn)上計(jì)算，每個(gè)點(diǎn)帶來(lái)的貢獻(xiàn)實(shí)際上是經(jīng)過(guò)它的路徑并大小，算完求和之后在除以 \(2\) 就得到了答案。 考慮怎么計(jì)算路徑并大小。 考慮這樣一個(gè)辦法，將所有路徑的起始點(diǎn)和終點(diǎn)按照 DFS 序排序，相鄰兩點(diǎn)（包括第一個(gè)會(huì)最后一個(gè)點(diǎn)）在樹(shù)上的距離之和便是其路徑并大小的兩倍。原理的話便是路徑 閱讀全文
posted @ 2024-02-27 18:11
ChiFAN鴨
閱讀(33)
評(píng)論(0)
推薦(0)
浙公網(wǎng)安備 33010602011771號(hào)