CSP-S 2025 游记

Skmqwq · 2025-11-08 10:57:30 · 生活·游记

在比赛前 20 天来到 ssf 北校区集训，被虐了，也不知道哪来的自信，相信自己一定能上 300。

10.31 回到苏州，摆了一天，写了个三维偏序板子，然后开始颓，颓了一天，晚上胡乱整理了一下考试用品（事实证明这是错的），然后睡了。

睡得不错，早起赶火车，在火车站看到了 Syx 竟然在看题，真是太不可思议了，为了攒rp学习 Syx 的精神，我也开始看题，上了火车，坐在 Syx 旁边，他直接开始看文了( ，唐。那我肯定还是要攒rp学习，看了一车典中典贪心，反贪（事实证明这是对的），比如 超级钢琴，加法，南园满地轻堆絮。

下车，坐车到了南航，看到了 sz 的大部队，%%%。然后吃饭，然后睡觉，后面忘了。

买了杯咖啡，进场。南航竟然有扶手电梯，真是太厉害了。不过它的厕所为什么是在机房里面的（难过）。试机：为什么我的鼠标滚轮是鬼畜型的！一开始工作人员不给我换（真是太不负责任了），后来在我百般刁难求情下才给我换了一个正常鼠标。

考试开始：14:30-14:40，在读 t1 的同时喝完了一杯咖啡，爽。14:35 会的 t1 的 nlogn，不过因为咖啡还没喝完，就再验证了一下（t1 竟然是反贪！照应上文），15:09 过的 t1，其实是被 freopen 的神奇 warning 卡了 10 min，最后的代码如下。 ::::info[club]

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mkp make_pair
#define fi first
#define se second
#define vi vector<int>
#define eb emplace_back
#define pb push_back
#define debug() printf("Skmqwq\n")
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
using namespace std;
inline void smax(int &a, int b) { a = max(a, b); }
inline void smin(int &a, int b) { a = min(a, b); }

const int N = 1e5 + 7;
int t, n, ans = 0;

struct node {
    int a, id1, b, id2, c, id3;
}a[N];
struct element {
    int x;
    bool operator<(const element A) const {
        return a[x].b > a[A.x].b;
    }
};

bool cmp(node a, node b) {
    return a.a > b.a;
}

void Solve() {
    cin >> n;
    rep(i, 1, n) {
        cin >> a[i].a >> a[i].b >> a[i].c;
        a[i].id1 = 1, a[i].id2 = 2, a[i].id3 = 3;
        if (a[i].a < a[i].b) swap(a[i].a, a[i].b), swap(a[i].id1, a[i].id2);
        if (a[i].b < a[i].c) swap(a[i].b, a[i].c), swap(a[i].id2, a[i].id3);
        if (a[i].a < a[i].b) swap(a[i].a, a[i].b), swap(a[i].id1, a[i].id2);
    }
    sort(a + 1, a + 1 + n, cmp);
    ans = 0;
    priority_queue<int> Q[4];
    rep(i, 1, n) {
        int id = a[i].id1, val = a[i].a;
        ans += val;
        Q[id].push(a[i].b - a[i].a);
        if ((int)Q[id].size() > (n >> 1)) {
            int tp = Q[id].top(); Q[id].pop();
            ans += tp;
        }
    }
    cout << ans << '\n';
}

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

    freopen("club.in", "r", stdin);
    freopen("club.out", "w", stdout);

    cin >> t;
    while (t--) Solve();

    return 0;
}
/*
3
4
4 2 1
3 2 4
5 3 4
3 5 1
4
0 1 0
0 1 0
0 2 0
0 2 0
2
10 9 8
4 0 0
*/

::::

好的来看 t2，上来就读错题了，以为乡村和城市是一个东西，看成唐题了，不过及时发现了，问题不大。想了一会，一下子就会特殊性质，这不直接把每一个新点 i 的所有边挂到那个 a_{i, j} = 0 的旧点上跑 kruskal就做完了吗，10min 糊完了，过了大样例，然后继续想，想了 15min 没有头猪，上了个厕所去看后面了。

回来看 t3 读完题啥也不会，感觉如果一个 s_i 是另一个 s_j 的子串就可以不断转换，形如递归一样的东西，不好做，跑了。看 t4，读完题，立马想到二项式反演，设 f_i 表示钦定 i 个录取的方案，g_i 表示恰好 i 个录取的方案，ans = \sum_{i=m}^{n} g_i，然后发现不可推，因为有后效性？（凡是这种前面会影响后面的题我一到也没切出来过，所以该加训了！），然后想了 10min dp 不会就跑了。

此时有点慌了，毕竟现在才 148，按照 js 历年的分数线必然拿不到 1= ，必须把 t2 切了。接着就开始想 t2，也想过 2^k 枚举，不过看到 m 的范围就放弃了（也没忘约束边数去想），在结束前 1h 想到可以把一个新点看成加入了 n^2 条边，这其中只有 n - 1 条是有用的，所以只需加入 O(n) 量级的边数就行，不过我场上没想到什么 O(n) 复杂度内快速且准确的确定前 n - 1 小的边，不过我会乱搞，一通乱搞之下应该对了吧（?），最终复杂度 O(knlogn + (m + nk)log_{m+nk})，不过正确性是 random，而且最后一个大样例怎么也过不了。

18:15，开始急了，疯狂地乱搞，疯狂地堆砌常数来试图增加正确性。

18:25，因为我的判断失误，导致我没有时间将那分我认为的正解（只过了前三个样例）和那份我认为稳 48 分的代码拼在一起，接下来就是本场最重要的抉择：48 \ or \ rand[0,100]，我想到 js 的分数线一向很高，感觉 48 必然不能 1=，于是心一横，交了那分 random 的，出了考场感觉 t2 t4 被过穿了，更慌了。

t2 最终代码如下： ::::info[road]

  #include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mkp make_pair
#define fi first
#define se second
#define vi vector<int>
#define eb emplace_back
#define pb push_back
#define debug() printf("Skmqwq\n")
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
using namespace std;
inline void smax(int &a, int b) { a = max(a, b); }
inline void smin(int &a, int b) { a = min(a, b); }

const int N = 1e4 + 7, M = 3e6 + 7, K = 15;
int n, m, kk, c[K], fa[N], vis[N], ans = 0, cnt = 0;
pii a[K][N];
struct Edge {
    int u, v, val, id;
    bool operator<(const Edge A) const {
        return val < A.val;
    }
}E[M];
priority_queue<Edge> Q;

void init() {
    rep(i, 1, n) fa[i] = i;
}
int find(int x) {
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
void merge(int x, int y) {
    fa[find(x)] = find(y);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // printf("Skmqwq");

    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);

    // debug();
    cin >> n >> m >> kk;
    rep(i, 1, m) {
        cin >> E[i].u >> E[i].v >> E[i].val;
        E[i].id = 0;
    }
    rep(i, 1, kk) {
        cin >> c[i];
        rep(j, 1, n) cin >> a[i][j].fi, a[i][j].se = j;
        sort(a[i] + 1, a[i] + 1 + n);
        rep(j, 1, min(n, (int)ceil(sqrt(n << 1)))) rep(k, 1, min(n, (int)ceil(sqrt(n << 1)))) if (j != k) {
            Edge tmp;
            tmp.u = a[i][j].se, tmp.v = a[i][k].se;
            tmp.val = a[i][j].fi + a[i][k].fi + c[i];
            tmp.id = i;
            E[++m] = tmp;
        }
        rep(j, 2, n) {
            Edge tmp;
            tmp.u = a[i][1].se, tmp.v = a[i][j].se;
            tmp.val = a[i][1].fi + a[i][j].fi + c[i];
            tmp.id = i;
            E[++m] = tmp;
        }
        rep(j, 3, n) if (j != 2) {
            Edge tmp;
            tmp.u = a[i][2].se, tmp.v = a[i][j].se;
            tmp.val = a[i][2].fi + a[i][j].fi + c[i];
            tmp.id = i;
            E[++m] = tmp;
        }
        rep(j, 1, n - 1) {
            Edge tmp;
            tmp.u = a[i][j].se, tmp.v = a[i][j + 1].se;
            tmp.val = a[i][j].fi + a[i][j + 1].fi + c[i];
            tmp.id = i;
            E[++m] = tmp;
        }
        // printf("%lld", m);
    }

    sort(E + 1, E + 1 + m);
    init();
    rep(i, 1, m) {
        if (!Q.empty() && Q.top().val < E[i].val) {
            Edge tp = Q.top(); Q.pop();
            int u = tp.u, v = tp.v, val = tp.val;
            if (find(u) == find(v)) continue;
            ans += val, ++cnt;
            merge(u, v);
        } else {
            int u = E[i].u, v = E[i].v, val = E[i].val, id = E[i].id;
            if (find(u) == find(v)) continue;
            ans += val, ++cnt;
            merge(u, v);
            if (id && !vis[id]) {
                vis[id] = 1;
                rep(j, 1, min(n, (int)ceil(sqrt(n << 1)))) rep(k, 1, min(n, (int)ceil(sqrt(n << 1)))) 
                if (j != k) {
                    Edge tmp;
                    tmp.u = a[id][j].se, tmp.v = a[id][k].se;
                    tmp.val = a[id][j].fi + a[id][k].fi, tmp.id = 0;
                    Q.push(tmp);
                }
                rep(j, 2, n) {
                    Edge tmp;
                    tmp.u = a[id][1].se, tmp.v = a[id][j].se;
                    tmp.val = a[id][1].fi + a[id][j].fi;
                    tmp.id = 0;
                    Q.push(tmp);
                }
                rep(j, 1, n) if (j != 2) {
                    Edge tmp;
                    tmp.u = a[id][2].se, tmp.v = a[id][j].se;
                    tmp.val = a[id][2].fi + a[id][j].fi;
                    tmp.id = 0;
                    Q.push(tmp);
                }
                rep(j, 1, n - 1) {
                    Edge tmp;
                    tmp.u = a[id][j].se, tmp.v = a[id][j + 1].se;
                    tmp.val = a[id][j].fi + a[id][j + 1].fi;
                    tmp.id = 0;
                    Q.push(tmp);
                }
            }
        }
        if (cnt == n - 1) break;
    }
    cout << ans << '\n';

    return 0;
}

::::

出来听说分数线可能低于 48 的时候后悔了，一个信息差导致了我的激进的行为（不过感觉如果知道我还是会那么干），唉，明年再来。

在大巴车上发现我的乱搞至少可以过 1 \sim 4 的测试点，至少有 16 分，感觉好点。

大巴车开得很颠，而且高速出口坏了，只能从下面走，从南京到苏州开了整整四个半小时，左边的 Syx 一直在喊耳朵炸了，下了车又开始问候司机祖宗十八代，唐。

到了家发现我的乱搞如果没写挂的话在有特殊性质的时候应该是有正确性的，所以至少 48 分，不过我感觉写挂的可能性更大，唉。

最终期望得分 100 + [48, 100] + 0 + 0 = [148, 200]，实际得分：100 + 64 + 0 + 0 = 164。

得知 ysy 大佬 229，zjh 大神 197 感觉爆完了。

唉，该加训了，希望 noip 翻盘！