有些題還沒寫，不一定保證正確。

ARC148

ARC148C

考慮到求最值，有一個很顯然的 dp 做法：考慮結點 (i) 的子樹初始時被翻轉(zhuǎn)次數(shù)的奇偶性，然后再根據(jù)最終要全部和點集相同或不同分討弄 4 個 dp，轉(zhuǎn)移隨便胡一下，然后上虛樹就行。

上面那個太難寫了，這里有一個比正解更優(yōu)的做法。不妨令點集中的點為黑色，其余點為白色，則問題轉(zhuǎn)化成將整棵樹染成白色。考慮深度最小的黑色點，顯然只有操作根到該點路徑上的任意一點時才能將其染成白色，貪心地，操作該點最優(yōu)?？紤]循環(huán)模擬上述過程。

實際上我們發(fā)現(xiàn)取出深度最小的黑色結點時，可以默認該點的所有子結點均為白色。那么對于每個子結點，都需要再進行一次操作以將其變回白色。判掉父子結點均為黑色的情況即為最小操作數(shù)。時間復雜度 (O(n))

EDqwq銳評：撅來撅去，父子相撅

ARC147

ARC147C

發(fā)現(xiàn)這個式子當所有 (x_i) 趨近于某一個值時答案比較優(yōu)，于是可以發(fā)現(xiàn)這是一個近似單谷函數(shù)，用二分 + 隨機化/特判過掉就行。

令 (max_{i = 1}^n L_i = M)，(min_{i = 1}^n R_i = m)。

• (M leq m)

  顯然 (forall 1 leq i leq n, L_i leq M) 且 (R_i geq m)，于是令 (forall 1 leq i leq n, x_i = m)，答案為 (0)

• (M < m)

  因為 (L_i leq R_i)，所以 (M, m) 必然位于兩個不同的下標。假設 (M = L_p, m = R_q)，那么有結論：(forall 1 leq i leq n, x_p leq x_i leq x_q)

  證明：如果存在若干位置，使得 (x_i < x_p) 或 (x_i > x_q)，則因為有 (x_q leq m < M leq x_p)，且 (forall 1 leq i leq n, L_i leq M) 且 (R_i geq m)，只需要令 (x_i < x_q) 的位置為 (x_q)，(x_i > x_p) 的位置為 (x_p) 即可，與題設矛盾。

  于是令 (C = sumlimits_{i eq p, q}^n sumlimits_{j eq p, q}^n |x_i - x_j|)，則答案為：

  (C + |x_p - x_q| + sumlimits_{i eq l, r} |x_i - x_p| + sumlimits_{i eq l, r} |x_i - x_q|)

  發(fā)現(xiàn)這個式子可以遞歸定義，簡單手玩可以發(fā)現(xiàn)最后的答案為：

  (sumlimits_{i = 0}^{n - 1} |L_i - R_i| imes (n - 2i - 1))

  其中 (L_i) 按降序排列，(R_i) 按升序排列。

  時間復雜度 (O(n log n))

ARC147D

大詐騙，差評。

考慮 設而不求。令 (a_i) 表示 (S_i) 和 (S_{i + 1}) 的公共元素，則長度為 (n - 1) 的 (a) 序列一共有 (m^{n - 1}) 種。

我們發(fā)現(xiàn)當 (a) 確定且 (S_1) 確定時，(S_2, ..., S_n) 也隨之確定。(S_1) 共有 (2^m) 種。

考慮再設 (A_i) 表示當 (S_1) 包含 (i) 時 (S_1, ..., S_n) 中包含 (i) 的集合總數(shù)，同理 (B_i) 為不包含時?？紤]選與不選每個數(shù)，發(fā)現(xiàn)答案為 (prodlimits_{i = 1}^n (A_i + B_i))，而 (forall 1 leq i leq n, A_i + B_i = n)。所以原式為 (n^m)

所以最終答案為 (n^m cdot m^{n - 1})，復雜度 (O(log m + log n))

ARC147E

你會考慮到一些顯然的貪心策略，但這些顯然都是錯的。

題目的要求是最終 (forall 1 leq i leq n, B_i leq A_i)。這個條件和 (forall 1 leq i leq 10^9, sumlimits_{j = 1}^n [b_j leq i] - sumlimits_{j = 1}^n [a_j leq i] geq 0) 是等價的（(a_i, b_i leq 10^9)）。

可以從值域的角度去考慮。考慮到值域上第一個不滿足上面限制的位置 (k)，顯然地 (k - 1) 滿足條件，那么意味著 (a_i = k, b_i > k) 的數(shù)量比 (a_i = b_i = k) 的數(shù)量要大。為滿足條件，需要找到一個 (b_i leq k, a_i > k) 的位置交換，否則無法滿足條件。如果有多個滿足條件的數(shù)，顯然選 (a_i) 最大的最優(yōu)。

于是考慮用優(yōu)先隊列維護一下，復雜度 (O(n log n))

ARC145

ARC145C

容易證明當且僅當相鄰兩個數(shù)相乘時原式取得最大值，所以考慮這個序列經(jīng)過重排可以得到多少個序列。

首先顯然地可以同時任意交換 (A_i) 和 (B_i)，方法數(shù)為 (n!)

然后可以任意選擇一對 (A_i, B_i) 交換，方法數(shù)為 (2^n)

然后考慮將得到的 (A_i, B_i) 對應回排列 (P)。

對于一對相差 (1) 的正整數(shù) ((a, b))，稱 (a) 為左元素，(b) 為右元素，那么對于排列 (P) 的任意一個前綴，必定有左元素的總數(shù)大于等于右元素的總數(shù)。把左元素看成左括號，右元素看成右括號，那么合法的排列 (P) 等價于合法的括號序列。

長度為 (2n) 的合法括號序列的數(shù)量為卡特蘭數(shù)，即 (frac{1}{n + 1} cdot {2n choose n})

所以最終的答案為 (2^n cdot n! cdot frac{1}{n + 1} cdot {2n choose n} = 2^n cdot frac{(2n)!}{(n + 1)!})，時間復雜度 (O(n))

ARC145D

神仙三進制構造。

假設存在一些互不相同的正整數(shù)，其中每一個數(shù)的三進制表示均只包含 (0, 1)，那么由這些數(shù)構成的集合一定符合除和為 (M) 外的所有限制條件。

證明：(forall x < y < z, x, y, z in S)，有 (z - y eq y - x) 實際上等價于 (2y eq x + z)。此時因為每個數(shù)的三進制表示上都只有 (0, 1)，所以 (x + z) 不可能進位。所以若 (2y = x + z)，那么對于 (y) 的三進制表示上的某一位：
1. 該位為 (0)，(x, z) 的這一位均為 (0)
2. 該位為 (1)，因為 (y) 的三進制表示只包含 (0, 1)，所以 (2y) 的三進制表示只包含 (0, 2)，故矛盾
3. 該位為 (2)，(x, z) 的這一位均為 (1)
所以若 (2y = x + z)，則一定有 (x = y = z)。又因為集合的互異性，所以矛盾，故原命題成立。

為使構造出的集合值域在 (pm 10^7) 內(nèi)，貪心地考慮選取最小的 (n) 個滿足條件的正整數(shù)。令這 (n) 個正整數(shù)的和為 (S)，此時如果 (n mid m - S)，因為顯然給所有數(shù)同時增加一個值不影響答案，則只需要給所有數(shù)增加 (frac{m - S}{n}) 即可。因此考慮構造這樣的一種情況。

我們注意到 (m - S leq n - 1 pmod n)，因此我們可以考慮給整個序列乘以 (3)，然后選擇 (m - S mod n) 個數(shù)增加 (1) 即可消除余數(shù)。檢驗發(fā)現(xiàn)這樣做也在值域內(nèi)，所以直接寫。

ARC143

ARC143C

分別考慮在每一堆石子上單獨博弈的情況，顯然先手的輸贏是確定的。對于第一次操作，顯然先手的人把所有先手必贏的位置全部取一次最優(yōu)。此后先手的人只需要跟著后手的人操作同樣的石子堆，顯然此時先手必贏。

于是當存在先手必贏的石子堆時先手必贏，反之先手必輸（初始時無法操作）。每個石子堆可以 (O(1)) 判斷，復雜度 (O(n))

ARC143D

發(fā)現(xiàn)題目給的形式類似于拆點，可以考慮再拼回去。

具體地，從 (A_i) 向 (B_i) 連邊建一張圖。由于路徑唯一，因此拆點后原圖的橋一定對應若干條新圖中的橋。將這些橋去掉，問題轉(zhuǎn)化成給無向圖中的每一條邊定向，使得該圖中橋和割點的個數(shù)之和最小。這里可以通過 dfs 樹構造，樹邊按照遍歷方向定向，返祖邊從后代到祖先定向。

具體原理我也不是很懂，但是看上去很對

然后整理答案即可。

ARC143E

這種東西有一個已經(jīng)草爛的結論：當且僅當白色點個數(shù)為奇數(shù)時有解

考慮葉結點。發(fā)現(xiàn)白色的葉結點必然在其父結點之前刪除，黑色葉結點反之。于是可以確定這對父子結點之間操作的先后順序。將一個點上的“裝置”移除，實際上相當于刪除該結點。于是可以將這些葉子結點和其父結點刪除，又會產(chǎn)生新的葉結點。此時繼續(xù)重復上面的流程，得到若干組父子結點的先后順序。

問題轉(zhuǎn)化成構造一組滿足這些順序約束且字典序最小的操作序列。發(fā)現(xiàn)實際上就是建 DAG 然后跑一次拓撲排序。

ARC134

ARC134C

可以考慮把題目限制轉(zhuǎn)化為等價的形式：每次從同一個盒子中取出一對由 1 號球和其他球組成的球，經(jīng)過若干次操作后，每個盒子內(nèi)的球數(shù)量均不為 (0)，并且只有 1 號球。

于是可以考慮先給每個盒子都放入若干個 (1) 號球，然后把剩下的球按照上面的構造一對對放回去。對于 (i) 號球，顯然將其放入 (k) 個箱子的方案數(shù)為 (C_{a_i + k - 1}^{k - 1})。最后考慮將剩下的 (a_1 - sumlimits_{i = 2}^n a_i) 個 1 號球放入 (k - 1) 個盒子，方案數(shù)為 (C_{a_1 - sumlimits_{i = 2}^n a_i - 1}^{k - 1})

于是最終的答案為 (prod_{i = 2}^n C_{a_i + k - 1}^{k - 1} cdot C_{a_1 - sumlimits_{i = 2}^n a_i - 1}^{k - 1})

用盧卡斯做就行。

ARC134D

神秘貪心。

考慮到肯定是優(yōu)先把 (a_i) 最小的 (i) 選進來，此時分兩種情況：

1. 存在 (1 leq k leq n)，使得 (a_k = a_i) 并且 (a_k geq a_{k + n})，顯然此時選且只選 (k) 是最優(yōu)的。

2. 反之，可以考慮將所有 (a_k = a_i) 的 (k) 選出，使得較大的 (a_{k + n}) 被延后。由于序列可以分成 (a_{p_1}, a_{p_2}, ..., a_{p_n}) 和 (a_{p_1 + n}, ..., a_{p_n + n}) 兩部分，所以可以把 (a_k < a_{p_1 + n}) 的 (k) 也選進來。對于 (a_k = a_{p_1 + n}) 的情況，暴力判斷加入是否可以使字典序變小。如果可以顯然全選最優(yōu)。

于是做完了，是不是很簡單呢？

ARC141

ARC141C

考慮一個合法的字符串 S，設 (L_i) 為左數(shù)第 (i) 個左括號的下標，(R_i) 為右括號。你發(fā)現(xiàn)實際上 (P = L_1, R_1, ..., L_n, R_n, Q = L_n, R_n, ..., L_1, R_1)，根據(jù) (P, Q) 把 (S) 草出來。然后再重新根據(jù) (S) 把似乎是 (P, Q) 的東西草出來，看一看是不是和給的一樣就行。

ARC140

ARC140C

隨便手玩可以發(fā)現(xiàn)類似于這樣的構造 ((X, X - 1, X + 1, X - 2, X + 2, ...))

雖然這樣取不到理論上界，但是我們可以獲得一些啟發(fā)。

以 (N) 為奇數(shù)為例，(N) 為偶數(shù)的情況類似?？紤]將 ([1, 2N]) 中除去 (X) 的數(shù)分成大小各為 (lfloor frac{N}{2} floor) 的兩部分，分別記為 (L_1, L_2, ...) 和 (R_1, R_2, ...)。顯然 (X, L_1, R_1, L_2, R_2, ...) 這樣構造是最優(yōu)的，可以取滿上限 (N - 1)

但是這個難寫，不如賀賀賀賀賀。

ARC140D

對于 (N) 個點 (N) 條邊的無向圖，考慮它的每一個連通分量。

假設某一個極大連通分量的大小為 (k)，顯然有 (k - 1) 條邊使得該連通分量連通。剩下一條邊必然構成一個環(huán)，反之該連通分量會增加一個頂點。于是對于原圖的每一個連通分量，其包含且僅包含一個環(huán)。

我們發(fā)現(xiàn)：原圖中連通分量的個數(shù)等于環(huán)的個數(shù)。

然后考慮 (A_i = -1) 的結點對于連通分量個數(shù)的影響。分類討論：

1. 環(huán)。顯然它不包含 (A_i = -1) 的結點。

2. 基環(huán)樹，也不包含 (A_i = -1) 的結點。

3. 樹，此時有且僅有 (1) 個 (A_i = -1) 的結點在樹上。

對于第一種和第二種情況，它們無法連接兩個連通分量，考慮把它們先提出來，求出對答案的影響。假設這些連通分量的個數(shù)為 (x)，形態(tài)為樹的連通分量的個數(shù)為 (y)，那么這兩種情況的總貢獻為：(x cdot n^y)

在分析樹的情況前先記這些樹分別為樹 1，...，樹 (m)。第 (i) 棵樹的大小為 (t_i)

然后考慮 (A_i = -1) 的邊連接若干個連通分量后形成了新的連通分量。顯然它們構成的環(huán)可以被這樣表示：樹 (p_1) -> 樹 (p_2) -> ... -> 樹 (p_1)

對于該環(huán)中的邊，顯然它從上一棵樹中的唯一一個 (A_i = -1) 的結點連過來，可以連到當前樹上的任意一個結點。于是這條邊有 (t_i) 種選擇。那么對于 (k) 棵樹構成的環(huán)，它對答案的貢獻是：

((k - 1)! cdot prod_{i = 1}^k t_{p_i})

于是最終的答案為

(x cdot n^y + sumlimits_{k = 1}^m (k - 1)! cdot prod_{i = 1}^k t_{p_i})

其中 (p) 是由任意 (k) 棵樹的編號構成的序列。

上式可以暴力 (O(n^2)) 求出，也可以寫高明的分治 NTT

ARC140E

第 (i + 1) 行第 (j + 1) 列的數(shù)為 ((lfloor frac{i}{23} floor cdot lfloor frac{j}{23} floor + i + j) mod 23 + 1)

證明可以看官方題解。

你問我怎么想到的？這不是非常非常顯然嗎

ARC139

ARC139D

題解

ARC126

ARC126C

觀察樣例發(fā)現(xiàn)當 (K) 足夠大時使所有數(shù)相等最優(yōu)，反之由于 (gcd(a_1, ..., a_n) leq min(a_1, ..., a_n))，可以合理猜測 (gcd) 不超過 (3 imes 10^5)。顯然取到一個 (gcd) 的代價可以貪心計算（取到下一個 (K) 的倍數(shù)）。

不妨設 (cnt_i = sumlimits_{j = 1}^n [a_j leq i], pre_i = sumlimits_{j = 1}^n max(i - a_j, 0))。顯然地 (gcd = i) 時的代價為 (sumlimits_{k = 0}^{frac{max(a_j)}{i}} pre_{(k + 1)x} - pre_{kx} - cnt_{kx} cdot x)

并且有 (pre_{i + 1} = pre_i + cnt_i, cnt_{i + 1} = cnt_i + sumlimits_{j = 1}^n [a_j = i + 1])

于是可以 (O(n ln n)) 做。

ARC127D

首先答案可以表示成先把 ([1, K]) 的數(shù)聚在一起，然后再排序需要的操作次數(shù)。

假設我們選出了 (K) 個元素，那么有結論：將 (K) 個元素聚攏在中間的元素最優(yōu)。令 (m) 為這 (K) 個位置的中位數(shù)?？紤]從前往后加入，那么當加入第 (m) 個數(shù)時，(m) 恰好是要求子段的中間位置。

觀察到 (K leq 16)，于是考慮狀壓 dp。令 (F_S) 為已經(jīng)聚攏的數(shù)集等于 (S) 時需要的最小代價。枚舉最后一次加入的數(shù) (a_i)，發(fā)現(xiàn)很難得到轉(zhuǎn)移。

不妨將最終的貢獻寫出來。令初始選擇的 (K) 個元素的下標為 (p_1, ..., p_K)，最終得到的子段的下標為 (q_1, ..., q_K)。顯然地，(forall 1 leq i < m)，對答案的貢獻之和為 (sumlimits_{i = 1}^{m - 1} |p_i - q_i| = sumlimits_{i = 1}^{m - 1} q_m + i - p_i)。同理 (forall m < i < K)，對答案的貢獻之和為 (sumlimits_{i = m + 1}^K p_i - (q_m + i))。

我們發(fā)現(xiàn)當 (K) 是偶數(shù)時 ((q_m + i)) 可以抵消，而 (K) 是奇數(shù)時會在 (m + 1) 處剩下一項。于是我們考慮在轉(zhuǎn)移時只考慮 (p_i) 的影響，然后在加入第 (m) 個數(shù)時判斷是否需要這一項即可。