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

Grakn Forces 2020

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

A

由于題目保證 a i ≠ b i ≠ c i a_i ≠ b_i ≠ c_i ai??=bi??=ci? 所以直接逐位判斷選什么即可，時間復雜度 O ( n ) O(n) O(n)

code

B

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

code

C

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

code

D

我們考慮 dp， f i f_i fi? 表示向左移動 i i i 至少像上移動幾格，最后從后往前取一遍 max，那么 a n s = min ? i = 1 1 0 6 f i + i ans=\min\limits_{i=1}^{10^6} f_i+i ans=i=1min106?fi?+i，時間復雜度 O ( n × m ) O(n\times m) O(n×m)

code

E

我們考慮會形成環的情況即為兩個不同的數 x , y x,y x,y 分別同時出現在兩個不同的集合 S , T S,T S,T 種，我們考慮每個集合里的元素 x x x 向當前集合 S S S 連代價為 a S + b x a_S+b_x aS?+bx? 的邊，那么答案為 ( ∑ i = 1 n ∑ j = 1 m a i + b j ) ? (\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}a_i+b_j)- (i=1∑n?j=1∑m?ai?+bj?)?連邊后的最大生成樹的權值，因為要刪代價最小的邊唄，時間復雜度 O ( ( n + m ) log ? ( n + m ) ) O((n+m)\log (n+m)) O((n+m)log(n+m))

code

F

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

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

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

code