CSP-S 2025 游记

KobeBeanBryantCox · 2025-09-20 21:58:19 · 生活·游记

CSP-S 2025 游记

不知道会不会是最后一年。

这辈子没 AK 过 J 组但是今年不打算考。

初赛

用 GESP 8 级免掉了。但是我都报完名了它才跟我说可以不用考。

既然报了名就不能给 CCF 白送钱，还是要去考一下的。

考前并没有做模拟题，由此得出我很久没有做过初赛题。

所以我并没有很快速地做完试题，大约在开考后一个半小时做完。

但是感觉今年比之前简单很多，甚至感觉不如早上的 J 组（虽然我没看题）。

::::success[以下是我对 S 组初赛的评价]{open}

1. 线段树：没见过我是从 0 开始标号的吧！
2. 分层图板子题，但是，诶，我就是不用分层图做，那咋了？
3. Dijkstra：我不喜欢 vis 数组，我们分手吧。
4. 这个人可能不用动就从 s 走到 t 了（s=t 导致 d_{t,0}<d_{t,1}）。
5. 我偏不用 unique，就要手写去重！
6. 组合数的函数名不叫 C，且通过暴力实现。
7. 出题人：我怎么染上了一种不编译就出题的恶习。
8. 我是 permutation 我带着我一家三口来创飞 CSP-S 考生了。
9. 公差为 1 的递减等差数列：你好啊，分块实现猜数，请与我交往吧！
10. false：我什么时候不等于 0 了？？？
11. 喜欢暴力算法吗？
12. 谁说分块一定比暴力优秀的。
13. 你没有蛋。

::::

估分 90+ 吧。

官方成绩：94。

复赛

J 这么简单，离 AK 最近的一次却没去考，去的话大概率就 AK 了。。。

省流：理论会做 100+100+50+40，实际 100+[80,100]+[0,20]+20。

笑点解析：最后 3 小时拿了 <50 分。

赛前很多场模拟赛都被 @A_Step_Back 吊打了，搞得心态很炸。

不管了，开题！

首先看 T1，第一眼费用流，想到我赛前就差网络流的板子没有打过，慌死了。

然后随机乱搞了几下，发现 \dfrac n 2 这个限制太严了，所以直接反悔贪心好像是对的。

开始写，约 15 分钟后过了所有大样例。

但是感觉进入考场的时候匆匆忙忙搞得没准备好，整个脑子都是混乱的，我发现我 T1 的代码写得很丑，简单贪心居然写了 50 行。

不管了，看 T2！

想了两百万年，发现城市和乡村居然不是一个东西。

先想到了状压，发现 m 太鬼大了，然后才发现刚开始居然保证是连通的，也就是说，m 条边很多没什么用，数量级直接降为 n。

没仔细算，但是感觉复杂度看起来很对啊，直接开写。

然后开题 45 分钟后过了所有大样例就没管了。

（其实我应该测一下极限数据的，后面算来复杂度爆了，优化也是显然的，要是多想一会会就不会这样了。）

不过大样例是 n=1000 的跑了 0.12 秒，合理推测 n=10000 能跑 1.2 秒，加上 CCF 神机说不定过了。

不过考虑到 CCF 给了 n=1000 的部分分，可能就是要卡这个了吧。

发现有点爽了，以为自己 45 分钟 200 分，想着好像稳了。我错了我再也不敢乱想了。

然后想着 T3 不会也是水题吧，直接开始乱搞。

显然可以注意到我们直接在 ACAM 上匹配、哈希判断看起来就很对（没学好导致的），然后天真地以为 T3<T2。

发现居然一个节点的 fail 是其后缀？？？所以直接做不对。

但是我在考场的时候坚信这个题的正解就是 ACAM，因为看起来很对，而且除非是 SAM 等高级东西并没有其余能做了（除了 trie）（且考虑到提高组不能考 SAM 等）。

想了两百万年真的不会做了，此时去看了 T4。

发现 T4 有 20 分简单状压 DP，直接写了。

但是脑子里一直在想着 T3 的 ACAM，也没有心情看其余部分分。

返回去看 T3，发现会 B 性质了，类似于一个三维偏序的东西（后来出考场发现 @CatFromMars 大佬的 B 性质写的就是三维偏序）。

但是我考前没有复习三维偏序的板子啊，忘记 cdq 怎么写了，思索了一下写树套树的话性价比不高，而且时间可能不太够。

所以直接写了 20 分暴力枚举以及哈希判断。

并不显然地没有注意到不保证两个询问串长度相等，所以疑似挂成 0 分了。

此时还剩下 35 分钟，想爆冲一下 T4 部分分，大概胡出来全为 1（A 性质）怎么做。

由于快结束了所以很紧张，写出来并没有写对，随机调参后发现剩余时间不多遂放弃。

吸取前两次经验后保留 10 分钟检查文件。

完赛。

不好玩，还没去年高，感觉我会很多部分分但是都没写出来。。。

搞笑的是，我并不认为我能 15 分钟切绿，45 分钟切蓝，以及 3 小时切不了紫。

官方：100+80+25+24=229，被 @A_Step_Back 的 270 吓哭了。

附考场代码：

::::success[T1]

#include<bits/stdc++.h>
using namespace std;
int in()
{
    int k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=1e5+10;
int a[N][5],ch[N];
void work()
{
    int n=in();
    for(int i=1;i<=n;i++)ch[i]=0;
    int sum=0,cnt[5]={};
    for(int i=1;i<=n;i++)
    {
        a[i][1]=in(),a[i][2]=in(),a[i][3]=in();
        int u=1;
        if(a[i][2]>a[i][u])u=2;
        if(a[i][3]>a[i][u])u=3;
        cnt[u]++,sum+=a[i][u],ch[i]=u;
    }
    if(cnt[1]<=n/2&&cnt[2]<=n/2&&cnt[3]<=n/2)return out(sum),putchar('\n'),void();
    int p=1;
    if(cnt[2]>n/2)p=2;
    if(cnt[3]>n/2)p=3;
    vector<int>aa;
    for(int i=1;i<=n;i++)
    {
        int x=a[i][1],y=a[i][2];
        if(p==1)x=a[i][3];
        else if(p==2)y=a[i][3];
        if(ch[i]==p)aa.push_back(a[i][p]-max(x,y));
    }
    sort(aa.begin(),aa.end());
    int tot=cnt[p]-n/2;
    for(int i=0;i<tot;i++)sum-=aa[i];
    out(sum),putchar('\n');
}
int main()
{
//  system("fc club5.ans club.out");return 0;
    freopen("club.in","r",stdin),freopen("club.out","w",stdout);
    for(int t=in();t--;work());
    return 0;
}

::::

::::success[T2]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int in()
{
    int k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=1.5e4;
struct dsu
{
    int f[N],h[N];
    void init(int n){for(int i=1;i<=n;i++)f[i]=i,h[i]=1;}
    int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
    void merge(int x,int y)
    {
        if((x=find(x))==(y=find(y)))return;
        if(h[x]>h[y])swap(x,y);
        f[x]=y,h[y]+=(h[x]==h[y]);
    }
}f;
struct edge
{
    int u,v,w;
    bool operator<(const edge &a)const{return w<a.w;}
};vector<edge>e,kk;
int n,m,k;
int kruskal(int type,vector<edge>&e)
{
    int ans=0;f.init(n+k);
    sort(e.begin(),e.end());
    for(edge g:e)
    {
        int u=g.u,v=g.v,w=g.w;
        if(f.find(u)==f.find(v))continue;
        f.merge(u,v),ans+=g.w;
        if(type)kk.push_back((edge){u,v,w});
    }
    return ans;
}
int a[20][N],c[20];
signed main()
{
//  system("fc road4.ans road.out");return 0;
    freopen("road.in","r",stdin),freopen("road.out","w",stdout);
    n=in(),m=in(),k=in();
    while(m--)
    {
        int u=in(),v=in(),w=in();
        e.push_back((edge){u,v,w});
    }
    int ans=kruskal(1,e);
    for(int i=1;i<=k;i++)
    {
        c[i]=in();
        for(int j=1;j<=n;j++)a[i][j]=in();
    }
    for(int S=1;S<(1<<k);S++)
    {
        vector<edge>p=kk;
        int sum=0;
        for(int i=1;i<=k;i++)
            if((S>>(i-1))&1)
            {
                sum+=c[i];
                for(int j=1;j<=n;j++)p.push_back((edge){n+i,j,a[i][j]});
            }
        ans=min(ans,sum+kruskal(0,p));
    }
    out(ans);
    return 0;
}

::::

::::success[T3]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
namespace case1
{
    const int N=2005,B=31,mod=993244853;
    int pw[N];
    void init(){pw[0]=1;for(int i=1;i<N;i++)pw[i]=pw[i-1]*B%mod;}
    struct hsh
    {
        int f[N],n;
        void init(string &s){n=s.size();for(int i=1;i<=n;i++)f[i]=(f[i-1]*B%mod+s[i-1]-'a')%mod;}
        int get(int l,int r){return l>r?0:(f[r]-f[l-1]*pw[r-l+1]%mod+mod)%mod;}
    }a[N];
    int solve(string &s,string &t)
    {
        hsh s1,t1;s1.init(s),t1.init(t);
        int siz=s.size(),ans=0;
        for(int i=1;i<=siz;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int len=a[j].n;
                if(i<len)continue;
                if(s1.get(i-len+1,i)==a[j].get(1,len)&&t1.get(i-len+1,i)==a[j+n].get(1,len))
                    if(s1.get(1,i-len)==t1.get(1,i-len)&&s1.get(i+1,siz)==t1.get(i+1,siz))ans++;
            }
        }
        return ans;
    }
    int main()
    {
        init();
        for(int i=1;i<=n;i++)
        {
            string s,t;cin>>s>>t;
            a[i].init(s),a[i+n].init(t);
        }
        while(q--)
        {
            string s,t;cin>>s>>t;
            cout<<solve(s,t)<<'\n';
        }
        return 0;
    }
}
signed main()
{
//  system("fc replace2.ans replace.out");return 0;
    freopen("replace.in","r",stdin),freopen("replace.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    if(n<=1000)return case1::main();
    while(q--)cout<<0<<'\n';
    return 0;
}

::::

::::success[T4]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=510,mod=998244353;
int n,m;
string s;
int c[N];
namespace case1
{
    int f[(1<<18)+5][20];
    int main()
    {
        f[0][0]=1;
        for(int S=0;S<(1<<n);S++)
        {
            int tot=__builtin_popcount(S);
            for(int i=0;i<=tot;i++)
            {
                for(int j=1,u;j<=n;j++)
                {
                    if((S>>(j-1))&1)continue;
                    if(tot-i<c[j])u=1;
                    else u=0;
                    if(s[tot+1]=='0')u=0;
                    f[S^(1<<(j-1))][i+u]=(f[S^(1<<(j-1))][i+u]+f[S][i])%mod;
                }
            }
        }
        int ans=0;
        for(int i=m;i<=n;i++)ans=(ans+f[(1<<n)-1][i])%mod;
        cout<<ans;
        return 0;
    }
}
signed main()
{
//  system("fc employ2.ans employ.out");return 0;
    freopen("employ.in","r",stdin),freopen("employ.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>s,s="#"+s;
    for(int i=1;i<=n;i++)cin>>c[i];
    if(n<=18)return case1::main();
    cout<<0;
    return 0;
}

::::

Fun Fact：T4 大数据输出 0 在官方数据中多拿了 4 分（不可以总司令！）