2017 Multi-University Training Contest 4 solutions BY 陳鬆楊

NO IMAGE

2017 Multi-University Training Contest 4 solutions BY 陳鬆楊

1001. Big Integer

如果知道k-1k−1個數的個數c_1,c_2,…,c_{k-1}c​1​​,c​2​​,…,c​k−1​​,那麼方案數就是:

\frac{\left(\sum\limits_{i=1}^{k-1}
c_i\right)!}{\prod\limits_{i=1}^{k-1}c_i!}​​i=1​∏​k−1​​c​i​​!​​(​i=1​∑​k−1​​c​i​​)!​​

構造多項式f_i(x)=\sum\limits_{j=0}^n
\frac{g_{i,j}}{j!}x^jf​i​​(x)=​j=0​∑​n​​​j!​​g​i,j​​​​x​j​​,則將這k-1k−1個多項式乘起來之後,每一項乘以i!i!即可得到答案,可以用NTT在O(nk^2\log(nk))O(nk​2​​log(nk))的時間內預處理出初始答案。

注意到我們只關心每個時刻答案的和,故可以在DFT意義下直接累加答案,最後再將結果IDFT回來。

對於單點修改操作,可以看成是給某個多項式疊加上一個只有一項係數不為00的多項式,觀察NTT的公式:

y_n=\sum_{i=0}^{d-1}
x_i\times\left(g^\frac{P-1}{d}\right)^{in}\bmod Py​n​​=∑​i=0​d−1​​x​i​​×(g​​d​​P−1​​​​)​in​​modP

那麼它在DFT後的結果是一個等比數列,故直接對原始多項式疊加一個等比數列即可完成修改。

對於疊加多項式,直接O(k)O(k)重新計算乘積是不可取的,正確方法是對於每一項記錄非00的乘積以及00的個數,單次修改時間複雜度為O(1)O(1)。每次操作的時間複雜度為O(nk)O(nk)。

總時間複雜度O(nk^2\log(nk)+mnk)O(nk​2​​log(nk)+mnk)。

1002. Classic Quotation

首先通過KMP演算法預處理出TT的nextnext陣列,設:

pref_ipref​i​​表示SS的字首ii與TT進行KMP後KMP的指標到達了哪裡。

preg_ipreg​i​​表示SS的字首ii中TT出現的次數。

suf_{i,j}suf​i,j​​表示從SS的字尾ii,從jj指標開始KMP,能匹配多少個TT。

那麼字首ii拼接上字尾jj中TT的個數為preg_i+suf_{j,pref_i}preg​i​​+suf​j,pref​i​​​​。

令pregpreg為pregpreg的字首和,sufsuf為sufsuf的字尾和,s_{i,j}s​i,j​​表示ii前面中prefpref為jj的個數,那麼對於詢問L,RL,R:

ans=\sum_{i=1}^L\sum_{j=R}^n
preg_i+suf_{j,pref_i}=(n-R+1)preg_L+\sum_{i=0}^{m-1}s_{L,i}\times suf_{R,i}ans=∑​i=1​L​​∑​j=R​n​​preg​i​​+suf​j,pref​i​​​​=(n−R+1)preg​L​​+∑​i=0​m−1​​s​L,i​​×suf​R,i​​

以上所有陣列均可以使用KMP和遞推求出,時間複雜度O((n+k)m)O((n+k)m)。

1003. Counting Divisors

設n=p_1^{c_1}p_2^{c_2}…p_m^{c_m}n=p​1​c​1​​​​p​2​c​2​​​​…p​m​c​m​​​​,則d(n^k)=(kc_1+1)(kc_2+1)…(kc_m+1)d(n​k​​)=(kc​1​​+1)(kc​2​​+1)…(kc​m​​+1)。

列舉不超過\sqrt{r}√​r​​​的所有質數pp,再列舉區間[l,r][l,r]中所有pp的倍數,將其分解質因數,最後剩下的部分就是超過\sqrt{r}√​r​​​的質數,只可能是00個或11個。

時間複雜度O(\sqrt{r}+(r-l+1)\log\log(r-l+1))O(√​r​​​+(r−l+1)loglog(r−l+1))。

1004. Dirt Ratio

二分答案midmid,檢驗是否存在一個區間滿足\frac{size(l,r)}{r-l+1}\leq
mid​r−l+1​​size(l,r)​​≤mid,也就是size(l,r)+mid\times
l\leq mid\times (r+1)size(l,r)+mid×l≤mid×(r+1)。

從左往右列舉每個位置作為rr,當rr變化為r+1r+1時,對sizesize的影響是一段區間加11,線段樹維護區間最小值即可。

時間複雜度O(n\log
n\log w)O(nlognlogw)。

1005. Lazy Running

取w=\min(d_{1,2},d_{2,3})w=min(d​1,2​​,d​2,3​​),那麼對於每一種方案,均可以通過往返跑ww這條邊使得距離增加2w2w。也就是說,如果存在距離為kk的方案,那麼必然存在距離為k+2wk+2w的方案。

設dis_{i,j}dis​i,j​​表示從起點出發到達ii,距離模2w2w為jj時的最短路,那麼根據dis_{2,j}dis​2,j​​解不等式即可得到最優路線。

時間複雜度O(w\log
w)O(wlogw)。

1006. Logical Chain

對於每個詢問,求出強連通分量,那麼一個點數為tt的強連通分量對答案的貢獻為\frac{t(t-1)}{2}​2​​t(t−1)​​。

利用Kosaraju演算法,只需要在正反圖各做一次DFS即可求出強連通分量。面對稠密圖,Kosaraju演算法的瓶頸在於尋找與點xx相連且未訪問過的點。考慮用bitset來儲存邊表g_xg​x​​,以及未訪問過的點集SS,那麼只需要取出g_x\&Sg​x​​&S內的所有11即可在O(\frac{n^2}{64})O(​64​​n​2​​​​)的時間內求出強連通分量。

時間複雜度O(\frac{mn^2}{64})O(​64​​mn​2​​​​)。

1007. Matching In Multiplication

首先如果一個點的度數為11,那麼它的匹配方案是固定的,繼而我們可以去掉這一對點。通過拓撲我們可以不斷去掉所有度數為11的點。

那麼剩下的圖中左右各有mm個點,每個點度數都不小於22,且左邊每個點度數都是22,而右側總度數是2m2m,因此右側只能是每個點度數都是22。這說明這個圖每個連通塊是個環,在環上間隔著取即可,一共兩種方案。

時間複雜度O(n)O(n)。

1008. Phone Call

不難發現這個過程就是Prim演算法求最小生成樹的過程,用Kruskal演算法同樣正確。

將所有線路按代價從小到大排序,對於每條線路(a,b,c,d)(a,b,c,d),首先把aa到bb路徑上的點都合併到LCA,再把cc到dd路徑上的點都合併到LCA,最後再把兩個LCA合併即可。

設f_if​i​​表示ii點往上深度最大的一個可能不是和ii在同一個連通塊的祖先,每次沿著ff跳即可。用路徑壓縮的並查集維護這個ff即可得到優秀的複雜度。

時間複雜度O(m\log
m)O(mlogm)。

1009. Questionnaire

取m=2m=2,必然存在一組可行解。

1010. Security Check

設f_{i,j}f​i,j​​表示僅考慮a[1..i]a[1..i]與b[1..j]b[1..j]時,最少需要多少時間。

若|a_i-b_j|>k∣a​i​​−b​j​​∣>k,則f_{i,j}=f_{i-1,j-1}+1f​i,j​​=f​i−1,j−1​​+1,否則f_{i,j}=\min(f_{i-1,j},f_{i,j-1})+1f​i,j​​=min(f​i−1,j​​,f​i,j−1​​)+1。

注意到後者只有O(nk)O(nk)個,可以暴力DP,前者可以通過二分找到最大的tt,滿足i,ji,j往前tt個均不衝突,然後再從某個後者狀態轉移過來。

時間複雜度O(nk\log
n)O(nklogn)。

1011. Time To Get Up

按題意模擬即可。

1012. Wavel Sequence

設f_{i,j,k}f​i,j,k​​表示僅考慮a[1..i]a[1..i]與b[1..j]b[1..j],選擇的兩個子序列結尾分別是a_ia​i​​和b_jb​j​​,且上升下降狀態是kk 時的方案數,則f_{i,j,k}=\sum
f_{x,y,1-k}f​i,j,k​​=∑f​x,y,1−k​​,其中x<i,y<jx<i,y<j。暴力轉移的時間複雜度為O(n^4)O(n​4​​),不能接受。

考慮將列舉決策點x,yx,y的過程也DP掉。設g_{i,y,k}g​i,y,k​​表示從某個f_{x,y,k}f​x,y,k​​作為決策點出發,當前要更新的是ii的方案數,h_{i,j,k}h​i,j,k​​表示從某個f_{x,y,k}f​x,y,k​​作為決策點出發,已經經歷了gg的列舉,當前要更新的是jj的方案數。轉移則是要麼開始更新,要麼將ii或者jj繼續列舉到i+1i+1以及j+1j+1。因為每次只有一個變數在動,因此另一個變數恰好可以表示上一個位置的值,可以很方便地判斷是否滿足上升和下降。

時間複雜度O(n^2)O(n​2​​)。

1013. Yuno And Claris

先考慮如何求區間第kk小值。對序列和權值都進行分塊,設b_{i,j}b​i,j​​表示前jj塊中權值在ii塊內的數字個數,c_{i,j}c​i,j​​表示前jj塊中數字ii的出現次數。那麼對於一個詢問[l,r][l,r],首先將零碎部分的貢獻加入到臨時陣列tbtb和tctc中,然後列舉答案位於哪一塊,確定位於哪一塊之後再暴力列舉答案即可在O(\sqrt{n})O(√​n​​​)的時間內求出區間第kk小值。

接著考慮如何實現區間[l,r][l,r]內xx變成yy的功能。顯然對於零碎的兩塊,可以直接暴力重構整塊。對於中間的每個整塊,如果某一塊不含xx,那麼無視這一塊;否則如果這一塊不含yy,那麼只需要將xx對映成yy;否則這一塊既有xx又有yy,這意味著xx與yy之間發生了合併,不妨直接暴力重構整塊。因為有cc陣列,我們可以在O(1)O(1)的時間內知道某一塊是否有某個數。

考慮什麼情況下會發生重構,也就是一個塊內發生了一次合併的時候。一開始長度為nn的序列會提供O(n)O(n)次合併的機會,而每次修改會對零碎的兩塊各提供一次機會,故總合並次數不超過O(n+m)O(n+m),因此當發生合併時直接重構並不會影響複雜度。

那麼現在每塊中的轉換情況只可能是一條條互不相交的鏈,只需要記錄每個初值轉換後是什麼,以及每個現值對應哪個初值即可。遇到查詢的時候,我們需要知道零碎部分每個位置的值,不妨直接重構那兩塊,然後遍歷一遍原陣列aa即可得到每個位置的值。

在修改的時候,還需要同步維護bb和cc陣列,因為只涉及兩個權值,因此暴力修改jj這一維也是可以承受的。

總時間複雜度O((n+m)\sqrt{n})O((n+m)√​n​​​)。

本條目釋出於2017年8月3日。屬於未分類分類。作者是sensible