天梯选拔赛2补题_2024_03_09

补题1:奶茶袋收集

题意:

做法：贪心。之前还做过类似的题，赛时一直想不出来。选择k个连续的的区间，就是需要添加k-1个挡板。问题是挡板设置在哪里？可以发现一个连续线段的max-min等于线段中各个差值之和。如果k=1，那么ans=∑(ai+1-ai);如果k=2，那么需要添加一个挡板。贪心地放，挡板应该放在最大的ai+1-ai中。然后答案为剩下的ai+1-ai。

void solve(){               //补L1-7--奶茶袋收集-贪心。之前写过一模一样的题。。现在还想歪了，往前缀和想。。
    int n,k,x,ans=0,last=-1;
    cin>>n>>k;
    vector<int> dif;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(i>=2) dif.emplace_back(x-last);
        last=x;
    }
    sort(dif.begin(),dif.end(),greater<int>());
    for(auto d:dif){
        if(k>1) k--;
        else ans+=d;
    }
    cout<<ans;
}

补题2:swj学长的融合

题意:

做法：题目本身完全没有难度，主要是读题目没读懂升级机制是什么，不知道怎么样“以此类推”。赛后读懂题目之后轻松补了。

vector<pair<int,int>> vct[100005];
int x,m,a,b,c,d,ans=0;
void dfs(int step){
    for(auto to:vct[step]){
        ans+=to.second;
        dfs(to.first);
    }
}
void solve(){               //补L2-2--swj学长的精灵融合--建图dfs..赛时题目都没读懂，不知道等级升级系统(类似金铲铲)是怎么样都，不知道怎么以此类推..
    cin>>x>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c>>d;
        int exp=1;
        if(d==1) exp=0;
        if(c==1) exp+=( (d-2) * (1+d-2) )/2;
        if(c==2) exp+=( (d-2) * (2+2*(d-2) ) )/2;
        if(c==3) exp+=( (d-2) * (5+5*(d-2)) )/2;
        //cout<<exp<<endl;
        vct[a].emplace_back(b,exp);
    }
    dfs(x);
    cout<<ans;
}