某島

… : "…アッカリ~ン . .. . " .. .
March 8, 2020

Codeforces Round #626 (WIP)

https://codeforces.com/contest/1322

A. Unusual Competitions

顯然可以貪心。最後結果一定是一些區間的並,我們讓這些區間儘可能小。
方法是從左到右掃描括弧序列,每遇到一個不合法的 ‘)’,我們向右邊找第一個 ‘(‘ 與它替換即可。

B. Present

C. Instant Noodles

給定一個二分圖 {X, Y},每個右邊的節點 y 有一個權值。
對於任意一個 X 的子集,定義它的的權值為所有相鄰的 Y 中節點的權值的和。
問所有這些子集的權值的 gcd 是多少。

直接掃一遍取 gcd 肯定不對,因為一些點總是一起出現。
因而我們對每個相鄰節點所組成的集合相同的 y 進行合併,再用合併過的結果掃一遍取 gcd 對不對呢?

證明:【略】。
注意這個題有卡常數的嫌疑。。。