比赛链接：https://codeforces.com/contest/1918

官解链接：https://codeforces.com/blog/entry/125300

这场比赛官解有几个地方不太清晰，我尽量解释严谨一些。

CF1918A. Brick Wall

题意

有 \(n \times m\) 的网格，使用 \(1 \times k\)（\(k\) 任意）的砖块填满，砖块可以水平或竖直放置。求水平与竖直砖块数量差的最大值。

题解

每一行最多能填 \(\lfloor \dfrac m 2 \rfloor\) 个水平砖块，故水平砖块数量上界是 \(n \lfloor \dfrac m 2 \rfloor\)。而这个上界能够达到，且同时可以一个竖直砖块都不放，则答案的最大值也是 \(n \lfloor \dfrac m 2 \rfloor\)。

代码实现

void solve() {
    int n, m;
    cin >> n >> m;
    cout << n * (m / 2) << "\n";
}

CF1918B. Minimize Inversions

题意

有长度均为 \(n\) 的排列 \(A\) 和 \(B\)，你可以指定任意两个位置，在 \(A\) 和 \(B\) 中同时交换这两个位置上的数。让它们逆序对总和达到最小，输出交换后的结果。

题解

提供的操作相当于将 \(A\) 和 \(B\) 相同位置上的数绑定后，任意重排一对数 \((x, y)\) 组成的数组。下面我们与 A 题类似，证明答案存在下界，并说明这个下界是可以达到的。

考虑在原数组中下标为 \((i, j)\) 的两个数对 \((a_i, b_i)\) 和 \((a_j, b_j)\)。若 \([a_i < a_j] = [b_i < b_j]\)，则在新数组中它们对逆序对贡献为 \(0\) 或 \(2\)；否则，它们的贡献始终为 \(1\)，无需考虑。既然 \(0\) 和 \(2\) 个数的总和是固定的，我们只需要尽量增大 \(0\) 的数量，而 \(0\) 数量的上界是 \(\sum_\limits{i < j} [a_i < a_j] = [b_i < b_j]\)，即不存在 \(2\) 的时候。

这个上界是可以达到的，只要使所有满足严格二维偏序关系 \(x \prec y\) 的两个数对， \(x\) 排在 \(y\) 之前即可（即偏序图的任意拓扑排序）。这是非常宽松的条件，以 \(a_i, b_i, \max(a_i, b_i), \min(a_i, b_i), a_ib_i\) 甚至 \(xa_i + yb_i (\forall x, y > 0)\) 等各种函数为 key 排序均可以达到这个目的。

代码实现

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    sa, sb = zip(*sorted(zip(a, b)))
    # sa, sb = zip(*sorted(zip(a, b), key=lambda x: max(x[0], x[1])))
    # sa, sb = zip(*sorted(zip(a, b), key=lambda x: min(x[0], x[1])))
    # sa, sb = zip(*sorted(zip(a, b), key=lambda x: x[0] + x[1]))
    # sa, sb = zip(*sorted(zip(a, b), key=lambda x: x[0]))
    # sa, sb = zip(*sorted(zip(a, b), key=lambda x: x[1]))
    # sa, sb = zip(*sorted(zip(a, b), key=lambda x: x[0] * x[1]))
    print(*sa)
    print(*sb)

CF1918C. XOR-distance

题意

给定正整数 \(a, b, r \le 10^{18}\)，求 \(\min\limits_{0 \le x \le r} |(a \oplus x) - (b \oplus x)|\)。

题解

贪心题。按位考虑：\((a \oplus x) - (b \oplus x) = \sum_\limits{b = 0}^{59} (a_i \oplus x_i) - (b_i \oplus x_i)\)。则 \(a_i = b_i\) 的位没有贡献，显然要让 \(x_i\) 为 \(0\)。

记 \(S\) 为 \(a_i \ne b_i\) 的位集合，\(X\) 为 \(x_i = 1\) 的位集合，\(X \subset S\)。由于结果带绝对值，\(X\) 和 \(S - X\) 对应的答案相同；而我们希望 \(x\) 尽可能小，因此指定 \(x\) 的最高（第 \(\max S\)）位为 \(0\)。又因为 \(2^{c+1} > \sum_{c=0}^b 2^c\)，已经确定最高位的情况下，之后若能够减小答案，能选则选即可。

代码实现

void solve() {
    i64 a, b, r;
    cin >> a >> b >> r;
    bool first = true;
    for (i64 m = 1ll << 59; m > 0; m >>= 1) {
        if (!((a ^ b) & m)) continue;
        if (r >= m && !first && abs((a ^ m) - (b ^ m)) < abs(a - b)) {
            a ^= m, b ^= m;
            r -= m;
        }
        if (first) first = false;
    }
    cout << abs(a - b) << "\n";
}

CF1918D. Blocking Elements

题意

给定数组 \(A\)。任选下标集合 \(B\)，删去数组中对应元素，数组被分为 \(|B| + 1\) 段 \([l_k, r_k]\)，代价为“被删去的数之和 \(\sum\limits_{b_i \in B} a_{b_i}\)”与“分割后的各子段和 \(\sum\limits_{i = l_k}^{r_k} a_i\)”中的最大值。求代价的最小值。

题解

看到最小化最大值显然要二分答案。判断答案是否可行可以使用 DP：记 \(dp_i\) 为 \(i\) 被选中，且每段和均不超过 \(s\) 时选中数的最小值。枚举上一个选中的数 \(j\)，转移方程为 \(dp_i = a_i + \min\set{dp_j | {\sum\limits_{j + 1}^{i-1} a_i \le s}}\)。为了方便记 \(a_{n+1} = 0\)，最终判断是否有 \(dp_{n + 1} \le s\) 即可。

注意合法转移区间的上下界是单调增的，因此最优做法是双指针计算转移区间，并使用单调队列优化 DP。总时间复杂度 \(O(n(\log n + \log \max A))\)。

代码实现

constexpr i64 INF = 1e18;
void solve() {
    int n;
    cin >> n, n++;
    vector<i64> a(n + 1);
    for (int i = 1; i < n; i++) cin >> a[i];
    i64 lb = ranges::max(a), rb = accumulate(a.begin(), a.end(), 0ll);
    auto v = views::iota(lb, rb + 1);
    auto check = [&](i64 s) {
        vector<i64> dp(n + 1, INF);
        dp[0] = 0;
        vector<int> q(n + 1);
        i64 sum = 0;
        int pnt = 0, l = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            while (sum > s) sum -= a[++pnt];
            while (q[l] < pnt) l++;
            dp[i] = a[i] + dp[q[l]];
            while (dp[q[r - 1]] > dp[i]) r--;
            q[r++] = i;
            sum += a[i];
        }
        return dp[n] > s;
    };
    cout << i64(ranges::partition_point(v, check) - v.begin() + lb) << "\n";
}