CSP2025游记（最废物的一年）

Hsl_Beat · 2025-11-01 21:05:52 · 生活·游记

我很菜不要喷我（可以把我当作赛后娱乐文章）

坐标HA!

J:

-0.5h

到考场了！老师让下载ide怎么没有vscodeaaa

用codeblocks 用了半天c语言文件一直给我

 fatal error: my_header.h: No such file or directory
"<bits/stdc++.h>"

0.5h

秒掉第一题充满信心

1.3h

秒掉第二题生怕自己行列看错挂分

2.3h

T3读错题以为是dp 结果发现说要连续

然后写异或的逆运算写了一整年

最后得到了O(n log n)勾史解法大样例过了

2.7h

第四题写出了50分的暴力然后发现T4不会了

3.2h

写背包然后炸了

3.45h

写不完了只能交50分的了

然后考场乱起来了，同桌跟我讨论T4 我说50分很简单啊排列组合就可以了然后剩1.3min 发现自己comb函数没写阶乘和逆元预处理因为我发现没有满足特殊性质的大样例

3.49h

ohohoh写完了提交了差点挂分

350分遗憾离场大家怎么都AK了就我没AK（

S：

0.5h

读T1 发现贪不了认为还是有希望的

1.3h

死磕dp 没有发现O(n^2)能怎么优化直接去看T2 抱着T2<T1的决心

2.3h

T2读错题以为添加了乡村，每个与城市的连边都要加上c_j，然后忘记了kruskal会把乡村也放到最小生成树里

2.7h

比赛过半想着用最短路优化T2结果复杂度算错以为不行发现自己没有AC任何题崩溃了放弃T2 开始佛系

3.2h

读T3 T3读错题读成可以替换多次写了半天样例不过一看没时间了糊了个10分暴力上去

3.3h

读T4 T4读错题看成通过人数不小于c_j（认为，这面试过这么多人了我还面试个头啊没名额了）然后写了半天开始尝试状压

3.5h

状压n=10可过 n=18RE了这个时候老师和广播疯狂的宣布“比赛即将结束，不要忘记提交代码然后点确认提交哦” 心态彻底崩溃

3.9h

T4不想调了去看T2 发现想到了正解结果没写完（提交代码后把本地的代码文件不知道什么时候删掉了aaa）

4.0h

140分遗憾离场

晚上回到家

ABC故意出这么简单是嘲讽谁呢

aaa怎么全世界都Jak了 S写出了T1aaa

10分代码打赏(S)

T1 死因少打半边引号为啥电脑要装10个输入法挂55分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
    int a, b, c;
};
ll dp1[222][222], dp2[222][222];
bool cmp(node a, node b)
{
    return a.a > b.a;
}
void solve()
{
    int n;
    cin >> n;
    vector<node> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i].a >> v[i].b >> v[i].c;
    }
    if (n == 100000) {
        sort(v.begin(), v.end(), cmp);
        int ans = 0;
        for (int i = 1; i <= (n / 2); i++) {
            ans += v[i].a;
        }
        cout << ans;
        return;
    }
    for (int i = 1; i <= n; i++) {
        memset(dp2, 0, sizeof(dp2));
        for (int j = ((i + 1) / 2) + 10; j >= 0; j--) {
            for (int k = ((i + 1) / 2) + 10; k >= 0; k--) {
                if (i - j - k > ((i + 1) / 2)) {
                    break;
                }
                if (j > 0) {
                    dp2[j][k] = max(dp2[j][k], dp1[j - 1][k] + v[i].a);
                }
                if (k > 0) {
                    dp2[j][k] = max(dp2[j][k], dp1[j][k - 1] + v[i].b);
                }
                if (i - j - k > 0) {
                    dp2[j][k] = max(dp2[j][k], dp1[j][k] + v[i].c);
                }
            }
        }
       memcpy(dp1, dp2, sizeof(dp2));
    }
    ll ans = 0;
    for (int i = 0; i <= (n / 2); i++) {
        for (int j = 0; j <= (n / 2); j++) {
            ans = max(ans, dp1[i][j]);
        }
    }
    cout << ans << '\n';
}
int main()
{
    freopen("club.in", "r", stdin);
    freopen("club.out, "w", stdout);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

T2 死因 kruskal函数里y指状态 219和222行变量名打成i 后面我忘记减一挂84分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int fa[1111111], n, m, k;
struct node{
    int u, v, w;
}edges[3333333];
int cnte;
void init()
{
    for (int i = 1; i <= n + k + 10; ++i) {
        fa[i] = i;
    }
}
int find(int x)
{
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}
void merge(int a, int b)
{
    a = find(a);
    b = find(b);
    fa[a] = b;
}
bool same(int a, int b)
{
    if (a == b) {
        return 1;
    }
    return find(a) == find(b);
}
bool cmp(node a, node b)
{
    return a.w < b.w;
}
int kruskal(int x, int y)
{
    init();
    ll cnt = 0, res = 0;
    for (int i = 0; i < cnte; ++i) {
        if (edges[i].u > n && !((i >> (edges[i].u - n)) & 1)) {
            continue;
        }
        if (edges[i].v > n && !((i >> (edges[i].v - n)) & 1)) {
            continue;
        }
        if (!same(edges[i].u, edges[i].v)) {
            merge(edges[i].u, edges[i].v);
            cnt++;
            res += edges[i].w;
        }
        if (cnt == x - 1) {
            break;
        }
    }
    return res;
}
int main()
{
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[cnte++] = {u, v, w};
    }
    vector<vector<int>> c(k + 1, vector<int>(n + 1));
    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j <= n; ++j) {
            cin >> c[i][j];
        }
    }
    for (int j = 1; j <= k; ++j) {
        for (int l = 1; l <= n; ++l) {
            edges[cnte++] = {n + j, l, c[j][l]};
        }
    }
    ll ans = LLONG_MAX;
    sort(edges, edges + cnte, cmp);
    for (int i = 0; i < (1 << k); ++i) {
        ll cnt = 0, cntt = 0;
        for (int j = 1; j <= k; ++j) {
            if ((i >> (j - 1)) & 1) {
                cnt++;
                cntt += c[j][0];
            }
        }
        ans = min(ans, kruskal(n + cnt, i) + cntt);
    }
    cout << ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
signed main()
{
    freopen("replace.in", "r", stdin);
    freopen("replace.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    unordered_map<string, string> mp;
    vector<string> v;
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        mp[a] = b;
        v.push_back(a);
    }
    bitset<1111111> vis;
    while (q--) {
        string s1, s2;
        cin >> s1 >> s2;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j + v[i].length() - 1 < s1.length(); j++) {
                string tp = s1;
                if (tp.substr(j, v[i].length()) == v[i]) {
                    tp.erase(j, v[i].length());
                    tp.insert(j, mp[v[i]]);
                    ans += (tp == s2);
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

T4 死因注释文件输入输出挂8分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
signed main()
{
    //freopen("employ.in", "r", stdin);
    //freopen("employ.out, "w", stdout);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> p;
    for (int i = 0; i < n; i++) {
        p.push_back(i);
    }
    ll ans = 0;
    do {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (i - cnt >= a[p[i]]) {
                continue;
            }
            cnt += (s[i] == '1');
        }
        ans += (cnt >= m);
        ans %= 998244353;
    } while (next_permutation(p.begin(), p.end()));
    cout << ans;
    return 0;
}