CSP-S 2025 游记

ikunTLE · 2025-01-01 00:00:04 · 生活·游记

Day -inf

参加了 You have no egg! 的初赛（？）。85pts。

Day -2

请假在家里摆烂。

Day -1

上午本来打算打一打板子的，但是因为起床喝了杯凉水在厕所里呆了一上午。最后只写了线段树 1。

坐高铁去的考场。住的酒店离考点大概 3 公里。

试机试了 30 min，原因是线段树写挂了（我不是上午刚打的吗）。

我的座位可以看到 @exLucas 的代码。 另外我和 @fbl123bc 和 @Nahia 一个考场。

试机的时候有一个小学生，这里放一下她的神秘语言：

老师我的电脑出问题了。

老师我的电脑又出问题了，这个代码运行没有输出，但是有代码返回值。

老师，原来是我的 Floyd 写错了，我竟然把我最喜欢的算法写错了。哈哈哈。

我认为编程可以在任何电脑上，校长办公室电脑也可以。

至于为什么这个小学生没有参加 J 组，大致是她已经上高中了吧。

Day 1

比完 J 组回来，和牢 @Soviet_Onion 共度美好午餐时光。

没时间休息，就直接去考场了。状态未知。

大概 13:50 就到了考点，等了 10 分钟才放进去。

[罚坐.jpg]

为什么 J 组可以提前动电脑，S 组不行（思考）。

开始后先乱读题，全读完发现并没有阅读理解，我竟然所有题都读懂了 /jy

先看 T1，一眼贪心。20 min 写完，测大样例电脑卡死，测了 10 min。

T2 不太会，遂打 \mathcal{O}(2^k\times(m+nk)) 的暴力。但是 \mathcal{O}(m+nk) 写成 \mathcal{O}(mk) 了，应该无伤大雅。大约 64 pts。

然后偷吃了特殊性质 A，大样例挂了忘调了。最后在考试还剩 30 min 的时候回来测调出来了。大概 8 pts。

总共花了 1 h 30 min，搞出来 72 pts（虽然没调完）。

T3 不太会，打了个 \mathcal{O}(L_1\times L_2) 的暴力。然后又打了特殊性质 B（其实也假了）。一共 25+20=45 pts，但是没判 t 的长度是否相等，全寄了。

特殊性质 B 只有 20 pts 的原因：懒得判断是否满足特殊性质了。直接判断了如果字符串过长，直接按特殊性质做。

Wowser! @ikunTLE T3 花了 45 min 获得了 0 pts！

先回去调了 T2 特殊性质 B。

最后 T4 更不会，全排列获得 8 pts。

感受

完全燃尽了，但不知道我哪里真的思考了。现在都记不大清楚后 2 个小时是不是在对着电脑发呆。

结束后

大巴车上燃尽了不知道在想什么。

bro 一晚上都在左右脑互博。

Day 2

把我的考场代码放出来，可能能更好地展示我到底在想什么（？）

::::info[club]

// 100pts
// 首先贪心分配 
// 若有部门超出 n/2 个，那么将所有人按与其他部门满意度的差排序，将差值小的放到其他部门 
#include<bits/stdc++.h>
using namespace std;
int read(){
    int x;
    scanf("%d",&x);
    return x;
}
const int N=1e5+10;
int ren[N][5],len[5];
void solve(){
    int n=read();
    vector<int>a[5]; // 存放着成员编号 
    for(int i=1;i<=n;++i){
        int x=read(),y=read(),z=read();
        ren[i][1]=x,ren[i][2]=y,ren[i][3]=z;
        if(x>=y&&x>=z)
            a[1].push_back(i);
        else if(y>=x&&y>=z)
            a[2].push_back(i);
        else a[3].push_back(i);
    }
    len[1]=a[1].size(),len[2]=a[2].size(),len[3]=a[3].size();
    int sum=0;
    for(int j=1;j<=3;++j)
        for(int i:a[j])
            sum+=ren[i][j];
    if(len[1]<=n/2&&len[2]<=n/2&&len[3]<=n/2){
        printf("%d\n",sum);
        return;
    }
    int p=0;
    for(int j=1;j<=3;++j)
        if(len[j]>n/2){
            p=j;
            break;
        }
    vector<int>jian;
    for(int i:a[p]){
        vector<int>temp;
        temp.push_back(ren[i][1]);
        temp.push_back(ren[i][2]);
        temp.push_back(ren[i][3]);
        sort(temp.begin(),temp.end());
        jian.push_back(temp[2]-temp[1]);
    }
    sort(jian.begin(),jian.end());
    int tot=len[p]-n/2; // 需要去掉多少个人
    int cnt=0; // 已经去掉了多少人 
    for(auto val:jian){
        sum-=val;
        ++cnt;
        if(cnt>=tot)
            break;
    }
    printf("%d\n",sum);
    return;
}
int main(){
    freopen("club.in","r",stdin);
    freopen("club.out","w",stdout);
    int T=read();
    while(T--)
        solve();
    return 0;
}
/*
Input #1:

3
4
4 2 1
3 2 4
5 3 4
3 5 1
4
0 1 0
0 1 0
0 2 0
0 2 0
2
10 9 8
4 0 0

Output #1:

18
4
13

My Input #1:

1
6
9 8 0
9 7 0
9 6 0
9 5 0
9 4 0
9 3 0

My Output #1:

48

*/

::::

::::info[road]

// 32pts 做法 
// 2^k 枚举每个乡村是否城市化
// 跑一遍最小生成树 
// merge vector : O(nk) = 1e5
// kruskal : O(m) = 5e6
// calc : 1e7
// 枚举 : 1024 / 32
// tot : 1e10 / 3e8
// (1~4) + (5~12) + (17~20) = 64pts 
// (13~14) 特殊性质 A = 8pts 
#include<bits/stdc++.h>
using namespace std;
int read(){
    int x;
    scanf("%d",&x);
    return x;
}
const int N=1e4+100,M=1e6+10;
int fa[N];
void _init(){
    for(int i=0;i<N;++i)
        fa[i]=i;
    return;
} 
int _find(int x){
    if(x==fa[x])
        return x;
    fa[x]=_find(fa[x]);
    return fa[x];
}
void _merge(int u,int v){
    int uu=_find(u),vv=_find(v);
    if(uu!=vv)
        fa[uu]=vv; 
    return;
}
struct node{
    int u,v,w;
    friend bool operator<(const node cmp1,const node cmp2){
        return cmp1.w<cmp2.w;
    }
};vector<node>e,dis[15];
// 乡村的编号 n+1 ~ n+k 
int c[15];
vector<node>merge_vec(vector<node>a,vector<node>b){ // ok
    int l1=a.size(),l2=b.size();
    int i=0,j=0;
    vector<node>res;
    while(i<l1&&j<l2){
        if(a[i].w<b[j].w){
            res.push_back(a[i]);
            ++i;
        }
        else{
            res.push_back(b[j]);
            ++j;
        }
    }
    while(i<l1){
        res.push_back(a[i]);
        ++i;
    }
    while(j<l2){
        res.push_back(b[j]);
        ++j;
    }
    return res;
}
long long kruskal(int n,int k,int s){
    vector<node>vc=e;
    int ed=n;
    for(int i=1;i<=k;++i)
        if(s&(1<<(i-1))){
            vc=merge_vec(vc,dis[i]);
            ++ed;
        }
    _init();
    long long sum=0;
    int cnt=0;
    for(auto nd:vc){
        int u=nd.u,v=nd.v,w=nd.w;
        if(_find(u)!=_find(v)){
            _merge(u,v);
            ++cnt;
            sum+=w;
        }
        if(cnt==ed-1)
            break;
    }
    return sum;
}
int main(){
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    int n=read(),m=read(),k=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        e.push_back({u,v,w});
    }
    sort(e.begin(),e.end());
    for(int i=1;i<=k;++i){
        c[i]=read();
        for(int j=1;j<=n;++j){
            int d=read();
            dis[i].push_back({n+i,j,d});
        }
        sort(dis[i].begin(),dis[i].end());
    }
    if(1ll*m*(1<<k)>=1e8){
        int s=0;
        for(int i=0;i<k;++i)
            s+=(1<<i);
        printf("%lld\n",kruskal(n,k,s));
        return 0;
    }
    long long minn=kruskal(n,0,0);
    for(int s=0;s<(1<<k);++s){
        long long _cost=0;
        for(int i=1;i<=k;++i)
            if(s&(1<<(i-1)))
                _cost+=c[i];
        _cost+=kruskal(n,k,s);
        minn=min(minn,_cost);
    }
    printf("%lld\n",minn);
    return 0;
}
/*
Input #1:

4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4

Output #1:

13

Input #2:

4 4 3
1 2 3
1 4 5
2 3 7
3 4 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

(特殊性质 A) 

*/

/*

Debug:

for merge_vec: 

void debug(vector<node>v){
    for(auto i:v)
        cerr<<i.w<<" ";
    cerr<<"\n";
    return;
}

    vector<node>vc1={(node){0,0,5},(node){0,0,6},(node){0,0,7},(node){0,0,15}},vc2={(node){0,0,7},(node){0,0,9},(node){0,0,19}};

    vector<node>vc3=merge_vec(vc1,vc2);

    debug(vc3);

check ok!

*/

::::

::::info[replace]

// 暴力解决询问 O(L1 * L2)
// (1~5) = 25pts
#include<bits/stdc++.h>
using namespace std;
int read(){
    int x;
    cin>>x;
    return x;
}
const int N=2e5+10;
string s1[N],s2[N];
int main(){
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr); 
    int n=read(),Q=read();
    for(int i=1;i<=n;++i)
        cin>>s1[i]>>s2[i];
    if(n>1000){
        map<int,int>mp;
        for(int i=1;i<=n;++i){
            int p1=s1[i].find('b');
            int p2=s2[i].find('b');
            ++mp[p1-p2];
        }
        while(Q--){
            string t1,t2;
            cin>>t1>>t2;
            int p1=t1.find('b');
            int p2=t2.find('b');
            int res=mp[p1-p2];
            printf("%d\n",res);
        }
        return 0;
    }
    while(Q--){
        string t1,t2;
        cin>>t1>>t2;
        int cnt=0;
        for(int i=1;i<=n;++i){
            int p=t1.find(s1[i]);
            if(p>=0){
                for(int j=0;j<(int)s1[i].size();++j)
                    t1[p+j]=s2[i][j];
                if(t1==t2)
                    ++cnt;
                for(int j=0;j<(int)s1[i].size();++j)
                    t1[p+j]=s1[i][j];
            }
        }
        cout<<cnt<<"\n";
    }
    return 0;
}
/*

Input #1:

4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

Output #1:

2
0

Input #2:

3 4
a b
b c
c d
aa bb
aa b
a c
b a

Output #2:

0
0
0
0

My Input #1:

4 2
aaab baaa
aaba abaa
abaa aaab
baaa aaba
aabaa aaaba
aaaab abaaa

My Output #1:

0
1

My Input #1:

8 3
aaab baaa
aaba abaa
abaa aaab
baaa aaba
abaa aaba
aaba aaba
aaab abaa
aabaa abaaa
aabaaa abaaaa
aabaa aaaba
aaaab abaaa

My Output #1:

2
1
1

*/

::::

::::info[employ]

// (1~2) = 8pts
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    int x;
    scanf("%lld",&x);
    return x;
}
const int N=510,MOD=998244353;
int c[N];
char s[N];
bool check_all1(int n){
    for(int i=1;i<=n;++i)
        if(s[i]=='0')
            return false;
    return true;
}
signed main(){
    freopen("employ.in","r",stdin);
    freopen("employ.out","w",stdout);
    int n=read(),m=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;++i)
        c[i]=read();
    if(n>=15){
        printf("0\n");
        return 0;
    }
    vector<int>_per;
    for(int i=1;i<=n;++i)
        _per.push_back(i);
    int tot=0;
    do{
        int mg=0,j=0,cnt=0;
        for(auto i:_per){
            ++j;
            if(mg>=c[i])
                ++mg;
            else if(s[j]=='1')
                ++cnt;
            else ++mg;
        }
        if(cnt>=m)
            ++tot;
    }
    while(next_permutation(_per.begin(),_per.end()));
    printf("%lld\n",tot%MOD);
    return 0;
}
/*

Input #1:

3 2
101
1 1 2

Output #1:

2

Input #2:

10 5
1101111011
6 0 4 2 1 2 5 4 3 3

Output #2:

2204128

*/ 

::::

Day 5

考完期中被编诗。

Day 6