隨手coding筆記 by波路特石

原題連結： https://tioj.ck.tp.edu.tw/problems/1545 這題看完第一直覺是令$\color{white}{\space dp[N][M]\space}$為輸入$\color{white}{\space N,M\space}$時的答案，可以很輕易的發現轉移是$\color{white}{\space O(N)\space}$。 複雜度$\color{white}{\space O(N^3)\space}$，可以拿下前兩筆subtask。 不過適當的利用精度捨棄不必要的運算之後可以利用這個方法拿到第三筆subtask。 但最終還是過不了第四筆QQ。 稍微被劇透一下解之後，得知若令$\color{white}{\space dp[N]\space}$為輸入$\color{white}{\space N,N\space}$時的答案，則有等式： $\color{white}{\space dp[i]=\frac{1}{2}\displaystyle\sum_{j=0}^{i-2}(\frac{\dbinom{n-1}{j}}{2^{n-1}}dp[i-j])+\frac{\dbinom{n-1}{n-1}}{2^{n-1}}\space}$ 轉移想法來源為，枚舉閃電傳完一輪後(第$\color{white}{\space N\space}$個人傳完)，已經有$\color{white}{\space j\space}$個人被殺掉且第$\color{white}{\space N\space}$個人還活著的機率(多乘一個$\color{white}{\space \frac{1}{2}\space}$)總和起來，但必需特判剛好傳完一輪其他人全死光的情況(此時第$\color{white}{\space N\space}$個人不需要再進行閃電判斷)。 所以稍微做個移項之後可得： $\color{white}{\space (2-\frac{\dbinom{n-1}{0}}{2^{n-1}})dp[i]=\displaystyle\sum_{j=1}^{i-2}(\frac{\dbinom{n-1}{j}}{2^{n-1}}dp[i-j])+2\frac{\dbinom{n-1}{n-1}}{2^{n-1}}\sp...

原題連結： http://codeforces.com/problemset/problem/1051/E 這題大概瞪個一眼就會發現是DP了 但是問題在轉移，怎麼想都很容易TLE 總之如果列出轉移式的話，大概會長這樣 $\color{white}{\space dp[i]=\displaystyle\sum_{l\leq substring (j,i]\leq r} dp[j] \space}$ 那就是要想辦法搜到滿足的$\color{white}{\space j \space}$的範圍，可以發現存在單調性，衝動之下可能就會想二分搜了 可以用hash來達成類似的動作，複雜度約為$\color{white}{\space O(nlogn) \space}$ 但是hash容易被攻擊，$\color{white}{\space O(nlogn) \space}$又感覺怕怕的 有沒有一個優美又是$\color{white}{\space O(n) \space}$的解呢？ 有！ 觀察字串比大小時的動作，也就是找到兩個字串的$\color{white}{\space LCP \space}$再比較下一個字元的大小 仔細看了一下，找$\color{white}{\space LCP \space}$的動作都是發生在字串$\color{white}{\space l,r \space}$跟字串$\color{white}{\space a \space}$的每個元素開始比較 那如果能預處理這些東西的$\color{white}{\space LCP \space}$，不就能$\color{white}{\space O(1) \space}$定位了嗎？ 當然這裡絕對不會把Suffix Array搬出來 Z-value就足夠了！ 把字串$\color{white}{\space a \space}$分別接在$\color{white}{\space l,r \space}$後面求Z-value，就完成預處理$\color{white}{\space LCP \space}$了 那區間的DP值也只不過是做點前綴處理而已(要記得判掉前綴0，跟反處理掉單一個0的情況) 整體就完全是線性的$\color{white}{\space O(...

原題連結： https://tioj.ck.tp.edu.tw/problems/1975 這題很神奇，至於神奇在哪先不馬上劇透(? 首先，當$\color{white}{\space M=0\space}$時，有顯然的$\color{white}{\space O(NlgN)\space}$排序解。 但我們換個角度，把區間的工作視為區間加值，那就有差分後的$\color{white}{\space O(N+C)\space}$解法。 這個解法的關鍵在於只要取被加最多次的點的值就是答案，所以接下來在處理「非即時性工作」時我們也將採取同樣的策略－－也就是在加完「即時性工作」後，把每個「非即時性工作」的量分別盡量的、 不重複的 分給 死線前 、 被加的值少 的點，最後再取一次被加最多次的點的值就是答案。 為了方便，我們事先把所有非即時性工作讀進來對死線排序，然後把當前工作$\color{white}{\space i\space}$死線$\color{white}{\space d_i\space}$前的點值全部補進資料結構內，每次拿前$\color{white}{\space w_i\space}$小的值出來每個$\color{white}{\space +1\space}$再丟回去－－這是最直觀的寫法了，首先一般我們會想到用pq來維護前k小，但這樣複雜度會是慘慘的$\color{white}{\space O(N+MClgC)\space}$。 於是很自然的也能發現，重複的值太多了，不妨把全部的值全部壓縮在一起綁成pair拿map維護吧！ ……結果照樣吃了TLE，因為不能重複分配的關係導致單調性失效。 不過這個壓縮在一起的動作卻是關鍵，可以觀察到，我們是把前$\color{white}{\space w_i\space}$小的值+1，假設被加的值種類分別是$\color{white}{\space v_1,v_2, \cdots ,v_t\space}$，那加值完之後不就只是把前面全部拔掉，變成$\color{white}{\space v_1+1,v_2+1,...,v_{t-1}+1\space}$，並且$\color{white}{\space v_t \space}$被拆成兩份而已嗎！？ 這個平移大部份資料位置卻不改變值的動作...

原題連結： https://tioj.ck.tp.edu.tw/problems/1775 久違的文章(? 被某人丟了這題，發現原本這題只有一個人過 本來以為不太可做，結果想了一下發現似乎有那麼一點希望(?)，就花了一段時間刻出來了ww 首先從水母圖的角度切入，很顯然的這是把很多棵樹的根節點連成一個環所形成的圖 接下來就能發現，只要將環上每個點的子樹的所有距離(包含自己)，分別記錄起來排序 且如果環的大小是$\color{white}{\space L\space}$，則對於每個點，得到「點到環的距離」後就可以枚舉環上的每個點二分搜得到除了自己這棵樹以外符合題目條件的個數了。 這裡只花了$\color{white}{\space O(NLlgN)\space}$ 所以接下來我們就能把題目縮減成在樹上的子問題，只要把環切開來一個一個做就好了。 這樣的話我們先來考慮一個類似的小問題： 「給定長度為$\color{white}{\space N\space}$的兩個序列$\color{white}{\space d_i\space}$和$\color{white}{\space k_i\space}$，如果我把序列切成$\color{white}{\space M\space}$塊，試問對於每個$\color{white}{\space i\space}$，滿足$\color{white}{\space d_i+d_j<=k_i\space}$的整數$\color{white}{\space j\space}$，且$\color{white}{\space i,j\space}$不在同一塊的個數有多少個？」 總之會有$\color{white}{\space O(NlgN)\space}$的作法 同樣的問題要如何對應到樹上面呢？ －－沒錯，就是樹分治！ 對於每一棵需要求該問題的樹，我們把這棵樹的重心拆掉之後遞迴下去 在合併一堆小樹時，從重心$\color{white}{\space dfs\space}$出去記錄其他點到自己的距離$\color{white}{\space d_i\space}$，這樣若有$\color{white}{\space M\space}$棵小樹，就對應到上面那個問題了！(不過要記得算上重心本身～...

原題連結： https://tioj.ck.tp.edu.tw/problems/1921 似乎很久沒發文了…… 最近有點忙加上最近寫的題目很多不是裸題就是看解答發現自己低能沒想到解(? 可以很輕易的列出DP式 若$\color{white}{\space dp[i]\space}$表示買進第$\color{white}{\space i\space}$台機器時，擁有的最多錢數 則 $\color{white}{\space dp[i]=max\{dp[j]+(D_i-D_j-1)\times G_j+R_j-P_i\space|\space0\leq j<i\text{,}dp[j]\geq 0\}\space}$ 化簡一下 $\color{white}{\space dp[i]=max\{G_j\times D_i + dp[j]-(D_j+1)\times G_j +R_j\space|\space0\leq j<i\text{,}dp[j]\geq 0\}-P_i\space}$ 很經典的斜率優化形式 會特別強調$\color{white}{\space dp[j]\geq 0\space}$是因為機器買進後如果錢是負的，就表示其實當下你根本沒錢買這台機器 這裡我直接令$\color{white}{\space dp[0]=C\space}$，並在最後把第$\color{white}{\space D+1\space}$天當成一台買進買出生產都是0的機器，答案就是買進最後這台的DP值了 一般斜率優化通常都會利用「斜率的單調性」配合「參數的單調性」來優化至$\color{white}{\space O(N)\space}$ 可是這題卻少了「斜率的單調性」，因為$\color{white}{\space G_j\space}$並不遞增 所以我們必須要維護「動態凸包」 理念大約是拿一個set，裡面放許多直線，在這題的話就是維護上凸包這樣 由於這題有「參數的單調性」，所以不用對線二分搜，從前面硬砍就好 最終問題就回到了實作動態凸包了 這裡我直接丟線進去 1.先把斜率相同的砍掉 2.再檢查自己會不會被兩側的直線完全覆蓋 3.往前砍 4.往後砍 大概是這樣的順序(?)，詳細可以看我的code(不過由於第...

原題連結： http://tioj.infor.org/problems/2030 因為上一題被CDQ洗腦很久之後莫名其妙把CDQ搞懂了 就跑來寫這題了ww 首先我們知道，對於2、3的操作是 一個詢問[QL,QR]，只要雷射光的[L,R]滿足QL<=L、R<=QR就能夠造成傷害 所以這個明顯能用CDQ分治解決 問題回到第一種操作，不妨讓所有傷害落在區間內所有重複數字中最左邊的數字上 如果沒有修改，那假設一個數字位置是R，左邊有重複同樣數字的位置是L(沒有重複可定義為0) 那只要滿足QL<=L、R<=QR就「不能造成傷害」 注意到是不能造成傷害，所以再開一棵BIT紀錄屏障先把區間和硬是放進答案裡，再用扣的就和前面的雷射光是一模一樣的操作了 那我們修改的部分就剩下維護每個數字「左邊有重複同樣數字的位置」了 可以發現對於每個數字開一個set去好好維護就能達成，不過要注意右邊的數字也會一起被動到要記得修掉><

原題連結：http://tioj.infor.org/problems/1919 感動QwQ 這題卡了超久= = 大概第一篇文章出來之前就一直卡著了(? 當初剛學完CDQ分治然後這題就一直被CDQ洗腦 導致怎麼寫都多一個log... 先觀察到這看起來就很整體二分(? 但由於不能直接開資結使用區間加，會加到重複的 那我們就固定讓「拍照區間由左邊看過來還沒出現過的數字」得到錢 也就是說，對於一個田地i，如果下一個和他一樣的雇主的位置是j 那麼要使i得到錢，就必須滿足詢問區間[L,R]有 L<=i、R<j，以及i<=R 先不管i<=R，我們可以發現在固定時間的時候這是一個二維詢問問題 只要把一維排序掉(我是用左界)，另一維就能用BIT修改維護掉 那i<=R的部分就能利用前綴相減，也就是原本排序掉的左界把R<i的錢都砍掉了！ 注意到整體二分時詢問是離線的 為了不讓每個二分搜上的node都重跑一次詢問，我們可以在把問題分類到右區間時順便扣掉現在得到的錢，這樣右區間就不需要重跑mid以前的詢問了 (還有記得把BIT清空><) 二分時每一層大約 詢問帶修改QlgM，排序QlgQ+MlgM 層數lgQ層 總複雜度約O((QlgMQ+MlgM)lgQ)，粗略估計的，理論上應該更優(?