CSP-J/S 2025 游记

· · 生活·游记

上午和下午都考了，考场在 rdfz。

成绩等出分了再写。

Day -1

在机房闲的没事干，默写了 3 遍 Dinic。

Day 0

下午在机房里写思维题，无所事事（

17:00 的时候去跟 ztr 吃大餐了，爽！

Day 1

早上起来之后肚子疼（ww呜呜呜

大概 7:40 左右出发，从 bnds 去 rdfz。普及组目标是 AK。

8:30

准时收到压缩包密码，顺利解压。

先开始看第一题，一眼把所有数找出来排序就好了。

8:45

第一题交了，开始看第二题。

这个时候肚子开始发作了...但我喝了口冰红茶就活过来了。

一眼排序求出排名 rank，然后好像可以算位置（？）

随手推了一下，三个样例就都过了。

然后想测大样例的，结果没有（无语...

只能交了看 T3。

9:00

打开 T3，一边读题一遍思考。

第 0.1 秒想到了异或这个东西可以求前缀异或然后直接查区间异或和。

第 0.2 秒想到了选不相交区间这个很典的贪心是按右端点选择。

第 0.3 秒想到了可以开桶来计算对于每个右端点，左端点最大是多少。

第 0.4 秒开始写代码。

第 1200 秒过了所有大样例并提交。

9:20

猛灌一口冰红茶，准备面对 T4（能否 AK 的关键。

打开之后，发现是计数题目。简单想了一下，好像可以令 dp_{i, sum, max} 表示状态，但复杂度是立方的。

在草稿纸上推了好久也没推出来。

本来打算写个部分分跑路，但不甘心不 AK。。。

然后接着想，突然发现 n \leq 5000 好像说明并不一定要纯 dp。

感觉自己在一瞬间悟了，可以枚举最大值是谁，剩下的可以 dp 统计！

然后开始写代码，在 10:00 之前过了所有大样例。

10:00

已经写完了 4 道题的正解，很开心，但肚子发作了。

赶紧去厕所里蹲了半小时。

10:30

回到座位，一边仔细检查，一边坐牢。。。

12:00

出考场了，感觉心情不错。

交流了一下，tyq 说 T1 开个桶就行，这才发现不用排序...

回家后准备睡觉，希望下午肚子不发作。

12:30

到家了。

开始睡觉。

14:30

开始考提高组。

打开 T1，发现不是签到题。

当时以为跟去年 NOIP 一样难度乱序，就把所有题都读了一遍，结果真的没有签到题。

只能开始仔细思考 T1。突然发现如果只有 2 组，就是一个非常典的悔贪。

然后继续想，发现如果最大值在第一组的人超过了 \frac{n}{2}，那么另外两组的人就可以随便选了。

因此假设存在一个组（不妨设为 a 组），最大值在这一组的人超过了 \frac{n}{2}，则可以转化成只有 2 组的情况，两个权值分别为 a 和 \max(b,c)！

然后写了个很典的优先队列悔贪就过大样例了。

15:30

开始看 T2，但是不会。

先随手写了一个 Kruskal + 暴搜的部分分，然后就不会了。

仔细思考了一下，想不出正解，这个时候已经过去了将近 1h，只能把特殊性质 A 打出来然后看 T3。

16:30

T3 想不出正解，开始写部分分。

发现了可以 Hash 然后暴力匹配，然后写了一个复杂度玄学的代码，但根据大样例，结果是对的。

这个时候距离考试结束只剩 30 分钟了，赶紧去看 T4。

18:00

快速浏览 T4，发现可以直接全排列，就迅速打完了。

18:30

考完了。

听 tyq 说 T1 按照最大值和次大值的差排序就好了，吓了一跳。

后来仔细思考了一下发现我是对的，嘻嘻

19:00

到家了。

开始睡觉。

22:00

一直在担心普及组能不能 AK，提高组能不能 1= ......

心里很慌，于是爬起来按照记忆复现了一下自己普及组的代码，复现的时候不看题面直接背出来了代码（每道题代码不超过 1.03KB

然后心里很开心嘻嘻：

（希望考场代码没写挂）

附代码（赛后背诵的代码，并非考场真实代码）：

T1

#include<bits/stdc++.h>
using namespace std;
int a[1000005], tot;
inline bool cmp(int x, int y){
    return x > y;
}
signed main(){
    string s; cin >> s;
    for(int i = 0; i < (int)s.length(); i++){
        if(isdigit(s[i])){
            a[++tot] = s[i] - '0';
        }
    }
    sort(a + 1, a + 1 + tot, cmp);
    for(int i = 1; i <= tot; i++) cout << a[i];
    cout << '\n';
    return 0;
}

T2

#include<bits/stdc++.h>
using namespace std;
int n, m, a[105];
inline bool cmp(int x, int y){
    return x > y;
}
signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n * m; i++) cin >> a[i];
    int R = a[1], rank;
    sort(a + 1, a + 1 + n * m, cmp);
    for(int i = 1; i <= n * m; i++){
        if(a[i] == R){
            rank = i;
            break;
        }
    }
    int c = ceil(1.0 * rank / n), r;
    if(c & 1){
        r = rank - (c - 1) * n;
    }else{
        r = n - (rank - (c - 1) * n) + 1;
    }
    cout << c << ' ' << r << '\n';
    return 0;
}

T3

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, k, a[500005], pre[500005], box[1 << 20], maxl[500005];
signed main(){
    n = read(), k = read();
    for(int i = 1; i <= n; i++){
        a[i] = read();
        pre[i] = pre[i - 1] ^ a[i];
    }
    for(int i = 0; i < (1 << 20); i++) box[i] = -1;
    box[pre[0]] = 0;
    for(int i = 1; i <= n; i++){
        int need = pre[i] ^ k;
        if(box[need] != -1){
            maxl[i] = box[need] + 1;
        }else{
            maxl[i] = -1;
        }
        box[pre[i]] = max(box[pre[i]], i);
    }
    int nowr = 0, cnt = 0;
    for(int i = 1; i <= n; i++){
        if(maxl[i] != -1){
            if(maxl[i] > nowr){
                cnt++;
                nowr = i;
            }
        }
    }
    cout << cnt << '\n';
    return 0;
}

T4

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
const int Mod = 998244353;
int n, a[5005], dp[5005][5005];
signed main(){
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    sort(a + 1, a + 1 + n);
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 5001; j++){
            dp[i][j] = (dp[i][j] + dp[i - 1][j] + dp[i - 1][max(0ll, j - a[i])]) % Mod;
        }
    }
    int ans = 0;
    for(int i = 3; i <= n; i++){
        ans = (ans + dp[i - 1][a[i] + 1]) % Mod;
    }
    cout << ans << '\n';
    return 0;
}

Day 2 ~ 4

复习段考。

最终成绩

Upd on 2025.11.5 19:30

J：100 + 100 + 100 + 100 = 400

S：100 + 56 + 25 + 8 = 189

Day 5

要去 NOIP 集训了。