CSP-S 2025 挂分记

· · 生活·游记

いいな　いいなと　欲しがってたのに
夢は遠くて　現実ばっかで :::align{right} 嘴上说着真好啊　真好啊　分明是如此渴望
可梦想触不可及　现实依旧如此 :::

好耀眼。

省流：预估 100 + 0 + 10 + 8 = 118 \text{ pts}，实际 100 + 0 + 25 + 0 = 125 \text{ pts}。

啊，这绝望的轮回！让我想到了去年，第一轮一等奖，第二轮二等奖，NOIP 三等奖。难道今年也要重蹈覆辙吗？

停课三天。

Day -2

上午打神秘模拟赛，好敷衍的题面和大样例。

获得了 100 + 60 + 0 + 40 = 200 的好成绩。

下午看题解补题。补了两题就不想补了。

回宿舍跟舍友聊了一晚上现状，竞赛还是太难了。

Day -1

上午是我组织的模拟赛，写模拟赛的题解。

下午讲题。哦草，我怎么不会 dp？

晚上被教练拉去机构打模拟赛。哦草，垃圾样例，全过了也只有 45 pts。后面的全都不会。喜提 70 pts。

回宿舍，听同学说语文老师搞了默写小测，50 个空，错 3 个要重新默写。哦草。

Day 0

补题，写题解，什么都没有复习。

讲了下注意事项，又听了他人讲的注意事项。

Day 1 上午

看了航模表演，还是什么都没有复习。

坐校车出发，好困。

Day 1 下午

又回到了考 NOIP 2024 的考场，有点怀念啊。

压缩包密码（貌似）是 Ren5Jie4Di4Ling5%，人皆第零……？我不理解。赛后才知道是人皆爆零。

提前 3 分钟开始比赛。

先找监考要了 3 张草稿纸，怎么有监考整个了大波浪呢，还是个男的。

花了 40 分钟阅读所有题面并试图简化题意，怎么都有点抽象啊。

好吧，来看看 T1，手玩了一下样例，又看了眼特殊性质。觉得 > \dfrac{n}{2} 的限制很烦，直接放弃限制，让超出的社团的人跳槽。

/*
15:13
若无 > n/2，皆大欢喜。
最多只有一个部门会 > n/2，考虑让他跳槽。
否则，设立优先队列，
找到变化量（前 - 后）最小的(且未满, never exists)的那个部门跳槽。
做一次即可，因为不会再出现 > n/2 的情况了。
15:34 end!!!!!
*/

真好。看看 T2，写了个 Kruskal 板子放着。以为乡村和城市是同一个点，硬控了一小下。

放着，看 T3，写了个无法描述复杂度的暴力，期望 10 pts。

T4 写了个 O(n!) 暴力，然后看特殊性质 A，觉得有些麻烦。

再看回 T2，冲特殊性质 A，哦草，为什么输出的比答案要小啊。

只剩下两分钟，还是没有调出来，投降喵。只好整理文件，准备结束。

Day 1 晚上

:::info[教练在路上发现的神秘小卡片]

:::

原来 T4 的 A 性质这么好骗吗，哦草。好像并没有那么好骗。

跟教练和其他同学去外面吃饭。回到家已经十点多了。

Day inf

赛后突然回忆起 T2，当时大概是这么写的。

直接看源代码吧。

:::error[请你在 0.1 s 内找到错误]

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;

const int N = 1e4 + 15, M = 1e6 + 7, MM = 2e6 + 7, K = 12;
const ll INF = 2e18;

int c[K], a[K][N];
// int freeCity[K];

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

bool cmp (Edge A, Edge B) {
    if (A.w == B.w) {
        if (A.u == B.u) return A.v < B.v;
        return A.u < B.u;
    }
    return A.w < B.w;
}

Edge given_edges[M], cur_edges[MM];

struct unionSet {
    int fa[N];

    int findfa(int u) {
        return (fa[u] == u) ? (u) : (fa[u] = findfa(fa[u]));
    }

    void reset(int n) {
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
    }
} uset;

ll kruskal(int n, int cur_m) {
    uset.reset(n);
    sort(cur_edges + 1, cur_edges + cur_m + 1, cmp);
    ll costs = 0;
    int cnt = 0;
    for (int i = 1; i <= cur_m; i++) {
        if (cnt == n - 1) break; // is a tree
        auto [u, v, w] = cur_edges[i];
        if (u != v && uset.findfa(u) != uset.findfa(v)) {
            costs += w;
            uset.fa[u] = v;
            cnt++;
        }
    }
    return costs;
}

void sub1to4(int n, int m) {
    for (int i = 1; i <= m; i++) {
        cur_edges[i] = given_edges[i];
    }
    ll res = kruskal(n, m);
    printf("%lld\n", res);
    return;
}

void subA(int n, int m, int k) {
    // puts("A");
    int cur_m = m;
    for (int i = 1; i <= m; i++) {
        cur_edges[i] = given_edges[i];
    }
    for (int i = 1; i <= k; i++) {
        int freeCity = -1;
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 0) {
                freeCity = j;
                break;
            }
        }
        for (int j = 1; j <= n; j++) {
            if (j == freeCity) continue;
            cur_m++;
            cur_edges[cur_m] = {freeCity, j, a[i][j]};
        }
    }
    ll res = kruskal(n, cur_m);
    printf("%lld\n", res);
    return;
}

int main() {
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);
    int n, m, k;
    bool is_A = true;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        given_edges[i] = {u, v, w};
    }

    for (int i = 1; i <= k; i++) {
        scanf("%d", &c[i]);
        if (c[i] != 0) is_A = false;
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    // puts("A");
    // printf("%d\n", is_A);

    if (k == 0) {
        sub1to4(n, m);
        return 0;
    }

    if (is_A) {
        subA(n, m, k);
        return 0;
    }

    ll min_costs = INF;

    for (int subset = 0; subset < (1 << k); subset++) {
        ll cur_costs = 0;
        int cur_m = m;
        int towns = 0;
        for (int i = 1; i <= m; i++) {
            cur_edges[i] = given_edges[i];
            // printf("%d: link(%d, %d, %d)\n", i, u, v, w);
        }
        for (int j = 0; j < k; j++) {
            if (subset & (1 << j)) {
                // select "TOWN" (j+1) to upgrade
                int idx = j + 1;
                for (int i = 1; i <= n; i++) {
                    cur_m++;
                    cur_edges[cur_m] = {n + towns + 1, i, a[idx][i]};
                    // printf("%d: link(%d, %d, %d)\n", cur_m, n + towns + 1, i, a[idx][i]);
                }
                towns++;
                cur_costs += c[idx];
                // printf("+= %d\n", c[idx]);
            }
        }

        cur_costs += kruskal(n + towns, cur_m);
        // printf("cur_cost = %lld\n", cur_costs);
        min_costs = min(min_costs, cur_costs);
    }

    printf("%lld\n", min_costs);
    return 0;
}

/*
15:40 start

16:36 16pts..?!
18:25 speA cannot do it
*/

:::

不 vp 模板赛导致的。哦草。

把那一行修改了一次重测，56 pts，哦草。

:::success[你真找不到错误？]

你在合并什么？！不合并根节点导致的。

:::

没想到 T4 CE 了，我的 8 pts 也打水漂了。

总结

最像 NOIP 的一次 CSP-S，也算是为真正的 NOIP 积累赛时经验吧。最后一次了。

我必须说出来，这最后的台词……