CSP-J 2025 游记

· · 生活·游记

第一次考复赛，写篇游记纪念一下。

考了三年，终于过初赛了！（一名初一的广东小蒟蒻）

考前：

做了两次模拟赛，一次橙黄绿蓝，一次黄黄绿绿，都有 200+，觉得自己今年稳拿一等了。

考复赛的前一天，我还在做往年的题。

考试时：

望着屏幕上的倒计时，快要开始了！

约 8:28 左右，密码出来了，由于视力不太好，密码输错了 5 分钟才输对了。

拿到题目，先开第一题。

看了 2 分钟，写了个桶就切掉了。

T1 代码：

#include<iostream>
#include<cstdio>
using namespace std;
string s;
int sum[20];
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    cin>>s;
    for(int i=0;i<s.size();i++)
        if(s[i]>='0'&&s[i]<='9')
            sum[s[i]-'0']++;
    for(int i=9;i>=0;i--)
        while(sum[i]--)
            cout<<i;
    return 0;   
}

接下来开 T2。

看完题之后，发现只需排序和模拟，于是 3 分钟就写出来了，后来发现模拟座位写错了，大概在 10:00 过了。

T2 代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int a[110];
int s;
int h;
bool cmp(int x,int y)
{
    return x>y;
}
int x=1,y=0;
int main()
{
    freopen("seat.in","r",stdin);
    freopen("seat.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n*m;i++)
        cin>>a[i];
    s=a[1];
    sort(a+1,a+1+n*m,cmp);
    for(int i=1;i<=n*m;i++)
    {
        if(x&1)y++;
        else y--;
//      cout<<x<<' '<<y<<'\n';
        if(a[i]==s)
        {
            cout<<x<<' '<<y;
            break;
        }
//      if(x==1)continue;
        if((y==n&&x%2==1)||(y==1&&x%2==0))
        {
            x++;
            if(x&1)y--;
            else y++;
        }
    }
    return 0;
}

看完 T3，感觉有点像动规，就去写 T4 了。

看了一下 T4，爆索能拿 40\text{pts}，特判能拿 24\text{pts}，就开始写 T4 了。

T4 写了个二进制枚举就过样例了，开始写特判，特判大概写到 10:40，时间要不够了，于是赶紧写 T3。

T4 代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[5010];
int maxx;
long long sum,ans;
long long mod=998244353;
bool flag=1;
long long C(int x,int y)
{
    long long j=1,sum=1;
    for(long long i=x;i>=x-y+1;i--)
    {
        if(j>y)
            sum=(sum*i)%mod;
        else
            sum=sum*i;
        while(j<=y&&sum%j==0)
            sum=sum/j,j++;
        if(j>y)
            sum=sum%mod;
//      cout<<sum<<'\n';
    }
    while(j<=y)
        sum=sum/j,j++;
//  cout<<'#'<<sum<<'\n';
    return sum%mod;
}
int main()
{
    freopen("polygon.in","r",stdin);
    freopen("polygon.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]!=1)
            flag=0;
    }
    if(flag)
    {
        for(int i=3;i<n;i++)
            ans=(ans+C(n,min(n-i,i)))%mod;
        cout<<(ans+1)%mod;
        return 0;
    }
    for(long long i=0;i<=(1<<n)-1;i++)
    {
        sum=maxx=0;
        for(int j=1;j<=n;j++)
            if((i>>(j-1))&1)
                sum+=a[j],maxx=max(maxx,a[j]);
        ans=(ans+(sum>maxx*2))%mod;
    }
    cout<<ans;
    return 0;
}

重看 T3，发现能把每一段异或和为 0 的记录下来再做最长上升子序列能拿 60\text{pts}，就匆匆忙忙写了。大概在 11:15 写完了。

T3 代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,k;
int a[500010];
int sum[500010];
int ans;
int x;
int dp[500010];
struct node{
    int st,ed;
}b[500010];
int len;
int main()
{
//  freopen("xor.in","r",stdin);
//  freopen("xor.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],sum[i]=(k^a[i]);
    for(int i=1,cnt;i<=n;i++)
    {
        if(!sum[i])
        {
            b[++len].st=i;
            b[len].ed=i;
            dp[len]=1;
            continue;
        }
        cnt=sum[i];
        for(int j=i+1;j<=n;j++)
        {
            cnt=cnt^sum[j];
            if((j-i+1)%2==0&&cnt==k)
                b[++len].st=i,b[len].ed=j,dp[len]=1;
            if((j-i+1)%2==1&&cnt==0)
                b[++len].st=i,b[len].ed=j,dp[len]=1;
        }
    }
    for(int i=1;i<=len;i++)
    {
//      cout<<b[i].st<<' '<<b[i].ed<<'\n';
        for(int j=1;j<i;j++)
        {
            if(b[j].ed<b[i].st)
                dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(dp[i],ans);
    }
    cout<<ans;
    return 0;
}

最后 15 分钟，每题都匆匆忙忙地测了样例后就结束了。

赛后上洛谷一测，100+100+60+40=300\text{pts}，以为能拿一等奖了，谁知道一出分，100+100+0+40=240\text{pts}，拿到代码后一看，T3 不小心把 freopen 注释掉了，我的一等奖啊！只能明年再来了，可恶的CCF。

愿大家不在重蹈覆辙！