加把勁

正睿noip二十聯測

day1

$ 100 + 0 + 0 + 30 $ ，菜完了。

寶寶會算術

真寶寶題，二進制拆分一下，簡單分析一下就過了。

寶寶玩游戲

躺尸大模擬。一開始想的是一個類似于插入排序的方法，需要在環上轉圈，難寫到爆炸；另一種做法是像冒泡排序一樣每次交換相鄰兩個，相對好寫（還是一坨）。懶得改了。

寶寶拼字母

一個顯然的事實是 \(A\) 和 \(B\) 相似（不妨認為 $ |A| \le |B| $ ），等價于 $ |A| + K \ge |B| $ 并且 $ LCP(A,B) + LCS(A,B) + K \ge |B| $ 。

對于每一種后綴分別做，在 tire 樹上維護前綴，同時只有最長公共后綴才是合法貢獻，把不合法的貢獻斥掉就好了。

寶寶選東西

首先按照 \(b\) 對每個物品排序，設 $ f(l,r) $ 表示 $ l,r $ 之間選擇恰好 \(k\) 個物品的最大價值。不難發現對于每個 \(r\) 來說 $ f(l,r) $ 符合決策單調性和四邊形不等式。然后就是分治優化，用鏈表維護前 \(k\) 大值，復雜度可以做到 $ O(n \log n) $ 。

day2

$ 100 + 56 + 36 + 52 $

小學算術

似乎是原哦，問題就是 $ \lfloor \frac{a}{b} \times c^d \rfloor \mod c $ ，答案就是 $ \lfloor \frac{ a \times c^d \bmod (c \times b) }{b} \rfloor \bmod c $ 。

馬戲表演

顯然是笛卡爾樹DP，容易寫出轉移式 $ f_i = \sum_j [ j \times (i-j+1) \le m ] \times f_j \times f_{i-j-1} \times \dbinom{i-1}{j} $ ，再把組合數拆開，是一個卷積的形式，然后注意到必然存在 $ \frac{ f_j }{ j! } = 1 $ 或 $ \frac{ f_{i-j-1} }{ (i-j+1)! } = 1 $ ，前綴和優化一下就好了。

拯救世界

首先做一個簡單DP，先枚舉可能的波動區間，$ [0,m] $ 到 $ [-m,0] $ ，初始的狀態為0，設 $ s_i $ 是 $ a_i $ 的前綴和，轉移是 $ \forall j+k+s_i \in [l,r] , f_{i+1,j+k} \gets f_{i,j} + k \times c_i $ 。

發現轉移是每次和一個凸函數做卷積，可以用 set 維護閔可夫斯基和，把超出合法范圍的刪掉，復雜度為 $ O( nk \log n) $ 。

還可以進一步優化，固定波動區間為 $ [0,m] $ ，初始的狀態是 $ [0,m] $ ，發現完全是等價的。

環上游戲

咕咕咕~

day3

$ 60 + 30 + 30 + 0 $ ，感覺垃圾場。

哈基米喲南北綠豆

第一反應是，因為可以使用一個多項式表示，所以平凡的情況都是有解的，但事實上并非如此，因為不能出現分數。注意到給定的運算中沒有除法和位移，所以最后的結果只能從二進制下的低位影響到高位。

結論是枚舉二進制下前 \(k\) 位，若存在 $ x_i = x_j $ 但 $ y_i \neq y_j $ ，則無解，否則必然有解。

阿西噶納哈呀魯

垃圾題。

注意到 \(a\) 的范圍很小，直接 $ O( n^2 V^2 ) $ DP。

賽事不初始化掛沒了。

歐馬吉利叮咚雞

推式子題。

我要玩原神，不改這玩意了。

叮咚叮咚哈基米

大難題，不會。

先考慮 $ a_i \le 0 $ 的情況，顯然最后 $ x_i $ 要么取 \(0\) ，要么所有 $ f_i'(x) $ 全都相同（設為 \(D\) ），并且 \(x_i\) 取 \(0\) 的 $ f_i'(0) \le D $ 。

假設 $ t_i $ 是定義 $ f_i(x) $ 在合理情況下能達到的最大值所需的最小 \(x\)（非負）。反證一發：設有兩個 $ a > 0 $ 的函數 $ f_i( x ) , f_j( x ) $ ，最優解都滿足 \(x \notin \{ 0,t \}\) ，那么 $ g(x) = f_i(x) + f_j(x_i + x_j - x) $ 是一個開口向上的二次函數，一定在定義域端點取到極值，與 \(x \notin \{ 0,t \}\) 矛盾。

總結一下，就是在 \(a\) 大于 0 的函數中，至多有一個滿足 \(x_i \notin \{ 0,t \}\) 。由于這樣的函數只有 $ n' \le 15 $ 個，直接 $ O( 2^{n'} n' ) $ 枚舉。

然后變成了一個 $ a>0 $ 的二次函數和很多 $ a \le 0 $ 的函數求最值，再然后不會了。

day4

$ 100 + 0 + 10 + 20 $ ，被 T2 徹底創飛的一集。

開心消消樂

對于每一對相同的數都需要一次操作，另外存在 ABAB 這樣的子序列也會需要一次操作，樹狀數組維護一下。

越獄

原題

小清新DP。

核心思想就是讓所有犯人的初始位置盡可能往前放（即不存在一種移動方式使得有犯人還能前進）。

設 $ f_{i,j} $ 表示 前 \(i\) 位中，當前房間的最終犯人數量為 \(j\) 的最大人數，分討轉移：

1. $ j \ge a_i + b_i , f_{i,j} \to f_{i+1,j} $

2. $ a_i \le j < a_i + b_i , f_{i,j} \to f_{ i,j-a_i } $

3. $ j < a_i $ ，枚舉 \(i+1\) 中當前人數 $ k \in [ 0,b_i ] $ ，若 $ k < b_i $ 則有 $ f_{i,j} + k \to f_{i+1,k} $ ；否則有 $ f_{i,j} + b_i \to f_{ i+1,j+b_i } $

前綴和優化一下，設 \(M = \max \{ m , a_i + b_i \}\) ，復雜度為 $ O(nM) $ 。

冒泡排序

先賀一個排序網絡的經典結論：排列 \(a\) 能在 \(k\) 輪雙向冒泡排序內被排序當且僅當對于任意 $ 1 \le x \le n $ ，若將 \(a\) 中 $ \le x $ 的元素看作 \(0\) ，將 \(a\) 中 $ >x $ 的元素看作 \(1\) ，則新序列能被排序網絡排序。

將排列抽象成 01 序列，進行 \(k\) 輪雙向冒泡，手模出來是刪掉序列前綴 0 和后綴 1 ，記 0 和 1 的連續段長度為 $ p_1 , \dots , p_m $ 和 $ q_1 , \dots , q_m $ 。每次相當于給 $ p_1 $ 和 $ q_m $ 減一，判斷條件是不存在第 $ k+1 $ 個 1 或在這之后至多有 \(k\) 個 0 。設當前的元素是 \(x\) ，則序列中有 $ n-x $ 個 1 ，驚人地發現原來的判斷條件等價于前 \(x\) 個元素中有至多 \(k\) 個 1 。

設 $ f_{i,j} $ 表示已經插入 $ n-i+1 $ 到 \(n\) 為 1 ，前 $ n-i $ 個元素中恰有 \(j\) 個 1 的方案數。

采用代價延后計算的思想，有四種轉移：

1. 當前位是 0

   若 $ n-i-1 $ 插入不在前 $ n-i-1 $ 個元素中，則有 $ f_{i,j} \times (j+1) \to f_{i+1,j} $

   否則，$ f_{i,j} \to f_{i+1,j+1} $ ，這里的貢獻不好維護，到下面的轉移再計算。

2. 當前位是 1

   若 $ n-i-1 $ 插入不在前 $ n-i-1 $ 個元素中，則有 $ f_{i,j} \times j^2 \to f_{i+1,j-1} $

   否則，$ f_{i,j} \times j \to f_{i+1,j} $

復雜度 $ O(NK) $ 。

黑白棋

時間倒流，改為刪除棋子。

枚舉第一個被刪除的連續的的最后一個棋子顏色，設其為 \(c\) ，反色為 $ c' $ ，則其余所有連續段（包括前一個和后一個）在該棋子被刪除時為 $ c'\dots c' $ 。

后面懶得寫了，直接上結論：存在至多一個連續段（不含其左右）只含 \(c\) 子序列，至多一個連續段（含左右）只含 $ c'c' $ 子序列，其余連續段（含左右）只含 $ c'cc' $ 。大力DP加前綴和優化即可做到 $ O(n) $ 。

day5

$ 85 + 100 + 10 + 10 $ ，小掛不算掛。

T1 魔法試劑

注意到集合 \(X\) 元素個數一定是 $ O( \log V ) $ 的，枚舉 \(X\) 中元素之和，可能的值很少，然后暴力判斷有解就行。

下界開小是會掛分的

T2 稱重

直覺上就是并查集維護數量關系。具體來說開 $ O( \log V ) $ 個帶權并查集， $ -1 $ 的情況需要特判。

T3 編碼

直覺上就是哈夫曼樹相關，被初賽知識點創飛了。

先思考 $ A = B $ 的情況，普通哈夫曼樹模板，就是合并石子。

對于 $ A \neq B $ 的情況，相當于是一個特殊的哈夫曼樹，每個節點兩條邊長度分別是 $ A,B $ 。一棵哈夫曼樹的最小代價就是所有葉子結點的深度和每種編碼的數量倒序匹配。

再考慮對著節點深度DP，當前的一個節點可能有兩種情況：成為一個葉子，計算貢獻；或者分出左右兒子，進入下一層。

對每一層分別做就好了。

T4 翻轉函數

魔改版馬拉車。（APJ講過）

修改一下回文的定義：存在一個映射使得序列可翻轉就稱為回文。

與普通的馬拉車最大區別在于：如果當前中心的對稱點的最大回文串超出當前回文串范圍，不能直接繼承貢獻，做法是把對稱點的回文區間縮小。需要維護相同顏色的前驅后繼，用于快速修改貢獻。

現在我們證明上述做法復雜度正確性：

設當前回文串的回文中心是 $ mid $ ，回文半徑是 $ R $ ，當前中心是 \(x\) ，它的對稱點是 \(y\) ，\(y\) 的回文半徑為 \(r\) ，那么這次區間縮小的代價為 $ mid - R - y + r $ ，顯然有 $ y + r \le mid + R $ ，那么可以得到 $ mid - R - y + r \le 2 ( mid - y ) $ 。這樣均攤時間復雜度就是 $ O(n) $ 的。值得注意的是，上述復雜度分析要求當區間右端點相同時，當前回文串的回文中心去更大的那個，否則復雜度是假的。

day6

$ 100 + 72 + 35 + 20 $ ，小掛不算掛。

T1 列隊

將一定數量的負值交替排列，使得他們沒有貢獻。不好玩。

T2 子序列

一個 $ O(n^3) $ 的暴力是顯然的，然后注意到每個點的狀態只有最大顏色和次大顏色可能對后面的轉移有貢獻，可以借此優化到 $ O(n^2) $ 。

然后上經典結論。 注意到一個事實是相鄰兩個被選中的數字之間顏色數不超過 4 ，因為如果有更多，一定可以再插入一個，保留最大的幾種顏色，轉移即可。復雜度 $ O(n) $ 。

T3 騎士

一個經典的 trick 是按照 $ \fracw0obha2h00{2} $ 分組，較小的一組兩兩之間一定沒有貢獻，另一組兩兩之間一定有貢獻。將較大的一組（降序排序）壓進狀態，較小的一組（升序排序）用于決策。假設當前較大的一組枚舉到第 \(i\) 個，設兩個集合大于 $ \fracw0obha2h00{2} $ 的數字數量是 $ x,y $ ，那么此時把 $ [ d-a_i , d-a_{i+1} ) $ 的數字加入集合，貢獻分別是 $ x,y $ ，然后轉移顯然。

T4 文本編輯

大聰明題。

操作一定形如先執行二操作映射，再一操作微調。其中二操作的映射關系啟示我們建圖之后是一個基環樹森林。

手玩一下就會發現：樹和基環樹代價就是邊權之和，但是純環需要借助一個其他節點，代價多一個 \(k\) 。

嘗試最小化這個代價。

我們先對于每個節點貪心選邊，如果連成純環，似乎就暴斃了。

觀察到這樣一個結論：最優圖中的純環的邊一定在貪心圖中存在，否則一定不優。對貪心圖中的環（不包括自環）狀壓，最多只有 13 個。還需要特判只有純環（無解）和只有自環的情況，復雜度是 $ O( 2^{ \frac{ \Sigma }{ 2 } } \Sigma ^ 2 ) $ 。

day7

$ 100 + 100 + 0 + 25 $

T1 劃分字符串

詐騙題，只有 10000000 這樣的才不是好串。

T2 記憶碎片

顯然答案是單調的，并且答案規模不超過 $ O( \sqrt {n} ) $ ，枚舉兩種整理方式的操作次數，貪心計算。

T3 三分圖計數

對于判斷一個圖是不是三分圖是沒有前途的，不如在排列上考慮問題。一個排列不是三分圖，相當于最長下降子序列長度超過 3 。按照貪心求 LDS 的方法DP。設 $ f_{x,y,z} $ 表示當前 LDS 元素為 $ i,j,k $ ，滿足還沒確定的數字中 $ [i+1,n] $ 有 \(x\) 個， $ [j+1,i-1] $ 有 \(y\) 個，$ [k+1,j-1] $ 有 \(z\) 個。先預處理再試填法。

復雜度 $ O( n^3 + T n^2 ) $ 。

T4 登山計劃

數據結構可愛捏。

不妨先考慮弱化問題 $ L=1 , R=n $ 。

經典序列分治，設當前分治區間 $ l,r $ ，中點是 $ mid $ 。對左側做后綴 min ，對右側做前綴 min ，枚舉子區間長度 \(k\) 。當區間左端點為 \(i\) 時，答案即為 \(| \min \{ sa_i , sa_{ i+k-1 } \} - \min \{ sb_i , sb_{ i+k-1 } \} |\) 。其中 $ sa_i $ 隨 \(i\) 單增， $ sa_{ i+k-1 } $ 隨 \(i\) 單降， $ sb $ 類似。二分臨界點記為 $ pa,pb $ 。

對于 \(i \le \min \{ pa , pb \}\) ，答案是 $ | sa_i - sb_i | $ ，可以ST表維護。

對于 \(i > \max\{ pa , pb \}\) ，答案是 $ | sa_{ i+k-1 } - sb_{ i+k-1 } | $ 同理。

若 $ pa < pb $ ，則中間的部分答案是 $ | sa_{ i+k-1 } - sb_i | $ ，同樣可以二分。反之亦然。

再推廣到一般的情況，類似于線段樹上區間查詢。復雜度 $ O( ( n+q ) \log ^2 n ) $ 。通過一些技巧可以做到 $ O( n \log ^2 n + q \log n ) $ 甚至 $ O( ( n+q ) \log n ) $ 。

day8

$ 100 + 70 + 35 + 10 $ ，卡常真是太壞了。

T1 魚人

直接在逆排列上考慮，如果存在一條人的邊跨度超過 2 ，就無法必勝。

T2 前期攻勢兇猛

不良心出題人，愛卡常。

一個事實是 $ (a,b) $ 能由 $ (x,y) $ 變換到，必然有 $ \gcd(x,y) = \gcd(a,b) $ 。

類似于歐幾里得算法流程，可以把一個向量拆為 $ O( \log V ) $ 個某一序列上的一段等差數列下標做加法。

值域很大，容易想到使用 map ，然后會被卡常。很不好。

T3 機械

感覺不太難。

對于 $ [ 1,n-1 ] $ 都需要恰好一個比它大的父親，對于 $ [ 2,n ] $ 都需要恰好一個比它小的父親。是一個類似于二分圖匹配的形式。

建 $ 2 n - 2 $ 個節點，原問題相當于給每條邊定向，使得每個節點都有出度。顯然每個基環樹都有 2 的貢獻，答案形如 $ 2^k $ 。

T4 則以后期見長

維護已有元素十分困難，考慮維護還不存在的元素。

對于一個元素 \(x\) 來說，在線段樹上存在這樣一類點：其祖先節點與包含 \(x\) 的區間有交但不包含，其所有后代節點都不含 \(x\) 。

這樣的節點數量是可控的。

給這樣的節點打一個 \(x\) 標記，可以用 set 維護，并處理當前區間的最大 $ mex $ 。

同時珂朵莉樹維護連續段，顏色段均攤后是 $ O( n \log ^ 2 n ) $ 。