2018HN省队集训
HNOI2018省隊集訓(xùn)
Day 1
流水賬
T1 tree
換根+求\(lca\)+求子樹和，一臉bzoj3083遙遠(yuǎn)的國度的既視感。子樹和討論一下就好了，\(lca\)？也是大力討論一波。
先寫了個線段樹標(biāo)記永久化，一發(fā)過了小樣例，然后大樣例。。。沒幾組詢問就\(WA\)了。寫了個暴力，每次輸出求出來的\(lca\)（我怎么這么機智啊），發(fā)現(xiàn)\(WA\)了，然后就對著自己的大力討論大力魔改。大概是\(10:00\)的時候大樣例終于過了，沒寫拍（因為不會寫\(win\)下的拍qaq）。
T2 function
看出來了結(jié)論，一直在\(yy\)怎么用斜率搞一搞。最終還是沒能\(yy\)出來，交了個\(42\)的暴力。
T3 or
一開始還以為自己只會寫\(O(n2^k)\)的暴力\(dp\)，然后轉(zhuǎn)念一想其實二進(jìn)制位都是等價的，就寫了個\(O(nk^2)dp\)過了樣例。最近有些\(ntt\)上癮所以當(dāng)然是順手敲了發(fā)\(ntt\)。
預(yù)估得分\(100+42+59=201\)，實際得分\(83+42+59=184\)。
T1被卡常qaq，我活該大常數(shù)。
總結(jié)
得分比較穩(wěn)定，該拿得分基本上都拿到了（卡常這件事出題人自己也沒想到）。T2在考場上缺乏去硬剛的信念與勇氣導(dǎo)致沒有做出來。T3的正解比較神仙。
簡要題解
tree
在換根的前提下子樹有三種情況：若詢問點不是根的祖先則子樹就是原來的子樹，若詢問點就是根則子樹就是整棵樹，若詢問點是根的祖先則子樹是整棵樹除去根所在的詢問點的那個兒子。這部分就是bzoj遙遠(yuǎn)的國度。
\(lca\)的情況相對復(fù)雜一些：若兩個點都在根的子樹中則\(lca\)就是在原樹中的\(lca\)，若一個在一個不在則\(lca\)就是根，若兩個都不在，需要判斷兩點路徑和根到\(1\)號點路徑有沒有交，也就是判斷兩點在原樹中的\(lca\)是不是根的祖先，若不是則\(lca\)還是原樹中的\(lca\)，否則\(lca\)是路徑交中深度最大的那個點。
function
首先一組詢問\((x,y)\)的答案是\(\min_{i\in[1,y]}S_y-S_i+A_i(x-y+i)\)，其中\(S_i\)是\(A_i\)的前綴和。
以\(x-y\)為自變量，相當(dāng)于在所有形如\(y=A_ix+A_ii-S_i\)的直線中找一個最小值，維護(hù)下凸殼就行了。
由于存在一些特殊性質(zhì)所以可以用單調(diào)棧維護(hù)凸殼。
or
首先觀察一下\(dp\)式：
\[dp[i][j]=\sum_{k=1}^{j}dp[i-1][j-k]\times\binom{j}{k}\times2^{j-k}\]
也就是
\[\frac{dp[i][j]}{j!}=\sum_{k=1}^{j}\frac{dp[i-1][j-k]\times2^{j-k}}{(j-k)!}\times\frac{1}{k!}\]
構(gòu)造指數(shù)型生成函數(shù)
\[F_i(x)=F_{i-1}(2x)\times (e^x-1)\]
（\(e^x=\sum_{i=0}^{\infty}\frac{1}{i!}x^i\)，\(F_{i-1}(2x)\)是因為把\(2^{j-k}\)和生成函數(shù)里的\(x^{j-k}\)合并了）
\[F_n(x)=\prod_{i=0}^{n-1}e^{2^ix}-1\]
當(dāng)\(n\)是偶數(shù)的時候滿足\(F_n(x)=F_{\frac n2}(x)\times F_{\frac n2}(2^{\frac n2}x)\)
所以倍增求一下就好了，分\(n\)是奇數(shù)還是偶數(shù)討論一下（偶數(shù)直接除二，奇數(shù)減一變成偶數(shù)）
落實情況
| 完成情況 | corrected | corrected | corrected |
Day 2
流水賬
T1看了半天發(fā)現(xiàn)是不會做的。先寫了\(30pts\)暴力，然后發(fā)現(xiàn)“只有一個質(zhì)因子”就可以完全按照大小來做，就寫了個\(BIT\)（結(jié)果\(laofu\)說值的個數(shù)很少只要開桶就行了）
T2先寫了個暴力打個表，想著\(40pts\)的狀壓結(jié)果推出來了一個\(O(n)\)的式子，直接就\(80pts\)了。
T3\(10pts\)暴力
T2打表，塊大小\(50w\)打了\(60k\)（三個表），本機跑極限數(shù)據(jù)開\(O2\)要\(5s\)。
預(yù)估得分\(40+80+10=130\)，實際得分\(40+0+10=50\)。
由于日?？荚嚪植磺宓降诇y文件夾內(nèi)還是文件夾外所以習(xí)慣性地把三份代碼都粘到文件夾外，我也不知道為什么就按成了\(Ctrl-x\)。于是愉快地“未找到源程序”qaq。
以后這種事情還是不要干了吧。
總結(jié)
我覺得這個分應(yīng)該是我的極限實力了吧qaq。
簡要題解
walk
留坑
game
首先\(O(n)\)的答案式是\(n!-2\sum_{i=0}^{n-1}i!+\sum_{i=0}^{n-2}i!(n-i-1)+1\)
大力開一下\[原式=n!-2\sum_{i=0}^{n-1}i!+(n-1)\sum_{i=0}^{n-2}i!-\sum_{i=0}^{n-2}i!\times i+1\\=n!-2\sum_{i=0}^{n-1}i!+(n-1)\sum_{i=0}^{n-2}i!-\sum_{i=0}^{n-2}[(i+1)!-i!]+1\\=n!-3\sum_{i=0}^{n-1}i!+n\sum_{i=0}^{n-2}i!+2\\=(n-3)\sum_{i=0}^{n-1}i!+2\]
所以就只要求一個階乘前綴和，打表階乘以及前綴和即可。
string
詢問離線，從小到大枚舉\(r\)，維護(hù)每個左端點的答案。
有一個這樣的性質(zhì)：一個串的所有回文后綴一定可以被分為不超過\(\log n\)個等差數(shù)列。
先考慮最長回文后綴，那么所有長度超過它的一半的回文后綴一定會構(gòu)成等差數(shù)列（這個畫畫圖就好了），要想不滿足等差必須讓長度減小一半，所以最多只有\(\log n\)個等差數(shù)列。
每個等差數(shù)列會讓一段連續(xù)的\(l\)的答案增大\(1\)。具體來講，這一段的左端點是等差數(shù)列中最大的回文后綴上一次出現(xiàn)的位置+1（如果之前沒出現(xiàn)過就是\(1\)），右端點是等差數(shù)列中最小的回文后綴的出現(xiàn)位置。
用線段樹維護(hù)每個回文后綴最后出現(xiàn)的位置（為保證復(fù)雜度修改的時候只能修改最長回文后綴，所以查詢的時候要查該回文后綴在回文樹上的整棵子樹），然后用樹狀數(shù)組維護(hù)每個左端點的答案。
落實情況
| 完成情況 | N/A | corrected | corrected |
Day 3
流水賬
T1想了一個\(O(n\log^2n)\)的假算法，過了大樣例，感覺很對的樣子。
T2看上去像是個\(dp\)，不管了先去做T3。
T3打表，觀察規(guī)律無果，\(10pts\)滾粗。
發(fā)現(xiàn)T1的算法是假的，但是并沒有想到正解。
T2\(yy\)了半天寫了一個\(O(n^3)\)的做法，下考前寫了鏈，感覺\(O(n^2)\)的做法也不是很難，只是沒有想清楚具體怎么實現(xiàn)所以就沒有寫。
預(yù)估得分\(??+50+10=??\)，實際得分\(95+50+10=155\)。
沒想到T1亂搞有\(95\)分，據(jù)說還有亂搞\(AC\)的。
總結(jié)
在T1上面糾結(jié)了太久，導(dǎo)致T2沒有把分?jǐn)?shù)打滿。如果是在滿狀態(tài)下開T2的話應(yīng)該可以拿到\(80\)分的樣子吧。
簡要題解
c
破環(huán)成鏈，對于\(l<r\)的線段，新加入線段\([l+m,r+m]\)，否則加入線段\([l,r+m]\)。這樣就需要選出一個長為\(m\)的區(qū)間包含盡可能多的不相交線段。
考慮強制每一條線段作為第一條線段，根據(jù)貪心，每選過一條線段之后下一條選的線段是確定的。不妨記為\(nxt_i\)，那么我們只關(guān)心每一條線段跳多少次\(nxt\)后達(dá)到\(m\)長度。把\(nxt\)數(shù)組倍增實現(xiàn)即可。
a
暴力枚舉這\(k\)個人路徑的交，這肯定是樹上的一條簡單路徑。那么這條路徑對答案的貢獻(xiàn)就是\(f_x\times f_y\)，其中\(x,y\)是枚舉的兩個點，\(f_x\)表示在\(x\)的子樹中選出\(k\)個點使得兩兩\(lca\)是\(x\)的方案數(shù)。
如果\(x,y\)其中一點是路徑的\(lca\)，不妨設(shè)是\(x\)，那么對答案的貢獻(xiàn)應(yīng)該是\(g_{x,y}\times f_y\)，其中\(g_{x,y}\)表示點\(x\)以\(y\)為根方向時的\(f\)值。
考慮滿足“兩兩\(lca\)是\(x\)”這一條件，顯然需要有若干個點在\(x\)上，然后在\(x\)的每個子樹中選至多一個點。
設(shè)一個多項式\(P_x(x)\)表示在\(x\)中選出\(i\)個子樹的方案數(shù)的生成函數(shù)，鑒于每棵子樹只能選一個，所以\(P(x)=\sum_{son}(1+size_{son}x)\times(1+x+x^2+x^3+...)\)，對于每個點分治\(FFT\)即可，這樣的總復(fù)雜度是\(O(n\log^2n)\)的。
然后求\(f\)的話就是\(\sum_{i=0}^{\min(k,deg_x)}A_k^i\times [x^i]P_x(x)\)，算這個的復(fù)雜度是\(O(n)\)的。
這樣可以求出所有的\(f\)，至于求\(g_{x,y}\)，其實就是求其生成函數(shù)\(Q_{x,y}(x)=P_x(x)\times\frac{1+(n-size_y)x}{1+size_yx}\)，這個東西是一個多項式除以二項式的形式，是可以做到\(O(deg)\)的。具體使用姿勢可以參考\(CTSC2018\)假面一題。
這樣對于每個兒子都直接\(O(deg)\)求一遍的話復(fù)雜度可能會退化成\(O(n^2)\)。發(fā)現(xiàn)除掉的內(nèi)容只和子樹\(size\)有關(guān)，而一個點不同大小的兒子最多只有\(O(\sqrt n)\)個，所以只要記一下，對\(size\)相同的兒子不重復(fù)處理即可。復(fù)雜度\(O(n\log^2n+n\sqrt n)\)
i
打表發(fā)現(xiàn)\(f(i)\)表示\(i\)在序列中出現(xiàn)的次數(shù)。
考慮一些東西的實際含義：\(g(i)\)表示前\(i\)個數(shù)出現(xiàn)的總次數(shù)，那么也就是第\(i\)個數(shù)最后出現(xiàn)的位置。
又因為\(g(i)\)是\(f(i)\)的前綴和，所以\(g(f(i))-f(f(i))=g(f(i)-1)\)，表示最后一個值為\(f(i)-1\)的位置（下標(biāo)）。
也就是說\(h(i)\)就表示從\(i\)往前每一段相同數(shù)字的最后一位的\(g(g(i))\)之和。
考慮\(g(g(i))\)怎么求。
\[g(g(i))-g(g(i-1))=\sum_{j=g(i-1)+1}^{g(i)}f(i)\\=\sum_{j=g(i-1)+1}^{g(i)}i=i\times f(i)\]
所以\(g(g(i))=\sum_{j=1}^{i}j\times f(j)\)
打表可以發(fā)現(xiàn)當(dāng)\(n\)達(dá)到\(10^9\)時\(f(n)\)不會超過\(10^6\)，所以可以按照\(f(i)\)分段處理，復(fù)雜度大概是\(O(T\times10^6)\)。
落實情況
| 完成情況 | corrected | N/A | corrected |
Day 4
流水賬
\(wfj\)的題，預(yù)感大事不妙。
T1這顯然就是\(wfj\)在考場上看錯題的那個版本吧。強行給\(HNOId2t3\)加一維狀態(tài)復(fù)雜度大概是\(O(n^2d^2)\)？反正能過前兩個\(subtask\)。
T2只會\(O(2^{x^2}n^2)\)的暴力。
T3我發(fā)現(xiàn)我不會\(O(n)\)做后面兩問，所以就爆零了。
想寫個T2的退火，結(jié)果沒有獲得比暴力分更高的分?jǐn)?shù)。
大概是\(12:00\)的時候一群一中\(dalaoAK\)離場了，好強啊。
預(yù)估得分\(30+15+0=45\)，實際得分\(30+15+0=45\)。
不得不說穩(wěn)得一匹。
總結(jié)
希望接下來的幾天里沒有今天這樣的毒瘤場。
p.s. \(wfj\)被阿掉了（不過他本人似乎還不滿足？）
簡要題解
y
凸優(yōu)化
s
套結(jié)論
f
不會
落實情況
| 完成情況 | N/A | N/A | N/A |
Day 5
流水賬
T1一眼網(wǎng)絡(luò)流的既視感，一開始想著建立二分圖，然后。。。一個黑點匹配兩個白點？還要最大權(quán)匹配？不太可做吧。感覺自己不太會寫\(30pts\)的狀壓\(dp\)，只要硬著頭皮剛正解。
大概是\(9:00\)左右的樣子靈感突顯：拆成一個三分圖。然后二十分鐘敲完費用流，一測大樣例就過了，爽。
T2看了一眼，就是用樹剖維護(hù)\(bitset\)然后搞一搞，但是統(tǒng)計答案我不會啊，只好去看T3。
T3這這這不是我哪天在洛谷上見過的原題嗎？有一個很顯然的結(jié)論：枚舉左端點，右端點從左往右掃排名一定單調(diào)減，權(quán)值一定單調(diào)不降，所以就可以二分交點，問題轉(zhuǎn)化為求一個子串在原串中的排名的問題。又是因為不太會寫\(30pts\)所以選擇剛正解，然后胡亂\(yy\)了一個\(O(n\log^2n)\)的做法，希望不會被卡常。
后來發(fā)現(xiàn)T1也是原題。跑到洛谷上交了兩道題，于是莫名變成了\(IOI\)賽制。（雖然基本上都是一遍過的）
T2發(fā)現(xiàn)了一種網(wǎng)絡(luò)流統(tǒng)計答案的方法，但是寫完T3已經(jīng)\(12:30\)了，又覺得網(wǎng)絡(luò)流應(yīng)該跑不過幾個點，就沒寫了（結(jié)果蘿卜跟我講網(wǎng)絡(luò)流有\(45pts\)？）
預(yù)估得分\(100+5+100=205\)，實際得分\(100+5+100=205\)。
總結(jié)
T2沒有嘗試更高的分?jǐn)?shù)比較可惜。
簡要題解
marshland
我們稱\(X+Y\)為奇數(shù)也就是有危險度的點為黑點，\(X+Y\)為偶數(shù)也就是沒有危險度的點為白點。
而白點內(nèi)部又分為兩類：行號（列號也行）為奇數(shù)和偶數(shù)的點，將其分別稱為\(1\)類點和\(2\)類點。
可以發(fā)現(xiàn)每一塊石頭都恰好覆蓋了一個黑點、一個\(1\)類點和一個\(2\)類點。
所以建立一個類似三分圖的模型：（用\((w,cost)\)表示容量為\(w\)費用為\(cost\)的邊）
\(S\)向每個\(1\)類點連\((1,0)\)，把每個黑點拆成入點和出點，每個\(1\)類點向相鄰的每個黑點的入點連\((1,0)\)，每個黑點的入點向出點連\((1,V_{i,j})\)，出點向相鄰的\(2\)類點連\((1,0)\)。
限制總流量不超過\(m\)，即求的是最大費用可行流而非最大費用最大流。仔細(xì)想一想就會發(fā)現(xiàn)石頭數(shù)量越多并不能保證解不更劣。
party
首先這幾個人聚會的點一定是\(lca\)。
用\(bitset\)維護(hù)每個點到樹鏈剖分中這個點的\(top\)的路徑并，再開一棵線段樹維護(hù)區(qū)間并集。
這樣查詢路徑的時候就可以做到一個\(\log\)。
考慮求出每個點到\(lca\)路徑的\(bitset\)，再求\(dp(S)\)表示\(S\)集合中的點到\(lca\)路徑的并。
根據(jù)霍爾定理答案就是\(\min(\frac{dp(S)}{|S|})\)
復(fù)雜度是\(O((n+qc\log n+q2^c)\frac {m}{\omega})\)。
platform
有一個很顯然的結(jié)論：枚舉左端點，右端點從左往右掃排名一定單調(diào)減，權(quán)值一定單調(diào)不降，所以就可以二分交點。
問題轉(zhuǎn)化為求一個子串在原串中的排名的問題，也就是求原串中有多少個本質(zhì)不同子串的字典序比給定子串的要大。
我們假設(shè)要算的是子串\(S_{l..r}\)。
在后綴排序中排在\(l\)后面的所有后綴中本質(zhì)不同的子串的字典序一定都比\(S_{l..r}\)的要大。
而排在前面的呢？一定沒有嗎？
我們發(fā)現(xiàn)保證沒有的情況當(dāng)且僅當(dāng)\(S_{l..r}\)這個子串是在后綴\(l\)中第一次出現(xiàn)。
如果是第一次出現(xiàn)那么可以直接計算答案\(ans_{S_{l..r}}=sun_n-sum_{Rank_l}+n-r+1\)
否則我們就找到這個子串第一次出現(xiàn)的位置然后再計算即可。
如何求第一次出現(xiàn)的位置？在\(SA\)上二分\(lcp\)即可。
復(fù)雜度兩個\(\log\)，然而比\(std\)一個\(\log\)的線段樹跑得還快qaq。
落實情況
| 完成情況 | corrected | corrected | corrected |
Day 6
流水賬
瀏覽一遍題目以后發(fā)現(xiàn)只有T2比較可做，就想了想容斥那方面的，也就是計算所有包含\(0,1,2,3\)對矛盾的三元組。
\(0\)想了蠻久怎么\(O(1)\)算，然后。。。我選擇寫\(O(n)\)的。
\(1\)直接枚舉邊，感覺比\(0\)的還要好寫一點。
\(2\)的話枚舉點，我開了個\(vector\)瞎搞，還帶個排序的\(\log\)。反正這也不是復(fù)雜度瓶頸。
\(3\)就是前天晚上葉佬講過的東西，這個結(jié)論的證明以及實現(xiàn)應(yīng)該都不難。
沒造極限數(shù)據(jù)測，所以存在翻車的可能性。
然后T1寫了\(A_i,B_i>0\)的點，交了一個\(O(n!^2)\)的鬼玩意。T3寫了個\(Hash\)。
預(yù)估得分\(20+100+20=140\)，實際得分\(30+100+20=150\)。
某人又被C++11卡CE了
總結(jié)
會寫的都寫了。T2沒造極限數(shù)據(jù)測比較容易出鍋，這次沒翻不保證以后也不會翻。
簡要題解
gift
對于排列\(a,b\)，連邊\((a_i,b_i)\)，這樣會形成若干個環(huán)。每個環(huán)需要交換環(huán)長\(-1\)次，所以答案就是\(n-\)環(huán)的數(shù)量。
現(xiàn)在我們的排列是不完整的，也就是說構(gòu)出來的圖也是不完整的。因為答案只和環(huán)的個數(shù)有關(guān)，所以我們可以把一些已經(jīng)確定了的部分合并起來，這樣圖中就只剩下了四種東西：完整的環(huán)、起點確定終點不確定的鏈、起點不確定終點確定的鏈以及起點終點都不確定的鏈。
我們求出每一種東西的個數(shù)，這個可以直接\(O(n)dfs\)。
發(fā)現(xiàn)完整的環(huán)在計算過程中是沒有貢獻(xiàn)的，只是把答案全部向右移了一位，所以可以不用考慮。
我們需要用剩下的三種東西拼出若干個環(huán)的方案數(shù)，而實際上只要計算出用一種東西拼出若干個環(huán)的方案數(shù)然后卷積起來就可以了。
對于起點終點都不確定的鏈，這個的方案數(shù)是\(S[s1][i]\)，其中\(S[i][j]\)表示第一類斯特林?jǐn)?shù)，\(s1\)是這種鏈的數(shù)量。這個東西可以\(O(n^2)\)求出。
對于起點終點有一個確定的鏈，方案數(shù)不好直接求，但是可以求拼出至少\(i\)個環(huán)的方案數(shù)。
\(f[i]=\sum_{j=i}^{n}C[n][j]\times S[j][i]\times A[m+n-j][n-j]\)
其中\(n\)是這種鏈的數(shù)量，\(m\)是起點終點都不確定的鏈的數(shù)量，\(S\)是第一類斯特林?jǐn)?shù)，\(C,A\)分別是組合數(shù)與排列數(shù)。
然后做一個簡單容斥即可。復(fù)雜度\(O(n^2)\)。
注意最后還要乘上一個階乘。
girls
總答案=任意三點的貢獻(xiàn)-包含至少一對矛盾的三點的貢獻(xiàn)+包含至少兩對矛盾的三點的貢獻(xiàn)-包含至少三對矛盾的三點的貢獻(xiàn)。
第一部分可以考慮枚舉其中一個\(O(n)\)計算。
第二部分枚舉邊，計算剩下的\(n-2\)個點\(O(m)\)。
第三部分枚舉點，對一個點的相鄰點排序，然后分當(dāng)前點是最小、次小還是最大三種情況討論，\(O(n\log n)\)。
第四部分就是三元環(huán)計數(shù)，可以將無向圖重定向，每條邊都指向度數(shù)較大的那個點，若度數(shù)相同則指向標(biāo)號較大的點。可以發(fā)現(xiàn)這樣構(gòu)出了一個\(DAG\)，而且保證每個點的出度不超過\(\sqrt m\)。
因為對于一個原圖中度數(shù)小于\(\sqrt m\)的點顯然成立，對于一個原圖中度數(shù)大于等于\(\sqrt m\)的點，要連向他的點的度數(shù)至少大于等于\(\sqrt m\)，然后這樣的點至多只有\(\sqrt m\)個，于是證明這個結(jié)論成立。
在\(DAG\)中的一個三元環(huán)一定是有兩條邊共終點，我們考慮枚舉剩下的那一條邊，這樣這條邊起點終點的鄰接點集合的交就是找出來的那些三元環(huán)。這樣一來其實三元環(huán)的數(shù)量也不超過\(m\sqrt m\)，復(fù)雜度\(O(m\sqrt m)\)。
string
落實情況
| 完成情況 | corrected | corrected | N/A |
Day 7
流水賬
新一代的毒瘤題啊。
T1只會寫爆搜，然后寫了樹的\(10pts\)。（這好歹也是正解的第一步啊）
T2想偏了，卡在高斯消元這個問題上，于是毫無進(jìn)展，成功爆零。
T3想寫個\(10pts\)。
預(yù)估得分\(20+0+10=30\)，實際得分\(20+0+0=20\)。
T3直接乘會爆\(long\ long\)，所以需要加一些奇妙的東西或者直接int128
總結(jié)
其實今天的題目并沒有想象中的那么毒瘤吧（畢竟自己還是可以改出來的）。
可能是受到了周圍環(huán)境的影響導(dǎo)致沒有做到最好的投入吧。
簡要題解
inkmaster
對于樹的情況，答案為\(C\times(C-1)^{n-1}\)。
在仙人掌上，顯然每一個環(huán)是獨立的，我們在計算這個環(huán)的時候不算環(huán)根，這樣把每個環(huán)的方案乘起來再乘個\(C\)就是最后的答案了。
考慮每一個環(huán)，某個環(huán)如果直接按照樹的方法去計算，會多算上首尾相同的方案，所以可以考慮容斥，減去強制首尾相同的方案（這時候倒數(shù)第二個點的顏色可能會與首尾相同），加上三個點相同的方案，減去四個...列出式子來就是：（假設(shè)環(huán)的大小不算環(huán)根是\(sz\)）
\[(C-1)^{sz}-(C-1)^{sz-1}+(C-1)^{sz-2}+...\pm (C-1)\]
（\(\pm\)取決于\(sz\)的奇偶性）
這是一個首項是\(C-1\)公比是\(1-C\)的等比數(shù)列，求一下和：
\[\pm(C-1)\frac{1-(1-C)^{sz}}{1-(1-C)}=\pm(C-1)\frac{1-(1-C)^{sz}}{C}\]
這樣就可以再\(O(\log n)\)的時間內(nèi)計算每一個環(huán)的貢獻(xiàn)了。
現(xiàn)在的問題在于：環(huán)的數(shù)量可以是\(O(n)\)個，一個個計算，復(fù)雜度是\(O(qn\log n)\)。
發(fā)現(xiàn)式子只和環(huán)的大小有關(guān)，而一棵\(n\)個節(jié)點的樹上不同大小的環(huán)的個數(shù)是\(O(\sqrt n)\)級別的。把大小相同的環(huán)的貢獻(xiàn)放在一起算，復(fù)雜度就是\(O(q\sqrt n\log n)\)。
branching
發(fā)現(xiàn)在每一個位置選擇\(2\)操作的結(jié)果都是一樣的，所以有一個比較顯然的結(jié)論：存在一個\(x\)值使得對于所有距離終點不超過\(x\)的點都選擇直接一步步走過去，而其余的點就選擇進(jìn)行\(2\)操作。
設(shè)進(jìn)行\(2\)操作走到終點的期望步數(shù)為\(x\)，則有方程：
\[x=1+\frac{\sum_i\min(dis(i,T),x)}{n}\]
因為有一個\(\min\)所以沒有辦法直接解這個方程，發(fā)現(xiàn)右邊這個函數(shù)的斜率是遞減的，可以考慮二分\(x\)。二分到整數(shù)即可，因為只要二分到整數(shù)以后，那個\(\min\)里面哪些點取\(dis(i,T)\)哪些點取\(x\)就已經(jīng)確定了，就可以解方程算出\(x\)了。
現(xiàn)在僅剩的一個問題在于怎么計算右式。我們發(fā)現(xiàn)就是計算距離\(T\)不超過\(x\)的點有多少個以及他們到點\(T\)的距離和。這個就直接動點分一下就好了嘛。
自己寫了一個\(O(n\log^3n)\)的做法，題解做法是\(O(n\log^2n)\)的，回去再看看qaq。
euclid
落實情況
| 完成情況 | corrected | corrected | N/A |
Day 8
流水賬
T1這這這線段樹維護(hù)矩陣然后不就做完了嗎。但是這個復(fù)雜度貌似有點鬼啊qaq。
T2這什么鬼題目啊，出題人毒瘤吧。
T3看一眼數(shù)據(jù)范圍感覺像是\(FWT\),然后就\(yy\)了一個很有道理的\(O(\sum k_i+m2^m)\)做法。一發(fā)過大樣例。
然后滾回去寫T1，倒是一下子就寫完了，也沒怎么\(debug\)就過了樣例。預(yù)估\(75\)分。
T2寫了個退火，就是完全隨機亂走的那種。
下考前意識到?jīng)]算退火的時間復(fù)雜度，心想著算了算了反正這題也是沒分的就沒管了。
預(yù)估得分\(75+0+100=175\)，實際得分\(65+8+100=173\)。
T1構(gòu)造轉(zhuǎn)移矩陣的時候?qū)懙氖?#61;1而不是++然后\(\sum|s_i|=0\)的點就\(G\)了。
然后T2\(spj\)出鍋，喜聞樂見.jpg
總結(jié)
T1的復(fù)雜度是假的這我能說什么。
T2的正解是假的這我能說什么。
T3全場艸標(biāo)算這我能說什么。
簡要題解
kill
對所有不合法串構(gòu)造\(AC\)自動機，然后在一些禁止節(jié)點上打上標(biāo)記，\(dp\)即可。
考慮動態(tài)修改還要區(qū)間查詢，所以用矩陣實現(xiàn)\(dp\)轉(zhuǎn)移，用線段樹維護(hù)區(qū)間矩陣乘積。禁止節(jié)點在\(dp\)中是沒有任何意義的，所以把除禁止節(jié)點外的所有節(jié)點重新標(biāo)號再做矩陣乘法，復(fù)雜度\(O(q\log n(\sum s_i-m)^3)\)。能過。
plitics
eat
考慮枚舉選出了\(k\)個拼盤后或起來的結(jié)果，一共是\(2^m\)種狀態(tài)。因為我們可以算出每一種狀態(tài)的價值，所以我們只關(guān)心每一種狀態(tài)被構(gòu)造出來的方案數(shù)。
設(shè)\(f_i\)表示是\(i\)集合的子集的集合數(shù)量，那么\(g_i=\binom{k}{f(i)}\)即表示選出\(k\)個盤子或起來集合是\(i\)的子集的方案數(shù)。
那么只要求出\(f_i\)，算出\(g_i\)再想辦法還原回去就好了。
顯然是可以\(FWT\)的吧，復(fù)雜度不算讀入是\(O(n+m2^m)\)。
所以說這題的復(fù)復(fù)雜度瓶頸實際上在讀入。
不過大家寫的貌似普遍都是，利用期望的線性性，對每一位分別考慮，然后復(fù)雜度就是\(O(m)\)的，非常優(yōu)秀。
感覺\(std\)的做法比較像bzoj3771Triple這道題的加強版，就是大力容斥，然后利用系數(shù)是帶符號第一類斯特林?jǐn)?shù)的性質(zhì)做到\(O(km2^m)\)
落實情況
| 完成情況 | corrected | corrected? | corrected |
轉(zhuǎn)載于:https://www.cnblogs.com/zhoushuyu/p/9211103.html
總結(jié)
以上是生活随笔為你收集整理的2018HN省队集训的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 流媒体之RTMP——librtmp拉流测
- 下一篇： HttpUtils调用