Codeforces Pinely Round 3 (Div. 1 + Div. 2)

A.Distinct Buttons(思维)

题意：

你在开始时站在点 $(0, 0)$ ，同时，手上有一个遥控器，上面有四个按钮：

U:移动到 $(x, y + 1)$ 的位置
R:移动到 $(x + 1, y)$ 的位置
D:移动到 $(x, y - 1)$ 的位置
L:移动到 $(x - 1, y)$ 的位置

如果四个按钮都被按下过，那么遥控器将会被损坏，问能否到达给出的所有 $n$ 个点。

分析：

如果只能使用三个按键，那么只有在需要到达的所有点均在以下四个面中的一个时才能完成：

所有点都在 $x$ 轴上方
所有点都在 $x$ 轴下方
所有点都在 $y$ 轴左侧
所有点都在 $y$ 轴右侧

输入时使用数组记录出现的位置，最后判断输出即可。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 5e2;

void solve() {
    int n;
    cin >> n;
    int a[5] = {0, 0, 0, 0};
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if (x > 0) {
            a[0] = 1;
        } else if (x < 0) {
            a[1] = 1;
        }
        if (y > 0) {
            a[2] = 1;
        } else if (y < 0) {
            a[3] = 1;
        }
    }
    if (a[0] + a[1] + a[2] + a[3] > 3) cout << "No" << endl;
    else cout << "Yes" << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

B.Make Almost Equal With Mod(思维)

题意：

给出一个数组 $a_1, a_2, ..., a_n$ ，你可以选择一个数字 $k$ ，使数组中所有数字对 $k$ 取模，问 $k$ 等于多少时，可以使得数组中的数字再操作后恰好包含两种不同的数字。

分析：

依次枚举 $2$ 的次方数即可。

说明：

选择 $2$ 作为 $k$ 时，剩下的结果仅包含 $0, 1$
如果剩下的数字全部为 $0$ 或 $1$ ，继续选择 $2^2 = 4$ 作为 $k$ ，若选择 $2$ 时剩下的数字为 $0$ ，那么选择 $k = 4$ 时剩下的就是 $0, 2$ ，同理，剩下数字均为 $1$ ，则选择 $k = 4$ 时剩下的数字就是 $1, 3$ 。
依次类推，由于每次取模的结果只会有两种可能性，那么当结果中两种情况均出现就找到了合法的 $k$ 。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 5e2;

LL a[MAXN];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (LL i = 2; ; i <<= 1) {
        set<LL> S;
        for (int j = 1; j <= n; j++) {
            S.insert(a[j] % i);
            if (S.size() > 2) break;
        }
        if (S.size() == 2) {
            cout << i << endl;
            return;
        }
    }
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

C.Heavy Intervals(思维)

题意：

给出 $n$ 个区间 $l_i, r_i]$ ，每个区间包含一个权值 $c_i$ ，且区间的价值为: $c_i \times (r_i - l_i)$ ，你可以在保证区间合法 $l_i < r_i)$ 的情况下，对所有区间的 $l_i, r_i, c_i$ 进行任意重排，问所有区间的价值之和最小是多少？

分析：

既然要让价值之和最小，那么大的权值 $c_i$ 就要与长度更小的区间匹配，那要怎么在保证区间合法的情况下，让构造的区间尽可能长呢？

可以使用类似括号匹配的思想，先对 $l_i$ 和 $r_i$ 进行排序，把 $l_i$ 和 $r_i$ 视为左右括号进行括号匹配，并将构造成的区间长度记录下来。

完成匹配后，对权值 $c_i$ 和构造的区间长度 $l e n$ 进行排序，并按最大的权值和最小的区间长度进行匹配，次大的权值和次小的区间长度进行匹配，依次类推，就能得到最小的价值之和。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 5e2;

LL l[MAXN], r[MAXN], c[MAXN], len[MAXN];

stack<int> st;

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    sort(l, l + n);
    sort(r, r + n);
    sort(c, c + n);
    int pos_l = 0, pos_r = 0, cnt = 0;
    for (int i = 0; i < n * 2; i++) {
        if (pos_l < n && pos_r < n) {
            if (l[pos_l] < r[pos_r]) {
                st.push(l[pos_l++]);
            } else {
                len[cnt++] = r[pos_r++] - st.top();
                st.pop();
            }
        } else {
            len[cnt++] = r[pos_r++] - st.top();
            st.pop();
        }
    }
    LL ans = 0;
    sort(len, len + n);
    for (int i = 0, j = n - 1; i < n; i++, j--) {
        ans += len[i] * c[j];
    }
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

D.Split Plus K(思维)

题意：

给出 $n$ 个正整数 $a_1, a_2, ..., a_n$ ，你可以进行若干次以下操作：

选择一个数字 $x$ ，并将这个数字删除。
选择两个正整数 $y, z$ 满足 $y + z = x + k$ ，并将这两个数字放回。

问：能否在经过若干次操作后，使数组中所有数字相同，如果可以，输出最少操作次数，否则，输出-1.

分析：

由于每次产生的两个数字 $y, z$ 的总和会比原本的数字 $x$ 大 $k$ ，因此，如果一个数字被分解了 $m$ 次，那么得到的 $m + 1$ 个数字的总和就是 $\times k$ 。

令 $b_0, b_1, ..., b_m$ 为最后生成的 $m + 1$ 个数字，由于分解时会增加 $k$ ，且会增加 $m$ 次，那么可以将 $m$ 个 $k$ 分配给 $b_1 \sim b_m$ ，即最后生成的数字为 $b_0, b_1 + k, b_2 + k, ..., b_m + k$ 。

由题目可得以下两个式子：

$b_0 = b_1 + k = ... = b_m + k$
$b_0 + b_1 + k + ... + b_m + k = a_i + m \times k$

由于无法知道最后分解出的数字数量 $m$ 到底是多少，因此需要对式子进行化简，让第二个式子两边同时减去 $m + 1$ 个 $k$ ，可得：

$b_0 - k) + b_1 + ... + b_m = a_i - k$

而此时所有的 $b_1 \sim b_m$ 以及 $b_0 - k$ 均为 $a_i - k$ 的因子，因此，可以在输入后，将所有 $a_i$ 均减去 $k$ 。

然后，需要考虑，如果减去 $k$ 后的 $a$ 数组中出现了同时包含正负数或同时出现 $0$ 和其他数字，此时是无法完成构造的，直接输出 $- 1$ 。

最后考虑最后生成的数字，既然要让操作次数尽可能少，那么拆出的数字就要尽可能大，怎么选择最大的结果呢？只有选择减去 $k$ 之后的所有 $a_i - k$ 的最大公约数 $G$ 。

由于每次操作会增加一个数字，因此，将 $a_i - k$ 分解为若干个 $G$ 所需的操作次数为 $\frac{a_i - k}{G} - 1$ 。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 5e2;

LL n, k, a[MAXN];

void solve() {
    cin >> n >> k;
    LL maxn = -1e18, minn = 1e18;
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] -= k, maxn = max(maxn, a[i]), minn = min(minn, a[i]);
    if (maxn == minn) {
        cout << 0 << endl;
        return;
    }
    if (minn < 0 && maxn >= 0 || minn == 0 && maxn > 0) {
        cout << "-1" << endl;
        return;
    }
    LL g = a[1];
    for (int i = 2; i <= n; i++) g = __gcd(g, a[i]);
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += a[i] / g - 1;
    }
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}