1918(922div2)

A. Brick Wall

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

B. Minimize Inversions

给出 $a, b$ 两个排列

同时交换排列 $a, b$ $(i, j)$ 位置，即 swap(a[i],a[j]),swap(b[i],b[j];

要使这两个排列的逆序对最少，输出 $a^{'}, b^{'}$

void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> f(n + 1);
    for (int i = 1; i <= n; i++) cin >> f[i].first;
    for (int i = 1; i <= n; i++) cin >> f[i].second;
    sort(f.begin() + 1, f.begin() + 1 + n);
    for (int i = 1; i <= n; i++) cout << f[i].first << " ";
    cout << '\n';
    for (int i = 1; i <= n; i++) cout << f[i].second << " ";
    cout << '\n';
}

C. XOR-distance

$x \in [0, r]$ 找出 $min (∣ (a \oplus x) - (b \oplus x) ∣)$

Solution

贪心

官方题解：

我们来考虑数字 $a$ 、 $b$ 、 $x$ 的位表示。让我们看看 $a$ 和 $b$ 在同一位置的任意 2 位，

如果它们相同，那么无论 $x$ 在该位置上是什么，数字 $| (a \oplus x) - (b \oplus x) |$ 在这个位置上都会是 0。因此，在所有这样的位置上设置为 0 是有利的（因为我们希望 $x \leq r$ ，并且答案不取决于位）。
如果 $a$ 和 $b$ 在同一位置的位不同，则在该位置上，无论是在 $a \oplus x$ 还是在 $b \oplus x$ 中都会有一个1，取决于 $x$ 在该位置上是什么。

假设 $a$ < $b$ ，如果不是的话，我们将交换它们。然后在最高的位置上，位不同， $a$ 中有一个 0， $b$ 中有一个 1。

位不同则有 $2$ 个选择

要么在这个位置上在 $x$ 中设置一个 1（然后在该位 $a \oplus x = 1, b \oplus x = 0$ ）
要么在 $x$ 中设置一个 0（然后在该位 $a \oplus x = 0, b \oplus x = 1$ ）。

假设我们在 $x$ 中设置一个 0，那么 $a \oplus x$ 肯定会小于 $b \oplus x$ （因为在最高位不同的情况下一定有: $a \oplus x = 0, b \oplus x = 1$ ）。因此，有利的是在所有接下来的位置上，在 $a \oplus x$ 中设置一个 1，因为这将使它们的差值更小。

因此，我们可以按降序遍历位置，如果位置不同，则在该位置上设置一个 1 在 $a \oplus x$ 中（如果这样 $x$ 不会超过 $r$ 的话）。

第二种情况（当我们在第一个不同的位上设置 1）类似地进行分析，但实际上并不需要，因为答案不会更小，而 $x$ 会变得更大。

时间复杂度：每个测试用例 $O (\log 10^{18})$ 。

代码

我一开始没有看懂为什么后面直接答案输出 $b - a$ 即可，后面发现可以更简单

#define int long long
void solve()
{
    int a, b, r, x = 0;
    cin >> a >> b >> r;
    if (a > b)
        swap(a, b);
    bool cn = 1;
    for (int i = 60; i >= 0; i--)
    {
        if ((a & (1LL << i)) != (b & (1LL << i)))//同一位置的位不同
        {
            if (cn)//第一个最高位不同的位置
                cn = 0;
            else
            {
                if (!(a & (1LL << i)) && x + (1LL << i) <= r)
                {
                    x += (1ll << i);//x在该位为1
                    a ^= (1ll << i);
                    b ^= (1ll << i);
                }
            }
        }
    }
    cout << b - a << '\n';
}

搞了半天和我的想法是一样的，最终的答案就是 $a, b (a < b)$ 从高到低位不同的位中 $a$ 该位为 $0$ 且 $x \leq r$ 各位之和(最高位除外)

假设我们在 $x$ 中设置一个 0，那么 $a \oplus x$ 肯定会小于 $b \oplus x$ （因为在最高位不同的情况下一定有: $a \oplus x = 0, b \oplus x = 1$ ）。因此，有利的是在所有接下来的位置上，在 $a \oplus x$ 中设置一个 1，因为这将使它们的差值更小。

#define int long long
void solve()
{
    int a, b, r, x = 0;
    cin >> a >> b >> r;
    if (a > b)
        swap(a, b);
    bool cn = 1;
    for (int i = 60; i >= 0; i--)
    {
        if ((a & (1LL << i)) != (b & (1LL << i)))
        {
            if (cn)
                cn = 0;
            else
            {
                if (!(a & (1LL << i)) && x + (1LL << i) <= r)
                    x += (1ll << i);
            }
        }
    }
    cout << (b ^ x) - (a ^ x) << '\n';
}

D. Blocking Elements

(待更 $\dots$ )