主標題：我是fvv

傳送門 https://codeforces.com/gym/105992

原本是打算vp的，但是發現自己的實現能力已經大大下降了，所以干脆就胡題吧，能寫就寫一點，不能寫算了。

H

按照題意模擬即可。

M

思路繞了點路，但是還是回到正軌上了，算是一學期思維可達性訓練的成果吧。

首先注意到可行性就是模擬二進制：先填寫高位，然后讓小球翻倍把填寫的位往高位推一格，然而沒有注意到 \(0\) 翻倍后還是 \(0\) ，因此以為翻倍的數量是按照最高位來分段的，但是這么搞就錯了，而且這樣沒辦法處理 \(x,y\)，于是就考慮了一個 \(\mathcal O(n\log^2 V)\) 的 dp，即 DP\([i,j]\) 表示把前 \(i\) 個小球填好了，并且第 \(i\) 個小球使用了 \(j\) 次翻倍的最小總代價，然后就是狀態 \([i,j] \rightarrow [i+1,k]\) 時只有 \(k>j\) 時才加入 \((k-j)\cdot y\) 的貢獻，然后就 TLE 了。

之后轉念一想，發現了 \(0\times 2 =0\) ，所以最優方案中一定存在一種方案是所有球的翻倍次數是一樣的，那么直接枚舉翻了幾次倍，在固定了翻倍次數后只需最小化 \(+1\) 操作次數即可，這個拿貪心很容易分析出來，所以最終的時間復雜度是 \(\mathcal O(n\log V)\) 。

馬麥批，做題做到一半杯哥又開始在群里狗叫了，煩死了

D

簡單的納什均衡分析。

I

裸的樹上背包，不過注意題目給自洽這個概念的定義，然后直接模擬即可。

K

題面一坨，但是本質上還是模擬，思路上沒有什么困難，大概還要寫一個快速冪。

G

這輩子都不喜歡構造，做了很多的無用思考而無法理解 \(n^2+40n\) 的 \(40\) 是怎么來的，結果竟然是 \(2500\) 以內的素數間隙，好吧，屬實無聊。而且其實代數學里的構造和xcpc里的構造的風格還不太一樣，太一坨了。

J

簡單圖論題，也是走了一點彎路，但還是弄對了。

首先由無向圖的環自然的想到把邊扔到 dfs 樹上去分析，既然希望盡量多操作，那么就是希望每次畫圈盡量做到只消除一個邊，那么就是希望在消除這個邊時畫出來的環只有這一條邊是白的其余都是黑的，然后定義一個邊上的等價關系 \(R:=\set{(u,v)|如果把 u 涂黑，那么通過 u 可以把 v消除}\) 顯然這是自反對稱傳遞的，而如果一個邊可以僅通過黑邊消除，那么這個邊的等價類都可以通過黑邊消除。

而如果 \((x,y)\notin R\) ,那么就意味著如果想要把 \(x,y\) 囊括到一個環里，還需要涂黑其他的白邊，這一命題在聯通性上的等價條件是僅通過黑邊，邊 \(x,y\) 的端點不在一個連通塊內，于是就可以很自然的導出做法：維護并查集，先加入黑邊再加入白邊，如果加入白邊不影響連通塊數量，那么這個白邊就可以通過黑邊消除，否則就把當前白邊視作黑邊，供后面的白邊使用。至于為什么加入的順序無關，這個的證明可以很自然的從連通塊的性質導出。

A

無趣的枚舉題，感覺正解不如我的 DP 解法

首先設序列 \(A\) 的長度為 \(n\) ，而元素 \(x\) 的出現次數為 \(count(x)\) ，那么通過統計每種元素對 \(g(A)\) 的貢獻可以得到 \(g(A)=\sum 2^n-2^{count(x)}\)，容易注意到 \(2^n-2^{count(x)}\ge 2^{n-1}\) 所以可以得出可能的 \(n\) 是非常少的，題解說是 \(\log\log x\) 級別的，可以當成常數項，也就是 \(n\sim \log x \pm \log\log x\) ，大約是 \(60\) 左右，之后題解直接枚舉 \(60\) 的分拆數，然后檢驗即可，這是很不優美的，時間復雜度是 \(\mathcal O(\log x\cdot p(\log x))\)，而拆分數 \(p(n)\sim {\exp(\pi\sqrt{2n\over 3})\over 4\sqrt 3 n}\)，是亞指數級別的，劣于多項式。

我的 DP 解法也需要利用 \(g(A)=\sum 2^n-2^{count(x)}\) 這一結論，考慮 \(2^n-2^{count(x)}\) 的二進制形式，就是形如

的形式，而此時容易發現 \(n\) 就是 \(1\) 的數量，那么考慮從低位往高位掃描，一旦某一項從 \(0\) 變成 \(1\) 了，那么以后都是 \(1\) 了，所以可以參考夢幻島寶珠的優化思路，僅記錄進位信息，于是有狀態 \(DP[i,j,k,s]\) 表示從低位向高位掃描，掃描到第 \(i\) 位，并且前 \(i\) 位和 \(x\) 的前 \(i\) 位是相同的，第 \(i\) 位上有 \(j\) 個 \(1\) ，然后目前前 \(i\) 位的 \(1\) 的總個數為 \(k\)，并且 \(1\) 到 \(i\) 位總共向 \(i+1\) 位進位了 \(s\) 的前提下，是否有解，顯然 \(s\le 2\log x\) 而轉移只需要考慮 \(j\rightarrow j'(j'\ge j)\) 即可，所以時間復雜度是 \(\mathcal O(\log^5 x)\) 的，是多項式復雜度，優于題解。

然而實際上在 \(\log x\) 十分小的時候，DP解法的計算次數還是多與枚舉解法的，數據要加強

C

注意到本質上每種餃子的愉悅值函數都是一個關于吃的次數的上凸函數，而總和就是這些上凸函數的 \((\max,+)\) 卷積，仍然是一個上凸函數，所以直接 wqs 二分即可，不過有多種情況需要分類討論，整體而言思路簡單而實現十分之繁瑣。

E

又一道勢能線段樹，看完題解算是漲知識了。
先前只知道jls線段樹，并且定義節點勢能為線段樹節點所管的子段中不同的數的種類，而總勢能的上限是 \(n\log n\) 的，而每次遞歸操作都會使 \(mx = se\) 從而使得勢能至少減少一，所以總的復雜度有保障。注意到 \(\gcd\) 本質上也就是在質因子的指數上取 \(\min\) ，所以遂嘗試遷移思路，但是最終失敗了。

模仿jls線段樹，對于每個線段樹節點維護 lcm 和 sum ，顯然一個節點不會被修改的充要條件是 lcm|x ，除此以外對于每個節點還打一個懶標記標記此節點的值是否全部相同。和jls線段樹一樣，首先將修改的線段打成線段樹上的節點，如果懶標記存在或者不需要修改，則直接 \(\mathcal O(\log V)\) 或者 \(\mathcal O(1)\) 完成處理并退出，否則遞歸下去暴力修改。

遞歸修改的復雜度分析如下：
定義總勢能為極大的存在懶標記的節點上的值的對數之和，即

顯然初始化的時候總勢能最多能到達 \(P=n\log V\)。對于操作一，每次至多修改 \(\log n\) 個節點，每個節點至多增加 \(\log V\) 的勢能，所以所有操作一對勢能的總貢獻不超過 \(n\log V\log n\)。對于操作二，在遞歸修改的過程中，只有懶標記不存在并且至少有一個節點會被修改時才會遞歸下去，這意味著只要遞歸一次，要修改的子段內就有多一個節點要被修改，而具體的對節點的修改，則會使得節點的值 \(val_i\) 至少變成 \(val_i\over 2\) ，所以節點的勢能減一，因此全體操作二的遞歸總次數少于總勢能少于 \(n\log V\log n\) ，再加上求 \(\gcd\) 的 \(\log\) 所以以上做法的時間復雜度時 \(\mathcal O(n\log n\log^2 V)\)

F

虹夏可愛。這是一道有趣的DP題
考慮樸素的暴力，嘗試從中找到優化的思路。
如果給定了選取的元素及其順序，如何檢測是否合法？可以在按照給定順序掃描字符串的時候，記錄一個 \(0\) 到 \(8\) 的數字 \(D\) 表示目前能找到的最長的蘿莉控前綴的長度，每加入一個字符串就更新 \(D\)。這一個過程啟發了一點：可以把字符串 \(i\) 抽象成一個 \(\mathbb N_9 \rightarrow \mathbb N_9\) 的映射，如果當前的 \(D\) 為 \(j\) 則經過這個字符串之后 \(D\) 就變成了 \(link_{i,j}\)

之后將方案中能使得 \(D\) 增加的字符串成為上升串，其余稱為不動串，那么顯然在任何一種方案中上升串的數量不超過 \(8\)，因此絕大多數都是不動串。抽象完字符串后考慮如何取消枚舉的順序，這個時候就要考慮使用動態規劃了，根據前文對于字符串的抽象可以得出，一個字符串想要成為具有 \(j\rightarrow j'\) 形式的上升串需要兩個條件: \(D=j\) 和 \(link_{i,j}=j'\)，具有 \(j\rightarrow j\) 形式的不動串同理：\(D=j\) 和 \(link_{i,j}=j\)，總而言之一方面是對該串本身的 \(link\) 具有一定的要求，另一方面是在 \(D\) 上升的過程中存在一個 \(D=j\) 的階段，如是則可以把對應的串直接插入到 \(D=j\) 的那一個階段上。相應的可以用一個長度為 \(8\) 的 \(012\) 串來表示上述信息，第 \(i\) 位為 \(1\) 表示存在 \(D=i\) 的階段；\(i\) 位為 \(2\) 表示暫時不存在 \(D=i\) 的階段，但是已經存在 要求存在 \(D=i\) 的階段的字符串了，類似于一個需求提前的操作；第 \(i\) 位為 \(0\) 則表示其余情況。于是可以考慮一個如是dp，DP\([i,s]\) 表示從前往后掃描到第 \(i\) 個字符串，并且需求信息為 \(s\) 的前提下，最大總長度是多少。至于轉移則是考慮加入第 \(i+1\) 個串后枚舉第 \(i+1\) 個串是具有怎樣形式的串(\(j\rightarrow j'\))，其中要求 \(s\) 中第 \(j+1\) 位到第 \(j'-1\) 位之間均為 \(0\)，并且將 \(s\) 中第 \(j'\) 位賦值為 \(1\) ，如果第 \(j\) 位為 \(1\) 則不改變，否則第 \(j\) 位改為 \(2\) ，因此加上處理字符串的時間復雜度，該解法的總復雜度是 \(\mathcal O(8\cdot 3^8\times n+8^3\times n)\)

UPD E 復雜度分析修正

鑄幣出題人，分析的東西是錯的，其中錯誤在于：在出題人給定的勢能的定義下，每遞歸一次并不能夠保證勢能一定減少一，比如只需要修改一個葉子節點的情況，實際上遞歸了 \(\log n\) 次才使得勢能降低了一，所以這種分析方法（實際上是勢能的定義）是不恰當的，以下給出修正。

對于一個線段樹的節點 \(x\) ，維護以下資料

\(l(x),r(x)\) - 節點接管的區間的左右端點
\(lazytag\) - 節點接管的區間內的元素是否全都相等
\(lcm\) - 顧名思義

還是依照原題解的方案，先把線段樹上所有 “自身有懶標記并且祖先沒有懶標記” 的節點抽出來，令它們構成的集合為 \(\mathbb S\) ，再定義 \(\mathbb S\) 的導出集合 \(D(\mathbb S):=\) 自身或存在自己的后代節點在 \(\mathbb S\) 中的全體節點構成的集合.

當然，實際上 \(D()\) 就是把 \(\mathbb S\) 中的節點到根的路徑并起來得到的點集.

之后定義線段樹的總勢能為

對于操作一，它能增加勢能最大的情況是整個序列都是 \(1\) 的情況，這個時候先依照線段樹區間修改的方法，使用 \(O(\log n)\) 的時間把修改區間打散成 \(\log n\) 個節點，假設這些節點構成的集合為 \(\mathbb T\)，則顯然有 \(|\mathbb T|=\Theta(\log n)\)，從而可以說明 \(|D(\mathbb T)|=\Theta(\log n)\)，之后修改的 \(x\) 直接頂滿，所以可以說明

而進行一次修改，不難驗證對于 \(\mathbb S\) 的修改量是 \(\log n\) 級別的，所以進行一次操作一，對于勢能的增量為 \(\Theta(\log x\log V)\sim \Theta(\log^2)\)

對于操作二，還是先根據線段樹區間修改的方式用 \(O(\log n)\) 的時間把修改區間打散，對于打散了的節點 \(x\) ，它遞歸下去的充要條件是 \(lcm(x)\) 不整除 \(val\)，從而說明經過修改后 \(lcm(x)\rightarrow LCM(lcm(x),val)\) 于是這樣子這個節點的勢能會減一，從而總復雜度會減一。
但是別忘了線段樹還有 pushdown 操作，實際上進行一次標記下傳操作會使得復勢能增加 \(O(\log V)\) ，而不難發現區間修改只會進行 \(O(\log n)\) 次標記下傳，所以這么多次操作后總的勢能還是 \(O(p\log^2)\) 的，這就能說明遞歸次數不會爆掉。

以上應該才是正確的復雜度分析