Pinely Round 3 (Div. 1 + Div. 2) 题解 | JorbanS

A - Distinct Buttons

string solve() {
    cin >> n;
    int u = 0, d = 0, l = 0, r = 0;
    for (int i = 0; i < n; i ++) {
        int x, y; cin >> x >> y;
        if (x > 0) r ++;
        if (x < 0) l ++;
        if (y < 0) d ++;
        if (y > 0) u ++;
    }
    if (!r || !l || !u || !d) return yes;
    return no;
}

B - Make Almost Equal With Mod

int n;
ll a[N];

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll solve() {
    cin >> n;
    int odd = 0;
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
        odd += a[i] & 1;
    }
    if (odd && (n - odd)) return 2;
    sort(a, a + n);
    ll d = 0;
    for (int i = 1; i < n; i ++) d = gcd(d, a[i] - a[i - 1]);
    return d * 2;
}

法二：考虑所给数的二进制表示的每一位，答案即为 $2$ 的幂，每一位模得 $0$ 或 $1$ 因此只要找到最低的存在不同的二进制位

C - Heavy Intervals

首先考虑区间 $d,D$ 和权值 $c,C$，有 $d<D,c<C$

$d\times c+D\times C?d\times C?D\times c$
$=d\times (c?C)+D\times (C?c)$
$=(C?c)(D?d)$
$>0$

因为 $l[i]<r[i]$ 所以 $\sum d$ 一定，因此要让小区间 $d$ 尽可能小

int n, m;
int l[N], c[N];

ll solve() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> l[i];
    set<int> s;
    for (int i = 0; i < n; i ++) {
        int x; cin >> x;
        s.insert(x);
    }
    for (int i = 0; i < n; i ++) cin >> c[i];
    sort(l, l + n);
    sort(c, c + n);
    reverse(c, c + n);
    vector<int> d;
    for (int i = n - 1; i >= 0; i --) {
        auto it = s.upper_bound(l[i]);
        d.push_back(*it - l[i]);
        s.erase(it);
    }
    sort(d.begin(), d.end());
    ll res = 0;
    for (int i = 0; i < n; i ++) res += (ll)c[i] * d[i];
    return res;
}