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(\mid(a\oplus x)-(b\oplus x)\mid)\)

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\) 各位之和(最高位除外)

#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\))