CF 記錄

CF VP & 比賽記錄

Codeforces Round #751

陽間場有陽間題。

C. Array Elimination

給定一個長度為 \(n\) 的序列，定義一次操作為選 \(k\) 個數減去它們按位與的結果。

求所有合法的 \(k\)，使得最後序列全部為 \(0\)。

關鍵：按位與。

這說明對于每一位，如果減去了，那麼肯定是減去了 \(k\) 個該位的 \(1\)。

是以一個 \(k\) 合法當且僅當所有位 \(1\) 的個數均滿足 $\text {mod}\ k=0 $。

E. Optimal Insertion

給定兩個序列 \(a,b\)，把它們合并為一個新序列。

保證新序列中 \(a\) 中元素的相對位置不變，\(b\) 随意，求最小逆序對數。

關鍵：決策單調性。

即 \(b\) 按照從小到大順序排序後，插入的位置是單調不降的。

考慮反證法：

如果存在兩個位置滿足 \(i<j\) 并且 \(b_i>b_j\)，那麼交換 \(b_i,b_j\) 不會使答案更差。

F. Difficult Mountain