Codeforces Round 931(Div.2) A~D2

A. Too Min Too Max （数学）

题意：

给定长度为 $n$ 的数组 $a$ ，求下列表达式的最大值， $(i, j, k, l)$ 为不同的索引
$a_i - a_j| + |a_j - a_k| + |a_k - a_l| + |a_l - a_i|$

分析：

构造出最小-最大 + 最大-次小 + 次小-次大 + 次大-最小的形式。
去掉绝对值之后可以保证为 $2$ 个最大+ $2$ 个次大- $2$ 个最小- $2$ 个次小

代码：

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int a[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + 1 + n);
        cout << a[n] - a[1] + (a[n - 1] - a[1]) + (a[n - 1] - a[2]) + (a[n] - a[2]) << endl;
    }
    return 0;
}

B.Yet Another Coin Problem （枚举）

题意：

有 $1, 3, 6, 10, 15$ 面额的硬币无数枚，组成 $n$ 元的硬币至少需要多少枚硬币。

分析：

可以发现每种硬币最多出现次数有着限制：面额 $1$ ，最多出现 $2$ 次，面额 $3$ ，最多出现 $1$ 次，面额 $6$ ，最多出现 $2$ 次，面额 $10$ ，最多出现 $2$ 次，面额 $15$ ，没有限制。
枚举每种硬币出现次数即可。

代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int ans = 1e9;
        for (int i1 = 0; i1 <= 2; i1++)
            for (int i3 = 0; i3 <= 1; i3++)
                for (int i6 = 0; i6 <= 2; i6++)
                    for (int i10 = 0; i10 <= 2; i10++) {
                        int sum = i1 + i3 * 3 + i6 * 6 + i10 * 10;
                        if (sum <= n && (n - sum) % 15 == 0)
                            ans = min(ans, (n - sum) / 15 + i1 + i3 + i6 + i10);
                    }
        cout << ans << endl;
    }
    return 0;
}

C.Find a Mine （交互）

题意：

给定 $\times m$ 的地图，地图上有两个位置有矿物。每次你需要输入一个坐标 $(x, y)$ ，系统将返回曼哈顿距离最近的矿物的距离。你需要通过最多四次询问，找到其中一个矿物的位置。

分析：

我们首先询问 $(1, 1), (1, m)$ ，并假设他们离第一个矿物更近，那么我们就可以解除第一个矿物的坐标，第三次询问用于确认计算结果是否正确。否则询问 $(1, n)$ ，再和 $(1, 1)$ 联立解出坐第一个矿物的坐标。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int ask(int x, int y) {
    cout << "? " << x << " " << y << endl;
    cout.flush();
    int tmp;
    cin >> tmp;
    return tmp;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int tmp1 = ask(1, 1), tmp2 = ask(1, m),
                tmp3 = ask(n, 1);
        if ((tmp1 + tmp3 + 3 - n) > 0 && (tmp1 + tmp3 + 3 - n) % 2 == 0) {
            int y1 = (tmp1 + tmp3 + 3 - n) / 2, x1 = tmp1 - y1 + 2;
            if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m) {
                int q = ask(x1, y1);
                if (q == 0) {
                    cout << "! " << x1 << " " << y1 << endl;
                    continue;
                }
            }
        }
        int x1 = (tmp1 + tmp2 + 3 - m) / 2, y1 = tmp1 + 2 - x1;
        cout << "! " << x1 << " " << y1 << endl;
        cout.flush();
    }
    return 0;
}

D1.XOR Break — Solo Version （位运算）

题意：

给定 $x$ ，每次可选择满足以下条件的 $y$ ：

$0 < y < x$ 且 $\bigoplus y < x$

令 $x$ 变成 $y$ 或者 $\bigoplus y$ ，询问是否能够通过最多 $63$ 次操作令 $x$ 变为 $m$ 。请输出操作序列。

分析：

$2$ 的幂次是无解的，如果是这种情况，直接就是失败。如果两个数最高位相同，可以通过一步操作 $x$ 到 $y$ 。否则最高位一定不同，从最高位往下，如果 $x$ 和 $y$ 第一个不同的位中 $y$ 是 $1$ 是无解的，因为无论如何操作这位都不可能是 $1$ 。否则就可以通过把从高位往下遇到的 $x$ 中的第一个 $1$ 变成从该位往下全是 $1$ ，可以得到一个全是 $1$ 的数字，再通过一步操作就可以变成 $y$ 。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

LL check(LL x, LL y) {
    if (y < x && (x ^ y) < x)
        return 1;
    LL t = (x ^ y);
    if (t < x && (x ^ t) < x)
        return 1;
    return 0;
}

LL pow1(LL x) {
    return (x & (x - 1)) == 0;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        LL n, m;
        cin >> n >> m;
        if ((n ^ m) < n) {
            cout << 1 << endl;
            cout << n << " " << m << " " << endl;
            continue;
        }
        if (pow1(n)) {
            cout << -1 << endl;
            continue;
        }
        int tmp1 = __lg(n ^ m);
        int tmp2 = -1;
        for (int i = tmp1 - 1; i >= 0; i--) {
            int bit1 = (n >> i & 1);
            int bit2 = (m >> i & 1);
            if (bit2 > bit1) {
                break;
            } else if (bit1) {
                tmp2 = i;
                break;
            }
        }
        if (tmp2 == -1) {
            cout << -1 << endl;
            continue;
        }
        vector<LL> ans;
        ans.push_back(n);
        LL tmp = n;
        tmp ^= 1LL << tmp1;
        tmp |= (1LL << (tmp2 + 1)) - 1;
        ans.push_back(tmp);
        if (tmp != m) {
            ans.push_back(m);
        }
        for (int i = 0; i + 1 < ans.size(); i++) {
            assert(check(ans[i], ans[i + 1]));
        }
        cout << ans.size() - 1 << endl;
        for (auto x: ans)
            cout << x << " ";
        cout << endl;
    }
    return 0;
}

D2.XOR Break — Solo Version （交互）

题意：

给一个数字 $n$ ，两个人轮流操作，

当前人选择将 $n$ 拆分成 $p_1 \bigoplus p_2,p_1 < n, p_2 < n$ 。无法拆分认为失败

另一个人选择将 $n$ 变成 $p_1$ 或者 $p_2$

两人各拆分一次算作一次，询问是先手必胜还是后手必胜。你可以选择先后手，并和测试机进行这个游戏，你需要在 $63$ 轮之内获胜。

分析：

首先考虑 $n$ 数位上 $1$ 的个数，如果 $1$ 的个数是偶数，那么选择先手，否则选择后手。如果 $1$ 的个数是偶数，我们可以将其拆成两个奇数给后手，后手只能选择一个奇数拆成奇数加偶数还给先手。先手又从中选择偶数拆成两个奇数。最后无法操作的状态为 $1$ 的个数为 $1$ 。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

LL get(LL x) {
    for (LL i = 60; i >= 0; i--) {
        if ((x >> i) & 1)
            return i;
    }
}

int cal(LL n) {
    int res = 0;
    for (int i = 60; i >= 0; i--) {
        if ((n >> i) & 1)
            res++;
    }
    return res;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        LL n, x, y;
        cin >> n;
        if (cal(n) & 1) {
            cout << "second" << endl;
            cout.flush();
            while (true) {
                cin >> x >> y;
                if (x == 0 && y == 0)
                    break;
                if (cal(x) % 2 == 0) {
                    LL x1 = (1ll << get(x));
                    cout << x1 << " " << (x ^ x1) << endl;
                    cout.flush();
                } else {
                    LL y1 = (1ll << get(y));
                    cout << y1 << " " << (y ^ y1) << endl;
                    cout.flush();
                }
            }
        } else {
            cout << "first" << endl;
            cout.flush();
            LL n1 = (1ll << get(n));
            cout << n1 << " " << (n ^ n1) << endl;
            cout.flush();
            while (true) {
                cin >> x >> y;
                if (x == 0 && y == 0)
                    break;
                if (cal(x) % 2 == 0) {
                    LL x1 = (1ll << get(x));
                    cout << x1 << " " << (x ^ x1) << endl;
                    cout.flush();
                } else {
                    LL y1 = (1ll << get(y));
                    cout << y1 << " " << (y ^ y1) << endl;
                    cout.flush();
                }
            }
        }
    }
    return 0;
}