上一篇寫滿了，又可以再開一篇了。

話說還有三周就要去退役了，真是快啊。

HZOI省選模擬66A 有限空間跳躍理論

考慮對一張\(DAG\)求拓撲序的過程，我們一次性刪除當前所有入度為\(0\)的點，并把這個點集記下來，這樣我們就得到一個拓撲序列。這個拓撲序列是一個點集序列，顯然拓撲序列不同，\(DAG\)一定不同，于是我們考慮對這種特殊的點集拓撲序列計數(shù)。設(shè)\(dp_S\)表示集合\(S\)中點已經(jīng)加入到了拓撲序列中的方案數(shù)，我們枚舉一個集合\(T\)作為當前入度為\(0\)的點集，顯然我們需要保證點集\(T\)內(nèi)部沒有邊，否則\(T\)中的點不可能入度均為\(0\)，之后\(dp_S\)向\(dp_{S\cup T}\)轉(zhuǎn)移即可。不難發(fā)現(xiàn)這種情況會算重，原因在于\(T\)可能不是一個極大的入度為\(0\)的點集，我們可能將極大的入度為\(0\)點集分到了數(shù)次加入。考慮容斥，使得極大入度為\(0\)點集被計算的次數(shù)和為\(1\)，設(shè)\(f_i\)表示\(i\)個點構(gòu)成的點集的容斥系數(shù)，不難發(fā)現(xiàn)有\(\sum_{i=0}^{n-1}\binom{n}{i}f_{n-i}=1\)，歸納一波發(fā)現(xiàn)\(f_i=(-1)^{i+1}\)，于是有\(dp_S=\displaystyle \sum_{i\cup j=S,i\cap j=\varnothing}dp_i\times [\text{點集j內(nèi)無邊}](-1)^{|j|+1}\)，不難發(fā)現(xiàn)這是一個子集卷積的形式，fwt優(yōu)化即可，復(fù)雜度\(O(2^nn^2)\)，代碼。

HZOI省選模擬90A 洛希極限

設(shè)\(f_{i,j}\)表示以\((i,j)\)為終點的最長路，最最暴力的想法就是枚舉一個\(i'<i,j'<j\)令\(f_{i',j'}\)向\(f_{i,j}\)轉(zhuǎn)移，轉(zhuǎn)移的時候還需要判斷是否存在一個矩形同時包含\((i,j),(i',j')\)。不難發(fā)現(xiàn)只有當\(i-i'\)和\(j-j'\)均大于\(1\)時這個轉(zhuǎn)移一定不優(yōu)，所以只需要枚舉和\((i-1,j-1)\)在同一行或同一列上的點即可。設(shè)\(left(i,j)\)表示使得\((i-1,x)\)和\((i,j)\)在同一個矩形里最小的\(x\)，\(up(i,j)\)表示使得\((x,j-1)\)和\((i,j)\)在用一個矩形里最小的\(x\)。顯然\(up(i,j)\)和\(left(i,j)\)是能從上面、左面向\((i,j)\)轉(zhuǎn)移的最遠點。不難發(fā)現(xiàn)\(left(i,j)\leq left(i,j+1),up(i,j)\leq up(i+1,j)\)，于是這個dp可以用單調(diào)隊列進行優(yōu)化?？紤]如何求出\(left(i,j)\)和\(up(i,j)\)，顯然可以掃描線，把一個矩形看成在上邊界加入，在下邊界刪除，給線段樹上每個節(jié)點開一個小根堆，標記永久化即可。求一行的\(left(i,j)\)和\(up(i,j)\)可以直接在線段樹上dfs一遍，由于堆可以\(O(1)\)求出最大值，所以這個復(fù)雜度是\(O(m)\)的。整體復(fù)雜度大概是\(O(Q\log^2n+nm)\)，由于\(\log n\)很小就直接跑過去了，代碼。

「LibreOJ NOI Round #2」簡單算術(shù)

一個常規(guī)想法就是枚舉\(m\)的劃分。如果\(\{b_i\}\)滿足\(\sum b_i=m\)且\(\sum ib_i=k\)，那么\(\{b_i\}\)對答案的貢獻就是\(\displaystyle \prod_{i=0}^{n} \binom{m-\sum_{j=0}^{i-1}b_j}{b_i}a_i^{b_i}\)?？梢詫?span id="w0obha2h00" class="math inline">\(\displaystyle\binom{m-\sum_{j=0}^{i-1}b_j}{b_i}\)寫成\(\displaystyle\binom{b_i+m-\sum_{j=0}^{i}b_j}{b_i}\)，于是根據(jù)庫默爾定理，這個組合數(shù)不為\(0\)當且僅當\(b_0+b_1+b_2+\dots+b_n\)在\(p\)進制下沒有進位?？紤]當\(p|m\)的約數(shù)時，\(m\)在\(p\)進制下最低位是\(0\)，那么所有\(b_i\)在\(p\)進制下最低位也都得是\(0\)，即所有\(b_i\)均滿足\(p|b_i\)。根據(jù)Lucas定理，顯然有:

我們要求的即\([x^k]F^m(x)\)，根據(jù)上面的式子不難發(fā)現(xiàn)當\(p|m\)時\([x^k]F^m(x)\equiv [x^{k/p}]F^{m/p}(x)(\rm{mod}\ p)\)。當\(k/p\)不是整數(shù)時，\([x^k]F^m(x)=0\)。

于是可以將\(m\)寫成\(ap+b\)的形式，于是有：

預(yù)處理\(F(x)\)的\(0,1,\dots,p-1\)此冪，直接暴力按照上面的式子迭代即可，復(fù)雜度\(O(n^2p^2+Tn^2\log_p m)\)，代碼。

HZOI省選模擬98D Radio Ga Ga

區(qū)間dp的做法比較顯然，就是設(shè)\(f_{l,r}\)表示考慮了區(qū)間\([l,r]\)的最大收益，由于知道了區(qū)間長度就知道了操作次數(shù)，所以轉(zhuǎn)移非常簡單，但是\(n\leq 10^9\)顯然白給。考慮換個dp方式，設(shè)\(dp_{i,0/1}\)表示在第\(k_i\)此操作恰好擴展到\(x_i\)，此時\(x_i\)為左/右端點的最大收益，顯然這個時候的區(qū)間就是\([x_i,x_i+k_i-1]\)或是\([x_i-k_i+1,x_i]\)，轉(zhuǎn)移的話就考慮枚舉上一次取到的收益是在\(k_j\)時刻，能轉(zhuǎn)移過來的條件是\(k_j\)時刻的區(qū)間被當前區(qū)間包含，且\(k_j\)時刻的區(qū)間端點不能是\(x_i\)。由于必須要保證\(k_j<k_i\)，所以不難發(fā)現(xiàn)轉(zhuǎn)移構(gòu)成了一個DAG，問題轉(zhuǎn)化為在這個DAG上求一條點權(quán)最長路。由于有多組詢問，所以考慮倒著進行dp即可。暴力轉(zhuǎn)移的復(fù)雜度是\(O(m^2)\)，不難想到搞個二維數(shù)據(jù)結(jié)構(gòu)來求矩形max優(yōu)化轉(zhuǎn)移，復(fù)雜度是\(O(m\log m^2)\)或\(O(m\sqrt{m})\)，為了復(fù)習kdt就寫了一發(fā)。這種求最值信息的kdt加上剪枝之后能跑過\(3\times 10^5\)級別的數(shù)據(jù)。

正解其實比較顯然，考慮將這\(2m\)個區(qū)間拿下來按照左端點從小到大排序，直接掃過去，在線段樹里插入右端點即可。顯然這樣能保證包含關(guān)系，又由于存在包含關(guān)系的兩個區(qū)間\([l_i,r_i],[l_j,r_j]\)一定滿足\(r_j-l_j+1\leq r_i-l_i+1\)，區(qū)間長度即當前操作次數(shù)，所以有\(k_j\leq k_i\)，這樣轉(zhuǎn)移的兩個條件就都滿足了。復(fù)雜度\(O(n\log n)\)，但懶得寫了，后面的代碼是kdt的80pts，代碼。

【NOI2019】回家路線

復(fù)習一下斜率優(yōu)化，為了寫凸包二分的板子就沒寫單調(diào)隊列。記得這個題我去年還只會暴力來著，所以這是否說明我可能比去年強了一點？代碼。

【UER #6】尋找罪犯

發(fā)現(xiàn)如果只對每個人建點的話不是很好做，于是考慮把每個人的供詞也建出點來；考慮2-sat，人與供詞以及供詞與人之間的連邊比較顯然，問題是如何利用2-sat來實現(xiàn)每個犯人最多只能說一句假話的限制。一個暴力的想法是對于一條供詞\((x,y)\)，另這個供詞為假向\(x\)說的其他供詞為真連邊；即如果\((x,y)\)這條供詞為假，那么就能推出\(x\)說的其他供詞為真，這樣連邊的復(fù)雜度是\(O(m^2)\)的。顯然可以對于每一個人將其說的供詞列出來，搞一個前后綴優(yōu)化建圖，這樣復(fù)雜度就是線性了。代碼。

ZR省選十連測Day2C LCA on Tree

設(shè)\(G(x)=(sz_x+1)W_x\)，\(sz_x\)表示\(x\)這棵子樹的大小，\(W_x\)表示子樹\(x\)的權(quán)值和；通過觀察不難發(fā)現(xiàn)\(F(x)=G(x)-\sum_{v\in son(x)}G(v)\)?？紤]這個東西可以拆成\(G(x)\)本身的貢獻、\(x\)重兒子的貢獻、輕兒子的貢獻；由于重兒子只有一個，所以維護一下子樹和就能快速求出\(x\)本身和重兒子的貢獻；至于輕兒子的貢獻，我們可以暴力跳重鏈。由于這個修改操作比較別致，所以需要按照bfs序來維護一些線段樹、樹狀數(shù)組來支持對兒子和孫子進行修改，推推式子就沒了。代碼。

多校聯(lián)考104B 藍超巨星

設(shè)\(L\)是最小的滿足\(aL\equiv 0(\rm mod\ n)\)的正整數(shù)，顯然\(L\)就是循環(huán)左移的最小循環(huán)節(jié)?？紤]枚舉答案\(\rm{mod}\ L\)的值，這樣我們就能知道循環(huán)左移了多少位。

對于\(S\)中的每一種字符我們記錄其第一次出現(xiàn)位置，就可以知道在循環(huán)左移當前位數(shù)下，每一種字符應(yīng)該變成什么字符。考慮字符\(c\)想要變成\(c'\)，首先得滿足\(c\)和\(c'\)在同一個置換環(huán)里，同時還得保證出現(xiàn)位置是相同的。搞一個\(hash\)，對于每一種字符記錄其相鄰出現(xiàn)位置的差，就能快速判斷了。之后我們就得到了一些形如\(ans\equiv b_i(\rm{mod}\ a_i)\)的同余方程，直接excrt合并下來就好了。時間復(fù)雜度是\(O(|\sum|n\log n)\)，代碼。

多校聯(lián)考103B 農(nóng)民(farmer)

對于一個點\(x\)，如果\(y\)是\(x\)的祖先且\(x\)在\(y\)的左子樹中，那么稱\(y\)是關(guān)于\(x\)的左偏點；如果\(x\)在\(y\)的右子樹中，就稱\(y\)是關(guān)于\(x\)的右偏點。發(fā)現(xiàn)如果\(x\)能被訪問到的話，必須要滿足\(x\)小于所有左偏點的點權(quán)，大于所有右偏點的點權(quán)，于是我們只關(guān)心左偏點點權(quán)最小值和右偏點點權(quán)最大值。考慮樹鏈剖分，發(fā)現(xiàn)在沒有二操作的時候每一條重鏈的偏移關(guān)系是固定的，于是可以直接用線段樹來維護；跳輕邊的時候直接判斷即可。顯然只會跳\(\log n\)次輕邊，所以復(fù)雜度是正確的。考慮二操作的意義就是使得一個子樹內(nèi)部的偏移關(guān)系取反，即左偏變成右偏，右偏變成左偏。我們對于左偏點的右偏點均維護最大值和最小值，在線段樹上打一個翻轉(zhuǎn)標記交換最大值和最小值即可。

復(fù)雜度是\(O(m\log^2 n)\)，代碼。

多校聯(lián)考101A 石子游戲

轉(zhuǎn)化一下題意，就是找到一個盡量小的集合\(\{p_i\}\)使得\(\displaystyle \bigoplus_{i=1}^m a_{p_i}=\displaystyle \bigoplus_{i=1}^n a_{i}\)，一個顯然的形式是集合大小\(m\)不會超過\(\log w\)。從線性基的角度來考慮，至多\(\log w\)個可以插入線性基的元素即可表示出\([0,w)\)之間的所有數(shù)。所以我們暴力做\(\log w\)遍fwt，每做完一次ifwt回來看一下那個點的點值是否為\(0\)。fwt可以直接轉(zhuǎn)成點值對位相乘，求一個點ifwt回來的點值可以直接掃一遍。于是復(fù)雜度是\(O(w\log w)\)，代碼。

多校聯(lián)考100A 小B的棋盤

這個對稱中心反映的其實就是這些點兩兩匹配的情況，即對稱中心一定是一對匹配的點形成的線段的中點。于是如果\(n>k\)，那么至少會有一對匹配的點來自于給定的\(n\)個點中，這樣的話可能的對稱中心一定是某一對匹配點的中點；如果\(n\leq k\)，那么對稱中心就會有無限多個了，輸出-1即可。

一個最暴力的想法是如果\((x,y)\)能成為對稱中心的話，那么至少有\(\frac{n-k}{2}\)對點形成的線段的中點是\((x,y)\)，于是可以暴力求出所有點對的中點，之后排序掃一遍即可，復(fù)雜度是\(O(n^2\log n)\)?？紤]將所有點按照橫坐標從小到大排序，那么如果線段\(AB(A<B)\)和線段\(CD(C<D)\)的中點相同，必然要滿足\(A<C<D<B\)，而我們需要匹配出至少\(\frac{n-k}{2}\)條線段，所以需要至少\(n-k\)個點；我們排序之后枚舉這樣的點對\(i,j\)，顯然必須有\(j-i+1\geq n-k\)，即\(i,j\)能匹配的話他們之間就必須有至少\(n-k\)個點，所以這樣的點對不會超過\(k^2\)個，暴力這樣的點對，利用上面那個單調(diào)的性質(zhì)雙指針匹配即可，復(fù)雜度是\(O(nk^2)\)，代碼。

多校聯(lián)考99B 西行寺無余涅槃

一個序列\(A\)做異或fwt的本質(zhì)其實是這樣的\({\rm FWT}(A)_i=\displaystyle \sum_{j=0}^{len-1}(-1)^{{\rm popcount}(i\& j)}A_j\)。

還是丟一份別人的題解吧，復(fù)雜度是\(O(2^{k-1}k(n+2^m))\)，代碼。

多校聯(lián)考97B 幻化成風

發(fā)現(xiàn)要求\(\{b_i\}\)中的數(shù)兩兩不同還是很難做的，于是考慮容斥，一個暴力的想法是直接枚舉子集劃分，使得一個集合里的數(shù)強行相等。這個容斥系數(shù)之前一直不會來著，去vuq里問了才知道是\(\displaystyle \prod_{}(-1)^{size-1}(size-1)!\)，\(size\)即連通塊的大小。

被劃分到了同一個子集里的數(shù)需要強制相等，于是冪次可以直接相加，我們要求的即\(\displaystyle \prod_{i=1}^{m'}x_i^{c_i}=n!\)的方案數(shù)，這里不要求\(x_i\)互不相等。不難想到\(n!\)可以寫成\(\displaystyle \prod p_i^{\omega_i}\)，于是我們只需要對每一個\(\omega_i\)求方程\(\displaystyle \sum_{j=1}^{m'}c_jx_j=\omega_i\)的方案數(shù)之后乘起來即可。從生成函數(shù)的角度考慮，發(fā)現(xiàn)這其實就是在求\(\displaystyle \prod_{i=1}^{m'}\frac{1}{1-x^{c_i}}\)，直接暴力求出分母暴力多項式求逆即可，由于分母的最高次冪不會超過\(m\)，所以復(fù)雜度其實是\(O(nm)\)的。由于我們還需要暴力子集劃分，所以復(fù)雜度是\(O({\rm Bell}(m)nm)\)的。

注意到我們其實并不關(guān)心子集劃分的情況，我們只關(guān)心\(\{c_i\}\)長什么樣子。于是我們可以爆搜\(\displaystyle \sum a_i\)的整數(shù)劃分，之后用一個狀壓dp來計算這種劃分方案的系數(shù)。這個狀態(tài)dp大概就是\(dp_{x,S}\)表示已經(jīng)湊出了前\(x-1\)個集合，當前的狀態(tài)為\(S\)的方案數(shù)，這里的\(S\)并不是一個二進制狀態(tài)，而是記錄每一種\(a_i\)還剩下多少個。由于\(\displaystyle \sum a_i,m\leq 30\)，所以這個狀態(tài)數(shù)非常小，直接暴力記搜轉(zhuǎn)移即可。

但是這樣還是有\(10^3\)種整數(shù)劃分是有用的，于是還是T了，代碼。

多校聯(lián)考94A a

考慮貢獻的式子\(\frac{(A_i-A_j)B_iB_j}{2A_iA_j}=\frac{B_iB_j}{2}(\frac{1}{A_j}-\frac{1}{A_i})=\frac{1}{2}(B_i\times \frac{B_j}{A_j}-B_j\times \frac{B_i}{A_i})\)，發(fā)現(xiàn)這個貢獻可以看成\((B_i,\frac{B_i}{A_i})\)叉\((B_j,\frac{B_j}{A_j})\)和原點形成的有向三角形面積。題目中要求的路徑滿足\(B_i\)，即點的橫坐標是單峰的；貢獻和盡量大且還需要回到起點。發(fā)現(xiàn)這其實就是描述了一個凸包，于是求一下凸包面積即可。復(fù)雜度\(O(n\log n)\)。

多校聯(lián)考96B 仙人掌

顯然一個點的點權(quán)=\(\text{兒子被操作次數(shù)}+\text{父親被操作次數(shù)}\)；如果操作\(x\)這個點，那么只有\(x\)的父親這一個點的\(\text{兒子被操作次數(shù)}\)改變；而對于\(x\)的所有兒子\(\text{父親被操作次數(shù)}\)都增加了\(1\)。

顯然父親的點權(quán)我們可以直接\(O(1)\)得到，難點在于處理兒子的點權(quán)異或值?？紤]在\(x\)處將\(x\)的所有兒子都存下來，那么我們需要一個數(shù)據(jù)結(jié)構(gòu)，支持整體加一、查詢整體異或值；同時一個兒子的點權(quán)還可能因為其子樹內(nèi)部的點影響而改變，所以還需要插入、刪除。

考慮\(x\)變成\(x+1\)在二進制下的變化，發(fā)現(xiàn)就是從低位到高位找到第一個\(0\)，之后把后面的\(1\)都變成\(0\)即可；可以用一棵trie樹來維護，插入的時候按照從低位到高位的順序插入，整體加一時只需要交換左右兒子，之后遞歸到左子樹（即原來的右子樹，在這一位上是\(1\)）即可，同時維護子樹異或值就能查詢?nèi)之惢蛑盗恕?/p>

時間復(fù)雜度是\(O((n+m)\log n)\)，代碼。

[NOI2017]整數(shù)

做法非常顯然，把\(a\)分解成二進制，顯然只會影響\(b\)往前的\(30\)位。把這\(30\)位拿出來，做一個二進制下的豎式加法/減法即可。最后可能還需要處理一個進位/借位的問題，需要找到前面的第一個\(0/1\)，同時把一段\(1/0\)取反。不難發(fā)現(xiàn)這些操作線段樹都能進行，時間復(fù)雜度是\(O(30n\log n)\)。有了這個做法不難想到將\(30\)個二進制位壓在一起，就能做到\(O(n\log n)\)了。

但是壓位太難寫了，于是考慮換一個做法。不壓位線段樹的復(fù)雜度帶一個\(30\)的原因是處理\(b\)往前的\(30\)個數(shù)位時都需要去線段樹上單點查/改，考慮找一個數(shù)據(jù)結(jié)構(gòu)能快速實現(xiàn)把這\(30\)位提取出來，并快速地把修改之后的\(30\)個數(shù)位修改回去。發(fā)現(xiàn)平衡樹可以輕松勝任這個工作，用兩棵平衡樹分別維護\(0/1\)出現(xiàn)的未知，找這\(30\)個數(shù)位就是一個區(qū)間提取，將修改后的\(30\)個數(shù)位插入可以直接建出二叉樹，將這個二叉樹插入進去。于是單次的復(fù)雜度就是\(O(30+\log n)\)，整體復(fù)雜度是\(O(n\log n+30n)\)。

但是由于splay常數(shù)實在是太大了，所以loj也跑不過去，代碼。

CF547D Mike and Fish

對于點\((i,j)\)我們視為一條從\(i\)連向\(j\)的無向邊；現(xiàn)在我們要給所有無向邊定一個方向，如果是\(i\rightarrow j\)，那么就將\((i,j)\)涂成紅色；如果是\(j\rightarrow i\)，那么就將\((i,j)\)涂成藍色。發(fā)現(xiàn)只需要保證給邊定向之后每個點均滿足\(|\text{入度}-\text{出度}|\leq 1\)，就等價于使得每行每列兩種顏色最多相差\(1\)。

一個特殊情況是所有點的度數(shù)都是偶數(shù)，那么這張圖就是一張歐拉圖，我們dfs一遍找一條歐拉回路，沿著歐拉回路給每條邊定向，這樣每個點均滿足入度=出度，符合要求；如果存在奇度點，那么奇度點的個數(shù)肯定是偶數(shù)個，令所有奇度點向一個虛點連邊，這樣虛點的度數(shù)也肯定是偶數(shù)。在這張圖上找歐拉回路并給邊定向即可，給邊定向后將虛點和所有與虛點相連的邊刪去，發(fā)現(xiàn)對于奇度點均滿足\(|\text{入度}-\text{出度}|=1\)，其余點均滿足\(\text{入度}=\text{出度}\)。

其實還胡了一個用lct維護的做法，但是太憨憨了，就不寫了。代碼。

[JLOI2016]成績比較

不想寫題解了，憨憨題，大概就是容斥一波之后胡亂推推式子，最后得到一個需要自然數(shù)冪次方和的東西，大力拉格朗日即可。復(fù)雜度\(O(m^2n)\)，代碼。

[APIO2016]劃艇

首先需要將區(qū)間離散化成若干個左閉右開的區(qū)間，發(fā)現(xiàn)給每個學校選一個值并且遞增是非常困難的，因為這個值是\(10^9\)級別。但是我們找出一個遞增的序列再分給每個學校卻是非常可行的，這樣我們只需要保證學校的編號遞增，而學校的編號只有\(500\)級別。

設(shè)\(dp_{i,j}\)表示對于離散化后的前\(i\)個區(qū)間，最大的學校編號為\(j\)的方案數(shù)。轉(zhuǎn)移的話我們就在當前這段區(qū)間里找一個更大的學校，大概可以寫成這樣：

\(len_i\)表示第\(i\)段區(qū)間的長度，\(S_i[k+1,j-1]\)表示在第\(i\)段區(qū)間中有多個可以填的學校編號\(x\)滿足\(k+1\leq x\leq j-1\)。大概就是枚舉一下前\(i-1\)個區(qū)間中的最大編號\(k\)，那么在區(qū)間\(i\)中我們選擇的學校編號都需要大于\(k\)，最大的編號是\(j\)，那么我們就從\(S_i[k+1,j-1]\)個學校里選\(p\)個出來，讓這\(p\)個學校和編號為\(j\)的學校構(gòu)成一段上升序列即可。

直接暴力轉(zhuǎn)移的復(fù)雜度是\(O(n^4)\)。不難注意到最后的那個\(\sum\)只跟\(S_i[k+1,j-1]\)有關(guān)，而\(S_i[k+1,j-1]\)不會超過\(n\)，于是我們預(yù)處理\(S(z)=\sum_{p=0}^z\binom{len_i}{p+1}\binom{z}{p}\)就能做到快速轉(zhuǎn)移了，時間復(fù)雜度為\(O(n^3)\)，代碼。

CF527E Data Center Drama

• 無向圖存在歐拉回路的條件：所有點度數(shù)均為偶數(shù)。
• 無向圖存在歐拉路徑的條件：至多兩個點度數(shù)為奇數(shù)。
• 有向圖存在歐拉回路的條件：所有點均滿足入度=出度。
• 有向圖存在歐拉路徑的條件：一個點滿足出度-入度=1，作為起點；一個點滿足入度-出度=1，作為終點；其余點均滿足入度=出度。

這道題要求所有點的入度、出度均為偶數(shù)，那么就首先得保證每個點的度數(shù)均為偶數(shù)。于是先把圖構(gòu)造成一張歐拉圖，把奇度點拿出來，每兩個點連一條邊即可。進一步注意到一條邊會使一個點的入度+1，一個點的出度+1，即所有點的入度和+1，出度和+1；如果有奇數(shù)條邊，那么所有點的入度和和出度和也都會是奇數(shù)，不可能使得每個點的入度、出度均為偶數(shù)；所以存在偶數(shù)條邊是一個必要不充分條件，所以如果構(gòu)造成歐拉圖之后有奇數(shù)條邊，那么就隨便欽定一個點給它加一條自環(huán)即可。

之后不會了，觀察題解可以發(fā)現(xiàn)，我們跑一個歐拉回路，隔一條邊換一個方向即可，代碼。

CF627E Orchestra

一個經(jīng)典的做法枚舉左邊界、右邊界，之后就得到了一個長度為\(r\)的序列，并將問題轉(zhuǎn)化為求\(\geq k\)的子區(qū)間個數(shù)，用雙指針掃一下即可，復(fù)雜度是\(O(c^2r)\)；我們注意到\(k\)非常小，于是考慮利用一下這個性質(zhì)。還是枚舉左邊界，之后把所有的點都加進去，每次刪除最右邊的點。我們用雙向鏈表維護序列中大于等于\(0\)的元素，設(shè)\(l_i\)表示\(i\)前面第一個滿足到\(i\)的區(qū)間和\(\geq k\)的位置，一個顯然的事情是我們至多在鏈表上往前跳\(k\)次就能找到\(l_i\)。于是刪除一個點，即使得序列中某個元素減一，至多只會影響其后面\(k\)個點\(l_i\)的變化；且由于只是減一，所以對于減一后不合法的\(l_i\)最多在鏈表往前跳一步就是新的合法的\(l_i\)。于是在鏈表中刪除一個點的復(fù)雜度是\(O(k)\)的。

一個點最多只會被刪\(c\)次，所以復(fù)雜度是\(O(c^2+nck)\)，代碼。

SDOI2013淘金

一個顯然的事實是行列是獨立的，設(shè)\(g(i)\)表示\(1\)到\(N\)中滿足\(f(x)=i\)的\(x\)有多少個，那么\((i,j)\)上的金子數(shù)量就是\(Au(i,j)=g(i)\times g(j)\)。寫個爆搜發(fā)現(xiàn)合法的數(shù)位積大概只有八千種左右，于是可以搞一個數(shù)位\(dp\)把所有的\(g\)都算出來。\(dp(i,j,0/1,0/1)\)表示從高到低填了\(i\)位，數(shù)位積為\(j\)，是否卡上界，是否有前導\(0\)。

求出\(g\)之后要求出前\(k\)大的\(Au(i,j)\)的和，將\(g\)排序之后開個堆即可。代碼。

SDOI2019世界地圖

考慮現(xiàn)在有了前綴mst以及后綴mst，我們怎么合并得到新的mst；一個直觀的想法是用類似lct維護mst的做法，對于新加入的一條邊，看一下加入后是否成環(huán)；如果不成環(huán)就直接加入，否則就斷掉環(huán)上邊權(quán)最大的一條邊。我們注意到前后綴mst合并的時候新的邊都形如\((1,i)-(m,i)\)，即新加入的邊都是連在第一排和第\(m\)排之間?？紤]上面lct維護的過程，發(fā)現(xiàn)斷掉的邊一定在\((1,i)\)到\((1,j)\)的路徑上，否則就在\((m,i)\)到\((m,j)\)的路徑上，這樣的話就只有第一排和第\(m\)排的點是有用的，所以如果知道第一排和第\(m\)排和虛樹的話，我們把虛樹上的邊和新加入的邊拿下來做一個\(kruskal\)就能得到合并后的mst了。

考慮對于每一個前綴mst求第一排點形成的虛樹，后綴同理。對于前綴\(i-1\)，我們維護第一排和第\(i-1\)排形成的虛樹。只需要把第\(i\)排的點和邊拿下來，像回答詢問一樣做一個合并就能得到前\(i\)排的mst了，對于新的mst我們還是求出第一排和第\(i\)排形成的虛樹，繼續(xù)往后推即可。時間復(fù)雜度是\(O(n(q+m)\log n)\)。

CF582D Number of Binominal Coefficients

庫默爾定理：\(\binom{a+b}{a}\)中\(p\)的冪次等于\(a+b\)在\(p\)進制下的進位數(shù)。證明的話看這位老哥的吧。

\(p^\alpha|\binom{n}{k}\)等價于\(\binom{n}{n-k}\)的\(p\)冪次數(shù)\(\geq \alpha\)。考慮數(shù)位\(dp\)，把\(A\)轉(zhuǎn)化為\(p\)進制(直接暴力轉(zhuǎn)的復(fù)雜度是\(O(\log_pA\log A)\))，搞一個\(f(i,j,0/1,0/1)\)表示從高到低填到了第\(i\)位，\(a+b\)的進位次數(shù)為\(j\)，是否卡上界，是否需要下一位的進位的方案數(shù)。轉(zhuǎn)移大力分類討論即可。

CF573E Bear and Bowling

顯然非負數(shù)是要全部選上的，考慮對負數(shù)的選擇做一個\(dp\)。設(shè)\(dp_{i,j}\)表示前\(i\)個數(shù)里選了\(j\)個負數(shù)，轉(zhuǎn)移非常簡單，為\(dp_{i,j}=\max\{dp_{i-1,j},dp_{i-1,j-1}+a_i\times j+rsum\}\)，其中\(rsum\)表示\(i\)后面非負數(shù)的和。

寫個暴力把dp數(shù)組打出來，可以發(fā)現(xiàn)dp數(shù)組是單增的，且差分之后是單減的，且對于每一個\(i\)，必定存在一個\(k\)滿足，\(\forall j\in [0,k],dp_{i,j}=dp_{i-1,j}\)且\(\forall j\in (k,i],dp_{i,j}=dp_{i-1,j-1}+a_i\times j+rsum\)，即存在一個分界點使得前面都是第一種轉(zhuǎn)移，后面都是第二種轉(zhuǎn)移。感性理解一下就是負數(shù)選得越多，貢獻增長就越慢，于是差分數(shù)組單減；而只有當\(dp_{i-1,j}-dp_{i-1,j-1}\)即差分后的結(jié)果小于\(a_i\times j+rsum\)的時候才會進行第二種轉(zhuǎn)移，所以大概只有后綴進行了轉(zhuǎn)移。瞎口胡的，感覺好假啊

于是可以用數(shù)據(jù)結(jié)構(gòu)維護這個\(dp\)，考慮維護差分數(shù)組，設(shè)\(c_j=dp_{i-1,j}-dp_{i-1,j-1}\)；我們二分找出兩種轉(zhuǎn)移的分界點\(k\)，則\(c'_k=a_i\times k+rsum\)，\(\forall j\in (k,i],c'_i=c_{i-1}+a_i\)，發(fā)現(xiàn)\(k\)后面相當于整體往后移了一位之后進行了一次區(qū)間加，而\(c_k\)的修改就是一個單點插入；于是我們可以用splay來維護差分數(shù)組即可。

復(fù)雜度的瓶頸在于二分找分界點，于是復(fù)雜度是\(O(n\log^2 n)\)的，代碼。

UOJ#523 【美團杯2020】半前綴計數(shù)

對于兩個半前綴\([1,i_1]+[j_1,k_1],[1,i_2]+[j_2,k_2]\)，不妨假設(shè)\(i_1<i_2\)。那么這兩個半前綴本質(zhì)相同當且僅當\([j_1,k_1]=[i_1+1,i_2]+[j_2,k_2]\)，即后綴\(j_1\)和后綴\(i_1+1\)有一段長度為\(i_2-i_1\)的LCP。由此我們可以得出，當后綴\(j_1\)和后綴\(i_1+1\)的LCP長度大于\(1\)時，\([1,i_1]+[j_1,k_1]\)這個半前綴一定能被一個滿足\(i_2>i_1\)的前綴形成的半前綴表示出來。

于是考慮倒著枚舉每一個前綴，對于前綴\(i\)，我們考慮在\([i+1,n]\)中找本質(zhì)不同的，和后綴\(i+1\)的LCP長度為\(0\)的子串，這樣的子串拼上\([1,i]\)后一定和那些更大的前綴形成的半前綴本質(zhì)不同；倒著枚舉前綴的時候用SAM來構(gòu)建后綴樹，和后綴\(i+1\)LCP長度為\(0\)的子串在后綴樹上與\(i+1\)的LCA肯定是根節(jié)點，于是我們對于每個節(jié)點維護其來自根節(jié)點的哪個兒子，對于根節(jié)點的每個兒子維護其子樹內(nèi)本質(zhì)不同的子串個數(shù)即可。

時間復(fù)雜度\(O(n)\)，代碼。

LGP3476 [POI2008]TRO-Triangles

\(O(n^3)\)暴力非常顯然，枚舉三個點海倫公式爆算即可。考慮只枚舉一個點，欽定這個點為原點，其余點按照到這個點的極角序排序。眾所周知，叉積可以算三角形面積，于是快樂雙指針，對于每個點掃出最遠的叉積為正的點，分別維護橫縱坐標之和，就可以叉積快速算了。

時間復(fù)雜度\(O(n^2\log n)\),代碼。

LGP5769 [JSOI2016]飛機調(diào)度

把每一條路徑看成一個點，如果飛機能從\(i\)路徑切換到\(j\)路徑我們就連一條\(i\)到\(j\)的邊。不難發(fā)現(xiàn)由于時間是不斷增加的，所以這樣連邊得到的圖應(yīng)該是一張\(\rm DAG\)，直接跑\(\rm DAG\)最小路徑覆蓋即可。代碼。