来自SN蒟蒻的CSP-S 第二轮游记

· · 生活·游记

引言

考完出来就知道这次算是考炸了，第一道题想了将近三个小时依旧没有打出正解，不知道像我一样的蒟蒻还多不，在洛谷还有几何，这是本人第二次参加CSP，写的第一篇游记.....

考前 n Day

在高一的学习中抽空练题，特别庆幸在某天里翻到了这里，让我得以在第二题有了那么一丝得分的机会

考前 n Hour

去考场之前把快读的两行背过了，又看了看考试的注意事项，在商店买了两条士力架，也算是横扫饥饿做回自己了

考场前 5 min

进考场后先把自己脑子里记着的快速幂，最大公因数和快读代码先写了下来，希望能用得上，题目发下来，看完第T1题目，感觉有点思路，但不多，嗯对，就开始码代码，虽然思路并不完整

考时前 2.5 Hour

T1 对数据的处理我用了个结构体数组，然后进行排序，然后排序贪心，直接模拟选择过程，事情似乎在向好的方向发展... ...然而，对于样例1中

2 \ 10 9 8 \ 4 0 0

这组样例怎么都过不去，因为我的搜索顺序永远是对于第i个人，总是 cnt_i=i_a+i_b+i_c 最大的人优先选择，之后的人在之前的人选过的前提下继续选择，导致程序并不会学会取舍，这个点卡了我将近两个小时，对，没有听错，蒟蒻确实卡在这里了....

考时后 1.5 Hour

T1的代码我赛时一共写了3版，怎么写都退不出来，这可能就是蒟蒻的日常吧，没办法，只能选择爆搜保分，就有了这个结果

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+7;
int t,n,ans;
int ca,cb,cc;
struct txt{
    int a,b,c;
};

txt stu[N];

void dfs(int x,int cnt){
    if(x==n){
        ans=max(ans,cnt);
    }

    if(ca<n/2){
        ca++;
        dfs(x+1,cnt+stu[x+1].a);
        ca--;   
    }
    if(cb<n/2){
        cb++;
        dfs(x+1,cnt+stu[x+1].b);
        cb--;
    }
    if(cc<n/2){
        cc++;
        dfs(x+1,cnt+stu[x+1].c);
        cc--;
    }
}


int main(){
    cin>>t;
    while(t--){

        ans=-0x3f3f3f;
        ca=0;
        cb=0;
        cc=0;

        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>stu[i].a>>stu[i].b>>stu[i].c;
        }
        dfs(0,0);
        cout<<ans<<endl;    
    }

}

我对这段代码的形容只能是质朴，纯粹，是的你没看错，连特殊性质也没有拿（我是不会说我当时心态有点急，写完爆搜直接看T2了的），然后去看了T2 ，看到了1~4点k=0,于是奉上了最小生成树的代码：

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+7;
int n,m,k;
int ans=0;
int fa[N];

struct txt{
    int a,b,w;
};

struct cmp{
    bool operator()(txt a,txt b){
        return a.w>b.w;
    }
};

priority_queue<txt,vector<txt>,cmp> que;

int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}


int main(){
    cin>>n>>m>>k;
//  cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;

    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        que.push({u,v,w});
    }

    for(int i=1;i<=k;i++){
        int lin;
        cin>>lin;
        for(int j=1;j<=n;j++){
            cin>>lin;
        }
    }
    int cnt=0;

    while(!que.empty()){

        if(cnt==n-1)break;

        txt head=que.top();que.pop();
        int xa=find(head.a),xb=find(head.b);
        if(xa==xb)continue;
        ans+=head.w;
        fa[xa]=xb;
        cnt++;
    }
    cout<<ans;
}

至于53行 我忘记我写的时break还是continue了,嗯对，又得折点分... ...

考后

感觉去年的S2=和今年估计3=都拿不上的落差属实有点大，还是练的题太少了，思维上不够灵活，代码实现和算法还是略微有点局限了，只能说继续加油吧，至少应该能继续参加NOIP的... ...