当前位置：首页 > news >正文

cf div2 1077 CDE

news 2026/3/26 23:11:35

C. Restricted Sorting

显然 \(k\) 是可以二分的，我们考虑对于一个固定的 \(k\)，如何 check。

考虑可交换条件 \(|a_{i}-a_{j}| \geq k\)：显然，最大值与最小值是最大概率可交换的。而其他一对元素的交换，可以间接地利用两个最值做到。因此，对于每个最终未在排序后位置的元素（已在对应位置上的元素不用看），我们只需要看它是否能和最大值或最小值交换就行了，check 复杂度 \(O(n)\)。这个思路类似于虚点：虚点就是两个最值，实点是每个元素，边代表可交换性。对于检查任意一对实点是否连通，只需要分别检查它们与虚点是否连通即可。

code

D. Shortest Statement Ever

这里给出 \(2\) 种做法。

1

\(dp\) 做法

考虑按照二进制高位到低位进行数位 \(dp\)，并在 \(dp\) 过程中记录每一步转移的路径，以还原方案。

状态定义

\(dp_{bit,cp,cq}\)：只考虑二进制高 \(bit\) 位的前缀（从第 \(30\) 位开始），\(p\) 已形成的前缀与 \(x\) 相应前缀的相对大小关系为 \(cp\)（\(-1\) 表示 \(p < x\)，\(0\) 表示 \(p=x\)，\(1\) 表示 \(p > x\)）；\(q\) 已形成的前缀与 \(y\) 相应前缀的相对大小关系为 \(cq\)（同上），\(|x-p|+|y-q|\) 的最小值。

则 \(|x-p|+|y-q|\) 的最小值为：

\[min(dp_{30,-1/0/1,-1/0/1}) \]

找到相应的 \(p, q\)，按照记录的转移路径一步步回溯即可。

之所以设置 \(cp,cq\) 这样的状态，是因为在决策当前位 \(p, q\) 填什么数字时，需要明确当前已构建前缀与 \(x,y\) 对应前缀的相对大小关系，才能进一步清楚 \(x\) 与 \(p\)（\(y\) 与 \(q\)）是更接近了还是更远离了，进而决定变化量对贡献是增加还是减少。

状态转移

即决策当前二进制位上 \(p, q\) 填什么数字。

首先，由题目给出的硬性要求 \(p\space \&\space q = 0\) ，对于每个二进制位 \(p\)，\(q\) 不能都填 \(1\)。因此只需要枚举 \((0,0), (0, 1),(1,0)\) 三种情况即可。
只考虑 \(cp \rightarrow next\_cp\) 的转移（\(cq \rightarrow next\_cq\) 同理）：
- \(cp = 0\)：也就意味着已经填过的高位前缀上的每一位都是与 \(x\) 相同的。那么 \(p\) 与 \(x\) 在这一位上的二进制数字大小关系就是 \(next\_cp\) 的值。
- \(cp \neq 0\)：由于高位权重更高，\(p\) 与 \(x\) 在这一位上的相对大小无法改变形成的新前缀的相对大小，因此这时 \(next\_cp = cp\)。
- 转移形成的贡献的加减需要根据 \(cp,cq\) 进一步决定。