A、小蒟和他的樂譜

簽到題，將原序列對 取模之后將序列掃描一遍就可以得到答案

B、小琛和他的學校

樹是無根的，可以隨便選取一個校區(qū)作為根節(jié)點。不妨設 號校區(qū)為根。
對于每一個校區(qū)，可以通過 計算出它子樹中校區(qū)的個數(shù) 以及子樹中學生的總數(shù) 。
然后再次進行 ，假設 為當前遍歷到的節(jié)點的某一個子節(jié)點，那么連接它們的這條邊所需支付的維護費用為 。
時間復雜度為 。

C、小魂和他的數(shù)列

由于 比較小，所以可以先將原序列離散。
之后通過 棵樹狀數(shù)組分別維護 元、 元、 元... 元的單調上升子序列的個數(shù)。
時間復雜度為 。

D、小翔和泰拉瑞亞

首先可以枚舉一個位置，盡量使它的高度降低，用掉所有包含該位置的魔法，然后求出全局的最高位
置，用最高位置與當前枚舉到的位置的高度差來更新答案。這樣必定能夠求到最優(yōu)解。
所以可以從左到右枚舉位置，當當前枚舉到的位置進入某一個魔法的區(qū)間時，就應用它。出來的時候就
撤銷它，然后通過線段樹來維護最大值。
判斷進入某一個魔法的實施區(qū)間可以按照左端點排序，實施了之后扔進按照右端點為關鍵字的小根堆里
判斷是否出了區(qū)間即可。
時間復雜度 。

E、小雀和他的王國

當圖中的割邊被斷開之后，原圖就會不連通。所以要盡量讓割邊的數(shù)量減少。
可以先隨便求出原圖的一棵生成樹。
然后通過樹上差分或者 算法求出割邊。
新連一條邊之后，在生成樹上新連邊的兩端點之間的路徑上的割邊將不再是割邊，所以需要求出一條割
邊最長的路徑，就是求一棵樹的帶權直徑， 或者 求出即可。

F、小球和新型材料

先考慮如何求出字符串 在每次循環(huán)移動過后回文子串的個數(shù)。
先把字符串 復制一次接在后面。
然后我們要求的就是區(qū)間 這 個區(qū)間內的回文子串個數(shù)分別有多少個。
可以用馬拉車算法求出以每個位置為中心最長的回文串長度。然后考慮對這 個區(qū)間的貢獻。
先考慮回文長度為奇數(shù)的情況:
設當前回文中心的位置為 ，以 為中心的最長的回文串的左端點為 ，右端點為 。那么它對第 個區(qū)間到第 個區(qū)間都有 的貢獻。
對于第 個區(qū)間和第 ，貢獻為 ；
對于第 個區(qū)間和第 ，貢獻為 ；
以此類推，直到貢獻為 （假設這些區(qū)間都存在的話）。
相當于按位加上一個等差數(shù)列，線段樹維護即可?；匚拈L度為偶數(shù)也同理。注意細節(jié)即可。
然后就可以判斷出回文子串個數(shù)之差是否大于 了。
再來考慮如何求最大收益。
把式子用二項式定理展開，就是：

由于 比較小，可以分P次求和，然后再累加起來。
考慮如何求：

把 倒過來，就是：

這就是一個卷積的形式，所以只要把 復制一遍，分別求出 在 次方和 在 次方后的值，然后用
把兩個式子卷乘起來，最后乘以 并累加，就能得到每次循環(huán)移動后的收益。最后減去 乘以移動次數(shù)后取最大值即可。
時間復雜度 。

很走心而且很棒的民間題解

范藝杰的博客