10.9

CF2144D Price Tags

題意

給定一個序列\(c\)，令\(a_i = \lceil \frac{c_i}{x} \rceil\)，\(x\)是任意大于\(1\)的正整數。

\(f(x) = \sum\limits^{n}_{i=1} a_i - ky\)，其中\(k\)是\(a\)與\(c\)相比新增數字的數量

求\(f(x)\)的最大值

思路

設\(c\)中最大值為\(A\)，首先容易發現\(x \in [1, A]\)
考慮當\(x\)固定時怎么做，
首先，計算出\(a\)，\(O(n)\)
接著，可以用雙指針統計出\(k\)，\(O(n)\)
總復雜度\(O(nA)\)，爆炸

考慮優化，計算過程顯然是沒有什么優化空間了，但也許我們并不需要計算出\(a\)數組
我們只需要知道，對于每一個值\(v\)，\(c\)中是否存在除以\(x\)后是\(v\)的值即可

也就是說，是否存在\(c_i\), 使得\(v = \lceil \frac{c_i}{x} \rceil\)

那么，\(c_i \in [(v-1)x + 1,\ vx]\)

只需統計\(c\)數組在這段區域內的元素個數即可，用桶很好實現，時間復雜度\(O(\frac{A}{x})\)

對于統計過程，用桶也很好實現，按上述方法統計出\(v\)在\(a\)中的出現次數，減去\(v\)在\(c\)中的個數，與\(0\)取\(max\)就可以得到新增的元素了，時間復雜度\(O(\frac{A}{x})\)

總復雜度\(O(n + \sum\limits_{x=1}^{A} \frac{A}{x}) = O(n + A\text{log}A)\)（加上預處理桶的時間）

10.10

*CF2112D

題意

給定一棵\(n\)個節點無根樹，試為每條邊確定一個方向，得到一個有向圖，使得圖中滿足存在一條從\(u\)到\(v\)的路徑的點對\((u, v)\)的數量恰好等于\(n\)

思路

首先容易發現得到的有向圖\(G = \{V, E\}\)是一個\(DAG\)，那么如果我們確定了每條邊的方向，就可以用拓撲排序統計出每個點可以到達的點數。

設\(f_u\)為點\(u\)在圖\(G\)能夠到達的除自身以外的點數，則\(f_u = \sum\limits_{(u, v) \in E} (f_v + 1)\)

那么，就可以求出整個圖中滿足條件的點對數\(y\)

其中，\(ind_v\)是節點\(v\)的入度

那么，根據條件，就有

觀察式子，由于\(ind_v\)，\(f_v\)均為非負整數，所以求和式中至多有一項為\(1\)，其余均為\(0\)

因此，圖中至多有一個節點的\(ind\)，\(f\)均為\(1\)（即在原樹中度數為\(2\)），其余點要么入度為\(0\)，要么可以到達的點均為\(0\)（出度為\(0\)）

所以，只需找到樹中的\(2\)度點，從該點開始搜索，確定每條邊的方向即可

10.11

*CF2148F

首先根據題意，我們只需要從第\(0\)項開始，每次選當前項及之后元素字典序最小的序列即可，分析可發現時間復雜度是\(O(\sum k \sqrt{\sum k})\)的

\(Proof:\)

首先發現這\(n\)個序列的長度中不同的數字個數是\(O(\sqrt{\sum k})\)

證明

設不同數字個數為\(t\)，則

\[\sum_{i=1}^{n} k_i \geq \sum_{i=1}^{t} i = \frac{t(t+1)}{2} \]

可以解得 \(t = O(\sqrt{\sum k})\)

那么顯然，由于當我們選定了一個序列之后，指針就會跳到它的末尾，所以\(p\)只能取\(K = \{ k _i \}\)當中的值，這意味著我們至多會進行 \(O(|K|) = O(\sqrt{\sum k})\) 次選最小字典序序列的決策

而每次至多比較 \(O(\sum k)\) 個元素，故總時間復雜度是 \(O(\sum k \sqrt{ \sum k })\) 的

10.12

*CF2111E

字典序問題，考慮貪心。

考慮我們的目標是什么，因為只有\(a, b, c\)三種字符，所以我們想盡量讓每個字符都變成\(a\)，特別地，不能變成\(a\)的\(c\)也應盡量變成\(b\)

再具體一點，我們達成目標的途徑有兩種：

1. 直接實現：\(x \rightarrow a \quad c \rightarrow b\)
2. 間接實現：\(b \rightarrow c \rightarrow a \quad c \rightarrow b \rightarrow a\)

那么，我們就可以貪心地從左到右考慮每個字符，看其能否變得更小，并且，直接實現的優先級高于間接實現

這是因為如果同時有\(x \rightarrow a \quad x \rightarrow y \rightarrow a \ (x, y \in \{b, c\}, x \neq y)\)，那么我們選擇直接實現可以為后面的\(y\)節省下\(y \rightarrow a\)這次操作，更優

而且，由于簡介實現對于操作的順序有要求，所以我們每次選擇最早的可行操作。

證明

首先證明直接實現的優先級高于間接實現

不妨設現在考慮將選擇對字符\(b\)的操作方式，假設一個最優解選擇了\(b \rightarrow c \rightarrow a\)，且存在操作\(A\):\(\ b \rightarrow a\)

若\(A\)被分配給了后面的一個\(b_2\)，則將對\(b\)和\(b_2\)的操作交換，得到的解還是最優解。

若\(A\)被分配給了后面的一個\(c\)，則將\(b \rightarrow c \rightarrow a\)中的\(c \rightarrow a\)給后面的那個\(c\)，得到的解仍是最優解

接著，證明可以選擇最早的可行操作

10.14

*CF2112D

很有趣的一道題

題意

對于一顆有根樹，每個節點可以被染成綠、藍、黃三種顏色，我們定義滿足下面條件的染色方案是“美麗的”：

1. 根節點是綠色的

2. 在綠點和藍點構成的集合中，任意兩點間路徑上沒有黃點

3. 在綠點和黃點構成的集合中，任意兩點間路徑上沒有藍點

其中條件2，3很關鍵，也很容易理解錯，其中我漏掉容易漏掉的是在這兩個條件的約束下任意兩個綠點之間的路徑上僅有綠點

題目要求的是：恰有\(m\)種不同的“美麗的”染色方案的有根樹的最小節點數

思路

原問題有點困難，我們先考慮已知一棵樹，求“美麗的”染色方案數。

根據上述題意，容易發現以下性質，

若一個節點為藍色或黃色，則其子樹中所有結點一定與它同色，即這棵子樹的染色方案是唯一的

所以，我們只需要考慮一個點染為綠色的方案即可

設節點\(u\)染為綠色，其子樹的染色方案數為\(f(u)\)，則

所以，原問題就是求\(f(1) = m\)的最小樹的節點數。

那么，很自然的，由于\(f(u)\)是乘積的形式，我們想到將\(m\)進行因數分解，于是，你發現原問題轉化成了更小的子問題

但是，由于節點度數不確定，我們無法確定將\(m\)分解為多少個數，不過仔細思考，其實這不要緊，

設\(f(u) = m\)的最小樹大小為\(g(m)\)

設\(m = f(u) = (f(v_1) + 2) \times \prod_{fa_v = u,v \neq v_1} (f(v) + 2) = (f(v_1) + 1) \times A\)，你可以為后面的連乘加上一個根節點\(u'\)，則\(f(u') = A\)，則\(siz_u = siz_{v_1} + (\ siz_{u'} - 1\ ) + 1 = siz_{v_1} + siz_{u'}\)

所以，有\(g(m) = g(i - 2) + g(\frac{m}{i}) \quad ( m = i\times A = (f(v_1) + 2) \times A)\)，\(O(\sum)\)

在手玩了幾個樣例之后，我們又會猜到一個結論，若\(m\)是偶數，無解

我第一反應是用歸納法證明的，顯然\(m = 2\)是無解的，而偶數無論是怎樣轉移，一定都會分解出至少一個偶數，由歸納法可知偶數都無解。

其實更簡單的方法是觀察式子的奇偶性，因為葉子的\(f = 1\)，而加二不會改變奇偶性，所以\(f\)一定是奇數。

那么，我們就可以愉快的用\(dp\)切掉這題了，預處理所有\(m\)的答案，轉移時枚舉因數，時間復雜度\(O(m\sqrt{m})\)，詢問時\(O(1)\)回答。

還有一種更快的轉移方法，類似篩法，枚舉\(i\)的倍數，\(f(ki) = \min\{f(ki),\ f(k) + f(i - 2)\}\)，\(O(\sum \frac{m}{i}) = O(m \lg m)\)

10.15

CF2043D

首先看到\(gcd\)，我們想到把\(gcd\)除掉變為\([ \lceil \frac{l}{g} \rceil, \lfloor \frac{r}{g} \rfloor]\)中互質的數對的最大間隔

我們枚舉這個差值，檢驗是否存在這樣的數對即可。

假設答案是\(d\)，則時間是\(O((r - l - d)^2 \lg A)\)的，\(A\)是值域（\(\lg A\)是\(gcd\)的復雜度）

但是，如果我們枚舉到兩個質數，查找就結束了，所以\(r - l - d \leq\)（\(l\) 到下一個質數的距離）\(+\)（\(r\) 到上一個質數的距離）

根據素數定理，\(N\)以內素數約有\(\frac{N}{\ln N}\)個，故兩個素數的間隔約為\(O(\ln N)\)，故\(O((r - l - d)^2 \lg A) \approx O(\ln^2A\lg A) = O(\lg^3 A)\)

10.17

Edu167

A

一開始結論猜錯了，后來才改過來，問題的關鍵在于人與金幣縱坐標之差，我們應盡可能讓人往金幣下方跑，然后等待金幣落下所以就是\(y_i - (|x_i|-1) \geq - |x_i|\)，即\(y_i \geq -1\)

B

思路一直在往匹配上想，對于每一個\(b\)中字符，找到在\(a\)中第一次出現位置，指針后移，繼續匹配，但這并不一定是最優的，反例\(a=cbcbc \quad b = bbbcc \quad s_{min} = bcbcbcc\)，問題在哪呢？我們發現問題在于在上述策略中，我們始終把\(a\)放在\(s\)的開頭位置，但實際上\(a\)可能在\(s\)中間，前面是由\(b\)提供的，所以就應該枚舉\(a\)的位置，即\(b\)的一段前綴，再進行匹配，還有，這種題數據范圍比較小，可以先往暴力的思路想，因為可能大概率沒有什么比較巧的高效算法

C

最優化問題，我們考慮貪心（實際上在這之前應該二分，dp，貪心都考慮一遍，覺得哪個比較可行，這里覺得是貪心的概率比較大），我們想到對每個人再\(a_i\)，\(b_i\)中選最大值，對嗎？因為如果\(a_i > b_i\)則\(b_i = 0\)或\(-1\)，也就是對第二部電影沒有貢獻，或會使答案變得更劣，所以我們可以放心的選最大值。這就自然引出了其它情況，如果\(a_i=b_i\)會怎樣？ 如果是\(0\)顯然不用考慮，否則，由于取最小值作為最終答案，我們可以最后再分配這部分觀眾，使兩電影得分盡量平均

D

依舊是貪心，我們直覺上可以感覺到選消耗（鑄造所用 \(-\) 融化返還）最少的最優，其次我們發現得分一定是兩分兩分地得，因為一旦鑄造后就可以再融化，所以我們可以把鑄造所用視為“觸發條件”，消耗視為代價，得到策略：對每一堆選擇\(\max\{a_i - b_i | a_i \leq c\}\)，重復這一過程，那么，我們可以將物品按\(a_i\)排序，預處理出一段前綴中代價最小的物品，然后對于每個\(c_i\)不斷選擇最優的物品，扣除代價，不斷重復直至無法找到可行的物品。

但是這樣很慢，我們發現在前面所說的過程中，只要\(c_i\)固定，那么整個過程及最終收益就都固定了，并且這個過程是可以遞推的，所以可以考慮將所有\(c_i\)的收益存其來，但\(c_i \leq 10^9\)，如何是好，觀察數據范圍，我們發現\(a_i, b_i \leq 10^6\)，是否可以存儲\(10^6\)量級的數據呢？通過觀察我們發現，其實\(c_i\)在經過一次循環后就會變到\(10^6\)以下，因為只要能夠取一個物品，就會一直取，直到\(c_i < a_x\)，于是這題就完美地解決了

事實上，一開始做題時我們就應該注意到值域上的限制，數據在\(10^6\)以內，可能暗示我們可以儲存一些基于值域的信息，值域在\(10^9\)級別，可能不太有希望存儲，也可能暗示我們進行離散化，或是其他一些轉化。

10.18

Edu166

C

賽時沒想明白就開始寫了，浪費了大量時間，最直觀的想法是我們可以先求出不考慮最后一個人的結果，然后再枚舉每一個人，在\(O(1)\)時間內調整答案。

記不考慮最后一個人時第\(i\)個人的職位為\(job_i\)

假設第\(i\)個人缺席，設它在原來的結果中的職位是\(x\)，那么它前面的人不會受到影響，那么對于后面的人來說，現在多出了一個\(x\)類型的職位，那么我們可以找到后面第一個分到\(x\)最優，但并沒有分到職位\(x\)的人\(j\)，然后給他職位\(x\)。

那么，對于\(j\)之后的人，又空出來一個類型為\(y \neq x\)的職位，就可以遞推這個過程。。。

實際上并沒有這么困難，因為到\(j\)的時候職位\(x\)已經沒了，所以后面不會有分到\(y\)最優，但分到\(x\)的人，除了第\((n+m+1)\)個人，因為它一開始沒被考慮，所以，我們只需要考慮第\(j\)個人和第\((n + m + 1)\)個人即可

如果不存在這樣的\(j\)，那么空出來這個位置給\(n+m+1\)就行了

所以，再仔細考慮一下，實際上我們只需要考慮第一個沒被分到最優職位的人\(a\)就行了

如果\(i < a\)且\(job_i \neq job_a\)，就讓\(a\)繼承\(i\)的職位，\(n+m+1\)繼承\(a\)的職位

否則，就讓\(n + m + 1\)繼承\(i\)的職位即可

應該想得差不多了在開始寫，還要充分挖掘條件，賽時沒有意識到\(a\)之后的人職位都相同，沒想到簡單的做法，而且沒想到遞推就開始寫了，干了很久

D

括號序問題，根據條件列方程即可

設一個前綴\([1, i]\)中\(1\)的個數與\(0\)的個數之差為\(f_i\)

設滿足條件的區間為\([l, r]\)，則

考慮枚舉每一個\(l\)，計算可行的\(r\)的個數，對于第一個條件，可用線段樹查找\([l, n]\)第一個\(f_i > 2f_{l-1}\)的位置，對于第二個條件，由于\(f \in [0, \frac{n}{2}]\)，值域較小，可以直接維護每一個值的出現位置，再其上二分即可

E

賽時沒時間做了。。。（C拖了太久）

讀完題目，觀察完樣例后，你會發現輸入中給出的數最后會形成一種類似BST的結構，\(l_i\)一定位于\(r_i\)之前，而且其中的較大值是分割前這一大段的最大值，所以新分成的兩小段就會“繼承”原來大段在整個序列中的位置關系，因此如果我們建立一顆BST，若\(r_i\)已在樹中，將\(l_i\)作為它的左兒子，反之亦然，最后中序遍歷即可得到給出的數的順序。

當然，直觀來看，由于每個數對\((l_i, r_i)\)相當于在一個階段的某個數（\(l_i\)或\(r_i\)）前／后新插入一個數，這個過程也可用鏈表來做，我當時只想到BST，沒想到鏈表

于是，輸入中給出的數的相對位置就確定了，且每個數都是自己段里的最大值，這樣，我們就把問題轉化成這樣：

有若干個分界點（序列頭、尾，即第\(0\)、\(n+1\)項可看作兩個值為\(0\)的分界點），兩個分界點之間的數應該比左、右分界點的最大值小，求合法的序列個數

對于這個問題，我們可以從插入的角度來看，從小到大考慮每一個未出現的數，考慮將其插入到某兩個相鄰分界點之間，看能插入到幾個空中。但是這有一個問題，先插入的數會影響后面的數的可插入位置，那么我們可以改變插入順序，從大到小插入，因為如果一個數不能被插入到某個空中，比它大的數也一定不能，這樣，我們記錄可以插入的空位，累乘到答案中，就可以了

為什么想到BST／鏈表？

從這個題目來說，我們實際上是要維護給出的數的相對位置，這是一種有序狀態，可以通過維護前驅來實現，而BST和鏈表本質上來說就是維護一個數的前驅和后繼的數據結構，鏈表可以看作是BST退化成一條鏈的結果，這也是為什么需要平衡樹來提升效率，普通的BST容易退化成與鏈表一樣的\(O(n)\)復雜度。并且，本題中給出了每個元素在插入時刻的后繼，可以直接插入，不需查找。 在本題中，我們可以記錄每個點在數據結構中對應的節點編號，從而快速查找

插入這一思路從何而來，轉換順序又是如何想到的？

排列組合問題中，插板法，插空法是常見的解題思路，可以往這方面思考。轉換順序則是在我們發現前面的數據會影響后面的計算的一種調整與嘗試，我理解的是在遇到有后效性的計算過程時可以考慮調換順序

10.20

Edu 165

C

賽時一直在想貪心QwQ

我的思路：對每個位置求出\(f_i = min(a_{i-1}, a_{i+1}) - a_i\)，即每個位置替換后最多可以將總和減少多少，然后每次選\(f_i\)最小的位置進行替換，并更新兩邊的\(f\)值。但是有反例：\([1, 2, 5],\ k=2\)

我的策略：\([1, 2, 5] \rightarrow [1, 2, 2] \rightarrow [1, 1, 2]\)

最優解：\([1, 2, 5] \rightarrow [1, 1, 5] \rightarrow [1, 1, 1]\)

我們發現這種遞增的序列按遞增順序來操作會更優，于是考慮反悔，將一個數刪除后與其旁邊替換它的數“并起來”，記一個 并起來的數的個數 作為權值，下次對這個數修改時就將這兩個數一起更改。

但是這種思路好像也是錯的T_T，因為當有兩個數的\(f\)與權值均相等時，貪心就會隨機選擇一個，但是這兩個數對于兩邊的\(f\)的貢獻可能是不一樣的，反悔并不能從根本上解決這一點

事實上，當你覺得需要反悔的時候，就應該順帶著考慮dp了，我們先從狀態開始，緊貼題目，我們設\(f(i, j)\)表示對前\(i\)個數進行\(j\)次操作所能得到的最小和

但是轉移似乎并不好實現，肯定是

的形式，\(g\)是對\([i - d + 1, i]\)操作\(k\)次能得到的最小和

思路卡住了，于是我們再回到具體的例子，還記得將貪心證偽的那個反例嗎？我們再來看看

通過觀察那個例子，我們容易得到一個結論：將一個長為\(l\)遞增序列中的數全部變為其中的最小值至少需要\(l - 1\)次操作

仔細一想，實際上不需要遞增也成立，但是如果有多個最小值呢？如\([3, 4, 2, 1, 1, 1, 2, 3]\)

其實它可以被分成\(3\)個最小值唯一的序列！\([3, 4, 2, 1]\)，\([1]\)，\([1, 2, 3]\)

那么我們是否可以用這個轉移呢？我們可以假定為達到最小和，區間\([l, r]\)一定需要至少\(r - l\)次操作，這樣，就有

盡管\(d - 1\)可能并不是最小的操作次數，但是由于這個區間可被分解，當前狀態一定會被分解后的最優解更新，所以這樣轉移沒問題。

也可以這樣考慮，我們在轉移過程中加入一個判斷，當且僅當將\([l, r]\)轉為最小和的操作次數等于\(r - l\)時，才進行轉移，但是，當次數小于\(r - l\)時，一定會有比這個轉移更優的決策點，所以刪去這個判斷也不會有影響

所以這個題就用\(O(nk^2)\)的dp解決就行了

這個題dp的轉移很Educational，不知道能不能在別的題里應用

D

考慮當Alice已經選完時，Bob的決策，顯然Bob會取其中\(b_i\)前\(k\)大的商品免費購買。

所以利潤就是

我們要選擇一個合適的集合\(T\)，是的這個值最大

那么我們可以進行這樣一步轉化，欽定\(T\)中的前\(k\)大，找出使利潤最大的其他元素（即其他元素中所有是正數的\((b_i - a_i)\)的和）

于是我們考慮將物品按\(b_i\)從大到小排序，我的思路是枚舉其中長為\(k\)的連續段，答案就是它后面元素的最大元素和減去該連續段中\(a_i\)的和

但是，這是最優的嗎？我們需要檢驗，答案顯然分為兩部分，后面元素的最大元素和 與 該連續段中\(a_i\)的和，前者顯然是后\((b_i - a_i)\)的所有正數和，但后者... 并不一定是最優的！你怎么保證這個連續段中\(a_i\)的和是最小的？

所以，正確做法應該是枚舉一個斷點，取前面\(a_i\)前\(k\)小的元素，后面所有\((b_i - a_i)\)正數的和作為該斷點的答案

做題一定要檢驗正確性啊！賽時一直傻傻地以為選連續段是最優的。。。

記住，OI也需要證明！一定要確定自己的策略的正確性！

Edu 164

D

首先我們發現，一個集合的value就是將其中的數分為兩組，每組和的最大值的最小值，也可表述為使用集合中元素能湊出的大于總和一半的值的最小值。

這個問題我們可以用背包解，然后......指數復雜度！爆炸！

然后我就罰坐了\(1h\)....

這個時候我們應該發現對每個子集用背包求解上述問題是沒有優化前途的，所以應該考慮猜結論，事實上，設集合中元素之和為\(s\)，若存在一個元素\(a > \frac{s}{2}\)，則答案就是\(a\)，否則，答案是\(\lceil \frac{s}{2} \rceil\)

如果我們可以把這些小球分成長為 l 的兩段，并且每一段的同個位置上的小球顏色都不相同，那就取到了答案下界。考慮我們把每種顏色按照球數從多到少地往段里面塞，塞完第一段塞第二段。那么違背要求當且僅當某種顏色在第一段末尾沒能塞完，塞到第二段開頭結果重疊了，然而此時這個顏色的出現次數一定 \(>\frac{s}{2}\)，說明存在主元素，不符合預設條件。

from 洛谷題解

有了這個結論，這題就迎刃而解了，我們只需要用背包算出能得到的每個和的方案數，順便在計算時根據當前枚舉的元素與和的一半的大小關系，更新答案即可。

還有，數組\(a\)應從小到大排序，防止dp轉移時已經湊出部分的和含有比所湊總和的一半大的元素。

Edu 163

D

賽時一直在考慮使用字符串相關算法，實際上枚舉就行了，做了\(1h\)才把思路轉換過來

10.21

Edu 162

打得很廢的一場

A

上來先讀錯題。。。

然后就開始猜結論，猜到了，贏

還是來分析一下吧，我們考慮問題中的不變量：\(1\)的個數，操作過程只是讓\(1\)變得更緊湊了，而沒有改變它的個數。

接著，我們考慮變化量---緊湊程度，那么如何描述這個量呢，一種簡單的方法是用最右邊與最左邊的\(1\)的下標之差來描述，設左右邊界分別為\(l, r\)，則“緊湊程度”\(f = r - l\)，那么，當操作結束后，有\(f = c - 1\)，\(c\)是\(1\)的個數

那么，考慮我們操作對\(f\)的影響，容易發現只有當我們操作最右邊的\(1\)時，\(r\)會減小\(1\)，\(f\)也隨之減小\(1\)，其他情況均會使\(f\)不變或增大

所以答案就是\(\Delta f = r - l - (c - 1)\)

找到不變量 \(\rightarrow\) 找到并刻畫（用式子表示）變量 \(\rightarrow\) 在變量與不變量之間建立聯系 \(\rightarrow\) 考慮操作對變量的影響

這種思路也許有助于猜結論和分析問題，也能幫助我們證明結論的正確性。

當然，在這之前，瞪眼法與觀察樣例永遠是更加使用的方法，對于簡單題，直接觀察通常更為高效

B

很久沒猜到結論，最后完全是靠運氣撞出來的，失敗

我的猜結論歷程大概是這樣的：

1. 考慮單個怪，假設每秒都對其發射\(k\)發子彈，則最少需要\(\lceil a_i / k \rceil\)秒，所以判斷\(\lceil a_i / k \rceil \leq x_i\)，但是這種判斷方式的整體性不強，僅僅關注個體，顯然無法得到正確答案

2. 我們加入更多整體信息，由于我們要擊殺所有怪，所以打出的子彈的總和一定等于所有怪的生命值之和，那么我們考慮能否在給定的時間內打完這些子彈，即判斷\(\sum a_i \leq kx_{max}\)

3. 過了半個小時之后，我才靈光一閃，猜到了正確結論，賽后想來有理有據的分析應該是這樣的，猜想2的缺點與猜想1相反，整體性過強，對個體的關注過少，直觀的想法是，可能有一個生命值很大的怪，但到角色的距離很近，這樣盡管后面的怪生命較大，能夠平攤這個大生命值，但角色還是會被擊殺，所以，我們想到（不知道怎么想到）枚舉到角色的距離，并進行2中的檢查，就可以了。

這題的思路我也不是很懂，大概有以下幾點，

1. 可以先隨便猜一個結論，然后舉反例并分析其問題，是過于關注個體還是過于關注整體？如果過于關注部分，可以嘗試考慮各部分的和或并；如果過于關注整體，可以嘗試對多個部分進行同樣的策略（云里霧里qwq）

2. 要有一些第一直覺，比如直覺上覺得距離近，生命值大的怪優先級更高，并將其與自己的策略相結合

C

調整法

首先，我們初始讓\(b=a\)，則第一個條件顯然滿足，接下來考慮對\(b\)中的每個元素進行一些加減，使得\(b\)與\(a\)相同位置上的數不同

那很顯然，如果我們有偶數個元素，只需讓一般的元素\(+1\)，另一半\(-1\)即可，奇數的話就是\(\lceil s / 2 \rceil\)個元素\(-1\)，\(\lfloor s / 2 \rfloor - 1\)個元素\(+1\)，還有一個元素\(+2\)（\(s\)是序列長度）

但是，由于\(\forall b_i > 0\)，\(b_i = a_i = 1\)的位置是不可以減小的，只能增加

那么，我們考慮按長度奇偶性分類，設長度為\(s\)，\(1\)的個數為\(c\)，\(a\)序列總和為\(s\)：

若\(s\)是偶數，則

如果有至少\(s/2\)個位置可減，輸出YES

否則，說明\(1\)的個數大于\(s/2\)，則將每個一\(+1\)，總和增大\(c\)，其余的數總共就要減去\(c\)，由于每個數至多減到\(1\)，所以可供減掉的值為\((sum - s)\)，若\(sum - s \geq c\)，輸出YES，否則輸出NO，并且，由于\(1\)的個數大于\(s/2\)，根據鴿巢原理，剩下的每個數都至少會被減一，從而與原序列不同

長度為奇數時同理，這里不再贅述

D

最優化：dp，貪心，二分，枚舉

我們選擇二分，考慮check怎么寫

即，判斷一個點是否能在時間\(t\)內被吃掉

首先，我們發現，能在時間\(t\)內吃掉\(i\)的slime一定在區間\([i + 1, i + t]\)或\([i - t, i - 1]\)內，我們先考慮右半邊區間，那么我們可以考慮其中的最大值（極端原理），顯然，最大值能夠吃掉這個區間內的所有slimes，最后再來吃\(i\)，于是，我們只需要判斷\(sum[i + 1, i + t] > a_i\)即可。

但是，還有一種特殊情況，由于本題的條件是嚴格大于時才能吃掉，所以如果[i + 1, i + t]中全都是一個值，就不能吃任何slime，所以，我們在二分的時候特判下\(i + 1\)與\(i + t\)之間的元素是否全相等，如果是，則令\(l = mid + 1\)

左半邊區間同理，兩者都求完后取\(\min\)即可

tag: 極端原理，最優化

10.22

Edu 161

C

記住預處理的重要性！

D

暴力是非常好想的，每輪遍歷整個序列，找出會被擊殺的怪，將其刪去，不斷重復這個過程

思考瓶頸在哪里，暴力有兩個部分，查找和刪除，刪除可用鏈表實現，那瓶頸就在于查找

于是，查找=數據結構=線段樹！盡管線段樹可能不是必要的，但確實有用。。。

于是，我們就可以維護一個序列\(f_i = a_{i-1} + a_{i+1} - d_i\)，查找其中大于\(0\)的位置，找到所有這樣的位置后，再將它們刪去（與鏈表結合），并更新兩邊位置的\(f\)值

這樣的話，每輪的查找次數應該等于該輪被擊殺的怪的數量\(+1\)，更新次數應該是前面這個數量的\(2\)倍，由于每個怪只會被擊殺一次，總的復雜度就是\(O(n\lg n)\)的

雖說是偏解，但好歹做出來了。。。

其實，正解的思路異曲同工，同樣是發現了每次刪除只會更新有限個元素，均攤后復雜度較優的特點。

我們發現每次刪去一個元素只會對相鄰的兩個元素產生影響，于是就可以記錄下每次刪去的元素，只更新可能被更新的元素，即刪去的元素的相鄰元素，就可以做到均攤\(O(n)\)的復雜度。

本題的關鍵點：每個元素只能被刪去一次，且每次更新\(O(1)\)個元素，均攤后復雜度較優

E

從特殊情況入手，一個長為\(n\)的單調遞增序列的上升子序列數是多少？顯然是\(2^n\)，然后考慮在它后面加一些數，假設加一個\(x\)，則對于前面小于\(x\)的部分，在其末尾加上一個\(x\)又能得到\(2^y\)個單增序列（\(y\)是前面序列中小于\(x\)的數的個數），再繼續加也同理

好吧，到這里思路就已經很明顯了，每次加一個數的貢獻都是\(2\)的冪次，所以就將輸入的數二進制拆分，根據其為\(1\)的位進行構造即可

1060 div.2

B

先對題目有些整體感受：

1. 整個序列類似一種波浪型，偶數位在波峰，奇數位在波谷

2. 操作一代價為\(0\)

結合一和二，我們發現，應該多用操作一，且應該讓偶數位盡可能大，于是，我們先對偶數位都進行一遍操作一，因為操作二只會讓操作一中的最大值變得更小，接著我們對計數位進行操作二，計算其降到\(\min(a_{i-1}, a_{i+1}) - 1\)及以下的最小代價就可以了

C1

這題研究數值性質，顯然存儲一些值域上的信息是會比較有利的

說到不互質的數，最常見的就是所有偶數了，所以，如果序列中出現兩個偶數，就不用操作，如果有一個偶數，一個奇數，則給那個奇數\(+1\)即可，若有兩個奇數，分別\(+1\)即可，所以，我們發現答案不超過\(2\)。

因此，對于每個質數，我們用\(c_x\)維護有多少個數被它整除，如果存在一個位置大于一，輸出\(0\)

接著，考慮\(1\)次操作的情況

如果有一個偶數，輸出\(1\)。

枚舉\(a_i\)，將\(a_i + 1\)分解質因數，如果其中一個質因數的\(c\)不為一，輸出\(1\)

否則，輸出\(2\)

完結撒花

C2

與C1的區別在于修改的代價不再為\(1\)

我們發現C1中的結論仍然成立，最多仍然只需要\(2\)次操作就能讓數列存在不互質的數，但根據樣例，我們發現這似乎不是最優的。

顯然判斷操作為\(0\)的做法與C1一樣，判斷\(1\)次操作也可以套用C1中的做法，加個答案取 \(\min\) 就行了

關鍵在于操作次數為\(2\)的方案，一個重要的觀察是，\(ans \leq b_{1st} + b_{2nd}\)，其中 \(b_{1st},\ b_{2nd}\) 分別是 \(b\) 中的最小值和次小值，因為我們只需要隨機選兩個奇數即可，所以不妨選代價最小和次小的（如果最小的或次小的之一對應的 \(a\) 值是偶數，那么在檢查一次操作時會有更小的答案，這個界仍然成立）

這時我們再考慮多次操作的問題，根據上面的結論，\(ans \leq b_{1st} + b_{2nd}\)，我們發現只有\(b_i\)最小的元素可以加多次，不然一定會超出這個界，為了出現不互質的數對，增加后的數一定是能被 能整除其他數的質數之一（已預處理） 整除所以只需枚舉質數，計算這個數模該質數的余數，算出最小代價即可。

10.23

Edu159

B

注意分討清楚

C

假設最終得到的數是 \(t\)，則 \(x\mid t - a_i\)，所以 \(\forall a_i \equiv k \pmod x\)，也就是 \(\forall a_i, a_j,\ x \mid a_i - a_j\)

那么，我們將數組從小到大排序，求出相鄰兩項之差的 \(\gcd\) 作為 \(x\)，然后查找小于最大值的最大的未出現的模 \(x\) 與數組中的數同余的數，即可

具體來說，查找時看哪個差值大于 \(x\) 就可以了。

還有一種特殊情況，如果原數組除以 \(x\) 得到的整數是連續的，我們既可以選 \(a_{\max} + x\)，也可以選 \(a_{\min} - x\)，兩者得到的操作次數是一樣的

D

對操作對坐標的影響求前綴和（如 \(\text{R} \rightarrow x \leftarrow x +1，y \leftarrow y\)）

那我們只需要在數組中快速查找是否存在某個坐標就行了，反轉可以通過某些前綴和推導進行轉化

于是現在問題轉化成這樣：如何在 \([l, r]\) 內快速判斷某個數是否存在

哈希表！

當然，為了防止沖突，也可以使用 STL 中的 map，復雜度會多一個 \(\log\)

但是，可能會有多個位置有同樣的值，而由于 map 只能將一個關鍵字映射到一個值上，這可能會導致劃分區間后我們找不到答案

然后卡了\(1h\)...

最后想出一種復雜的解決方法：將每個位置上的 \(pair\) 離散化，然后用 \(vector\) 記錄每個 \(pair\) 出現的所有位置

你說的對，但實際上只要用 \(map\) 將每個 \(pair\) 映射到一個 \(vector\) 就行了

ZWR大神的做法：

反轉開兩份前綴和跟 \(map\) 還是太復雜了，實際上中間翻轉的部分可以看作將原路徑在平面上關于起終點連線中點中心對稱后得到的，但我們并不需要實際對這段路經進行對稱，只需要將查詢的那個點對稱過去就行了，即如果原路徑經過了點 \(P'\)，那么反轉后的路徑就一定經過點 \(P\)，\(P\) 與 \(P'\) 關于對稱中心對稱

stO ZZFLS_zwr Orz

E

分析題意，\(C(a, b)\) 就是 $l_a + l_b - $ 將 \(a\) 反轉后與 \(b\) 的最長公共前綴長度，但是由于我們要批量求這個東西，所以我們考慮 \(Trie\)，將所有串反轉后的串插入到 \(Trie\) 中，然后用每個原串在 \(Trie\) 中匹配，統計答案即可

Edu 158

C

\(40min\) 時才過

條件：下取整，對整個數列進行操作，每輪操作的 \(x\) 固定
目標：使數列中數字全相同

除法，且對整個數列操作，意味著整個數列中數的相對大小關系是不變的

所以，數列中數字全相同 \(\Leftrightarrow\) 數列中的最小值等于最大值

那么我們就定義 \(f = a_{\max} - a_{\min}\)，目標就是讓 \(f\) 變成 \(0\)。

取整，考慮取整的性質，\(\lceil \frac{a+x}{2} \rceil = \lceil \frac{a + x \bmod 2}{2} \rceil + \lfloor \frac{x}{2} \rfloor\)

因為同時給所有數加上 \(\lfloor \frac{x}{2} \rfloor\) 不會使 \(f\) 變小，所以我們發現有用的實際上是 \(x \bmod 2\)，即，\(x\) 可以只取 \(0\) 和 \(1\)

然后，我們考慮數列的最大值 \(a\) 和最小值 \(b\)，\(a > b\)，若 \(b\) 是偶數，則如果我們取 \(x=1\)

那么，

若 \(x=0\)

故當 \(b\) 是偶數時，應取 \(0\)，同理，當 \(b\) 是奇數時，應取 \(1\)

D

我的思路：

首先猜測第一個選最大值最優，然后考慮怎樣情況是最差的，顯然是每次都選邊界上最小的擊殺，然后就做完啦！！！

Wrong Answer on test 6

好吧，反思過后我們發現第一個結論并不一定成立，即第一個不一定要選最大值

6
1 5 6 3 4 1

在這個例子中，選 \(6\) 的最壞情況是 \(9\)，選 \(5\) 的最壞情況是 \(8\)

看來我們必須要考慮所有初始點了。。。 \(O(n^2)\)

現在我們有兩條優化思路：

1. 嘗試優化枚舉初始點的過程（利用排除法）
2. 嘗試優化對一個點計算答案的過程

思考良久，好像這兩條都沒什么前途。。。

最后，看完題解，發現第二條結論也是錯的？！

73
98 100 99 1 1 1 1 1 1 1 1 (repeat 70 times)

在這個例子中，取完 \(100\) 取 \(98\) 并不是最壞情況，取完 \(100\) 然后一直取右邊的，最后再取 \(98\) 顯然比結論中的策略更差

那么我們只能轉而考慮其它方法，最后得出對于一個中心點，它左邊的點的最晚擊殺時間應該是它右邊的點的個數，即 \(n - i\)，中心點右邊的點則是它左邊點的個數，即 \(i - 1\)

所以，一個中心點的答案應該等于每個點的生命值 \(+\) 它的最晚擊殺時間，然后做完了。。。

從這題中我們可以看到，猜結論是要的，但是它不能解決所有問題，當我們發現沒有優化思路或無法再進行下去時，可以考慮結論是否正確，選擇修正結論，或摒棄結論，換一個思路繼續思考

10.24

Edu 155

B

一個結論是，如果要滿足每個方格都有與它同行或同列的 chip，要么每行都有一個 chip，要么每列都有一個 chip。

因為如果存在一列和一行沒有 chip，那么這一行與這一列的交叉點一定不滿足題意

所以，答案就是 \(\min\{\sum_{i=1}^{n} (A_i + B_{\min}),\ \sum_{i=1}^{n}(B_i + A_{\min})\}\)

C

計數題

因為這是一個 \(01\) 串，所以相鄰字符不同就是要變成 \(010101....\) 或 \(101010...\) 的樣子，那么我們只需要從每個連續相同數字段中刪去元素，直到每個段都為一即可

選擇所刪去元素的方案數為 \(\sum \binom{c_i}{c_i - 1}\)，由于操作順序可變，應該再乘上操作次數的階乘

D

異或 \(\rightarrow\) 可差分 \(\rightarrow\) \(f(l, r) = s_r \oplus s_{l-1}\)

然后沒有思路，因為異或對于加法，乘法均沒有分配律

換個思路，位運算 \(\rightarrow\) 每位獨立，分開處理，done

所以我們只需要維護每一位上，區間 \([l, r]\) 間一的個數是奇還是偶，如果是奇，這一位就會為 \(f(l, r)\) 貢獻 \(2^b\)，\(b\)是當前考慮的位，所以只需要分別記錄特定奇偶性位置 后綴下標和 以及 數量 即可

E -- My First Interactive Problem in Contest !

題意：

給你一顆 \(n\) 個節點的樹，你需要給樹上的 \(n-1\) 條邊染上顏色，然后與交互庫玩一個游戲

游戲內容是這樣的：

交互庫會欽定一個不是根的點，你可以從這個點向周圍移動，目標是用 \(d\) 步走到根（\(d\) 是結點的深度），即每一步都要向根的方向走。每次你到達一個節點（包括初始節點），交互庫都會給出一個數組 \(c\)，\(c_i\) 表示與當前結點相連的邊中顏色為 \(i\) 的有多少條，然后你可以從中選擇一種顏色，表示沿該種顏色的邊行走，如果你選的顏色有多條邊，交互庫將隨機選擇一條

請你給出一種染色方案，使得顏色總數最小，并根據交互庫給出的信息，每次選擇合適的顏色，到達根節點

---

根據題意，我們每次都必須向根的方向行走，即，我們只能走從該節點連向它父親的那條邊，于是問題就變成，怎樣染色可以使得這條邊能被區分出來。

顯然，\((x, p_x)\) 這條邊的顏色必須與其他連向兒子的邊的顏色不同，不然交互庫不能保證一定走這條邊

我們嘗試手玩，根據深度進行染色似乎是一個比較合理的想法，我們發現，用 \(3\) 種顏色一定能夠滿足上述要求

具體的，第一層的邊染成顏色 \(a\)，第二層染成 \(b\)，第三層染成 \(c\)，第四層再染成 \(a\)...
即

所以，接下來，我們應該逐個分析，什么時候用一種顏色，什么時候用兩種，什么時候用三種

首先，如果樹只有兩層，即節點一連向其他所有結點，那么答案是 \(1\)

接著，我們考慮為什么當時手玩的時候選擇 \(3\) 種顏色，而不是 \(2\) 種

問題出在二度點上

我們在前面說過，染色的目標是將連向父親的邊區分出來，但是，對于二度點，即使兩條邊被染成不同顏色，我們也無法區分，因為兩種顏色的邊數都是 \(1\)，解決的辦法是規定一個順序，例如在 \(3\) 種顏色的條件下，我們規定了 \(a\) 優于 \(b\)，\(b\) 優于 \(c\)，\(c\) 優于 \(a\)，也就是說，如果 \(a\)，\(c\) 同時為\(1\)，那么我們選 \(c\)

那么，仿照同樣的思路，如果想僅用兩種顏色進行染色，就必須規定遇到二度點時兩者的順序，且這個順序對于所有的二度點均相同，這里假設是 \(a > b\)，即對于二度點，連向父親的邊染成 \(a\)，連向兒子的染成 \(b\)

接下來我們就要看什么時候這個方案能夠自洽

我們的方案：

1. 一個點連向其父親的邊的顏色 \(\in \{a, b\}\) 且與其連向兒子的邊的顏色均不同（這暗示著連向兒子的邊顏色均相同）
2. 對于二度點，連向父親的邊顏色為 \(a\)，連向兒子的顏色為 \(b\)

首先，如果有一個二度點，方案滿足，進一步的，如果所有二度點的深度均相同，方案滿足

如果有兩個二度點位于相鄰層，方案不滿足

我們進一步一般化，考慮兩個二度點 \(x, y\) 和他們的 \(LCA\)，\(d\)，

容易發現，路徑 \(x \leadsto d\) 和 \(y \leadsto d\) 上的邊的顏色都是交替的，那么如果 \(\delta(x, d)\) 是奇數，\(d \rightarrow x\) 所在子樹的邊顏色一定是 \(a\)，否則一定是 \(b\)，\(y\) 同理，而由于從點 \(d\) 出發向下的邊顏色均相同，所以，\(\delta(x, d)\) 與 \(\delta(y, d)\) 的奇偶性相同，即 \(dep_x \equiv dep_y \pmod 2\)，也就是說，所有二度點的深度的奇偶性必須相同

但是通過手玩后，我們發現，根節點比較特殊，因為它沒有指向父親的邊，所以邊 \((1, u)\) 的顏色不必相同

這也好辦，把策略改成，在每顆以根結點的兒子為根的子樹中，所有二度點的深度的奇偶性必須相同，即可

于是，我們就可以判斷出能否用兩種顏色染色了

染色時需要注意，不能在判斷的時候染色，應該在判斷結束后，遍歷根的每個兒子，如果在這個兒子 \(v\) 的子樹中，所有二度點的深度都是偶數，那么 \((1, v)\) 染為顏色 \(b\)，否則染為顏色 \(a\)

交互的時候，對于一種顏色的，只需要輸出 \(1\) 即可，對于兩種顏色，哪個的出現次數為 \(1\) 輸出哪個，對于三種顏色，如果 \(c\) 中僅有一個位置不為 \(0\)（那么一定為 \(1\)，葉子），輸出這個顏色，否則按照順序，同時有 \(a,b\)，輸出\(1\)；同時有 \(b, c\)，輸出 \(2\)；同時有 \(a, c\)，輸出 \(3\)（顏色的數字編號與字母編號數對應的，上文為了與節點區分，使用字母，實際寫代碼時應用數字）

10.25

Edu 154

C

注意題目中的操作：向序列末尾添加一個數，刪除序列的最后一個數，這很符合棧的特點，于是我們考慮用棧解決這個問題。

具體的，棧頂表示當前序列的有序狀態，\(0\) 表示無序，\(1\) 表示有序，\(-1\) 表示不確定

那么，棧的最低端兩個元素（對應序列長度為 \(0, 1\) 的情況）應該為 \(1\)

對于 \(+\) 操作，如果棧頂為 \(0\)，應繼續入棧 \(0\)，否則入棧 \(-1\) （在無序的序列后添加元素仍是無序的）

對于 \(-\) 操作，如果棧頂為 \(1\)，應該將棧頂彈出，并將新棧頂改為 \(1\) （在有序的序列后刪除元素仍是有序的）

也就是說，最后棧的結構應該是這樣的：前面是 \(1\) 和 \(-1\)，后面是連續的 \(0\)，一直到棧頂

對于明確順序狀態的操作，如果棧頂與輸入的數據不符且棧頂不是 \(-1\)，出現矛盾，輸出 NO

最后，如果沒有輸出 NO，輸出 YES

D

容易發現，進行一次乘法后，如果所乘的 \(x > 0\)，操作區間內的元素相對順序是不變的，否則，元素相對順序就會全部反過來

那么如果我們有一個單谷的序列，我們就可以通過對遞減的那段前綴乘上一個負數，花費一次操作，完成排序

那么我們的問題就變成如何用最少次數將原序列變成一個單谷序列

對于最低點右側的部分，它是遞增的，則對于每一個 \(a_{i-1} \geq a_i\) 的位置，我們都至少需要一次操作將后綴 \([i, n]\) 乘上一個數（因為乘法只能讓數變大，所以取后綴不劣），即我們只需統計一段后綴中 \(a_{i-1} \geq a_i\) 的位置的數量

對于最低點左側的部分，同理我們可以得出應該統計 \(a_i \leq a_{i+1}\) 的位置

于是我們只需枚舉最低點，將兩邊滿足條件的位置個數加起來，再加上 \(\times (-1)\) 那一次操作（最低點下標為 \(1\) 不用乘），取最小值即可

E

好題！

首先，如果給定一個排列，那我們可以貪心地算出其中不相交子排列的個數，即每次都取最前面的子排列

求每個排列的 cost 和，我們考慮用貢獻法，

我的想法，求出有多少個排列的 cost 值為 \(x\)，最后加起來

真正的貢獻法：求出每個子排列會被計算多少次

即，我們記 \(f_i\) 為只考慮前 \(i\) 個元素，以第 \(i\) 個元素結尾的排列被計算的個數

那么，利用容斥計算，先令 \(f_i = k! \times k^{i-k}\)，即最后 \(k\) 個元素是一個排列，前面隨便填的方案數，

然后，因為要滿足貪心性質，那么 \(\forall j \in [i-k+1, i-1]\)，以 \(j\) 結尾的排列不能被計算貢獻，它被計算貢獻的方案數是 \(f_j \times (i-j)!\)，乘 \((i?j)!\) 是由于 \([i?k+1,i]\) 這個段中 \(1\) 到 \(k\) 各出現一次，而 \([i?k+1,j]\) 中的數已經被以 \(j\) 為結尾的段確定了，剩下 \(i?j\) 個數任意指定次序。（注意這里是被計算貢獻的以 \(j\) 結尾的排列數，也就是說上一個排列一定在 \(j - k\) 及之前結尾，不然以 \(j\) 結尾的排列會被覆蓋，從而沒被計數）

所以，\(f_i = k! \times k^{i-k} - \sum_{j = i - k + 1}^{i - 1} f_j \times (i-j)!\)

最后，由于為了轉移，\(f\) 僅考慮了前 \(i\) 個元素的填法，統計答案時 \(ans = \sum f_i \times k^{n - i}\)

10.27

Edu 153

A

猜測只用考慮 \(()()()()\cdots\) 和 \(((((\ \cdots ))))\) 這兩種可能答案，因為除了 \((,\ ),\ ()\)，兩者沒有公共子串，因此，不存在一個串同時是兩者的子串

倒是 \(string\) 的用法需要注意一下

s.find(t, pos) 返回從 pos 開始的第一個 t 出現的位置，如果沒找到，返回 npos（即 \(-1\)）

B

首先考慮最優解肯定是盡量選價值為 \(k\) 的金幣，剩下的再用價值為一的金幣，即最優情況下，我們應用 \(\lfloor m/k \rfloor\) 個價值為 \(k\) 的金幣，再用 \(m \bmod k\) 個價值為 \(1\) 的金幣，湊出 \(m\)

但是，如果價值為 \(k\) 的普通金幣不夠用，我們可以用價值為 \(1\) 的普通金幣來換。

即，

coin_k_needed = m / k; // 需要的價值為k的金幣
coin_1_needed = m % k; // 需要的價值為1的金幣
coin_k_fancy = max(0, coin_k_needed - ak); // 需要的價值為k的fancy幣
coin_1_fancy = max(0, coin_1_needed - a1); // 需要的價值為1的fancy幣
coin_1_left = max(0, a1 - coin_1_needed); // 剩下的價值為1的普通金幣
exchange = min(coin_k_fancy, coin_1_left / k); // 能夠通過剩下的價值為1的普通金幣兌換的價值為k的fancy幣

ans = coin_1_fancy + coin_k_fancy - exchange

C

博弈論原理的應用：如果一個局面能夠轉移到的狀態都是必敗態，則該狀態是必勝態，否則，如果能夠轉移到至少一個必勝態，則該狀態是必敗態

在本題中，一個數可以轉移到在它前面且比他小的數，那我們只需要判斷這些數是不是都必敗即可

具體地，使用兩個樹狀數組，分別維護值在 \([1, x]\) 的數的個數，以及值在 \([1, x]\) 的 unlucky 數的個數，對于每個數，判斷 ask_1(a[i] - 1) == ask_2(a[i] - 1) 即可

D

首先，我們先統計出序列中 \(01\) 以及 \(10\) 的個數，即每個 \(1\) 左邊的 \(0\) 的個數之和，以及每個\(1\) 右邊的 \(0\) 的個數之和，那么我們的目標是讓這兩個值相等，于是我們考慮他們的差值，目標即為讓這個差值變為 \(0\)

接著，我們考慮交換操作對這個差值的影響，分析后可以發現，若交換一個 \(1, 0\)（\(1\) 在 \(0\) 之前），則差值將會增大 \(2(p_0 - p_1)\)，反之，如果交換 \(0, 1\)，差值將會減小 \(2(p_1 - p_0)\)，即，差值的變化量 \(\Delta = 2(p_0 - p_1)\)

那么，我們的問題就變成，有若干個二元組 \((p_0, p_1)\)，每個的價值為 \(2(p_0 - p_1)\)，選出其中的一些，使得價值總和為 \(k\)（初始的差值），求選擇的二元組數量的最小值，并且，不能選兩個有公共端點的二元組，即 \(\forall (p_0, p_1), (q_0, q_1) \in T, p_0 \ne q_0, p_1 \ne q_1\)（ \(T\) 是選出的集合）

然后不會做了，這個限制太難搞了

我們從另一個角度考慮，這個限制的關鍵在于不能選有兩個公共端點的二元組，實際上，我們細品這句話，它等價于每個點只能被選一次

這樣就好做多了，原來的價值定義為 \(2\sum (p_{i0} - p_{i1})\)，那么，如果我們將其看成若干個點，代價就是：

\(p_i\) 是我們所選第 \(i\) 個點的下標

于是，我們需要上式等于 \(k\)，并且所選的點中系數為 \(1\) 和 \(-1\) 的點數量相等，求滿足上述要求所需要的最少系數為正的點

于是，定義 \(f(i, j, k)\) 為僅考慮串中前 \(i\) 個字符，正數點與負數點個數差值為 \(j\)，總價值為 \(k\) 所需要的最少系數為正的點

那么：

于是這題就愉快的做完了

題解中的方法則是更加基于對序列特征的刻畫

定義 \(f(i, a, b)\) 為僅考慮串中前 \(i\) 個字符，序列中有 \(a\) 個 \(0\)，有 \(b\) 個 \(01\) 時，與原串不同的位置數量的最小值

考慮順轉，

若第 \(i + 1\) 位填 \(0\)，則 \(f(i + 1, a + 1, b) += f(i, a, b)\)
若第 \(i + 1\) 位填 \(1\)，則 \(f(i + 1, a, b + a) += f(i, a, b)\)，因為前面的每個 \(0\) 添上新的這個 \(1\) 都能構成一個新的 \(01\)

那么我們最后如何得到答案呢？

設原串中 \(0\) 的個數為 \(x\)，長度為 \(n\)，那么最后我們的 \(01\) 的個數應該等于所有 \(0, 1\) 的組合地一半，即 \(\frac{x(n-x)}{2}\)

那么答案就是 \(f(n, x, \frac{x(n - x)}{2})\) ......

還要除以 \(2\) ！因為 \(f\) 記的是不同位置個數，而交換一次最多能復位兩個元素，所以除以 \(2\)

Edu 152

C

字符串操作，使用哈希

實際上有更簡單的做法，我們維護每個串實際上修改的區間

因為如果要排序的區間 \([l, r]\) 的開頭是一段連續的 \(0\)，那么排序完后這些連續的 \(0\) 應該還在原位，所以是不變的，結尾同理，即，實際修改的區間的左端點是 \([l, n]\) 中第一個 \(1\)，而右端點是 \([1, r]\) 中最后一個 \(0\)

特別的，如果新的左右端點不能構成一個區間，說明不會有修改

那我們只需要看有多少對不同的新左右端點即可

vp的時候發現了性質，但是研究的是兩個串不公共部分的性質，實際上這可以轉到每個串自己身上，但沒有想到

D

還是充分利用性質，發現如果一段區間有 \(2\)，那么可以花 \(1\) 的代價將 \(2\) 左邊第一個 \(0\) 到右邊第一個 \(0\) 之間的區間（包括端點）染成紅色，如果有 \(1\) 無 \(2\)，那么可以花 \(1\) 的代價將 \(1\) 左邊第一個 \(0\) 到右邊第一個 \(0\) 之間的區間（只包括一個端點）染成紅色

那么我們只需要從前往后掃一遍，如果當前區間能夠用 \(1\) 的代價染色，就一直擴展右邊界，否則就將答案加一，左端點跳到右端點之后

10.28

Edu 151

D

設 \(s_i = \sum_{i=1}^{i} a_i\)，那么我們可以發現最優的 \(k\) 一定出現在 \(s\) 之中，即 \(\exists s_i = k_{opt}\)

然后我就一直在考慮最優點的位置的特點，沒有進展

一萬年后，換了種思路，我們發現在前面的限制下，當我們令 \(k = s_i\) 時，答案就是 \(k + (\ [i + 1, n]\) 以 \(0\) 為基準計算得到的答案 \()\)

那我們設 \(f_i = [i + 1, n]\) 以 \(0\) 為基準計算得到的答案，考慮如何轉移（vp時一直在想暴力的做法，沒往轉移上想T_T）

為了轉移，我們的基準不能變，考慮 \(f_i \leftarrow f_j \ (j > i)\) 那么如果 \(\sum_{k=i}^{j - 1} a_k > 0\)，那么后面的基準就不再是 \(0\)，所以我們應該將 \(i\) 到第一次 Rating 降到 \(s_i\) 以下的位置劃為一段，那這部分對 Rating 的修改就是無效的，因為最終回到了 \(s_i\)，然后后面的部分就可以轉移過來了，如果后面 Rating 不會降到 \(s_i\)，那么 \(f_i\) 就等于后面所有數的和，最后答案就是 \(\max_{1 \leq i < n}\{s_i + f_{i+1}\}\)

上述算法可用線段樹實現 \(O(n\lg n)\)

但是我們如果更深入地考慮轉移的過程，可以將其優化到 \(O(n)\) 的

每次，我們都會選擇和小于 \(0\) 的一段數，將其跳過，那么實際上 \(f_i\) 就等于 \(sum[x, n]\)，\(x\) 是滿足以下條件最靠前的位置：\(\forall y \geq x,\ sum[x, y] > 0\)，進一步考慮，實際上前面的部分 \([i, x - 1]\) 實際上就是以 \(i\) 開頭的最小前綴和，所以 \(s_{i - 1} + f_i\) 就是序列總和減去以 \(i\) 開頭的最小前綴和，那么，遍歷所有 \(i\) 之后，我們實際上得到的就是序列的 總和減最小子段和

那我們就只需要求出最小子段和即可，答案就是最小子段左端點 \(-1\) 的前綴和

10.29

Edu 150

D

C題一直在調，浪費了很長時間

最小值的最大值，考慮二分，即判定能否使數列中全部數都大于等于 \(x\)

于是我們考慮讓每個數都變得盡可能大（原來我考慮的是小于 \(x\) 的數，不太好想）

我們觀察這個操作的特點，容易發現只有當一個數被操作奇數次，它才會變大，否則就會變小，并且增大的值等于最后一次操作的編號減去 操作次數 除以 \(2\)

這樣的話，我們發現不是所有的數都能變大，只有當 \(n \equiv k \pmod 2\) 時，才有可能每個數都變大

我們重新考慮操作的特點，相當于加上最大操作，然后加上一堆 \(-1\)，那我們可以考慮將每個操作分配到每個數上，那么顯然大的操作應該分到小數上，并且，由于我們想讓所有數都變得盡可能大，我們就將最大操作 \(k\) 分配給最小值，將 \(k - 1\) 分配給次小值，以此類推，即 \(k \sim k - n + 1\) 全部從小到大被分給不同的數

那么剩下的數都只會兩兩組成 \(-1\)，使值變得更小，那我們的 \(check\) 就只需要判斷每個數（加上第一次分配的操作之后）與 \(x\) 的差之和，是否大于 \(-1\) 的個數（即 \((k - n) / 2\)）即可，實際上連判斷也不需要，可以用公式計算出來

特別的，對于 \(k < n\) 的情況，只需要對前 \(k\) 小的元素加就行了

另一種情況是 \(k \not\equiv n \pmod 2\)，這是，一定有一個元素是變小的，也就是說，我們第一輪分配的時候要少分配一個元素，根據貪心，我們選擇舍棄分配給最大值的操作，然后按原來方法計算即可