← 返回

补题记录

前言

马上CSP了，才发现之前好几次比赛的题目都没补。。。得赶紧加训了，顺便写一篇博客记录一下。

[CSP-S 2024] 超速检测

题目链接

Solution

先考虑问题一，首先，对于每一辆车而言，由于 $v_i,a_i$ 都是定值，所以车辆的速度一定是 单调递增或单调递减 的。（当然也可能是定值）。那么每一辆车超速的范围一定是一段区间，且这段区间可以直接求出来。那么对于每一辆车都可以得到一个对应的区间 $[l_i,r_i]$。那么只要区间范围内存在测速点，该车就会被判定为超速。

那么第一问就可以通过二分判断区间内是否存在测速点解决。

之后考虑问题二，在求出所有的区间 $[l_i,r_i]$ 之后，问题就变成了求解最多需要保留几个测速点，使得对于所有区间 $[l_i,r_i]$，都存在一个测速点。

那么这个问题很显然就是线段覆盖问题，考虑贪心。将区间的右端点从小到大排序，如果线段内没有测速点，选择这个右端点作为测速点。这样显然是最优的。

所以最后的时间复杂度就是 $O(n\log n)$

[CSP-S 2025] 社团招新

题目链接

Description

给定 $n$ 个新成员和 $3$ 个社团，其中第 $i(1\le i\le n)$ 个新成员对社团 $j(1\le j\le 3)$ 的满意度为 $a_{i,j}$。总满意度为所有新成员对所有社团的满意度之和。在满足任意一个社团的成员数量不超过 $n/2$ 的前提下，最大化总满意度。

Solution

考虑贪心，对于每一个新成员，必然优先选择满意度最高的社团。但可能会出现某一社团选择的人数已经超过 $n/2$ 的情况。那么就需要转移一部分成员到其他社团。所以我们需要使得损失的贡献尽可能小，即最大减次大尽可能小。

那么我们只需要贪心选择满意度最高的社团，同时按照最大减次大的值排序即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
// #define NOI_IO
#define vi vector<int>
#define PII pair<int, pair<int, int>>
const int MaxN = 2e5 + 100;
const int INF = 1e9;
const int mod = 1e9 + 7;
int T = 1, N, M;
// int a[MaxN];
struct node
{
    int x, y, z;
} a[MaxN];
inline void Solve()
{
    vi g[10];
    cin >> N;
    int sum = 0;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].z;
        sum += max({a[i].x, a[i].y, a[i].z});
        // if(a[i].x==max({}))
        int x = max({a[i].x, a[i].y, a[i].z});
        // cerr<<cnt<<" ";
        if (x == a[i].x)
        {
            int cnt=min(a[i].x-a[i].y,a[i].x-a[i].z);
            g[1].push_back(cnt);
            cnt1++;
        }
        else if (x == a[i].y)
        {
            int cnt=min(a[i].y-a[i].x,a[i].y-a[i].z);
            g[2].push_back(cnt);
            cnt2++;
        }
        else if (x == a[i].z)
        {
            int cnt=min(a[i].z-a[i].x,a[i].z-a[i].y);
            g[3].push_back(cnt);
            cnt3++;
        }
    }
    // cerr<<endl;
    if (cnt1 <= N / 2 && cnt2 <= N / 2 && cnt3 <= N / 2)
    {
        cout << sum << endl;
        return;
    }
    // cerr << cnt1 << " " << cnt2 << " " << cnt3 << endl;

    int flag = 0;
    if (cnt1 >= cnt2 && cnt1 >= cnt3)
        flag = 1;
    else if (cnt2 >= cnt1 && cnt2 >= cnt3)
        flag = 2;
    else if (cnt3 >= cnt1 && cnt3 >= cnt2)
        flag = 3;
    // cerr << flag << endl;
    sort(g[flag].begin(), g[flag].end());
    for (int i = 0; i < g[flag].size() - N / 2; i++)
    {
        // cerr<<g[flag][i]<<" ";
        sum -= g[flag][i];
    }
    // cerr<<endl;
    cout << sum << endl;
}

signed main()
{
#ifdef NOI_IO
    freopen("club.in", "r", stdin);
    freopen("club.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}

[CSP-S 2025] 道路修复

题目链接

Solution

题目要求将原有的 $n$ 座城市两两连通的最小费用。那么显然需要使用最小生成树来求解。

注意到 $k\le 10$，那么我们可以通过枚举所有的 $2^k$ 种情况，分别求解一次最小生成树。复杂度为 $O(2^k(kn+m)\log(kn+m))$。期望得分 $32$ pts。

考虑优化，首先，我们可以先对原图跑一次最小生成树，可以求出 $N-1$ 条边，显然，剩余的边对于答案一定没用贡献，所以只需要保留这 $N-1$ 条边，并继续枚举 $2^k$ 种情况，每次只需要在这 $N-1$ 条边中选择 $k$ 条边即可。复杂度为 $O(2^kkn\log kn+m\log m)$。期望得分 $64$ pts。

考虑进一步优化，不难发现时间复杂度的瓶颈在排序上，所以我们可以在一开始就先预处理出 $N-1$ 条边和 $kn$ 条边，直接排序，在枚举过程中遇到没有选择的边，就直接跳过即可。复杂度为 $O(2^kkn+kn\log kn+m\log m)$。期望得分 $100$ pts。

Code

#include <bits/stdc++.h>
using namespace std;
// #define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
#define vi vector<int>
#define PII pair<int, int>
const int MaxN = 1e6 + 100;
const int INF = 1e9;
const int mod = 1e9 + 7;
int T = 1, N, M, k;

int a[11][10000 + 5];
int town[11];

struct Edge
{
    int u, v, w;
    int from;
};

struct edge
{
    int u, v, w;
    bool used;
} e[MaxN];

struct DSU
{
    vector<int> fa, sz;
    void init(int n)
    {
        fa.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
    bool join(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (sz[x] < sz[y])
            swap(x, y);
        fa[y] = x;
        sz[x] += sz[y];
        return true;
    }
};

inline void Solve()
{
    cin >> N >> M >> k;
    for (int i = 1; i <= M; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].used = false;
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> town[i];
        for (int j = 1; j <= N; j++)
            cin >> a[i][j];
    }

    vector<int> idx(M);
    iota(idx.begin(), idx.end(), 1);
    sort(idx.begin(), idx.end(), [&](int i, int j)
         { return e[i].w < e[j].w; });

    DSU dsu;
    dsu.init(N);
    vector<Edge> used;
    used.reserve(N - 1);
    int cnt_used = 0;
    for (int id : idx)
    {
        if (dsu.join(e[id].u, e[id].v))
        {
            e[id].used = true;
            cnt_used++;
            used.push_back({e[id].u, e[id].v, e[id].w, 0});
            if (cnt_used == N - 1)
                break;
        }
    }

    sort(used.begin(), used.end(), [](const Edge &A, const Edge &B)
         { return A.w < B.w; });

    vector<vector<char>> keep(k + 1, vector<char>(N + 1, 0));
    for (int t = 1; t <= k; ++t)
    {
        vector<Edge> tmp;
        tmp.reserve(used.size() + N);
        for (auto &be : used)
            tmp.push_back(be);
        for (int v = 1; v <= N; ++v)
            tmp.push_back({N + 1, v, a[t][v], t});
        sort(tmp.begin(), tmp.end(), [](const Edge &A, const Edge &B)
             { return A.w < B.w; });

        DSU d;
        d.init(N + 1);
        int need = N + 1;
        for (auto &ed : tmp)
        {
            if (d.join(ed.u, ed.v))
            {
                if (ed.u == N + 1)
                    keep[t][ed.v] = 1;
                else if (ed.v == N + 1)
                    keep[t][ed.u] = 1;
                if (--need == 1)
                    break;
            }
        }
    }

    vector<Edge> c;
    c.reserve(used.size() + k * N);
    for (auto &be : used)
        c.push_back(be);
    for (int t = 1; t <= k; ++t)
        for (int v = 1; v <= N; ++v)
            if (keep[t][v])
                c.push_back({N + t, v, a[t][v], t});

    sort(c.begin(), c.end(), [](const Edge &A, const Edge &B)
         { return A.w < B.w; });

    ll ans = (ll)4e18;
    int ALL = 1 << k;
    for (int mask = 0; mask < ALL; ++mask)
    {
        int towns = __builtin_popcount((unsigned)mask);
        DSU d;
        d.init(N + k);
        int pps = N + towns;
        ll sum = 0;
        if (towns)
        {
            for (int t = 1; t <= k; ++t)
                if ((mask >> (t - 1)) & 1)
                    sum += town[t];
        }
        for (auto &ed : c)
        {
            if (ed.from == 0)
            {
                if (d.join(ed.u, ed.v))
                {
                    sum += ed.w;
                    if (--pps == 1)
                        break;
                }
            }
            else
            {
                int t = ed.from;
                if (!((mask >> (t - 1)) & 1))
                    continue;
                if (d.join(ed.u, ed.v))
                {
                    sum += ed.w;
                    if (--pps == 1)
                        break;
                }
            }
        }
        if (pps == 1)
            ans = min(ans, sum);
    }

    cout << ans << endl;
}

signed main()
{
#ifdef NOI_IO
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}

本文采用 CC BY-NC 4.0 许可协议，转载请注明出处并保持非商业用途。