當前位置:首頁 > IT技術(shù) > 其他 > 正文

AtCoder做題記錄
2022-09-06 22:55:10

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

ARC148

ARC148C

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

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

實際上我們發(fā)現(xiàn)取出深度最小的黑色結(jié)點時,可以默認該點的所有子結(jié)點均為白色。那么對于每個子結(jié)點,都需要再進行一次操作以將其變回白色。判掉父子結(jié)點均為黑色的情況即為最小操作數(shù)。時間復(fù)雜度 (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) 必然位于兩個不同的下標。假設(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),則因為有 (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)這個式子可以遞歸定義,簡單手玩可以發(fā)現(xiàn)最后的答案為:

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

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

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

ARC147D

大詐騙,差評。

考慮 設(shè)而不求。令 (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) 種。

考慮再設(shè) (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}),復(fù)雜度 (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)先隊列維護一下,復(fù)雜度 (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) 對應(yīng)回排列 (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)!}),時間復(fù)雜度 (O(n))

ARC145D

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

假設(shè)存在一些互不相同的正整數(shù),其中每一個數(shù)的三進制表示均只包含 (0, 1),那么由這些數(shù)構(gòu)成的集合一定符合除和為 (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)。又因為集合的互異性,所以矛盾,故原命題成立。

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

我們注意到 (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)) 判斷,復(fù)雜度 (O(n))

ARC143D

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

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

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

然后整理答案即可。

ARC143E

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

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

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

ARC134

ARC134C

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

于是可以考慮先給每個盒子都放入若干個 (1) 號球,然后把剩下的球按照上面的構(gòu)造一對對放回去。對于 (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,設(shè) (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)類似于這樣的構(gòu)造 ((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, ...) 這樣構(gòu)造是最優(yōu)的,可以取滿上限 (N - 1)

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

ARC140D

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

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

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

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

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

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

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

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

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

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

對于該環(huán)中的邊,顯然它從上一棵樹中的唯一一個 (A_i = -1) 的結(jié)點連過來,可以連到當前樹上的任意一個結(jié)點。于是這條邊有 (t_i) 種選擇。那么對于 (k) 棵樹構(gòu)成的環(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) 棵樹的編號構(gòu)成的序列。

上式可以暴力 (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ù))。

不妨設(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ù)。

假設(shè)我們選出了 (K) 個元素,那么有結(jié)論:將 (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ù)時判斷是否需要這一項即可。

本文摘自 :https://www.cnblogs.com/

開通會員,享受整站包年服務(wù)立即開通 >