散文網(wǎng) » 科技 »學(xué)習(xí) » [AtCoder is All You Need]ABC 279 DEF - Solution

[AtCoder is All You Need]ABC 279 DEF - Solution

2022-11-26 23:52 作者:故寓諸無竟 0人讀過 | 我要投稿

題目簡述

????????Problem D：給定函數(shù) $%5Cfrac%7BA%7D%7B%5Csqrt%7B1%2Bx%7D%7D%20%2B%20B%5Ccdot%20x%20%5Cquad%20(x%20%5Cin%20N)$ （其中A，B為已知常量），求最小值。

????????Problem E：太難簡述了。

????????Problem F：太難簡述了。

????????原題目地址：https://atcoder.jp/contests/abc279/tasks

思路

? ? ? ? Problem D：其實(shí)我已經(jīng)翻譯得差不多了。可以直接求導(dǎo)得到唯一極值點(diǎn)，由于是整數(shù)，所以考慮其附近的整點(diǎn)處的函數(shù)值即可。時間復(fù)雜度為 $O(1)$ 。注意到函數(shù)實(shí)際上是一個凸函數(shù)，那么為了避免數(shù)值誤差，可以使用三分法，時間復(fù)雜度為 $O(%5Clog%20%5Cfrac%7BB%7D%7BA%7D)$ 。

????????Problem E：對于每一個 $i$ 的查詢，事實(shí)上差別并不大（并且只用考慮元素 $1$ 所處的位置），考慮遞推地計(jì)算。由于不會進(jìn)行 $B_%7BA_i%7D%2CB_%7BA_%7Bi%2B1%7D%7D$ 的交換操作，因此自然地，考慮將所有進(jìn)行的操作分兩大段處理： $i$ 之前的操作和 $i$ 之后的操作。假設(shè)我們從左到右的遞推。

????????對于 $i$ 之前的操作，從左到右遞推是正常操作的順序，按正常進(jìn)行即可，相當(dāng)于維護(hù)一個 $c_i$ 變量，表示當(dāng)前進(jìn)行了 $i$ 之前的操作后，元素 $1$ 所處的位置。更新方法為： $c_1$ 初值為 $1$ ；當(dāng) $A_%7Bi%7D%20%3D%20c_%7Bi-1%7D$ ，則更新 $c_i%3A%3Dc_%7Bi-1%7D%2B1$ ；當(dāng) $A_%7Bi%7D%2B1%20%3D%20c_%7Bi-1%7D$ ，則更新 $c_i%3A%3Dc_%7Bi-1%7D-1$ 。這一點(diǎn)直接由交換操作的定義可以得出。

????????對于 $i$ 之后的操作，似乎處理起來比較困難。但由于交換位置操作的可逆性，我們可以遞推計(jì)算。維護(hù) $p_i$ 數(shù)組，表示“ $i$ 之后的操作全部進(jìn)行后，某元素值所處的位置”（注意，這是一個向量，因?yàn)橐４?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=1%5Csim%20n" alt="1%5Csim%20n">所有元素的位置）。假設(shè)我們得到了 $p_%7Bi-1%7D$ ，如何計(jì)算 $p_i$ 呢？注意到二者唯一的差距就在于操作 $i$ 是否進(jìn)行；根據(jù) $p_%7Bi-1%7D$ 的意義，我們可以發(fā)現(xiàn)， $A_i%2CA_%7Bi%2B1%7D$ 交換的兩個元素，在最后的實(shí)際位置其實(shí)是 $p_%7Bi-1%7D(A_%7Bi%7D)%2Cp_%7Bi-1%7D(A_%7Bi%2B1%7D)$ （因?yàn)槭菑?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=%5C%7B1%2C...%2Cn%5C%7D" alt="%5C%7B1%2C...%2Cn%5C%7D">開始的，所以有這個結(jié)論），因此在 $p_i$ 中只需要交換 $p_%7Bi-1%7D(A_%7Bi%7D)%2Cp_%7Bi-1%7D(A_%7Bi%2B1%7D)$ 的位置即可。

????????接下來是計(jì)算答案。在進(jìn)行完 $i$ 之前的操作后，問題可以等價地轉(zhuǎn)化為初始序列為 $%5C%7B1%2C...%2Cn%5C%7D$ ，經(jīng)過 $i$ 之后的操作后，元素 $c_i$ 所處的位置。由此可以從左到右地維護(hù)并順勢計(jì)算答案?？偟臅r間復(fù)雜度為 $O(n)$ 。

????????Problem F：如果熟悉，一下子就能發(fā)現(xiàn)這是一個經(jīng)典的并查集結(jié)構(gòu)：小球之間只需要明確是否歸屬同一集合。由此我們維護(hù)一個關(guān)于小球標(biāo)號的并查集，初始時，每個小球都以自己為根。問題在于如何在這樣的并查集中維護(hù)小球所屬的盒子編號；以及，為了方便修改，如何維護(hù)某盒子對應(yīng)著哪一個集合。

????????令 $b$ 數(shù)組表示小球所屬的盒子編號， $rt$ 數(shù)組表示盒子對應(yīng)的集合的并查集根。如果一個盒子 $i$ 是空的，不妨設(shè) $rt_i%20%3D%20-1$ 。下面分別敘述三個操作：

操作3：答案就是 $b_%7Bfind(x)%7D$ 。
操作2：把 $k%2B1$ 對應(yīng)的集合作為新的根，并更新 $b_%7Bk%2B1%7D%20%3A%3D%20x%2Crt_%7Bx%7D%3Dk%2B1$ ；注意，這里其實(shí)有兩種情況，如果 $rt_x%3D-1$ ，意味著 $x$ 盒子是空的，不需要額外操作。如果 $rt_x%20%5Cne%20-1$ ，就意味著 $x$ 盒子不空，需要設(shè)置一下并查集的 $pa$ 數(shù)組。
操作1：如果 $rt_y%3D-1$ ，則相當(dāng)于什么也沒干；如果 $rt_x%3D-1$ ，則需要將 $rt_y$ 所在集合的盒子進(jìn)行更新： $b_%7Brt_y%7D%20%3A%3D%20x%20$ ，然后重置根： $rt_x%20%3A%3D%20rt_y%2Crt_y%20%3A%3D%20-1$ ；如果二者均非空，則需要置 $pa(rt_y)%20%3A%3D%20rt_x%2Crt_y%3A%3D-1$ 。