Skip to content

2026 S1

Codeforces Round 1075 (Div. 2)

C1. XOR Convenience (Easy Version)

卡在這題完全沒想法，雖然一眼就看出 \(p_i \oplus i = p_j\)，最後想到的方法是使用一個set不斷地從剩下最大的元素做 xor 直到 \(p_i \oplus i\) 的值出現在剩下的元素中。

看了解答發現這題主要的想法會是，由第 n - 1 個元素出發，可以知道 \(p_{n-1} \oplus (n - 1) = p_n\) 這是必定成立，因為後面只剩 \(p_n\)，所以一種貪心想法是，能不能構造出一種排列使得 \(i \oplus p_n = p_{i}\)，可以發現 \(p_n = 1\) 時在 i = 2k 時有 \(2k \oplus 1 = 2k + 1\)，在 \(i = 2k + 1\) 時 \(2k + 1 \oplus 1 = 2k\)。

因此可以將 i 利用奇偶性質將 i 分成 2k, 2k + 1。

當 n 為偶數時，可以做這樣的分配 ex. n = 10, \([p_1, 3, 2, 5, 4, 7, 6, 9, 8, 1]\)，此時 \(p_1 = 10\)

當 n 為奇數時，可以做這樣的分配 ex. n = 9, \([p_1, 3, 2, 5, 4, 7, 6, 9, 1]\)，此時 \(p_1 = 8\)

因此可以有這樣結論

\[ p_1 = \left\{ \begin{array}{ll} n \text{, n is even} \\ n \oplus 1 \text{, n is odd} \end{array} \right. \]
\[ \left\{ \begin{array}{ll} p_i = i \oplus 1 \text{, for } i \in [2, n - 1] \\ p_n = 1 \end{array} \right. \]

C2. XOR-convenience (Hard Version)

顯然的對於 2 的冪次方(\(2, 4, ... 2^x\))是無解的，因為 \(2^x \oplus y = 2^x + y \ge 2^x\)，因為值域為 \([1, 2^x]\) 所以這種情況是無解的。

考慮當 \(n \neq 2^x\) 的情況:

由 C1 可以知道當 n 為奇數時， \(p_1 = n - 1\)，此時 n - 1 為偶數，所以 \(p_1 \oplus 1 = (n - 1) \oplus 1 = n\)，所以當 n 為奇數時可以直接套用 C1 的方法。

當 n 為偶數時，\(p_1 = n\)，此時 \(p_1 \oplus 1\) 可能會產生大於 n 的數值，所以這樣無法構造出一個合法的解，因此把 \(n\) 分解成 \(n = 2^x + r\text{, } r < 2^x\)，我們可以把 \(p_1\) 跟 \(p_r\) 交換，可以得到對於 \(i = r\):

\[r \oplus p_1 = r \oplus n = r \oplus 2^x + r = 2^x\]

而從 \(r < 2^x\)，可以知道後面有一個 \(p_j = 2^x\)。

對於 \(i = 1\):

\[1 \oplus p_r = 1 \oplus (r \oplus 1) = r\]

而可以知道對於 \(p_{r + 1} = r + 1 \oplus 1\)，由這個方法可以構造出一個合法解。

以 n = 10 為例子, \([p_1, 3, 2, 5, 4, 7, 6, 9, 8, 1]\)，此時 \(p_1 = 10\)，而 \(p_1 \oplus 1 = 11\) 是一個不合法的排列，我們可以將 \(10\) 拆解成 \(8 + 2\) 可以將 \(p_1 = 10\) 跟 \(p_2 = 3\) 進行交換，得到 \([3, 10, 2, 5, 4, 7, 6, 9, 8, 1]\) 的排列，可以檢查 \(1 \oplus 3 = 2\)，\(2 \oplus 10 = 8\) 滿足題目要求。

Codeforces Round 1086 (Div. 2)

  • virtual practice

B - Cyclists

使用暴力模擬，但可以有更好的方式。

C - Stamina and Tasks

原本想說可以透過乘100將分數化為整數計算，但是這題是沒寫過的dp類型。

我們選擇 i 後，可以得到 \(S \cdot c_i\)，接著 \(S' = S (1 - \frac{p_i}{100})\)。 假設我們會以某種順序 \(j\) 選擇答案，最後 \(f_{j} = S \cdot c_j + S (1 - \frac{p_j}{100}) \cdot c_{j+1} + S (1 - \frac{p_j}{100})(1 - \frac{p_{j+1}}{100}i) \cdot c_{j+2} + ...\)，由 $ S=1 $ 可以得:

\[f = c_j + (1 - \frac{p_j}{100}) \cdot c_{j+1} + (1 - \frac{p_j}{100})(1 - \frac{p_{j+1}}{100}) \cdot c_{j+2} + ...\]

設 \(r_j = 1 - \frac{p_j}{100}\):

\[ \begin{array}{ll} f_j &= c_j + r_j \cdot c_{j+1} + r_jr_{j+1} \cdot c_{j+2} + ... \\ &= c_j + r_j (c_{j+1} + r_{j+1} \cdot c_{j+2} + ... ) \\ &= c_j + r_j f_{j+1} \end{array} \]

由上面可以知道選擇 \(j\) 的影響相當於將 \(f_{j + 1}\) 乘上 \(r_j\)。

因此對於 \(i\) 我們有兩種選擇:

  1. 不選 \(i \rightarrow f_{i + 1}\)

  2. 選 \(i \rightarrow r_jf_{i + 1} + c_i\)

\(f_i=max(f_{i+1},f_{i+1}(1−\frac{p_i}{100})+c_i)\)

Codeforces Round 1087 (Div. 2)

B. Array

這題一眼 Fenwick Tree，結果因為 idx 轉換卡了很久。

  • 把模板加上一個 mapping function

C. Find the Zero

因為前面卡太久，這題賽後才想出來，注意到一旦兩個 \(> 0\) 的元素排列在一起，也代表一定會有兩個 0 排列在一起，所以利用兩個兩個元素的詢問，這樣一定可以找到答案。

只有在 0X0X0X0.. 這種情況會導致詢問全部元素後仍然沒辦法確定答案，此時已經使用了 n 個詢問，無法在 n + 1 的限制下回答問題。

最後想到若是使用 n - 2 次比較，若是前面的回答都是不同的元素可以推理出前面可能會有 n - 1 或 n 個 \(> 0\) 的元素。

最後剩下的情況可能是

  1. XX 00
  2. X0 0X

可以利用兩次比較確定出 0 的位置

D. Ghostfires

題目的限制是 \(S_i \neq S_{i + 1}, S_i \neq S_{i + 3}\)，自己寫的時候一直想用相鄰不同的方向去思考。

這題可以容易的觀察出:

  1. 若是 \(R = G = B\) 可以 \(RGBGBRBRG\) 不斷循環直到 \(R = G = B = 0\)。

  2. 若是 \(R \ge G + B\) ，也就是有一個特別大的數，我們可以用他與其他兩個進行配對，\(RGRBRGRB....\)。

講解

由上面影片學到，一種經典的思考方式為想辦法讓其他狀態盡量轉移成為已知的狀態。

假設 \(R \ge G \ge B\)，因此會有幾種狀況:

  1. \(R > G = B\):

    可以使用兩個 R 分別配對各一個 G 和 B，使得 R 減少速度比 G 和 B 更快，直到 \(R = G = B\) 或是用完。

  2. \(R > G > B\):

先使用 R 和 G 直到 \(R > G = B\)，接著就跟 1. 一樣。