隨手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)，粗略估計的，理論上應該更優(?

原題連結： http://tioj.infor.org/problems/1169 首先要先想到第三子題怎麼做 對於每一個顏色，都開一棵線段樹 對於一個顏色K的線段樹維護： 1.從左邊開始不含K的最長區間 2.從右邊開始不含K的最長區間 3.這個區間不含K的最長區間 維護並不難想也不難寫，總複雜度O(2^cN+QlgN)，空間複雜度O(2^CN) 問題在當C到24時，不管是時間還是空間都有問題 我們首先觀察到，在尚未有任何氣球的時候，對於每個顏色的線段樹長相都一樣 先把原序列當成N個的單點修改操作，這樣每個修改操作一定只會到動到lgN個線段樹的節點 那這裡就可以用動態開點的方式，如果記憶體是空的表示這個區間絕對沒有該顏色，可以直接把答案填滿，這樣也不用預處理2^cN。 至於詢問操作就照原本的寫，只要注意不要讀到空的記憶體就好了 複雜度O((N+Q)lgN)，空間上如果對顏色離散化或用map會更好，不過我是直接硬開2^24個指標就是了XD

原題連結： http://tioj.infor.org/problems/1971 最近怎麼反而在練選訓題了(汗 明明根本還沒進選訓 這題一整個經典拈題 前55分有顯然的O(MN) SG Value解 比較值得提到的是後面的第三子題和第四子題 我先確定55分自己能拿之後跳過第三的12分開始想後面的33分 因為保證a_i<=20，假設我們能在這個子題實行SG Value的話 首先先觀察到所有>1的SG值都沒有用處，可以直接填上1就好了，0就還是0 於是可以觀察到，對於連續K個的區間，最多只存在2^K種區間SG 又因為第四子題a_i<=20，所以對於一個SG[i]需要呼叫的子問題絕對不低於SG[i-20]，也就是K=20 所以可以保證出現第一個重複的「大小N的區間SG」時，後面的SG結果就會和前面呈現週期性的重複 由於區間SG只有2^20種，轉換後又很方便是整數，所以可以開一個2^20的陣列紀錄每種區間SG出現的時刻 這裡還用map之類的資結絕對是中毒了(?，計算轉換的值可以邊跑邊算，所以是完完全全的O(2^N) 寫起來也不難，找到週期後記得處理一下餘數問題加前面就有88分了，似乎頗賺的(? 最讓我意外的是剩下的12分，因為我第一次拿完88分就直接卡死了只好放棄 直到最近看了某國手的文才發現，據說用O(MN)拿bitset硬開會過！？ ......然後真的過了 雖然看他的文章讓我有種我可能假解了的feel，可是看在我執行時間不算久的情況下就算了(X 結論就是，bitset真強大啊OwO~~ \

原題連結： http://tioj.infor.org/problems/1872 這題本來沒什麼想法，看題解想了好久才搞懂QQ 首先我們要先對詢問區間的右界排序(QlgQ) 然後利用差分的概念，維護序列b[i]=query(i,r)/query(i+1,r) 也就是計算詢問往左擴大一個後會需要多乘多少 這裡我是用bit維護，這樣對於一個詢問[l,r]，固定r後求得的答案就是bit_query(r)*inv(bit_query(l-1)) 維護良好的話，詢問複雜度會是QlgN 再來是維護的部分 當我們要增加一個r的時候，我們對於每個a[r]的質因數p做分開處理(質因數分解O(NlgN)) 假想r-1以前的維護都已經完成，那麼對於一個質數p，我們將會維護出一個從a[1]~a[r-1]的「嚴格遞減單調隊列」 其中內含的是a[i]中最大的p冪次因數 這時候就可以開始用一個stack做單調隊列的維護，先求出a[r]中最大的p冪次因數，冪次為c 則當top的冪次r： r<=c 該top原位置的b[i]必須被更動(因為表示這個冪次r會完全被c蓋住)，然後就可以把top拔掉了 r>c 該top原位置的b[i]必須稍做更動(增加幅度減少)，並把c推入stack後更新b[r]退出(更後面的元素我們可以相信他們已經被前面的元素更新完了) 更新b[r]、更動b[i]的部分分別一個是用乘的，一個是用除的(乘反元素) 這裡我在線篩的時候有預處理把每個質數的冪次和反元素都蓋好(複雜度NlgN)，所以更新更動都是lgN 對於每個質數，每個元素至多加入一次、拔掉一次，均攤O(1)，單一質數最慘複雜度O(NlgN) 但注意到數字最大只有10^6，所以要卡最緊也只能多約lgC個質數(實際上是更好的一個反函數)，維護總複雜度O(NlgClgN) 總複雜度O(Q(lgQ+lgN)+NlgClgN) 附上code:

原題連結： http://tioj.infor.org/problems/1974 這題是一階的模考題 難度在其中應該是偏易的？ 想法在於試著枚舉其中一維度，如果能在極短的時間內求出另一維度的當前最大值就能完成。 矩形只有10^5個，左右界分開看每一維度共有2*10^5個，不難發現座標範圍10^9只是一個叫你離散化的騙局(?)，兩個維度分別真正會出現不同值域的範圍只有2*10^5種而已。 因為要枚舉其中一維度，所以這個維度(我是用x)就不需要離散化，於是先對y座標離散化。 維護y座標的最大值時，可以發現如果硬是把欲枚舉x座標的矩形加進來，對於一個固定的y座標，只要把在其上的矩形加進來最後扣掉重疊的矩形就好。 利用掃描線+線段樹跟著枚舉一起跑，維護好「扣掉重疊矩形」這個動作，就能夠O(1)查詢每個x座標的極值。 線段樹總共被修改2*n次，總共複雜度O(nlgn) 由於題目的權重不存在負值，然後我沒有發現這件事@@ 如果有負值的話還要記得額外判斷十字線有一維度完全沒射中的情況，最後和0取MAX應該才是正解。

原題連結： http://codeforces.com/problemset/problem/914/D 這題我在比賽當中想到詢問O((logn)^2)的作法，雖然壓常數後過了，可是最後還是被system test卡掉QQ 不過在賽後重送一次一模一樣的code卻過了，不知道是不是伺服器負荷量問題... 原題的詢問可以視為，詢問區間內無法被x整除的數字是否超過1個。 則考慮一個gcd線段樹，query的時候在外面開一個「無法被整除數字」的計數器。 函式裡，只要有區間能被x整除就直接return，否則就持續往詢問的區間遞迴。 如果當前node是涵蓋在詢問區間裡的： case 1: l==r(node的區間只代表一個數字) 　　因為能遞迴到這裡表示一定不能整除，計數器+1 case 2: otherwise 　　暴力往下遞迴 最後在函式的開頭補上，計數器>1就直接return。 可以觀察到，會暴力遞迴到底的次數頂多只有兩次，兩次後計數器會>1，其他的待跑函式會全部return，複雜度O(logn) 總複雜度O(N+Qlogn)(不含修改，修改約O(logn*logC)，但gcd的期望值和單點修改的常數都遠比預計的小，所以可以不用在意)

第一篇文章ww 原題連結： https://zerojudge.tw/ShowProblem?problemid=c259 剛看到的時候覺得是經典題，但沒什麼想法 拜某建中的蔣大大傳了篇文章之後才搞懂這精湛的解法 寫完之後居然一次過了Orz 人品爆發(? 解題概念： 開一棵線段樹，維護以下： 1.總和(sum) 2.最小值(Min) 3.最小值的個數(min_count) 4.次小值(sec_min)，葉節點預設INF 5.懶標(lazy) 前4個在未修改的情況下的維護是很簡單的 關鍵在「修改值」 對於一個線段樹上的node和V取MAX，分成3個case來處理： case 1:V<=min 　　return case 2:V<sec_min 　　利用min_count和Min做運算後維護sum，把Min和lazy覆蓋掉後return case 3:V>=sec_min 　　暴力往下推左右兒子 如果不觸發case 3的話，複雜度會是完美的O(QlogN) 而對於case 3的複雜度分析，考慮每次遞迴後，因為是對整個node取MAX，則數字種數必定會減少1，至多減少node的區間大小次，所以減少的次數是呈線性的，複雜度為O(NlogN) 總複雜度約為O((N+Q)logN)