CCPC2024 哈尔滨站 题解

B - 凹包（计算几何，铜牌题）

Question

给出一个二维平面上的点集，要求选择若干个点以及点之间的连接顺序，使得这些点连成一个面积严格 $>0$ 的凹多边形，最大化这个凹多边形的面积

Solution

首先不考虑凹的性质，一个点集中选取 $n$ 个点组成最大 图形肯定是凸包，所以我们需要找一个不在凸包上的点，然后找凸包上的一条边，把这条边删去，把这条边的两个点连向这个不在凸包上的点，就组成了一个凹包

所以问题转化成了如何找一个不在凸包上的点，以及凸包上相连的两点，使得这三个点组成的三角形面积最小

最朴素的办法是枚举一条边，然后在不在凸包上的点集中选择一个离这条边最近的点，这就有点类似于旋转卡壳的味道了

其实只需要在非凸包上的点集里再做一次凸包，然后用双指针做一个类似于旋转卡壳的方法，维护离当前边最近的点

Code

#include <bits/stdc++.h>

using i128 = __int128_t;
constexpr i128 INF = 2e18;

struct Point {
    i128 x, y;
    Point(){x = 0, y = 0;}
    Point(i128 x, i128 y) : x(x), y(y) {}
};

typedef Point Vector;

Vector operator - (Point A, Point B) {return Vector(A.x - B.x, A.y - B.y);}

i128 cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
i128 area2(Point A, Point B, Point C) {return cross(B - A, C - A);}
i128 abs(i128 x) {return (x > 0 ? x : -x);}

std::vector<int> convexhull(std::vector<Point> &p) {
    int n = p.size();
    sort(p.begin(), p.end(), [] (Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });

    std::vector<int> ch(n * 2); int m = 0;
    for (int i = 0; i < n; i++) {
        while (m > 1 && cross(p[ch[m - 1]] - p[ch[m - 2]], p[i] - p[ch[m - 2]]) <= 0) m--;
        ch[m++] = i;
    }
    for (int i = n - 2, t = m; i >= 0; i--) {
        while (m > t && cross(p[ch[m - 1]] - p[ch[m - 2]], p[i] - p[ch[m - 2]]) <= 0) m--;
        ch[m++] = i;
    }
    if (n > 1) m--;
    ch.resize(m);
    return ch;
}

i128 convex_polygon_area2(std::vector<Point> &p) {
    int n = p.size();
    i128 area = 0;
    for (int i = 1; i < n - 1; i++) area += area2(p[0], p[i], p[i + 1]);
    return area;
}

void print(i128 x) {
    if (x  < 10) {
        putchar(x + '0');
        return ;
    }
    print(x / 10);
    putchar((x % 10) + '0');
}

void solve() {
    int n; std::cin >> n;
    std::vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        int x, y; std::cin >> x >> y;
        p[i] = Point(x, y);
    }    

    std::vector<int> vis(n, 0);
    auto ch1 = convexhull(p);
    std::vector<Point> p2, res1;
    for (int i = 0; i < ch1.size(); i++) vis[ch1[i]] = 1, res1.push_back(p[ch1[i]]);
    for (int i = 0; i < n; i++)
        if (vis[i] == 0) p2.push_back(p[i]);

    i128 ans = convex_polygon_area2(res1);

    if (p2.size() < 3) {
        if (p2.size() == 0) {
            std::cout << "-1\n"; 
        }
        if (p2.size() == 1) {
            i128 min_area = INF;
            for (int i = 0; i < res1.size(); i++) {
                min_area = std::min(min_area, area2(res1[i], res1[(i + 1) % res1.size()], p2[0]));
            }
            print(ans - min_area);
            putchar('\n');
        }
        if (p2.size() == 2) {
            i128 min_area = INF;
            for (int i = 0; i < res1.size(); i++) {
                min_area = std::min(min_area, area2(res1[i], res1[(i + 1) % res1.size()], p2[0]));
                min_area = std::min(min_area, area2(res1[i], res1[(i + 1) % res1.size()], p2[1]));
            }
            print(ans - min_area);
            putchar('\n');
        }
        return ;
    }
    std::vector<int> ch2 = convexhull(p2);
    std::vector<Point> res2;
    for (int i = 0; i < ch2.size(); i++)
        res2.push_back(p2[ch2[i]]);
    i128 min_area = INF;

    int st = -1; i128 min_ = INF;
    for (int i = 0; i < res2.size(); i++) {
        i128 now_area = area2(res1[0], res1[1], res2[i]);
        if (st == -1 || min_ > now_area)
            st = i, min_ = now_area;
    }

    for (int i = 0, j = st; i < res1.size(); i++) {
        int nxt1 = (i + 1) % res1.size(), nxt2 = (j + 1) % res2.size();
        while (area2(res1[i], res1[nxt1], res2[j]) > area2(res1[i], res1[nxt1], res2[nxt2]))
            j = nxt2, nxt2 = (j + 1) % res2.size();
        
        min_area = std::min(min_area, area2(res1[i], res1[nxt1], res2[j]));
    }

    print(ans - min_area);
    putchar('\n');
}

int main() {
    
    int T; std::cin >> T;
    while (T--) solve();
    return 0;
}

C - 在哈尔滨指路

Solution

签到

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;
ll Tex, m;
void AC(){
    cin >> m;
    ll x = 0, y = 0, cnt = 0;
    char ch;
    for(int i = 1; i <= m; i ++){
        cin >> ch >> cnt;
        if(ch == 'S') y -= cnt;
        else if(ch == 'N') y += cnt;
        else if(ch == 'E') x += cnt;
        else x -= cnt;  
    }

    if(x == 0 && y == 0){
        cout << 7 << " " << 'E' << "\n";
        cout << 'Z' << " " << 1 << "\n";
        cout << "L" << "\n";
        cout << 'Z' << " " << 1 << "\n";
        cout << "L" << "\n";
        cout << 'Z' << " " << 1 << "\n";
        cout << "L" << "\n";
        cout << 'Z' << " " << 1 << "\n";
        return;
    }

    if(y == 0){
        if(x > 0){
            cout << 1 << " " << 'E' << "\n";
            cout << 'Z' << " " << x << "\n";
        }
        else{
            cout << 1 << " " << 'W' << "\n";
            cout << 'Z' << " " << -x << "\n";
        }
        return;
    }

    if(x == 0){
        if(y > 0){
            cout << 1 << " " << 'N' << "\n";
            cout << 'Z' << " " << y << "\n";
        }
        else{
            cout << 1 << " " << 'S' << "\n";
            cout << 'Z' << " " << -y << "\n";
        }
        return;
    }

    if(x > 0){
        cout << 3 << " " << 'E' << "\n";
        cout << 'Z' << " " << x << "\n";
        if(y > 0){
            cout << 'L' << "\n";
            cout << 'Z' << " " << y << "\n";
        }
        else{
            cout << 'R' << '\n';
            cout << 'Z' << " " << -y << "\n";
        }
    }
    else{
        cout << 3 << " " << 'W' << "\n";
        cout << 'Z' << " " << -x << "\n";
        if(y > 0){
            cout << 'R' << "\n";
            cout << 'Z' << " " << y << "\n";
        }
        else{
            cout << 'L' << '\n';
            cout << 'Z' << " " << -y << "\n";
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> Tex;
    while(Tex --) AC();
    return 0;
}

K - 农场经营

Question

有 $n$ 种作物，有 $m$ 个单位时间，处理一单位 $i$ 作物的收益为 $w_i$，处理时长 $x_i\in [l_i,r_i]$，需要满足 $\sum x_i=m$

现在你可以删除一个作物的时长限制，求 $\sum w_i\times x_i$ 的最大值

Solution

先不考虑删除的情况

贪心的想法，肯定 $w_i$ 越大 $x_i$ 越大越好，但是 $x_i$ 不能都到 $r_i$ ，因为其他的作物有限制

所以我们先算保底需要做多少个单位，也就是 $\sum l_i$ ，剩下的自由时间为 $m'=m-\sum l_i$

对于这些自由时间，我们只需要按照 $w_i$ 从大到小得贪心的安排即可，这个过程可以二分得到

然后考虑删除

枚举删除了 $i$，显然，按照 $w_i$ 排序后，$m'$ 必然不会分配到大于 $i$ 的作物上去，所以还是按照不删除的情况二分 $m'$ 的位置

如果分配玩了前 $i$ 个依然有剩余，就全部分配给第 $i$ 个位置，因为 $i$ 的范围为 $[0,m]$

Code

#include <bits/stdc++.h>

using ll = long long;

struct Node {
    ll w, l, r;
    bool operator <(const Node B) const {
        return w > B. w;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    ll n, m; std::cin >> n >> m;
    std::vector<Node> a(n + 1);
    long long sum_l = 0, sum_l_ans = 0;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i].w >> a[i].l >> a[i].r;
        sum_l += a[i].l;
        sum_l_ans += 1ll * a[i].l * a[i].w;
    }

    ll ans = 0;
    ll m_ = m - sum_l;
    sort(a.begin() + 1, a.end());
    std::vector<ll> p = {0}, sum_p = {0};
    for (int i = 1; i <= n; i++) {
        ll now_m = m_ + a[i].l;
        int pos = std::upper_bound(p.begin(), p.end(), now_m) - p.begin(); pos -= 1;
        ll tmp = now_m - p[pos], now_ans;

        if (pos == i - 1)
            now_ans = sum_l_ans - a[i].l * a[i].w + sum_p[pos] + tmp * a[i].w;
        else
            now_ans = sum_l_ans - a[i].l * a[i].w + sum_p[pos] + tmp * a[pos + 1].w;
        
        ans = std::max(ans, now_ans);

        p.push_back(p.back() + a[i].r - a[i].l);
        sum_p.push_back(sum_p.back() + (a[i].r - a[i].l) * a[i].w);
    }

    std::cout << ans << '\n';
    return 0;
}

G - 欢迎加入线上会议！

Solution

签到

找出一个不是特殊点的位置开始 bfs，模拟这个过程即可

Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int n, m, k; std::cin >> n >> m >> k;
    std::vector<std::vector<int>> g(n + 1);
    std::vector<int> b(n + 1, 0);
    for (int i = 1; i <= k; i++) {
        int x; std::cin >> x;
        b[x] = 1;
    }
    
    for (int i = 1; i <= m; i++) {
        int u, v; std::cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }

    int st = -1;
    for (int i = 1; i <= n; i++) {
        if (b[i] != 1) {st = i; break;} 
    }

    if (st == -1) {std::cout << "No\n"; return 0;}

    std::vector<int> vis(n + 1, 0);
    std::queue<int> q; q.push(st); vis[st] = 1;

    std::vector<std::vector<int>> ans;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        std::vector<int> now;
        now.push_back(u);
        for (auto v : g[u]) if (!vis[v]) {
            now.push_back(v);
            vis[v] = 1;
            if (!b[v]) q.push(v);
        }
        if (now.size() > 1)
            ans.push_back(now);
    }

    if ((*std::min_element(vis.begin() + 1, vis.end())) == 0) {
        std::cout << "No\n"; return 0;
    }

    std::cout << "Yes\n";
    std::cout << ans.size() << "\n";
    for (auto &now : ans) {
        std::cout << now.front() << " " << now.size() - 1 << " ";
        for (int i = 1; i < now.size(); i++)
            std::cout << now[i] << " ";
        std::cout << "\n";
    }
    return 0;
}

J - 新能源汽车

Question

有一个 $n$ 种电瓶的车，每种电瓶上界 $a_i$，消耗 $1$ 单位任意电瓶种的电力前进 $1$ 个单位，有 $m$ 个充电站，每个充电站可以给一个制定的电瓶充电，求初始电瓶满电的情况下最远可以行驶多远

Solution

有一个朴素的贪心算法：对于走一单位的路，尽可能先用最近的充电站的电，最近的用完了再用第二近的，这个想法是 $O(n^2)$ 的，

考虑使用堆来优化这个过程，用一个堆记录一个二元组，第一位记录充电站的位置，第二维记录充电站是给那个电池充电的

提前预处理 nxt 数组表示往后第一个与第 $i$ 个充电类型相同的充电站

我们记录当前所有电瓶的电量数组 $now$，模拟暴力的过程，取出一个充电站，先用这个充电站的电

当遇到一个充电站时，就把 $now$ 修改成初始值，然后把当前的下一个位置丢进堆

Code

#include <bits/stdc++.h>
#define int long long

constexpr int INF = 2e9;

void solve() {
    int n, m; std::cin >> n >> m;
    std::vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
        std::cin >> a[i];
    std::vector<int> x(m + 1, 0), t(m + 1, 0);
    std::vector<int> b(n + 1, 0), nxt(m + 1, 0);
    for (int i = 1; i <= m; i++) 
        std::cin >> x[i] >> t[i];

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

    std::fill(b.begin(), b.end() , m + 1);
    for (int i = m; i >= 1; i--) {
        nxt[i] = b[t[i]];
        b[t[i]] = i;
    }
    
    for (int i = 1; i <= n; i++) {
        if (b[i] == m + 1) 
            pq.push({INF, i});
        else 
            pq.push({x[b[i]], i});
    }

    std::vector<int> now_a = a;

    int ans = 0;
    x.push_back(INF);

    for (int i = 1; i <= m + 1; i++) {
        int len = x[i] - x[i - 1];

        while (!pq.empty() && pq.top().first < x[i]) pq.pop();

        while (!pq.empty()) {
            if (len <= 0) break;
            auto [pos, id] = pq.top();
            if (now_a[id] < len) {
                pq.pop();
                len -= now_a[id];
                ans += now_a[id];
                now_a[id] = 0;
            }
            else {
                if (now_a[id] == len) pq.pop();
                now_a[id] -= len;
                ans += len;
                len = 0;
            }
        }
        if (len > 0) break;
        now_a[t[i]] = a[t[i]];
        if (nxt[i] != m + 1)
            pq.push({x[nxt[i]], t[i]});
        else 
            pq.push({INF, t[i]});
    }

    std::cout << ans << '\n';
}

signed main() {
    freopen ("J.in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int T; std::cin >> T;
    while (T--) solve();
    return 0;
}

M - 奇怪的上取整

Solution

签到，对于每个 $f(n,i)$ 的返回值就是小于等于 $i$ 的最大的 $n$ 的因子

所以可以把 $n$ 质因数分解，在因子之间的数的返回值相同，可以一起处理

Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int T; std::cin >> T;
    while (T--) {
        long long x; std::cin >> x;
        std::vector<long long> p;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                p.push_back(i);
                if (x / i != i) p.push_back(x / i);
            }
        }
        p.push_back(1); p.push_back(x);
        std::sort(p.begin(), p.end());

        long long ans = 0;
        for (int i = 1; i < p.size(); i++) {
            long long now = x / p[i - 1];
            ans += now * (p[i] - p[i - 1]);
        }
        ans += 1;
        std::cout << ans << '\n';
    }
    return 0;
}