UOJ424. count

對(duì)于區(qū)間最大值位置本質(zhì)不同的序列計(jì)數(shù)，可以直接轉(zhuǎn)化為笛卡爾樹(shù)計(jì)數(shù)。

考慮如何判定合法的笛卡爾樹(shù)，左子樹(shù)的值需要 \(<\) 根，右子樹(shù)需要 $\le $ 根。上述約束需要滿(mǎn)足左子樹(shù)深度 \(\le m\)，笛卡爾樹(shù)是二叉樹(shù)，可以轉(zhuǎn)化為括號(hào)序列計(jì)數(shù)。

首先 \(n<m\) 肯定無(wú)解，可以猜測(cè) \(m\le n\) 的時(shí)候?qū)τ诤戏ǖ牡芽枠?shù)一定存在構(gòu)造使得 \([1,m]\) 都出現(xiàn)過(guò)一次，這個(gè)很好感性理解。

因此我們現(xiàn)在就是要求從 \((0,0)\) 點(diǎn)出發(fā)，每次可以向右下或者右上走一步，不碰到 \(y=-1\) 和 \(y=m+1\) 的方案數(shù)。

直接用反射容斥就解決了。

UOJ693. 【UR #23】地鐵規(guī)劃

本質(zhì)上是用單棧維護(hù)原本的雙棧維護(hù)的不帶刪雙指針。

先回顧一下雙棧，左棧中從上到下為從左到右，右棧中從下到上為從左到右。每次將 \(l\) 右移就是等于說(shuō)是彈出左棧棧頂，將 \(r\) 右移就是加入右棧棧頂。左棧空了就重構(gòu)。

記錄原先左棧中的邊為 \(0\) 邊，右棧中的邊為 \(1\) 邊。其中 \(0\) 邊要求其被倒序加入。

使用單棧之后，右移 \(r\) 就是加入若干 \(1\) 邊，左移 \(l\) 就是先讓棧頂為 \(0\) 邊，然后 undo。

\(r\) 的移動(dòng)過(guò)直接做就行了。\(l\) 的時(shí)候一個(gè)很暴力的思路就是不斷彈出 \(1\) 邊直到遇到了 \(0\) 邊，但是這是很不優(yōu)的，因?yàn)槿绻麨榱艘粋€(gè) \(0\) 邊而遇到了許多 \(1\) 邊的話(huà)，就會(huì)被卡爆。為了不白白彈出這些 \(1\) 邊，我們考慮你前面如果彈了很多 \(1\) 邊，必然會(huì)導(dǎo)致后面的 \(1\) 邊少，所以不如就是多搞點(diǎn) \(0\) 邊出來(lái)。于是我們就直接彈棧，直到彈出來(lái)的 \(0\) 邊和 \(1\) 一樣多。然后把 \(1\) 邊全部都按照原順序放進(jìn)去，再把 \(0\) 邊丟進(jìn)去，這樣子使得很多 \(0\) 邊都上移了。

可能開(kāi)始會(huì)有疑惑，為什么不把 \(1\) 邊倒著塞回去，使得 \(1\) 邊變成 \(0\) 邊，但是需要注意 \(0,1\) 本質(zhì)上是兩個(gè)獨(dú)立的棧，只有把 \(0\) 棧全部彈出來(lái)之后，再翻轉(zhuǎn) \(1\) 邊才是正確的。

上述彈棧過(guò)程注意 corner case，當(dāng)沒(méi)有 \(0\) 邊的時(shí)候就直接把所有 \(1\) 邊翻轉(zhuǎn)了。如果所有邊都被彈出來(lái)之后還沒(méi)有兩者數(shù)量相等，那就可以把所有 \(1\) 邊倒著加進(jìn)去了。這個(gè)做法是根號(hào)的。

采用二進(jìn)制分組法，我們對(duì)于 \(0\) 進(jìn)行二進(jìn)制分組，比如按照 \(1,4,8\) 為組的大小進(jìn)行劃分。每次彈出一組之后就停止，也就是彈 \(\rm lowbit\) 個(gè) \(0\) 邊。對(duì)于 \(1\) 邊可以發(fā)現(xiàn)在棧中形成了 \(\log\) 個(gè)連續(xù)段，每次彈出一個(gè)連續(xù)段，因此每個(gè)元素至多被操作 \(\log\) 次。對(duì)于 \(0\) 邊，每次操作之后所在組的大小至少變成 \(\dfrac{1}{2}\)，比如 \(8\to 1,2,4\)，所以也至多被操作 \(\log\) 次。

QOJ2562. Fake Plastic Trees 2

有一顆帶點(diǎn)權(quán)的樹(shù)，對(duì)于 \(k\in [0,K]\)，判斷是否可以刪去樹(shù)上的 \(k\) 條邊，使得剩下的每個(gè)聯(lián)通塊點(diǎn)權(quán)和在 \([L,R]\) 之中。\(n\le 10^3,K\le 50,l,r\le 10^{15}\)。

暴力 dp 就是設(shè) \(dp_{i,j,k}\) 表示 \(i\) 子樹(shù)內(nèi)斷了 \(j\) 條邊，能否達(dá)到權(quán)值 \(k\)。然后跑一下樹(shù)上背包。

第三維度考慮用 std::vector 保存所有可能的狀態(tài)。但是狀態(tài)數(shù)太大了，我們需要對(duì)于狀態(tài)剪枝。由于最后只需要判斷是否存在 \([L,R]\) 之內(nèi)的權(quán)值，于是對(duì)于三個(gè)狀態(tài) \(x<y<z\)，當(dāng) \(z-x\le R-L+1\) 的時(shí)候，\(y\) 是無(wú)用的。直接不用保存即可。

如果一個(gè)聯(lián)通塊內(nèi)取值不足 \(L\) 是要一直選擇的，這一直是一個(gè)狀態(tài)不會(huì)增多。到了 \([L,R]\) 之內(nèi)可以閉合該聯(lián)通塊，因此初始狀態(tài)只會(huì)擴(kuò)展出 \(O(R-L)\) 個(gè)新?tīng)顟B(tài)。又因?yàn)闋顟B(tài)數(shù)要除以 \(R-L+1\)，所以對(duì)于一個(gè)初始狀態(tài)只會(huì)擴(kuò)展出 \(O(1)\) 個(gè)狀態(tài)，擴(kuò)展了 \(k\) 次也就最多出現(xiàn) \(O(k)\) 個(gè)狀態(tài)。因此對(duì)于 \(dp_{i,j}\) 其第三維的大小為 \(O(j)\)。總的時(shí)間復(fù)雜度 \(O(nk^3)\)。

P8375 [APIO2022] 游戲

還是要利用性質(zhì)，經(jīng)典算法可擴(kuò)展性差。

\(k=1\) 就是維護(hù)每個(gè)點(diǎn)和 \(1\) 點(diǎn)的雙向可達(dá)性?？梢员┝?dfs，我們加入一條邊 \((u,v)\) 的時(shí)候，對(duì)于 \(u\)，看看 \(v\) 能否到達(dá) \(1\)，如果能的話(huà)就更新 \(u\to 1\) 的可達(dá)性。對(duì)于 \(v\) 看看 \(1\) 能否達(dá)到 \(u\)，如果能的話(huà)，就更新 \(1\to v\) 的可達(dá)性。一個(gè)點(diǎn)的可達(dá)性如果更新之后就暴力沿著圖更新這個(gè)信息，可以發(fā)現(xiàn)每個(gè)點(diǎn)只會(huì)被標(biāo)記最多兩次，因此時(shí)間復(fù)雜度就是 \(O(n)\) 的。

同理對(duì)于 \(k\) 個(gè)點(diǎn)可以直接 \(O(nk)\)。對(duì)于某點(diǎn)只要能到達(dá)它的的最大編號(hào)關(guān)鍵點(diǎn)的編號(hào)大于它能到達(dá)的最小編號(hào)關(guān)鍵點(diǎn)的編號(hào)就代表出現(xiàn)了環(huán)。

考慮維護(hù) \(l_i\) 表示 \([1,l_i]\) 可達(dá) \(i\)，維護(hù) \(r_i\) 表示 \(i\) 可達(dá) \([r_i,n]\)，考慮維護(hù)區(qū)間 \([l_i,r_i]\)。當(dāng) \(r_i\le l_i\) 的時(shí)候就出現(xiàn)了環(huán)。對(duì)于新加入的一條邊 \(u\to v\)，可以發(fā)現(xiàn)當(dāng)兩個(gè)區(qū)間重合的時(shí)候是無(wú)影響的，非包含的時(shí)候如果 \(u\) 區(qū)間在 \(v\) 左邊也是無(wú)影響的，如果 \(u\) 區(qū)間在 \(v\) 區(qū)間左邊就產(chǎn)生了環(huán)。對(duì)于包含情況是不會(huì)產(chǎn)生環(huán)的，但是會(huì)更新一些 \([l_i,r_i]\)。把這些區(qū)間放到線段樹(shù)區(qū)間上去，并且維護(hù)通過(guò) \(\rm mid\) 的可達(dá)性，發(fā)生單側(cè)的變化的時(shí)候遞歸到下一層即可。

QOJ8047.DFS order 4

由于可能多顆樹(shù)能得到相同的 dfs 序，所以我們可以來(lái)考慮有多少種 dfs 序可以還原到一顆合法的樹(shù)。需要判定序列合法性。

如何判定一個(gè)序列合法？我們貪心的把點(diǎn)往一條父鏈上掛。如果 \(p_i>p_{i-1}\)，那么可以?huà)煸谶@條鏈末尾 \(p_{i-1}\) 的下方。如果 \(p_i>p_{i-1}\)，我們可以在這條鏈上找到一個(gè)最淺的祖先滿(mǎn)足 \(p_k<p_i\)，我們把 \(p_i\) 掛在 \(p_k\) 的父親上(這相當(dāng)于 dfs 的回溯過(guò)程)，這樣子既滿(mǎn)足兄弟節(jié)點(diǎn)編號(hào)遞增，也滿(mǎn)足了兒子大于父親。這樣子排列就和樹(shù)一一對(duì)應(yīng)了。

這樣子貪心連出來(lái)的樹(shù)等價(jià)于以下限制：每個(gè)點(diǎn)編號(hào)大于父親，每個(gè)點(diǎn)兒子編號(hào)單調(diào)遞增，且小于上一個(gè)兄弟的最后一個(gè)兒子。

可以發(fā)現(xiàn)第 \(2\) 到 \(k\) 個(gè)兄弟節(jié)點(diǎn)和父親間的約束沒(méi)有用，可以通過(guò) \(son_2>son_1>fa\) 來(lái)得到。直接刪掉就行了，只有在兄弟之間連邊。

有一個(gè)結(jié)論就是一顆外向圖的拓?fù)湫騻€(gè)數(shù)是 \(\dfrac{n!}{\prod sz_i}\)。但是本題由于有了小于上一個(gè)兄弟的最后一個(gè)兒子這個(gè)限制，導(dǎo)致這不是一顆外向樹(shù)。

考慮容斥掉這條邊，也就是 \([u<v]=1-[u>v]\)。等號(hào)右邊的兩種情況都是一棵樹(shù)，第一種情況系數(shù)是 \(+1\)，第二種情況系數(shù)是 \(-1\)。

現(xiàn)在需要分析一下新構(gòu)建的外向樹(shù)長(zhǎng)什么樣子。從父子關(guān)系角度考慮，有如下三種：一個(gè)父親和它的第一個(gè)兒子，相鄰兄弟，上一個(gè)兄弟的最后一個(gè)兒子和這個(gè)點(diǎn)。

現(xiàn)在考慮在一層兄弟鏈上面考慮，其中不止有第二類(lèi)邊，還有第三類(lèi)邊，也就是中間會(huì)夾雜著若干個(gè)上一個(gè)兄弟的一堆兒子。在鏈上如果走到了下方的節(jié)點(diǎn)，根據(jù)上述邊分類(lèi)，可以發(fā)現(xiàn)這是屬于 \(-[u>v]\) 這種邊的需要乘上一個(gè) \(-1\) 的系數(shù)。

設(shè) \(d_i\) 表示 \(sz=i\) 的子樹(shù)的貢獻(xiàn)，在鏈上掛子樹(shù)的時(shí)候算貢獻(xiàn)。\(f_{i,k}\) 表示 \(sz=i\)，在鏈上深度走到了 \(k\) 的方案數(shù)。

首先有 \(f_{i,0}=g_i\)。

合并子樹(shù)，\(f_{i+j,k}\gets f_{i,k}\times d_j\times\dfrac{j}{i+j}\)

往下走，\(f_{i+j,k+1}\gets -d_j\times f_{i,k}\times\dfrac{j}{i+j}\)

往上走，\(f_{i+1,k-1}\gets f_{i,k}\times \dfrac{1}{i+1}\)。

直接在一條鏈上往上連一個(gè)點(diǎn)，\(d_{i+1}\gets f_{i,0}\times\dfrac{1}{i+1}\)。

注意一下細(xì)節(jié)，我們是按照 \(sz\) 從小往大處理，所以有些 \(f_{i,k}\times d_j\) 的 \(d_j\) 在 \(i\) 處還沒(méi)有被算到，需要在 \(j\) 處再處理一下。

答案就是 \(d_n\)。時(shí)間復(fù)雜度 \(O(n^3)\)。

UOJ750.小火車(chē)

可以 meet-in-middle，不過(guò)底數(shù)為 \(3\)，沒(méi)有前途?？梢匀_隨機(jī)數(shù)據(jù)，根據(jù)生日碰撞，我們?cè)趦蛇吀鬟x \(O(\sqrt p)\) 個(gè)集合進(jìn)行匹配就行了。

這題本質(zhì)是找出兩個(gè)不交集合，使得兩者在模 \(p\) 意義下和相等，一個(gè)賦 \(1\)，另一個(gè)賦 \(-1\)?？梢酝ㄟ^(guò) \(2^n\) 枚舉出所有集合放到桶里面匹配。如果有兩個(gè)集合有重復(fù)元素，刪去之后兩個(gè)集合還是相等的。由于 \(p<2^n\)，也就是子集的個(gè)數(shù)大于桶的個(gè)數(shù)，所以一定有解。于是就優(yōu)化到了 \(O(2^n)\)。不過(guò)這還不夠，我們優(yōu)化的方向是把指數(shù)規(guī)模縮減為 \(\dfrac{1}{2}\)。

考慮我們其實(shí)只需要找到一個(gè)元素個(gè)數(shù) \(\ge 2\) 的桶，并不需要得出全部信息。因此可以類(lèi)似于線段樹(shù)二分的結(jié)構(gòu)，每次尋找 \(r-l+1<cnt_{l,r}\) 的區(qū)間走。求 \(cnt_{l,r}\) 可以直接 meet-in-middle 并用雙指針優(yōu)化。時(shí)間復(fù)雜度 \(O(2^{\frac{n}{2}}\log p)\)。

UOJ449. 【集訓(xùn)隊(duì)作業(yè)2018】喂鴿子

j將投喂序列中每個(gè)元素出現(xiàn)的前 \(k\) 次全部提取出來(lái)，構(gòu)成一個(gè)有用序列。

考慮直接對(duì)于一個(gè)長(zhǎng)度為 \(nk\) 的有用序列進(jìn)行統(tǒng)計(jì)。我們需要統(tǒng)計(jì)的量就是它的概率和期望長(zhǎng)度，知道這些信息之后就可以直接求答案 \(E(X)=\sum p_x\times l_x\)。

概率就是每個(gè)位置當(dāng)前能被出現(xiàn)的元素種類(lèi)分之一，也就是沒(méi)達(dá)到 \(k\) 的元素個(gè)數(shù)，把這些概率乘起來(lái)就是這個(gè)序列成為有用序列的概率。

關(guān)于期望長(zhǎng)度就是可以在每個(gè)位置前面出現(xiàn)一些不在有用序列里面的元素，也就是一些在之前就已經(jīng)達(dá)到 \(k\) 的元素再重復(fù)出現(xiàn)就不再放到有用序列里了。這個(gè)系數(shù)和之前已經(jīng)達(dá)到 \(k\) 的元素個(gè)數(shù)有關(guān)。

于是考慮 dp，可以發(fā)現(xiàn)唯一的約束條件就是之前達(dá)到 \(k\) 的元素個(gè)數(shù)，放到狀態(tài)里面直接設(shè) \((i,j)\) 二維狀態(tài)就行了。

有點(diǎn)細(xì)節(jié)，由于 \(l\times p=(\sum l_i)\times (\prod p_i)\)，我們需要每個(gè) \(l\) 被全局的概率都乘一遍。所以設(shè) \(f_{i,j}\) 表示前 \(i\) 個(gè)位置里面有 \(j\) 種元素達(dá)到了 \(k\) 的貢獻(xiàn)，\(g_{i,j}\) 表示前 \(i\) 個(gè)數(shù)里面有 \(j\) 個(gè)達(dá)到 \(k\) 個(gè)的方案數(shù) \(\times\) 概率。之所以要帶上方案數(shù)，是是因?yàn)槲覀円獙?duì)于所有情況求和，相同的方案合并就是一個(gè)方案數(shù)。我們每次加入一個(gè)數(shù)不考慮方案數(shù)，因?yàn)椴缓每刂埔粋€(gè)數(shù)的出現(xiàn)次數(shù)，統(tǒng)一在第 \(k\) 次出現(xiàn)的時(shí)候，在前面 \(i-1-(j-1)\times k\) 個(gè)位置里面選 \(k-1\) 個(gè)位置與當(dāng)前位置組合，也就是 \({i-1-(j-1)\times k\choose k-1}\times (n-(j-1))\)。

每次要讓之前的數(shù)乘上現(xiàn)在的概率也就是 \(p_jf_{i-1,j}\)，當(dāng)前這一位的貢獻(xiàn)是新增的期望長(zhǎng)度乘以之前所有的一路的概率 \(E_jg_{i,j}\)。

對(duì)于 \(j-1\to j\) 的轉(zhuǎn)移也是同理，不過(guò)需要乘上一個(gè)組合數(shù)的系數(shù)。

轉(zhuǎn)移復(fù)雜度是 \(O(1)\) 的。于是時(shí)間復(fù)雜度就是狀態(tài)數(shù) \(O(n^2k)\)。

QOJ8553.Exchanging Kubic

先用 \(n\) 次找到所有正負(fù)位置以及正位置的權(quán)值 ++---+++---+-。

我們將符號(hào)相同的連續(xù)段合并，這樣的話(huà)就可以得到一個(gè)正負(fù)交替的序列，并且我們知道所有正數(shù)的值。

對(duì)于 +-+ 進(jìn)行詢(xún)問(wèn)，一種情況是得到三個(gè)數(shù)之和（也就是返回值和兩個(gè)正數(shù)段都不同），這樣子可以直接得到負(fù)數(shù)的權(quán)值，于是直接將這三段合并成一個(gè)正段。一種情況是兩個(gè)正的最大值，這樣子我們可以知道負(fù)數(shù)的絕對(duì)值是大于兩個(gè)正數(shù)中的小者。那么我們索性就直接從全局正段最小值開(kāi)始做，詢(xún)問(wèn)其兩邊的正負(fù)正結(jié)構(gòu)，如果都不行的話(huà)就把它和周?chē)鷥蓚€(gè)負(fù)段合并起來(lái)。