有些題還沒(méi)寫(xiě)，不一定保證正確。

ARC148

ARC148C

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

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

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

EDqwq銳評(píng)：撅來(lái)撅去，父子相撅

ARC147

ARC147C

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

令 (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)

  因?yàn)?(L_i leq R_i)，所以 (M, m) 必然位于兩個(gè)不同的下標(biāo)。假設(shè) (M = L_p, m = R_q)，那么有結(jié)論：(forall 1 leq i leq n, x_p leq x_i leq x_q)

  證明：如果存在若干位置，使得 (x_i < x_p) 或 (x_i > x_q)，則因?yàn)橛?(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) 即可，與題設(shè)矛盾。

  于是令 (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)這個(gè)式子可以遞歸定義，簡(jiǎn)單手玩可以發(fā)現(xiàn)最后的答案為：

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

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

  時(shí)間復(fù)雜度 (O(n log n))

ARC147D

大詐騙，差評(píng)。

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

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

考慮再設(shè) (A_i) 表示當(dāng) (S_1) 包含 (i) 時(shí) (S_1, ..., S_n) 中包含 (i) 的集合總數(shù)，同理 (B_i) 為不包含時(shí)?？紤]選與不選每個(gè)數(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})，復(fù)雜度 (O(log m + log n))

ARC147E

你會(huì)考慮到一些顯然的貪心策略，但這些顯然都是錯(cuò)的。

題目的要求是最終 (forall 1 leq i leq n, B_i leq A_i)。這個(gè)條件和 (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) 是等價(jià)的（(a_i, b_i leq 10^9)）。

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

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

ARC145

ARC145C

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

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

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

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

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

長(zhǎng)度為 (2n) 的合法括號(hào)序列的數(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)!})，時(shí)間復(fù)雜度 (O(n))

ARC145D

神仙三進(jìn)制構(gòu)造。

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

證明：(forall x < y < z, x, y, z in S)，有 (z - y eq y - x) 實(shí)際上等價(jià)于 (2y eq x + z)。此時(shí)因?yàn)槊總€(gè)數(shù)的三進(jìn)制表示上都只有 (0, 1)，所以 (x + z) 不可能進(jìn)位。所以若 (2y = x + z)，那么對(duì)于 (y) 的三進(jìn)制表示上的某一位：
1. 該位為 (0)，(x, z) 的這一位均為 (0)
2. 該位為 (1)，因?yàn)?(y) 的三進(jìn)制表示只包含 (0, 1)，所以 (2y) 的三進(jìn)制表示只包含 (0, 2)，故矛盾
3. 該位為 (2)，(x, z) 的這一位均為 (1)
所以若 (2y = x + z)，則一定有 (x = y = z)。又因?yàn)榧系幕ギ愋?，所以矛盾，故原命題成立。

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

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

ARC143

ARC143C

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

于是當(dāng)存在先手必贏的石子堆時(shí)先手必贏，反之先手必輸（初始時(shí)無(wú)法操作）。每個(gè)石子堆可以 (O(1)) 判斷，復(fù)雜度 (O(n))

ARC143D

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

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

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

然后整理答案即可。

ARC143E

這種東西有一個(gè)已經(jīng)草爛的結(jié)論：當(dāng)且僅當(dāng)白色點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)有解

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

問(wèn)題轉(zhuǎn)化成構(gòu)造一組滿(mǎn)足這些順序約束且字典序最小的操作序列。發(fā)現(xiàn)實(shí)際上就是建 DAG 然后跑一次拓?fù)渑判颉?/p>

ARC134

ARC134C

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

于是可以考慮先給每個(gè)盒子都放入若干個(gè) (1) 號(hào)球，然后把剩下的球按照上面的構(gòu)造一對(duì)對(duì)放回去。對(duì)于 (i) 號(hào)球，顯然將其放入 (k) 個(gè)箱子的方案數(shù)為 (C_{a_i + k - 1}^{k - 1})。最后考慮將剩下的 (a_1 - sumlimits_{i = 2}^n a_i) 個(gè) 1 號(hào)球放入 (k - 1) 個(gè)盒子，方案數(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) 選進(jìn)來(lái)，此時(shí)分兩種情況：

1. 存在 (1 leq k leq n)，使得 (a_k = a_i) 并且 (a_k geq a_{k + n})，顯然此時(shí)選且只選 (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) 也選進(jìn)來(lái)。對(duì)于 (a_k = a_{p_1 + n}) 的情況，暴力判斷加入是否可以使字典序變小。如果可以顯然全選最優(yōu)。

于是做完了，是不是很簡(jiǎn)單呢？

ARC141

ARC141C

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

ARC140

ARC140C

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

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

以 (N) 為奇數(shù)為例，(N) 為偶數(shù)的情況類(lèi)似?？紤]將 ([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, ...) 這樣構(gòu)造是最優(yōu)的，可以取滿(mǎn)上限 (N - 1)

但是這個(gè)難寫(xiě)，不如賀賀賀賀賀。

ARC140D

對(duì)于 (N) 個(gè)點(diǎn) (N) 條邊的無(wú)向圖，考慮它的每一個(gè)連通分量。

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

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

然后考慮 (A_i = -1) 的結(jié)點(diǎn)對(duì)于連通分量個(gè)數(shù)的影響。分類(lèi)討論：

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

2. 基環(huán)樹(shù)，也不包含 (A_i = -1) 的結(jié)點(diǎn)。

3. 樹(shù)，此時(shí)有且僅有 (1) 個(gè) (A_i = -1) 的結(jié)點(diǎn)在樹(shù)上。

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

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

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

對(duì)于該環(huán)中的邊，顯然它從上一棵樹(shù)中的唯一一個(gè) (A_i = -1) 的結(jié)點(diǎn)連過(guò)來(lái)，可以連到當(dāng)前樹(shù)上的任意一個(gè)結(jié)點(diǎn)。于是這條邊有 (t_i) 種選擇。那么對(duì)于 (k) 棵樹(shù)構(gòu)成的環(huán)，它對(duì)答案的貢獻(xià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) 棵樹(shù)的編號(hào)構(gòu)成的序列。

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

ARC140E

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

證明可以看官方題解。

你問(wèn)我怎么想到的？這不是非常非常顯然嗎

ARC139

ARC139D

題解

ARC126

ARC126C

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

不妨設(shè) (cnt_i = sumlimits_{j = 1}^n [a_j leq i], pre_i = sumlimits_{j = 1}^n max(i - a_j, 0))。顯然地 (gcd = i) 時(shí)的代價(jià)為 (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ù)。

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

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

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

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