傳送門

T4. 搬磚

給定 \(n\) 個非負整數 \(a_i\)，每次可以花費 \(1\) 的代價使得一個數字加 \(1\) 或者減 \(1\)（不能被減到負數），問最少需要多少代價使得所有數字的異或值為 \(0\) 。

要求多測

限制：

  • 對于 \(5\%\) 的數據：\(n=2, a_i \leqslant 10^9\)
  • 對于另外 \(10\%\) 的數據：\(n \leqslant 5\)，\(a_i \leqslant 30\)
  • 對于另外 \(15\%\) 的數據：\(n \leqslant 15\)，\(a_i \leqslant 10^3\)
  • 對于另外 \(20\%\) 的數據：\(n \leqslant 8\)，\(a_i \leqslant 10^9\)
  • 對于另外 \(15\%\) 的數據：\(n \leqslant 10\)，\(a_i \leqslant 10^9\)
  • 對于所有數據：\(1 \leqslant T \leqslant 6, 1 \leqslant n \leqslant 15, 0 \leqslant a_i \leqslant 10^9\)

參考難度：藍

算法分析

下文中，假定 \(m = \max(a_i)\)

\(5\) 分：

此時 \(n = 2\)，問題變為了使得兩數相等的最小代價，輸出兩數的差值即可。

\(15\) 分（另外 \(10\%\) 的數據）：

此時 \(n \leqslant 5\)，\(a_i \leqslant 30\)，考慮直接 \(dfs\) 暴力枚舉每個 \(a_i\) 的最終取值 \(a_i'\)，那么對于每一種情況所需要付出的代價就是 \(|a_i - a_i'|\) 之和，即 \(\sum |a_i - a_i'|\) 。取所有情況中的最小代價即可，時間復雜度為 \(O(m^n)\) 。

\(30\) 分（另外 \(15\%\) 的數據）：

此時 \(n \leqslant 15\)，\(a_i \leqslant 10^3\)，原問題是“使得 \(n\) 個數字的異或值為 \(0\)”，那么當我們枚舉了 \(a_n\) 的最終取值 \(a_n'\) 之后，問題變為了“使得前 \(n-1\) 個數字的異或值為 \(a_n'\)”。不難發現這是一個子問題，因此可以考慮動態規劃。

定義 dp[i][j] 表示使得前 \(i\) 個數字的異或值為 \(j\) 的最小代價，枚舉 \(im, j\) 后，再枚舉 \(k\) 表示當前第 \(i\) 個數字的最終取值，那么可以得到轉移方程：

\[dp[i][j] = \min(dp[i][j], dp[i-1][j \oplus k] + |a_i-k|) \]

最終的答案為 \(dp[n][0]\)，總時間復雜度為 \(O(nm^2)\) 。

\(65\) 分（另外 \(35\%\) 的數據）：

此時 \(a_i \leqslant 10^9\)，依賴于枚舉值域的做法顯然不行。由于 \(n \leqslant 10\) 很小，且每個數字相比最終的結果只有不變、變小和變大這 \(3\) 種可能性。那么所有數字的變化情況組合在一起一共只有 \(3^n = 59049\) 種可能性，因此可以考慮狀態壓縮，將每個數字的變化情況壓縮成一個三進制的數字 \(S\) 。

具體地，令 \(0, 1, 2\) 分別表示不變、變小、變大。那么 \(S = (211002)_3\) 表示第 \(2,3\) 個數字不變，第 \(4,5\) 個數字變小，第 \(1,6\) 個數字變大。

再注意到進行按位異或時，每一位之間是相互不影響的，結合上述的“用狀態壓縮去表示變化情況”的想法，我們可以從高位到低位去確定每一位最終的異或值為 \(0\) 的最小代價即可。

至于為什么是從高到低而非從低到高？這是因為所有低位的二次冪之和必然都小于高位的某一位的值，我們確定好高位相比于之前是變大還是變小之后，無論之后的低位取 \(0\) 還是 \(1\)，都不會改變原本已經確定好的變大或者變小的狀態。這樣一來，我們只需要知道當前的 \(S\) 是多少，就可以知道每個數字的每一位取 \(0\) 或者 \(1\) 時所需要付出的代價。

至此，可以考慮狀壓dp，去按位計算最終的最小代價。定義 dp[i][j][S][0/1] 表示當前考慮到了第 \(i\) 位，確定了這一位的前 \(j\) 個數字，所有數字的變化狀態為 \(S\)，這一位的異或和為 \(0/1\) 對應的最小代價。枚舉 \(i, j, S\)，并考慮 \(a_j\) 的第 \(i\) 位取 \(0/1\)，設 \(T\) 為原本的數字變化狀態，設 \(v\) 為原本 \(a_j\) 的第 \(i\) 位的值。可以分為以下三類進行轉移：

  1. 原本的 \(a_j\) 不變：
  • 這一位取 \(0\)，若 \(v=0\)則 \(a_j\) 不變，若 \(v=1\) 則 \(a_j\) 變小：

\[dp[i][j][S][k] = \min(dp[i][j][S][k], dp[i][j-1][T][k] + (\text{若}v\text{為}1) \times 2^i) \]

  • 這一位取 \(1\)，若 \(v=0\) 則 \(a_j\) 變大，若 \(v=1\) 則 \(a_j\) 不變

\[dp[i][j][S][k] = \min(dp[i][j][S][k], dp[i][j-1][T][k \oplus 1] + (\text{若}v\text{為}0) \times 2^i) \]

  1. 原本的 \(a_j\) 已經變小過了：
  • 這一位取 \(0\)，若 \(v=0\) 則代價不變，若 \(v=1\) 則代價增加：

\[dp[i][j][S][k] = \min(dp[i][j][S][k], dp[i][j-1][T][k] + (\text{若}v\text{為}1) \times 2^i) \]

  • 這一位取 \(1\)，若 \(v=1\) 則代價不變，若 \(v=0\) 則代價減少：

\[dp[i][j][S][k] = \min(dp[i][j][S][k], dp[i][j-1][T][k \oplus 1] - (\text{若}v\text{為}0) \times 2^i) \]

  1. 原本的 \(a_j\) 已經變大過了：
  • 這一位取 \(0\)，若 \(v=0\) 則代價不變，若 \(v=1\) 則代價減少：

\[dp[i][j][S][k] = \min(dp[i][j][S][k], dp[i][j-1][T][k] - (\text{若}v\text{為}1) \times 2^i) \]

  • 這一位取 \(1\)，若 \(v=1\) 則代價不變，若 \(v=0\) 則代價增加：

\[dp[i][j][S][k] = \min(dp[i][j][S][k], dp[i][j-1][T][k \oplus 1] + (\text{若}v\text{為}0) \times 2^i) \]

值得注意的是，上述的所有轉移方程中，當 \(j=1\) 時，應當從 \(i-1\) 且 \(j=n\) 轉移過來。
答案為：枚舉 \(S\) 后取最小的 \(dp[i][n][S][0]\) 。
總時間復雜度為 \(T(Tn3^n\log m)\) 。

\(100\) 分：

不難發現 \(O(3^n)\) 的復雜度在于我們需要記錄每個數字是變大還是變小，從而來判斷每一位從 \(0 \to 1\) 或者 \(1 \to 0\) 時，到底是增加代價還是減少代價。若要降低這部分的復雜度，難點在于如何構造出一種方法來將數字變小和變大情況的代價計算進行合并，下文中用每一位的 \(x\) 代表 \(0/1\) 中的任意一個值。

先考慮數字變小的情況，假設當前某個數字 \(a_j\) 從第 \(i\) 位到第 \(0\) 位的值形如 \((1xxxxx)_2\)，那么如果我們希望將它第 \(i\) 位的 \(1\) 改為 \(0\) 從而使得第 \(i\) 位整體的異或值為 \(0\)，有兩種變化方式：

  • \((1xxxxx)_2 \to (0xxxxx)_2\)，那么根據 \(65\) 分的做法，我們能夠知道之后的每一位需要根據是 \(1 \to 0\) 還是 \(0 \to 1\) 來決定增加還是減少代價。
  • \((0xxxxx)_2 \to (100000)_2 \to (1xxxxx)_2\)，第 \(i\) 位變小后，會先經過后面位全是 \(0\) 的狀態，此時如果我們希望繼續變成 \((1xxxxx)_2\) 的任意狀態，那么需要在之后遍歷后面位的過程中將若干個 \(1 \to 0\) 即可，這樣一來代價只會是增加的。

再考慮 \(a_j\) 的值變大的情況，設第 \(i\) 位到第 \(0\) 位的值形如 \((0xxxxx)_2\)，那么將第 \(i\) 位的 \(0\) 變為 \(1\) 同樣有兩種變化方式：

  • \((0xxxxx)_2 \to (1xxxxx)_2\)，之后的每一位需要根據是 \(0 \to 1\) 還是 \(1 \to 0\) 來決定增加還是減少代價。
  • \((0xxxxx)_2 \to (100000)_2 \to (1xxxxx)_2\)，第 \(i\) 位變大后，會先經過后面全是 \(0\) 的狀態，此時如果我們希望繼續變成 \((1xxxxx)_2\) 的任意狀態，那么只需要在之后遍歷后面位的過程中將若干個 \(0 \to 1\) 即可，這樣一來代價也只會是增加。

如此一來，通過 \((1xxxxx)_2 \to (011111)_2\) 以及 \((0xxxxxx)_2 \to (100000)_2\) 的變換，我們能夠讓數字 \(a_j\) 在之后的每一位需要變化的時候，都需要考慮增加代價，而不需要考慮減少代價；這樣做等價于將變小和變大兩種情況的代價計算方式，都合并為“增加代價”這一種情況了。于是可以將原本的三進制狀態 \(S\) 改為二進制狀態，用來記錄每個數字是否發生變化，而無需記錄具體時變小還是變大。

值得注意的是，當一個數字在第 \(i\) 位發生 \((1xxxxx)_2 \to (011111)_2\) 時，相當于給后面第 \([i-1, 0]\) 的每一位的整體異或值進行了 \(\oplus 1\)；又因為異或偶數次 \(1\) 并不會改變整體的異或值，因此我們需要再給原本的 \(dp\) 數組多定義一個狀態 \([0/1]\) 用來表示當前所有發生變化的數字，給后面每一位提前貢獻了多少的異或值（\(0\) 或 \(1\)）。

至此，定義 dp[i][j][S][0/1][0/1] 表示當前考慮到了第 \(i\) 位，確定了這一位的前 \(j\) 個數字，所有數字的變化狀態為 \(S\)，這一位的異或和為 \(0/1\)，已經變化的數字貢獻的每位異或值為 \(0/1\)，對應的最小代價。設 \(T\) 為原本的數字變化狀態，設 \(v\) 為原本 \(a_j\) 第 \(i\) 位的值，則轉移如下：

  • 考慮 \(a_j\) 原本沒有變化，在當前第 \(i\) 位仍然不發生變化，那么代價為 \(0\) 。

\[dp[i][j][S][k][l] = \min(dp[i][j][S][k][l], dp[i][j-1][T][k \oplus v][l]) \]

  • 考慮 \(a_j\) 原本沒有變化，在當前第 \(i\) 位發生變化。若 \(v=0\)，則代價 \(cost = 2^i - (a_j \& (2^i - 1))\)；若 \(v = 1\)，則代價 \(cost = 1 + (a_j \& (2^i-1))\)

\[dp[i][j][S][k][l] = \min(dp[i][j][S][k][l], dp[i][j-1][T][k \oplus v \oplus 1][l \oplus v] + cost) \]

  • 考慮 \(a_j\) 發生過變化，且不改變當前第 \(i\) 位的值，那么代價為 \(0\) 。注意此時 \(a_j\) 這一位的值已經在之前變化高位的時候算入了 \(l\) 的值里面，不需要再對 \(k\) 進行異或 \(v\) 。

\[dp[i][j][S][k][l] = \min(dp[i][j][S][k][l], dp[i][j-1][T][k][l]) \]

  • 考慮 \(a_j\) 發生過變化，且改變當前第 \(i\) 位的值，那么代價為 \(2^i\) 。注意此時改變了 \(a_j\) 這一位的值，需要對 \(k\) 進行異或 \(1\) 。

\[dp[i][j][S][k][l] = \min(dp[i][j][S][k][l], dp[i][j-1][T][k \oplus v][l] + 2^i) \]

轉移的其他細節見 \(65\) 分做法，這里再補充：當第 \(i\) 位都處理好之后，在處理第 \(i-1\) 位之前，需要令 \(dp[i][n][S][1][1] = dp[i][n][S][0][1]\)，然后將 \(dp[i][n][S][1][0]\) 和 \(dp[i][n][S][0][1]\) 變為 \(\infty\) 。這表示處理到第 \(i\) 位為止，如果已經發生改變的數字給后面位的異或值產生了 \(1\) 的貢獻，那么在處理后面位的時候，異或值的初始值應當是 \(1\)；反之，初始值為 \(0\) 。

答案為：枚舉 \(S\) 后取最小的 \(\min(dp[0][n][S][0][0], dp[0][n][S][1][1])\) 。

總時間復雜度為 \(O(n2^n\log m)\) 。