CSP 2025 游记 | 急了

Shadow_T · 2025-10-30 07:38:32 · 生活·游记

Day -3

现学 tarjan 和一些树形 dp。快放学了借了 Gold14526 打了神秘的羽毛球，被嘲讽了/cf

Day -2

模拟赛简单插板怎么推不出一点。/fn

会赢的吗/kel

该来的终将来了。还是自信一点。和yyy yyc yqf 在讲课教室展开了别样的粉笔大战。随机踢棒球。

Day 1

睡不着。窗户忘关了的噪音+焦虑的双重 debuff，终于在凌晨3点才能睡着。

没办法了，起床打神秘 csp-j。

前面 3 题半个小时速通了，第四题秒了 80，此时是 9:40。还有好多时间，不能白兰了，仔细一想我背包如果从大到小做前面 dp 的结果无法重复利用，所以就从小到大做。唉大样例怎么过了。能AK吗。

预估：100+100+100+100=400。

csp-s rp++

开 T1 怎么题面依托。。。感觉压力巨大。稳住。

直接对脑电波，唉我们先无视限制直接选，然后只要调整到次小值肯定是对的。这个调整我们直接找出次小值调整就行了。写写写。大样例过。

脑子可能有点问题，感觉写啥变量名都会 CE。表示次小值地 cx 怎么包含 x（？）肯定会 CE。mn2 怎么又数字后缀？肯定会 CE。于是最后使用了 gqh 表达对某同学的拜谢。

建立 road.cpp 草草写下 I really want to win 和 luogu uid 734379。

随即在 T2 开始彻底红温。O(2^k m log m) 的做法秒了。没有算分反正是过不了的。然而我对自己的定位是过 T2。

弘文弘文。

当时间打到 6:30 的时候，大样例跑 9s。我彻底怒了。强制自己开 T3，写了依托哈希。replace1 过，replace2 过，咦？replace3 怎么我后面输出的都是 360。彻底怒了。

好的，发现题目看错了。

接下来又梦到哪里写哪里写了 30 分钟，可以参考我极度混乱的代码。但是输出比 replace3 要少了。/fn /fn /fn

怎么办呢，不能全盘皆输了。不知道什么时候在 T2 注释里红温写了依托 win。

还是回去 T2 吧。发现 m 很大，n 很小，猜了一手只有原 MST 上的边要保留。写写写。咦？样例怎么过了。放个拍子也过了。大样例 0.9s。

算是，过了，吗。我松了一口气。然后发现神秘大样例没给满。然后自己造了极限数据又要跑 9s。这下没救了。

在比赛最后 20\min 发现注释掉 sort 只要跑 1.2s。重复 sort 太多了，可以用类似归并。至死没有想到可以提前排序。。。。

最后 10min，读了 T4 题面。并且写下了 8 pts 暴力。我怎么还会拼 next_permutation。

在还有 5min 的时候打完了。拜拜 OI.

估分是 100+80+0+8=188 吧。不是人类了。被浮木骂了。感觉有整整一天相思了。

回来看 la T2 最后只需要提前排序崩了。

我这一年虽说有颓废，但是也是切切实实的努力过了。可以说是我最努力的一年。最终却只剩下这种分数？

只能说学 OI 的 70\% 考祖宗保佑了 /ll。

Day ?

ccf 神秘 bug。严肃查分。

csp-j：400。

csp-s：213。

呜呜呜怎么我 T3 放了我 25 分。呜呜呜怎么 1= 了。呜呜呜怎么有 7 钩了。呜呜呜怎么有 noip 了。

lzq 可以去上厕所了！！！！拜谢队爷。

Finally

前面的东西先不写了，周末补。

放一下最终成绩/kel

replace 不知道为啥有的 25 pts。。。

也是上200了/ll

接下来是考场代码。

ZJ-J01840

number

#include <bits/stdc++.h>
using namespace std;
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    Ios();
    string s;
    cin>>s;
    string t="";
    for(int i=0;s[i];i++)
    if(s[i]>='0'&&s[i]<='9') t+=s[i];
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());
    cout<<t<<"\n";
    return 0;
}
//8:37 pretset passed(4)

seat

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define pb push_back
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
pii a[1001];
int main()
{
    freopen("seat.in","r",stdin);
    freopen("seat.out","w",stdout);
    Ios();
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n*m;i++) cin>>a[i].fir,a[i].sec=i;
    sort(a+1,a+n*m+1);
    reverse(a+1,a+n*m+1);
    int pos;
    for(int i=1;i<=n*m;i++)
    if(a[i].sec==1)
    {
        pos=i;
        break;
    }
    int x=1,y=1,o=0;
    pos--;
    while(pos--)
    {
        if(o==0)
        {
            if(x==n) y++,o^=1;
            else x++;
        }
        else
        {
            if(x==1) y++,o^=1;
            else x--;
        }
    }
    cout<<y<<" "<<x<<"\n";
    return 0;
}
//8:49 pretest passed(3)

xor

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define pb push_back
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int maxn=5e5+10;
int a[maxn];
map<int,bool> mp;
int main()
{
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    Ios();
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    int cnt=0,o=0;
    mp[0]=1;
    for(int i=1;i<=n;i++)
    {
        o^=a[i];
        if(mp[o^k])
        {
            cnt++;
            mp.clear();
            mp[0]=1;
            o=0;
        }
        else mp[o]=1;
    }
    cout<<cnt;
    return 0;
}
//8:58 pretest passed(6)

polygon

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define pb push_back
#define ll long long
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int maxn=5005;
const int mod=998244353;
int a[maxn];
ll dp[50005];
ll gqh[maxn];
int main()
{
    freopen("polygon.in","r",stdin);
    freopen("polygon.out","w",stdout);
    Ios();
    int n;
    cin>>n;
    gqh[0]=1;
    for(int i=1;i<=n;i++) gqh[i]=gqh[i-1]*2,gqh[i]%=mod;
    int Max=0;
    for(int i=1;i<=n;i++) cin>>a[i],Max=max(Max,a[i]);
    Max*=2;
    sort(a+1,a+1+n);
    ll ans=0;
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        //choose ai
        int mx=a[i]*2;
        for(int j=mx+1-a[i];j<=Max*2;j++)
        {
            int u=j+a[i];
            if(u>Max) continue;
        //  cerr<<i<<" "<<j<<" "<<dp[j]<<" ts\n";
            ans+=dp[j],ans%=mod;
        }
        //j+ai>=mx+1
        //j>=mx+1-ai
        for(int j=Max*2;j>=1;j--)
        {
            if(j>=a[i]) dp[j]=dp[j]+dp[j-a[i]],dp[j]%=mod;
            else dp[j]=dp[j];
        //  cerr<<i<<" "<<j<<" "<<dp[j]<<"\n";
        }
        //if(i<n)
        for(int j=Max+1;j<=Max*2;j++)
        {
            ans+=dp[j]*gqh[n-i]%mod;
            ans%=mod;
            dp[j]=0;
        }
    }
    cout<<ans<<"\n";
    return 0;
}
//11:09 pretest passed(5)

ZJ-S01897

club

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int maxn=1e5+10;
int a[maxn][3];
vector<int> cs1,cs2,cs3;
void solve()
{
    cs1.clear(),cs2.clear(),cs3.clear();
    int n;
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i][0]>>a[i][1]>>a[i][2];
        int mx=max(max(a[i][0],a[i][1]),a[i][2]);
        int gqh=0;
        if(a[i][0]==mx) ans+=a[i][0],gqh=max(a[i][1],a[i][2]);
        else if(a[i][1]==mx) ans+=a[i][1],gqh=max(a[i][0],a[i][2]);
        else ans+=a[i][2],gqh=max(a[i][0],a[i][1]);
        gqh=mx-gqh;
        if(a[i][0]==mx) cs1.pb(gqh);
        else if(a[i][1]==mx) cs2.pb(gqh);
        else cs3.pb(gqh);
    }
    sort(cs1.begin(),cs1.end());
    sort(cs2.begin(),cs2.end());
    sort(cs3.begin(),cs3.end());
    if(cs1.size()>n/2)
    {
        int u=cs1.size()-n/2;
        for(int i=0;i<u;i++) ans-=cs1[i];
    }
    else if(cs2.size()>n/2)
    {
        int u=cs2.size()-n/2;
        for(int i=0;i<u;i++) ans-=cs2[i];
    }
    else if(cs3.size()>n/2)
    {
        int u=cs3.size()-n/2;
        for(int i=0;i<u;i++) ans-=cs3[i];
    }
    cout<<ans<<"\n";
}
int main()
{
    freopen("club.in","r",stdin);
    freopen("club.out","w",stdout);
    Ios();
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}
//14:46 pretest passed(5)

road

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define fir first
#define sec second
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int maxn=2e5+10;
vector<int> g[maxn];
struct gqh
{
    int u,v,w,id;
};
bool cmp(gqh a,gqh b)
{
    return a.w<b.w;
}
const int maxm=2e6+10;
gqh b[maxm];
gqh c[maxm];
int tot,id;
int f[maxn];
int n,m,k;
int find(int x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}
bitset<maxm> used;
ll Winner()
{
    for(int i=1;i<=tot;i++) c[i]=b[i];
    sort(c+1,c+1+tot,cmp);
    for(int i=1;i<=id;i++) f[i]=i;
    ll res=0;
    int num=0;
    for(int i=1;i<=tot;i++)
    {
        if(find(c[i].u)==find(c[i].v)) continue;
        f[find(c[i].u)]=find(c[i].v);
        res+=c[i].w;
        if(num==id-1) break;
    }
    return res;
}
int cs=0;
void wk()
{
    for(int i=1;i<=tot;i++) c[i]=b[i];
    stable_sort(c+1,c+1+tot,cmp);
    for(int i=1;i<=id;i++) f[i]=i;
    int num=0,u=0;
    for(int i=1;i<=tot;i++)
    {
        //cs++;
        if(find(c[i].u)==find(c[i].v)) continue;
        f[find(c[i].u)]=find(c[i].v);
        used[c[i].id]=1;
        b[++u]=c[i];
        num++;
        if(num==id-1) break;
    }
    tot=u;
}
ll C[11];
int w[11][10005];
bool get(int x,int w)
{
    return (x>>w)&1;
}
void read(int &x)
{
    x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x*=10,x+=(c-'0'),c=getchar();
}
ll ans=1e18;
void dfs(int x,ll ad)
{
    if(x>k)
    {
        ans=min(ans,Winner()+ad);
        return;
    }
    dfs(x+1,ad);
    id++;
    for(int j=1;j<=n;j++)
    {
        tot++,b[tot].u=id,b[tot].v=j,b[tot].w=w[x][j];
    }
    ad+=C[x];
    dfs(x+1,ad);
    tot-=n,id--;
}
int main()
{
//  cerr<<(1024*1e4*log2(1e4))<<"\n";
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    Ios();
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        tot++;
//      read(b[tot].u);
//      read(b[tot].v);
//      read(b[tot].w);
        cin>>b[tot].u>>b[tot].v>>b[tot].w;
        b[tot].id=i;
    }
    bool p=0;
    for(int d=1;d<=k;d++)
    {
        cin>>C[d];
        p|=C[d];
        for(int j=1;j<=n;j++) cin>>w[d][j];
    }
    tot=m,id=n;
    wk();
    id=n;
    if(!p)
    {
        ll ans=1e18;
        int beg=0;
        if(!p) beg=(1<<k)-1;
        for(int i=beg;i<(1<<k);i++)
        {
            //cerr<<i<<"/"<<(1<<k)<<"\n";
            tot=m,id=n;
            ll ad=0;
            for(int p=1;p<=k;p++)
            if(get(i,p-1))
            {
                id++;
                for(int j=1;j<=n;j++)
                tot++,b[tot].u=id,b[tot].v=j,b[tot].w=w[p][j];
                ad+=C[p];
            }
            ans=min(ans,Winner()+ad);
        }
        cout<<ans;
        return 0;
    }
    dfs(1,0);
    cout<<ans;
    return 0;
    //cerr<<cs<<"\n";
}
//I really want to win!
//luogu uid 734379
//winwiwnwinwniwinwinws

replace

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define fir first
#define sec second
#define ull unsigned long long
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int maxn=2e5+10;
const int maxm=5e6+10;
ull p[maxm];
const int mod=1e9+7;
struct Hash
{
    ull hs[maxm];
    ull get(int l,int r)
    {
        ull res=hs[r]-hs[l-1]*p[r-l+1]%mod;
        return (res%mod+mod)%mod;
    }
    void build(string s)
    {
        int len=s.size();
        s=" "+s;
        for(int i=1;i<=len;i++) hs[i]=hs[i-1]*131+s[i],hs[i]%=mod;
    }
}hsb;
ull hss(string s)
{
    ull res=0;
    for(int i=0;s[i];i++) res*=131,res+=s[i],res%=mod;
    return res;
}
#define umap unordered_map
#define pss pair<string,string>
struct st
{
    ull u,v;
    ull wq,wh;
    bool operator<(const st &a) const
    {
        if(u!=a.u) return u<a.u;
        if(v!=a.v) return v<a.v;
        if(wq!=a.wq) return wq<a.wq;
        return wh<a.wh;
    }
};
map<st,int> dy;
ull hsq,hsh;
int len1=0,len2=0;
pss cf(string a,string b)
{
    hsq=0,hsh=0;
    if(a==b) return {"",""};
    int pos1;
    for(int i=0;a[i];i++)
    if(a[i]!=b[i])
    {
        pos1=i;
        break;
    }
    int pos2;
    for(int i=a.size()-1;i>=0;i--)
    if(a[i]!=b[i])
    {
        pos2=i;
        break;
    }
    string A="",B="";
    for(int i=pos1;i<=pos2;i++) A+=a[i],B+=b[i];
    string wq="",wh="";
    for(int i=0;i<pos1;i++) wq+=a[i];
    for(int i=pos2+1;i<a.size();i++) wh+=a[i];
    hsq=hss(wq),hsh=hss(wh);
    len1=wq.size(),len2=wh.size();
    return {A,B};
}
string a[maxn],b[maxn];
ull hs1[maxn],hs2[maxn],hsz1[maxn],hsz2[maxn];
int lenq[maxn],lenh[maxn];
int main()
{
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);
    Ios();
    int n,q;
    cin>>n>>q;
    p[0]=1;
    for(int i=1;i<=5e6;i++) p[i]=p[i-1]*131,p[i]%=mod;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        if(a[i]==b[i])
        {
        continue;
        }
        pss g=cf(a[i],b[i]);
        hs1[i]=hsq,hs2[i]=hsh;
        hsz1[i]=hss(g.fir);hsz2[i]=hss(g.sec);
        lenq[i]=len1,lenh[i]=len2;
        //cerr<<hs1[i]<<" "<<hs2[i]<<" "<<hsz1[i]<<" "<<hsz2[i]<<" "<<lenq[i]<<" "<<lenh[i]<<"\n";
    }
    while(q--)
    {
        string t1,t2;
        cin>>t1>>t2;
        int N=t1.size();
        hsb.build(t1);
        pss u=cf(t1,t2);
        ull nd1=hss(u.fir),nd2=hss(u.sec);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==b[i]) continue;
            if(hsz1[i]==nd1&&hsz2[i]==nd2)
            {
                int l1=len1-lenq[i]+1,r1=len1,l2=N-len2+1,r2=N-len2+1+lenh[i]-1;
                if(l1>=1&&r1<=N&&l2>=1&&r2<=N)
                if(hsb.get(l1,r1)==hs1[i]&&hsb.get(l2,r2)==hs2[i])
                ans++;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}
/*
3
5
aabcaa aacdaa
addabadd addcdadd
addabad addcdad
*/

employ

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define fir first
#define sec second
#define ull unsigned long long
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int c[101];
int p[101];
int main()
{
    freopen("employ.in","r",stdin);
    freopen("employ.out","w",stdout);
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) p[i]=i;
    int ans=0;
    do
    {
        int no=0,ly=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='0'||no>=c[p[i]])
            {
                no++;
                continue;
            }
            ly++;
        }
        if(ly>=m) ans++;
        //for(int i=1;i<=n;i++) cerr<<p[i]<<" ";
    }
    while(next_permutation(p+1,p+1+n));
    cout<<ans;
    return 0;
}