专栏文章

CSP2025游记（附上代码及挂分原因）

HHsl_Beat
生活·游记参与者 14已保存评论 14

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@minfke0k
此快照首次捕获于
2025/12/02 01:35
3 个月前
此快照最后确认于
2025/12/02 01:35
3 个月前
查看原文
我很菜 不要喷我（可以把我当作赛后娱乐文章）
坐标HA!

J:

-0.5h

到考场了！老师让下载ide怎么没有vscodeaaa
用codeblocks 用了半天c语言文件 一直给我
TEXT
 fatal error: my_header.h: No such file or directory
"<bits/stdc++.h>"

0.5h

秒掉第一题 充满信心

1.3h

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

2.3h

T3读错题 以为是dp 结果发现说要连续
然后写异或的逆运算写了一整年
最后得到了O(nlogn)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(n2)O(n^2)能怎么优化 直接去看T2 抱着T2<T1的决心

2.3h

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

2.7h

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

3.2h

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

3.3h

读T4 T4读错题看成通过人数不小于cjc_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分
CPP
#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分
CPP
#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;
}
T3
CPP
#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分
CPP
#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;
}

评论

共 14 条评论，欢迎与作者交流。

正在加载评论...