發現自己不會T3可以退群了

排序問題（組合、模擬）

可以發現Gobo Sort相當于在所有排列中隨機選擇一個，所以當第\(i\)個數出現次數為\(a_i\)時，期望的Sort次數就是\(\frac{(n+m)!}{\prod\limits_{i=1}^{10^9} a_i!}\)。

我們希望Sort次數盡可能大，也就是能夠讓\([L,R]\)內的\(a_i\)盡可能平均。我們把所有\(a_i \neq 0 , i \in [L,R]\)的所有\(a_i\)扔進小根堆，每一次pop堆頂考慮其余的所有數是否能夠加到當前堆頂的\(a_i\)的個數，如果不能就把剩下的平攤。

代碼

游戲（線性篩、組合）

實際會對最后答案產生影響的數\(x\)一定會滿足\([l,r]\)內不存在比\(x\)小的\(x\)的因子。

所以通過線性篩先求出所有數的最小質因子，就可以求出所有會對答案產生影響的數，那么現在就是要求求出這些數中最后一個出現的數的出現位置的總和。

考慮枚舉最后一個數出現的位置\(x\)，那么\([x+1,len]\)里全部都是不產生影響的數，那么我們可以先選定后面\(y\)個數是不產生影響的數、前面亂排，減去后面\(y+1\)個數是不產生影響的數的方案數，就是從后往前第\(y+1\)個數是最后一個對答案產生影響的數的方案數。

代碼

守衛（DP）

不會做qwq

考慮：對于一個區間\([l,r]\)，\(r\)位置一定會放一個保鏢，把\(r\)所能夠看到的所有位置刪掉之后又會形成若干個區間，這些區間的右端點和右端點右邊的點中一定要放一個保鏢，這就變成了一個子問題。

所以可以考慮DP。設\(f_{i,j}\)表示區間\([i,j]\)的答案，轉移先把所有\(j\)能看到的點拿出來，假設形成了區間\([l_1,r_1],[l_2,r_2],...,[l_k,r_k]\)，那么轉移就是\(f_{i,j} = 1 + \sum\limits_{i=0}^k \min(f_{l_i,r_i} , f_{l_i,r_i+1})\)。

這樣轉移是三方的不夠優秀，但是注意到對于區間\([i,j]\)的不能看到的區間一定是區間\([l,j](l<i)\)的看不到的區間的子集，所以可以先固定右端點掃左端點，對于已經形成的不能看見的區間直接將答案貢獻進去，這樣復雜度就降為\(O(n^2)\)。

代碼

轉載于:https://www.cnblogs.com/Itst/p/10992647.html

總結

以上是生活随笔為你收集整理的JXOI2018做题笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。