$\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{k}\mathrm{n}\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{c}\mathrm{e}\mathrm{s}2020\mathrm{A}-\mathrm{F}$ 簡要題解

Grakn Forces 2020

注：若題目為多組資料 $n$ 表示 $\sum n$

A

由於題目保證 $a_i\ne b_i\ne c_i$ 所以直接逐位判斷選什麼即可，時間複雜度 $O(n)$

code

B

貪心地加數，直至這個序列不能加數增加一個序列，模擬一遍即可，時間複雜度 $O(n)$

code

C

我們考慮二分時間 $t$，然後分別模擬左端點與右端點在 $t$ 秒後的位置如果 $r\le l$ 則表示這個 $t$ 是合法的。時間複雜度 $O(n\log n)$

code

D

我們考慮 dp。$f_i$ 表示向左移動 $i$ 至少像上移動幾格。最後從後往前取一遍 max。那麼 $ans=\underset{i=1}{\overset{10^6}{\min }}{f}_i+i$。時間複雜度 $O(n\times m)$

code

E

我們考慮會形成環的情況即為兩個不同的數 $x,y$ 分別同時出現在兩個不同的集合 $S,T$ 種。我們考慮每個集合裡的元素 $x$ 向當前集合 $S$ 連代價為 $a_S+b_x$ 的邊。那麼答案為 $(\sum _{i=1}^n\sum _{j=1}^m{a}_i+b_j)-$連邊後的最大生成樹的權值。因為要刪代價最小的邊唄。時間複雜度 $O((n+m)\log (n+m))$

code

F

構造題。先把相鄰的兩個數邊相等，再相鄰四個，以此類推。

比如 $n=5:$ 12345 $\sim$ 66345 $\sim$ 66775 $\sim$ 86875 $\sim$ 88885

我們只要分治模擬一下即可，時間複雜度 $O(n\log n)$

code