Problem A. CF704B Ant Man

題意：

有 \(n\) 個元素，第 \(i\) 個元素有五個參數 \(x_i,a_i,b_i,c_i,d_i\)。

你需要求出一個 \(1 \sim n\) 的排列 \(p\)，滿足 \(p_1 = s, p_n = e\)，同時最小化這個排列的權值。

一個排列的權值為 \(\sum_{i=1}^{n-1} f(p_i, p_{i+1})\)，其中 \(f(i,j)\) 定義為：

• 若 \(i > j\)，則 \(f(i,j) = x_i - x_j + c_i + b_j\)。
• 若 \(i < j\)，則 \(f(i,j) = x_j - x_i + d_i + a_j\)。

\(2 \leq n \le 5 \times 10^3\)，\(s \ne e\)，\(1 \le x_1 < x_2 < \cdots < x_n \le 10^9\)，\(1 \le a_i,b_i,c_i,d_i \le 10^9\)。

解法：

這一類問題都可以描述如下：

你要求一個排列 \(p_1,p_2,\cdots,p_n\)，最小 / 最大化 \(\sum \limits_{i=1}^{n-1} f(p_i,p_{i+1})\)，其中 \(f(i,j)=\begin{cases} f(i)+g(j) && i<j\\h(i)+r(j) && i>j\end{cases}\)。

考慮到 \(f\) 的值與參數關系有關，考慮欽定順序進行連續段 DP，記 \(f_{i,j}\) 表示已經填入 \([1,i]\)，目前形成了 \(j\) 個連續段的答案。轉移都是容易的，不過細節是插入 \(s\) 和 \(e\) 時有些轉移是不合法的需要注意。

Submission Link.

Problem B. CF1835C Twin Clusters

題意：

給定 \(k\) 與一個長度為 \(2^{k+1}\) 的整數序列，每個數 \(a_i \in [0,4^k)\)。求序列的兩個非空不交子區間，異或和相等或確定無解。

\(0 \leq k \leq 17\)。

解法：

性質很多，逐步挖掘。

首先，不交的限制絕大多數情況都沒意義。如果找到兩個相交子區間異或相等，當且僅當一個區間包含另一個且長度差為 \(1\) 時無法構造不交的區間。

其次，我們斷言必然有解?？紤]反證。根據上述結論，容易知道每種區間異或和出現次數不超過 \(2\) 次，否則有解。其次，考慮區間個數為 \(\dfrac{2^{k+1}(2^{k+1}+1)}{2} > \dfrac{2^{2k+2}}{2}=2^{2k+1}=2\times 4^k\)，每種異或結果不超過 \(2\) 個，故至少有 \(4^k+1\) 個不同區間異或，與題意矛盾。

最后，根據生日悖論，每次隨機一個區間并計算異或和，加入 map 維護即可。復雜度 \(O(2^{k+1}\operatorname{poly}(k))\)。

Submission Link.

Problem C. CF865E Hex Dyslexia

題意：

給定一個十六進制數 \(x\)，可能含有前導 \(0\)。找到最小的長度和輸入的數相等的十六進制數 \(b\) 使得存在另一個個長度和這個數相等的十六進制數 \(a\) 滿足 \(a-b=x\) 且 \(a,b\) 的各位數字可以通過重排相同。\(a,b\) 可以有前導 \(0\)。若無解請報告，否則輸出最小的 \(b\)。

記 \(n\) 為 \(x\) 長度，保證 \(n \leq 14\)，時限 \(3\) 秒。

解法：

首先考慮有解的必要條件。

由于 \(a,b\) 重排相等，所以必然模 \(15\) 同余。原因比較顯然。

考慮 \(a-b=x\)，所以 \(x \equiv 0 \pmod {15}\)。這是有解的必要條件。

考慮 \(a\) 與 \(b\) 各位數字相等，但是卻有 \(b=a-x\)，若記 \(s\) 為 \(x\) 各位數字和，則 \(\dfrac s {15}\) 為 \(a-b\) 退位次數，原因是每次退位會使得數位和減去 \(15\)。

考慮枚舉哪些位退位，復雜度至多 \(O\left(\binom {n} {\frac{n}{2}}\right)\)。

枚舉進位后，每個位置的 \(a_i-b_i\) 可以直接求出。不妨將 \(b\) 看作 \(a\) 的置換，畫出置換環，每條邊的邊權是 \(a_i - a_{p_i}\)。我們需要在每個點上寫上 \([0,15]\) 的點權，使得每條邊左右兩數差為邊權，同時最小化 \(a_1,a_2,\cdots,a_n\) 的字典序。

事實上，我們可以發現每個置換環的最小點權必然都為 \(0\)，否則將環上所有點權減去最小值即可。然后我們還可以發現，兩個有相同數的環可以通過更改指出的邊進行合并。于是我們得到結論，存在最優解使得存在唯一的置換環，大小為 \(n\)。

接下來是容易的，進行 DP，記 \(f_S\) 表示目前已經加入了 \(S\) 這些點的最小答案，轉移是簡單的，總復雜度 \(O\left(\binom {n} {\frac{n}{2}} n2^n\right)\)，可以通過。

Submission Link.