2023SDCPC｜Apr.6 CUC2024区域赛重现#7

The 13th Shandong ICPC Provincial Collegiate Programming Contest

ID	Difficulty	Topic	Status
A	⭐	Implementation, Greedy	0:10:36
B			(-1)
C
D	⭐⭐	Binary Search, Greedy	1:17:06
E	⭐⭐⭐	Math, Number theory, Implementation	(Upsolved)
F
G	⭐	Implementation, Greedy	0:46:48
H
I	⭐	Implementation	0:48:18 (+1)
J
K
L	⭐⭐	Constructive algorithms, Implementation	1:36:02
M	⭐⭐	Computational Geometry	(-1) (Upsolved)

A. Orders

题意每天可加工 $k$ 个产品，在第 $a_i$ 天消耗 $b_i$ 个产品，判断是否有解。
思路 $ka_i\geqslant\sum{b_i}$。

void eachT() {
    int n = read(), k = read();
    vector<pair<int, int> > a(n);
    for (auto& i : a) i.f = read(), i.s = read();
    sort(a.begin(), a.end());
    ll sum = 0;
    for (auto i : a) {
        sum += i.s;
        if (1ll * i.f * k < sum) return void(printf("No\n"));
    }
    printf("Yes\n");
}

B. Building Company

D. Fast and Fat

题意 $n$ 个人分别有其 $v_i$ 和 $w_i$。每个人可选择背至多一个人，当 $i$ 背着 $j$ 时，若 $w_i>w_j$，则 $v_i$ 不变，否则 $v_i:=v_i - (w_j - w_i)$。求所有有未被背负的人中最小的 $v$ 的最大值。
思路二分答案为 $x$。$v_i<x$ 的人必须被背起，对于 $v_i\geqslant x$ 的人，希望背之后仍有 $v_i\geqslant x$。依表达式 $v_i:=(v_i+w_i) - w_j$ 知，贪心地选择让最大的 $v_i+w_i$ 背最大的 $w_j$，以此类推，是最优策略。

void eachT() {
    int n = read();
    vector<pii> a;
    int l = 1e9, r = 1, mid = -1;
    for (int i = 0; i < n; i++) {
        int v = read(), w = read();
        a.push_back({ v,w });
        l = min(l, v); r = max(r, v);
    }
    auto half = [&](ll x) {
        vector<pii> top, back;
        for (auto i : a) {
            if (i.f < x) top.push_back(i);
            else back.push_back(i);
        }
        sort(top.begin(), top.end(), [&](pii n1, pii n2) { return n1.s > n2.s; });
        sort(back.begin(), back.end(), [&](pii n1, pii n2) { return n1.f + n1.s > n2.f + n2.s; });
        if (top.size() > back.size()) return 0;
        for (int i = 0; i < top.size(); ++i) {
            if (back[i].f - top[i].s + back[i].s < x) return 0;
        }
        return 1;
    };
    while (l <= r) { mid = l + r >> 1; if (half(mid)) l = mid + 1; else r = mid - 1; }
    printf("%d\n", r);
}

E. Math Problem

题意给定 $n,k,m$，可任意多次花费 $a$ 将 $n$ 变为 $kn + x ,~ 0 \leqslant x< k$，或花费 $b$ 将 $n$ 变为 $\lfloor\frac nk\rfloor$，求将 $n$ 变为 $m$ 的 倍数(multiple) 的最小花费。
思路两个操作对应 $k$ 进制下的「补末位」和「删末位」操作。因操作方法不惟一，且位数很少，枚举删的位数。（止步于此，可能是被进制局限了） 继续枚举补的位数，虽然补的数无法确定，但它有一个范围，只要范围内存在 $m$ 的倍数即保证有解。

具体地说，对 $n$ 进行 $x$ 次乘法操作后的取值区间是 $\left[nk^x,~ (n+1)k^x-1 \right]$。要判断区间 $\left(l,r\right]$ 中是否存在 $m$ 的倍数，只需判断 $\lfloor\frac{l}{m}\rfloor < \lfloor\frac rm\rfloor$，或 $l-(l\bmod m)+m \geqslant r$，等价于 $(l\bmod m)+len \geqslant m$，使用后者的优势在于，避免了计算高次幂导致的溢出。

void eachT() {
    ll n = read(), k = read(), m = read(), a = read(), b = read();
    ll ans = (ll)8e18;
    if (k == 1 && n % m) ans = -1;
    else for (ll bcnt = 0; ; bcnt += b) {
        ll l = n % m, len = 1;
        for (ll acnt = 0;; acnt += a) {
            if (l == 0 || l + len > m) { ans = min(ans, acnt + bcnt); break; }
            l *= k, len *= k, l %= m;
        }
        if (!n || !ans) break;
        n /= k;
    }
    printf("%lld\n", ans);
}

G. Matching

题意给定序列 $a$，按 ¹ 以下规则构造出一张无向图 $G$：若 $i - j = a_i - a_j$，则 $G$ 中将存在一条连接节点 $i$ 与 $j$ 的无向边，其边权为 $a_i + a_j$，求 $G$ 中所有边的边权之和最大的 匹配(matching¹) 。

¹. A matching of an undirected graph means that we choose some edges from the graph such that any two edges have no common vertices. Specifically, not choosing any edge is also a matching. ↩
思路以 $a_i-i$ 为键存入 map，对每个 map 贪心地按边权从大到小选择偶数个。

void eachT() {
    int n = read();
    map<int, vector<int> > mp;
    for (int i = 1; i <= n; ++i) {
        int x = read();
        mp[x - i].push_back(x);
    }
    ll ans = 0;
    for (auto [j, v] : mp) {
        sort(v.begin(), v.end(), greater<int>());
        for (int i = 1; i < v.size(); i += 2) {
            if (v[i] + v[i - 1] >= 0) ans += v[i] + v[i - 1];
        }
    }
    printf("%lld\n", ans);
}

I. Three Dice

题意能否掷出三只骰子，使得朝上的面的红色点数之和为 $a$，黑色点数之和为 $b$。
思路循环枚举。

void eachT() {
    int a = read(), b = read();
    int ta[] = { 0,1,0,0,1,0,0,0 };
    for (int i = 1; i <= 6; ++i)
        for (int j = 1; j <= 6; ++j)
            for (int k = 1; k <= 6; ++k) {
                int sum[2] = { 0 };
                sum[ta[i]] += i;
                sum[ta[j]] += j;
                sum[ta[k]] += k;
                if (sum[1] == a && sum[0] == b)
                    return void(printf("Yes\n"));
            }
    printf("No\n");
}

L. Puzzle: Sashigane

题意正方形黑白棋盘中有惟一黑格，用 L 型覆盖白格，给出覆盖方案。
思路从黑色格子开始，每次操作向外包一层 L，形成更大的正方形，直至覆盖完毕。

void eachT() {
    int n = read(), x = read(), y = read();
    int dy = 1, dx = 1;
    printf("Yes\n%d\n", n - 1);
    for (int i = 1; i < n; ++i) {
        if (x == n) dx = -1, x -= i - 1;
        if (y == n) dy = -1, y -= i - 1;
        x += dx;
        y += dy;
        printf("%d %d %d %d\n", x, y, -i * dx, -i * dy);
    }
}

M. Computational Geometry

题意给定 $n$ 个顶点的凸多边形 $P$，需要选择 $P$ 的三个顶点记为 $A,B,C$（按逆时针顺序），且 $B$ 沿逆时针方向到 $C$ 之间恰有 $k$ 条边。将由线段 $AB,AC$，以及 $B$ 和 $C$ 之间的 $k$ 条边围成的 $k + 2$ 边形记作 $Q$。求 $Q$ 可能的最大面积 $S_Q$。
思路 $SQ=S{B\dots C}+S_{\triangle ABC}$，枚举 $B$，则 $B,C$ 已经确定，$A$ 需取距离直线 $BC$ 最远的点，用三分法解决 （赛时三分法的符号反了） ，时间复杂度 $\Theta(n\log n)$。

void eachT() {
    int n = read(), k = read();
    vector<pair<int, int> > pos(n);
    for (int i = 0; i < n; ++i) pos[i].f = read(), pos[i].s = read();

    auto getarea = [&](int i, int j, int k) {
        i %= n, j %= n, k %= n;
        ll x1 = pos[i].f, y1 = pos[i].s;
        ll x2 = pos[j].f, y2 = pos[j].s;
        ll x3 = pos[k].f, y3 = pos[k].s;
        ll _ans = x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;
        return abs(_ans);
    };

    ll area = 0, ans = 0;
    for (int i = 0; i < k; ++i) area += getarea(0, i, i + 1);

    auto solve = [&](int a, int b) {
        ll _ans = 0;
        int lt = a, rt = b, lm = -1, rm = -1;
        while (lt + 2 < rt) {
            lm = (lt * 2 + rt) / 3, rm = (rt * 2 + lt) / 3;
            if (getarea(lm, a, b) < getarea(rm, a, b)) lt = lm;
            else rt = rm;
        }
        for (int tt = lt; tt <= rt; ++tt)
            _ans = max(_ans, getarea(a, b, tt));
        return _ans;
    };

    for (int i = 0; i <= n; ++i) {
        ans = max(ans, area + solve(i + k, i + n));
        area += getarea(i + k + 1, i, i + k);
        area -= getarea(i + k + 1, i, i + 1);
    }

    printf("%.9lf\n", ans * 0.5);
}

评注一 亦可使用点到直线距离公式进行比较：

int A, B, C;
auto getkb = [&](int i, int j) {
    i %= n, j %= n;
    A = pos[i].s - pos[j].s;
    B = pos[j].f - pos[i].f;
    C = pos[i].f * pos[j].s - pos[j].f * pos[i].s;
};

auto getd = [&](int i) {
    i %= n;
    return A * pos[i].f + B * pos[i].s + C; // 无需 / sqrt(A*A + B*B)
};

评注二 注意到 $A$ 的位置是逆时针旋转的，可模拟这个过程以代替三分法，将时间复杂度优化到 $\Theta(n)$。