CCPC Final 2016 个人题解

CCPC Final 2016 个人题解

Coast23
  2026-02-04 18:57:12 2026-02-04 18:57:12 创建   2026-02-13 12:04:45 2026-02-13 12:04:45 更新    3.8k 字  18 分钟  

学算法学到自闭，试图靠写远古题找回自信。

比赛链接：第二届中国大学生程序设计竞赛总决赛（CCPC Final 2016）

A. The Third Cup is Free

题意：签到。

void solve(){
    int n = read();
    std::vector<int> a(n);
    for(auto& x : a) x = read();
    std::sort(a.rbegin(), a.rend());
    ll ans = 0;
    for(int i = 0; i < n; ++i){
        if(i % 3 == 2) continue;
        ans += a[i];
    }
    printf("%lld\n", ans);
}

B. Wash

题意：

有() 件衣服，() 台洗衣机，() 台烘干机。

第台洗衣机洗衣要分钟，第台烘干机烘干要分钟。

每件衣服都要先洗后烘，求最少需要多少分钟。

首先肯定要贪心，用小根堆分别模拟洗衣和烘干的过程，求出有序的洗衣完成时间，以及烘干完成时间。

接下来就是两两配对，最小化。

这应该是排序不等式的一个应用吧，用小的配大的，就能让最小。

故答案为。

时间复杂度。

AC Code:

void solve(){
    int L = read(), n = read(), m = read();
    std::vector<ll> w(n), d(m);
    for(auto& x : w) x = read();
    for(auto& x : d) x = read();
    std::vector<ll> A(L), B(L);

    auto calc = [&](std::vector<ll>& a, std::vector<ll>& res) -> void {
      //  struct X {ll nxt, cost;};
        std::priority_queue<std::pair<ll, ll>> q;
        for(auto t : a) q.push({-t, t});
        for(int i = 0; i < L; ++i){
            auto x = q.top(); q.pop();
            res[i] = -x.first;
            x.first = -(-x.first + x.second);
            q.push(x);
        }
    };
    calc(w, A); calc(d, B);
    std::reverse(B.begin(), B.end());
    ll ans = 0;
    for(int i = 0; i < L; ++i){
        ans = std::max(ans, A[i] + B[i]);
    }
    printf("%lld\n", ans);
}

D. Game Leader

题意：

Tom 有() 个好友，排名从到，其中 Tom 的排名是。除 Tom 外每个好于都有自己的好友榜单（有 Tom 不认识的陌生人），在除 Tom 以外的个好友榜单中，排名为的人的霸榜次数为。

Tom 已知() 条好友关系，求在满足这些已知好友关系和上面的的情况下，最少有多少个陌生人的榜单被 Tom 的好友霸榜。

题目很绕，需要慢慢分析。

朋友总数陌生人总数

最小化陌生人数，等价于最大化朋友数。

也就是尽可能地让 Tom 的朋友互相作为 Leader，去填充的名额。

用数组 L[i] 表示第() 个朋友的 Leader，首先有，。

对于已知的好友关系，如果和互相认识，就用对方更新自己的 Leader。

（需要注意的是，这里的 L[i] 不代表真实的 Leader，只是一个下界，因为可能有未知的朋友关系，把 Leader 更新为排名更小的人。）

然后统计第个朋友成为 Leader 的次数，记为 cnt[i]，并和真实的 Leader 次数 C[i] 比较：

  • 如果，缺的位置必须用陌生人 Leader 填充，最少需要个陌生人。

  • 如果，说明至少有个朋友的 Leader 关系不对，但可以肯定的是，想要将调整为，不需要靠陌生人来占名额（名额都溢出了还要你干啥）。

这在当年居然是个金牌题，unbelievable 啊。

AC Code:

void solve(){
    int n = read(), m = read(), R = read();
    std::vector<ll> C(n + 1);
    std::vector<ll> L(n + 1);
    for(int i = 1; i <= n; ++i) C[i] = read();
    for(int i = 1; i <= n; ++i) L[i] = std::min(i, R);
    L[R] = 1;
    for(int i = 0; i < m; ++i){
        ll x = read(), y = read();
        L[x] = std::min(L[x], y);
        L[y] = std::min(L[y], x);
    }
    std::vector<ll> cnt(n + 1);
    for(int i = 1; i <= n; ++i) ++cnt[L[i]];
    ll ans = 0;
    for(int i = 1; i <= n; ++i) ans += std::max(0LL, C[i] - cnt[i]);
    printf("%lld\n", ans);
}

E. Problem Buyer

题意：

TopSetter 有() 道题，第道题的难度区间为。

比赛需要() 道题，第道题要求的难度为()。

现从个题目中随机抽取个，要确保无论抽的是哪些题，都能从中挑出个匹配比赛要求难度的题目。

求最小的。

先先将赛题难度从小到大排序，难度区间按从小到大排序。

正难则反，考虑最少删多少个问题，就能使剩下的题无法满足要求。

Call back 一下 Hall 定理：

二分图存在完美匹配的充要条件为:。

为了破坏这个条件，我们需要找到一个子集，使得最小。记：

  • 若，说明一开始就无法匹配，输出 IMPOSSIBLE；
  • 若，为使其小于，至少要删个问题，反过来也就是最多可以保留个问题。

问题顺利转化，难点在于怎么搞，总不能枚举所有的子集吧？

想了一下，发现 一定是一段连续区间。以下是一个感性证明：

假设不连续，我们将它分为个部分：中间的 Gap，Gap 左边的集合和右边的集合。

相对应地，把供应区间分为类：

  1. 只覆盖中的某些问题（记为）；
  2. 只覆盖中的某些问题（记为）；
  3. 既覆盖中的某些问题，又覆盖中的某些问题；
  4. 在和之间的、与和无交集的题，显然是的真子集。
  • 如果比还小，把加入会让减小；
  • 如果比还大，说明给了很大的贡献，或很有可能是比小的（这里我想不出严谨证明）。

于是就 guess 出了这样一个结论：无论哪种情况，要么可以通过填满空隙得到一个更坏的连续段，要么可以通过丢一些部分得到一个更坏的连续段。因此 一定是一段连续区间。

对于赛题区间，可知=。同时枚举和肯定是过不了的。

考虑枚举右端点，并用数据结构维护所有可能的左端点。

把变形一下，我们要求。

对于的问题，它能够覆盖所有的需求，也就是对(是满足的最小下标，可用 upper_bound 获取) 内的都有贡献，这显然是一个区间加操作。然后再查询区间最小值，用以更新。使用线段树即可。时间复杂度。

我的线段树板子是 1-based index 的，但数组我习惯 0-based index，所以代码里有一些下标转换（写的时候后悔死了，就应该统一一下）。

AC Code:

struct SGT {
    struct Node {
        int l, r, val, add;
        Node() {l = r = val = add = 0;}
    };
    int n;
    std::vector<Node> t;

    SGT(int _n) : n(_n){t.assign(n << 2, Node());}
    
    void pushup(int p){
        t[p].val = std::min(t[p << 1].val, t[p << 1 | 1].val);
    }

    void pushdown(int p){
        if(!t[p].add) return;
        t[p << 1].val += t[p].add;
        t[p << 1 | 1].val += t[p].add;
        t[p << 1].add += t[p].add;
        t[p << 1 | 1].add += t[p].add;
        t[p].add = 0;
    }

    void build(int p, int l, int r){
        t[p].l = l, t[p].r = r;
        if(l == r) return t[p].val = l, void(); // 初始值为下标
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        pushup(p);
    }

    void add(int p, int L, int R, ll v){
        if(t[p].l >= L and t[p].r <= R){
            t[p].val += v;
            t[p].add += v;
            return;
        }
        pushdown(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if(L <= mid) add(p << 1, L, R, v);
        if(R > mid) add(p << 1 | 1, L, R, v);
        pushup(p);
    }

    ll query(int p, int L, int R){
        if(t[p].l >= L and t[p].r <= R) return t[p].val;
        pushdown(p); // byd 忘记 pushdown 调半天
        int mid = (t[p].l + t[p].r) >> 1;
        ll res = 2e18;
        if(L <= mid) res = std::min(res, query(p << 1, L, R));
        if(R > mid) res = std::min(res, query(p << 1 | 1, L, R));
        return res;
    }
};

void solve(){
    int n = read(), m = read();
    std::vector<std::pair<int, int>> a(n);
    for(auto& [l, r] : a) l = read(), r = read();
    std::sort(a.begin(), a.end());
    std::vector<int> C(m);
    for(int i = 0; i < m; ++i) C[i] = read();
    std::sort(C.begin(), C.end());
    SGT sgt(n); sgt.build(1, 1, m);
    ll Q = 2e18;
    int p = 0;

    for(int i = 0; i < m; ++i){
        // 将所有左端点 <= C[i] 的问题计入贡献
        while(p < n and a[p].first <= C[i]){
            int R = a[p].second;
            int pos = std::upper_bound(C.begin(), C.end(), R) - C.begin();
            // 1-based sgt, pos 不用减一
            if(pos > 0) sgt.add(1, 1, pos, 1);
            ++p;
        }
        // 1-based sgt, i 要加一
        ll val = sgt.query(1, 1, i + 1);
        // i 是 0-based，需要加一
        Q = std::min(Q, val - (i + 1) - 1);
    } 

    if(Q < 0) return puts("IMPOSSIBLE!"), void();
    printf("%lld\n", n - Q);
}

G. Pandaland

题意：

有一个二维平面，上面总共有() 条带权无向边，保证边与边不相交。求图的最小环的长度。

顶点是二维点对的形式，先拿个 map 映射成编号，然后正常地求最小环。做法是枚举所有边，求删掉边权为的边后，和之间的最短路，答案就是。

用 Dijkstra 做，复杂度是的，交上去 TL 了，多测跑不过。

发现“边与边不相交”这个条件还没用上，这表明题目的图是平面图，但我不知道平面图有啥性质。

Dijkstra 不过是个 BFS，考虑剪枝。很显然，对于当前从优先队列弹出的顶点，如果当前最小环长度，直接 break 掉即可，不用再搜下去了。

没想到加上这个剪枝后就跑得飞快，msms，或许是平面图有比较优秀的性质？

AC Code:

void solve(){
    int m = read();
    struct Edge {int v; ll w; int id;};
    struct Edge2 {int u; int v; ll w;};
    std::vector<std::vector<Edge>> adj(m << 1 | 1);
    std::vector<Edge2> edge(m);
    std::map<std::pair<int, int>, int> node;
    int cnt = 0;
    auto getId = [&](int x, int y) -> int {
        if(node.count({x, y})) return node[{x, y}];
        return node[{x, y}] = cnt++;
    };

    for(int i = 0; i < m; ++i){
        int x1 = read(), y1 = read();
        int x2 = read(), y2 = read();
        ll w = read();
        int u = getId(x1, y1), v = getId(x2, y2);
        adj[u].push_back({v, w, i});
        adj[v].push_back({u, w, i});
        edge[i] = {u, v, w}; // 起点, 终点, 边权
    }

    const ll inf = 2e18;
    ll ans = inf;

    auto dijkstra = [&](int id) -> ll {
        auto& [s, t, dw] = edge[id];
        std::vector<ll> dis(cnt, inf);
        dis[s] = 0;
        std::vector<bool> vis(cnt);
        std::priority_queue<std::pair<ll, int>> q;
        q.push({0, s});
        while(q.size()){
            int x = q.top().second; q.pop();
            if(vis[x]) continue; vis[x] = 1;
            if(dis[x] >= ans - dw) break;
            for(auto& [y, w, i] : adj[x]){
                if(i == id) continue; // ban
                if(dis[y] > dis[x] + w){
                    dis[y] = dis[x] + w;
                    q.push({-dis[y], y});
                }
            }
        }
        return dis[t] + dw;
    };

    for(int i = 0; i < m; ++i){
        ans = std::min(ans, dijkstra(i));
    }
    printf("%lld\n", ans == inf ? 0 : ans);
}

H. Engineer Assignment

题意：

有个项目，第个项目需要种技能。

有个工程师，第个工程师有种技能。

每个工程师最多负责一个项目，为完成项目，需要负责该项目的所有工程师覆盖所需技能。

求最多能完成多少个项目。

数据范围：

  • .
  • .
  • .
  • .

看这个数据范围，无疑是个瞎搞题。

工程师不超过个，那就状压，用 bitmask 表示工程师占用情况。对于每个项目，枚举所有 mask，预处理出能完成该项目的组合，塞进 vector 里。

担心爆搜过不去，所以我写了记忆化搜索。

时间复杂度。

AC Code:

void solve(){
    int n = read(), m = read();
    std::vector<std::vector<int>> C(n), D(m);
    for(int i = 0; i < n; ++i){
        int c = read();
        C[i] = std::vector<int>(c);
        for(auto& x : C[i]) x = read();
    }
    for(int i = 0; i < m; ++i){
        int d = read();
        D[i] = std::vector<int>(d);
        for(auto& x : D[i]) x = read();
    }

    auto check = [&](int id, int mask) -> bool {
        for(auto& need : C[id]){
            bool ok = false;
            for(int i = 0; i < m and !ok; ++i){
                if((mask >> i) & 1){
                    for(auto& skill : D[i]){
                        if(skill == need){
                            ok = true;
                            break;
                        }
                    }
                }
            }
            if(!ok) return false;
        }
        return true;
    };

    std::vector<std::vector<int>> Mask(n);
    for(int i = 0; i < n; ++i){
        for(int mask = 1; mask < (1 << m); ++mask){
            if(check(i, mask)) Mask[i].push_back(mask);
        }
    }
    std::vector<std::vector<int>> rec(n, std::vector<int>(1 << m, -1));

    auto dfs = [&](auto&& self, int id, int mask) -> int {
        if(id == n) return 0;
        if(rec[id][mask] != -1) return rec[id][mask];
        int res = self(self, id + 1, mask);
        for(auto& sub : Mask[id]){
            if(!(mask & sub)){
                res = std::max(res, 1 + self(self, id + 1, mask | sub));
            }
        }
        return rec[id][mask] = res;
    };
    int ans = dfs(dfs, 0, 0);
    printf("%d\n", ans);
}

I. Mr. Panda and Crystal

题意：

有种水晶，点魔力值。

对于第种水晶，有两种获取方式：

  • 花费点魔力值进行合成（如果允许）
  • 使用一定数量的其它水晶来合成（根据配方）

配方共有条。

每种水晶都有价格，目标是最大化水晶总价格。

数据范围：

  • .
  • .
  • .

求出合成每个水晶所需的最小魔力值 cost[i]，就是个完全背包了。

合成关系很复杂，不容易建模，考虑直接暴力：遍历所有合成规则，更新 cost[i]，重复此过程直到成本不再更新为止（类似 Bellman-Ford）。

时间复杂度。

AC Code:

void solve(){
    int m = read(), n = read(), k = read();
    std::vector<ll> dp(m + 1);
    std::vector<ll> cost(n + 1);
    std::vector<ll> price(n + 1);
    struct Rule {
        int id;
        std::vector<std::pair<int, int>> need; // [id, cnt]
    };
    std::vector<Rule> rule(k);

    const ll inf = 2e18;
    for(int i = 1; i <= n; ++i){
        int type = read();
        if(!type){
            cost[i] = inf;
            price[i] = read();
        }
        else{
            cost[i] = read();
            price[i] = read();
        }
    }
    for(int i = 0; i < k; ++i){
        Rule r; r.id = read();
        int cnt = read();
        for(int j = 0; j < cnt; ++j){
            int u = read(), v = read();
            r.need.push_back({u, v});
        }
        rule.push_back(r);
    }
    bool upd = true;
    while(upd){
        upd = false;
        for(auto& r : rule){
            ll cur = 0;
            bool ok = true;
            for(auto& [u, v] : r.need){
                if(cost[u] == inf){
                    ok = false;
                    break;
                }
                cur += cost[u] * v;
                if(cur > m) break;
            }
            if(ok and cur < cost[r.id]){
                cost[r.id] = cur;
                upd = true;
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        if(cost[i] > m) continue;
        for(int j = cost[i]; j <= m; ++j){
            dp[j] = std::max(dp[j], dp[j - cost[i]] + price[i]);
        }
    }
    printf("%lld\n", dp[m]);
}

J. Worried School

题意：模拟题。

AC Code:

void solve(){
    int G = read();
    std::string name; std::cin >> name;
    std::vector<std::vector<std::string>> a(5);
    for(int i = 0; i < 5; ++i){
        a[i] = std::vector<std::string>(20);
        for(int j = 0; j < 20; ++j){
            std::cin >> a[i][j];
        }
    }
    std::vector<std::string> b(20);
    for(auto& x : b) std::cin >> x;
    
    auto check = [&](int Y) -> bool {
        std::map<std::string, bool> mp;
        int X = G - Y;
        for(int j = 0; j < 20 and X; ++j){
            for(int i = 0; i < 5 and X; ++i){
                if(mp.count(a[i][j])) continue;
                mp[a[i][j]] = 1, --X;
            }
        }
        for(int i = 0; i < 20 and Y; ++i){
            if(mp.count(b[i])) continue;
            mp[b[i]] = 1, --Y;
        }
        return mp.count(name) == 1;
    };

    for(int y = 0; y <= G; ++y){
        if(!check(y)) return printf("%d\n", y), void();
    }
    
    puts("ADVANCED!");
}

L. Daylight Saving Time

题意：

给定 California Local Time，判断它是 PST，PDT，Both，还是 Neither。

用 ctime 库的 mktime 函数会自动修正 tm 结构体里的 tm_wday 与 tm_wday 字段，前者表示该天自周日以来的天数 ()，利用它就可以很快求出某年某月第个周日的天数。

AC Code:

void solve(){
    int Y, M, D, h, m, s;
    scanf("%d-%d-%d %d:%d:%d", &Y, &M, &D, &h, &m, &s);
    if(M == 1 or M == 2 or M == 12) return puts("PST"), void();
    if(M >= 4 and M <= 10) return puts("PDT"), void();

    auto get = [&](int y, int m, int n) -> int {
        tm t = {0};
        t.tm_year = y - 1900;
        t.tm_mon = m - 1;
        t.tm_mday = 1;
        mktime(&t);

        if(t.tm_wday == 0) return 1 + (n - 1) * 7;
        else return 1 + (7 - t.tm_wday) + (n - 1) * 7;
    };

    if(M == 3){
        int nth = get(Y, 3, 2);
        if(D < nth) return puts("PST"), void();
        if(D > nth) return puts("PDT"), void();
        if(h < 2) return puts("PST"), void();
        if(h >= 3) return puts("PDT"), void();
            // [02:00:00, 03:00:00)
        return puts("Neither"), void();
    }

    else if(M == 11){
        int nth = get(Y, 11, 1);
        if(D < nth) return puts("PDT"), void();
        if(D > nth) return puts("PST"), void();
        if(h < 1) return puts("PDT"), void();
        if(h >= 2) return puts("PST"), void();
        return puts("Both"), void();
    }
}
  • 标题: CCPC Final 2016 个人题解
  • 作者: Coast23
  • 创建于 : 2026-02-04 18:57:12
  • 更新于 : 2026-02-13 12:04:45
  • 链接: https://coast23.github.io/2026/02/04/CCPC-Final-2016-个人题解/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
CCPC Final 2016 个人题解
  1. A. The Third Cup is Free
  2. B. Wash
  3. D. Game Leader
  4. E. Problem Buyer
  5. G. Pandaland
  6. H. Engineer Assignment
  7. I. Mr. Panda and Crystal
  8. J. Worried School
  9. L. Daylight Saving Time