CSP-J/S 2026 游记

· · 生活·游记

Preface

今年简直是惊心动魄的一年,一波三折。

CSP 之前 whk 有点下滑,导致 FM 一直压力我,没时间碰 OI(埋下伏笔)。

J1 & S1

来到 NBFLS(宁外)。

J 组没啥好说的,感觉稳过。

中午去 NBFLS 的食堂吃饭,不得不说比我们学校好吃。

S 组开始乱搞,前面都还行,就是完善程序不知道在干啥,本来最后一大题写的是对的,但是最后几分钟感觉不对,把对的 3 道全部改错。

J 过了。S 59,差一分。

有趣的事情发生了,发现 省组织单位预留部分奖励名额,遂发邮件,结果 S 给我过了。

J2 & S2

酒店和去年是一样的。

J2

密码 Trick||Treat! 牛逼,才发现是万圣节。

T1

开题,发现 T1 是签到题,秒了。但是急于开 T2,没去注意特殊性质,过掉了所有大样例。(埋下伏笔)。 :::info[Code]

#include<bits/stdc++.h>
using namespace std;
string c1,s1,c2,s2;
inline bool check1(){return c1==c2;}
inline bool check2(){return s1.substr(0,2)==s2.substr(0,2);}
inline bool check3(){return (s1[2]>='A'&&s1[2]<='C'&&s2[2]>='A'&&s2[2]<='C')||((s1[2]>='D'&&s1[2]<='F'&&s2[2]>='D'&&s2[2]<='F'));}
inline bool check4(){return abs(s1[2]-s2[2])==1;}
int main(){
    freopen("travel.in","r",stdin);
    freopen("travel.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>c1>>s1>>c2>>s2;
    cout<<check1()<<(check1()&&check2())<<(check1()&&check2()&&check3())<<(check1()&&check2()&&check3()&&check4());
    return 0;
}
/*
By ZJ-J00357.
Luogu UID:1086453.
*/

:::

T2

看到回文直接想到 \mathcal O(n) 判,看完数据范围发现不能拆开字符串。

在草稿纸上写了几个假的做法,最后终于想到了可以用双指针模拟。

写的时候怎么也调不对,使用 cerr 逐个排查最后才发现我 string 了个 s,然后读入时使用了 cin>>s[i],炸掉了。

过掉了所有大样例。

个人认为代码很清新易懂。 :::info[Code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
long long n,a[maxn],ans;
string s=" ";
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        char c;cin>>a[i]>>c;
        s+=c;
    }
    int l=1,r=n;
    while(l<=r){
        if(a[l]>a[r]){
            if(s[l]!=s[r]) ans+=a[r];
            a[l]-=a[r],r--;
        }else if(a[l]<a[r]){
            if(s[l]!=s[r]) ans+=a[l];
            a[r]-=a[l],l++;
        }else{
            if(s[l]!=s[r]) ans+=a[l];
            l++,r--;
        }
    }
    cout<<ans;
    return 0;
}
/*
By ZJ-J00357.
Luogu UID:1086453.
*/

:::

T3

随便写了个背包 DP,发现假了,其实自己也感觉没啥道理。

正当我想放弃时,我突然想到了平常大洛谷比赛的经验——拆位贡献,遂想,秒了。

然后发现没过样例,模拟后发现应该是不断收缩可用元素的,不能让上一轮没参加的加入到这一轮来,应当优先选高位。 :::info[Code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,m,a[maxn],ans;
bool f[maxn];
int main(){
    freopen("and.in","r",stdin);
    freopen("and.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=30;i>=0;i--){
        int res=0;
        vector<int>t;
        for(int j=1;j<=n;j++){
            if(f[j]) continue;
            if(a[j]&(1<<i)) res++;
            else t.push_back(j);
        }
        if(res>=m){
            ans+=(1<<i);
            for(int v:t) f[v]=1;
        }
    }
    cout<<ans;
    return 0;
}
/*
By ZJ-J00357.
Luogu UID:1086453.
*/

:::

T4

距离考试结束仅剩 1h,AK 的欲望过大,导致我想了 30 分钟正解,发现想不出,赶紧打 \mathcal O(n^3) 暴力,但是死活调不出来,遗憾离场。 :::info[Code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5,maxm=3e5+5;
int n,m,a[maxn],c[maxm];
int main(){
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        bitset<maxm>f;
        for(int j=i;j<=n;j++){
            if(f[a[j]]){
                bool o=0;
                for(int k=i;k<j;k++){
                    if(a[k]==a[j]) o=1;
                    if(o) f[k]=0;
                }
            }
            f[a[j]]=1;
        }
        for(int j=1;j<=m;j++){
            if(f[j]) c[j]++;
        }
    }
    for(int i=1;i<=m;i++) cout<<c[i]<<' ';
    return 0;
}
/*
By ZJ-J00357.
Luogu UID:1086453.
*/

:::

Noon

发现 T1 第四问没考虑 D,F 相邻的情况,只能祈祷 CCF 数据不要专门对着我的代码卡。

S2

罚坐开始。

考虑到赛前根本没有时间复习 S 组,不认为自己有切黄的实力,故心态不太好(埋下伏笔)。

T1

上来想了一会儿正解,想不出,遂打 \mathcal O(n^2) 暴力。尽管如此,中间还是出了种种问题,调了接近 2h。然后考虑特殊性质,发现假了。 :::info[Code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+5;
ll n,m,a[maxn],ans;
namespace Sub{
    bool check(){
        for(int i=1;i<=n;i++){
            if(a[i]!=i) return 0;
        }
        return 1;
    }
    int solve(){
        ll l=1,r=m,res=0;
        while(l<=r){
            ll mid=(l+r)/2;
            if(mid*(mid-1)<=2*m) res=mid,l=mid+1;
            else r=mid-1;
        }
        return res;
    }
    void main(){
        ll k=a[2]-a[1],x=solve();
        cout<<min(n,x);
    }
}
int main(){
    freopen("crystal.in","r",stdin);
    freopen("crystal.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    if(Sub::check()){Sub::main();return 0;}
    for(int k=1;k<=n;k++){
        ll res=0,t=m;
        vector<ll>v;
        for(int i=1;i<=k;i++) v.push_back(a[k]-a[i]);
        sort(v.begin(),v.end());
        for(ll x:v){
            if(t>=x) t-=x,res++;
            else break;
        }
        cerr<<res<<' '<<k<<'\n';
        ans=max(ans,res);
    }
    cout<<ans;
    return 0;
}
/*
By ZJ-S00382.
Luogu UID:1086453.
*/

::: 估计只能拿了 45 分。

插播:

赛后完全没看题解。

在学校没事干,上课想,发现其实但凡对着我的 \mathcal O(n^2) 代码多想一会,就可以发现单调性,想到二分,时间复杂度 \mathcal O(n \log n),过掉 T1。

T2

T1 炸了导致后面心态爆炸。

不难发现 Floyd,遂对着样例解释写(埋下伏笔)。

开始的时候发现空间有点小炸啊,编译器运行直接 MLE,遂把一些东西改成 vector。

由于时间不太够了,中间有些东西不知所云。 :::info[Code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=505,maxm=5e5+5,INF=1e9;
int c,n,m,d,q,w[maxm],k[maxn],f[maxn][maxn],o[maxn][maxm],id[maxm];
vector<int>a[maxn],t[maxn];
inline int C(int x,int y,int p){return t[x][p]+t[y][p];}
void Floyd(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) f[i][j]=(f[i][j]?f[i][j]:INF);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
        }
    }
}
int main(){
    freopen("subway.in","r",stdin);
    freopen("subway.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>c>>n>>m>>d>>q;
    for(int i=1;i<=m;i++) cin>>w[i];
    for(int i=1;i<=n;i++){
        cin>>k[i],a[i].resize(k[i]+1),t[i].resize(k[i]+1);
        for(int j=1;j<=k[i];j++){
            cin>>a[i][j]>>t[i][j],o[i][a[i][j]]=1;
            id[a[i][j]]=i;
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(o[j][i]&&o[k][i]) f[j][k]=f[k][j]=C(j,k,i);
            }
        }
    }
    Floyd();
    while(q--){
        int x,y;cin>>x>>y;
        cout<<w[x]+t[id[x]][x]+f[id[x]][id[y]]+t[id[y]][y]+w[y]<<'\n';
    }
    return 0;
}
/*
By ZJ-S00382.
Luogu UID:1086453.
*/

::: 写完之后发现样例解释中变量部分和数字部分对不上,就搁那想,想半天,突然老师冲进来,说什么 T2 不用去管样例解释的文字部分,以数值部分为准。

直接给我气晕了,你只告诉我这个东西错了不告诉我这个东西怎么改,那不是加大题目阅读难度吗。

反正到最后也没想出来,直接交了。

T3 & T4

心态完全崩了,总司令输出 0。

Correction

补题。 :::success[J T1]

#include<bits/stdc++.h>
using namespace std;
string c1,s1,c2,s2;
inline bool check1(){return c1==c2;}
inline bool check2(){return s1.substr(0,2)==s2.substr(0,2);}
inline bool check3(){return (s1[2]>='A'&&s1[2]<='C'&&s2[2]>='A'&&s2[2]<='C')||(s1[2]>='D'&&s1[2]<='F'&&s2[2]>='D'&&s2[2]<='F');}
inline bool check4(){return (s1[2]<='C'&&abs(s1[2]-s2[2])==1)||(s1[2]>'C'&&abs(s1[2]-s2[2])==2);}
int main(){
    cin>>c1>>s1>>c2>>s2;
    cout<<check1()<<(check1()&&check2())<<(check1()&&check2()&&check3())<<(check1()&&check2()&&check3()&&check4());
}

::: :::success[S T1]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+5;
ll n,m,a[maxn],s[maxn],ans;
ll solve(int p){
    int l=1,r=p,res=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[p]*mid-(s[p]-s[p-mid])<=m) res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i],ans=max(ans,solve(i));
    cout<<ans;
}

::: 剩下的明年再补吧,今年就到这里了。

Conclusion

估分:

\text{J : [80,90]+100+100+0=[280,290]}\\ \text{S : [45,60]+0+0+0=[45,60]}

实际成绩:

\text{J : 90+100+100+12=302}\\ \text{S : 45+0+0+0=45}

J 组一等玄啊,但是不管今年有没有一等,每年都会把重心放在 S 组上。

S 组的话鉴定为对自己不够自信,认为自己不能切黄。希望明年能争取一/二等+蓝勾。

都初二了还这种成绩。

我该在哪里停留?我问我自己。

明年再战吧!