官方题解| 挑战赛#18

userId_undefined

NoonMaple

倔强青铜

2025-05-21 09:56:54

发布于：浙江

68阅读
0回复
0点赞

本场挑战赛的所有题目的难度评级为：

题目编号 题目标题 难度
T1 午枫爱画画 入门
T2 午枫爱谦让 普及-
T3 午枫爱搬家 普及-
T4 午枫爱操作 普及/提高-
T5 午枫爱迷宫 普及/提高-
T6 午枫爱37 普及+/提高

挑战赛18题解

T1

输入输出

按照题目要求输出即可，注意多的一方需要最后额外连续输出对应字符。

用 while 或 for 循环皆可实现。

时间复杂度 O(max{n,m})O(max\{n,m\})

std

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

void solve(){
    int n,m;cin>>n>>m;
    while(n && m){
        cout<<"#*";
        n--;
        m--;
    }
    for(int i=1;i<=n;i++) cout<<"#";
    for(int i=1;i<=m;i++) cout<<"*";
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T2

贪心，排序

由于双方都想让对方拿的数字更大且数组元素个数保证为偶数，所以每次拿的时候只会拿当前剩下数中最小的数。

具体实现方法可以将整个数组从小到大排序后，遍历整个数组，将奇数位置和偶数位置的数分别求和即是两人分别拿到的数字之和，不用真的实现删除（拿走）操作。

时间复杂度 O(nlogn)O(nlogn)

std

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

typedef long long ll;

void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a.begin()+1,a.end());

    ll resa=0,resb=0;
    for(int i=1;i<=n;i++){
        if(i&1) resa+=a[i];
        else resb+=a[i];
    }

    cout<<resa<<" "<<resb<<endl;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T3

二分

考虑二分答案，checkcheck 时可以求出每次二分的搬运次数，因为是固定顺序，所以直接枚举所有物品，不断累加重量，当前重量和大于 midmid 值时视为一次搬运次数，并重置物品总重量。

通过调整二分的左右边界，最终确定答案。要注意的是初始二分范围是 [max(wi),1014][max(w_i),10^{14}] ，如果左边界初始设置成 00 可能会导致在 checkcheck 过程中将不该统计进去的次数算进去，如 mid<wimid<w_i 的情况。

时间复杂度 O(nlog(∑i=1nwi))O(nlog(\sum_{i=1}^n w_i))

std

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

typedef long long ll;

void solve(){
    ll n,k;cin>>n>>k;
    vector<ll>w(n+1);
    for(int i=1;i<=n;i++) cin>>w[i];

    auto check=[&](ll mid){
        ll res=0;
        ll sum=0;
        for(int i=1;i<=n;i++){
            if(sum+w[i]>mid){
                res++;
                sum=w[i];
            }
            else sum+=w[i];
        }
        if(sum) res++;
        return res<=k;
    };

    ll l=*max_element(w.begin()+1,w.end()),r=1e14+10;
    while(l<r){
        ll mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T4

贪心

通过手模不难发现，对于一段连续的 00 ，如果这段 00 右边至少有一个 11 ，那么可以通过一次操作使得这段 00 都变为 11 ，因为这段 00 一定是在高位的，所有这样的操作一定是最优的；由于操作后会出现新的 00 ，那么重复之前的过程，直到最后无法操作为止。

所以每次选取左端点为最左边的 00 ，右端点的距离左端点最近的 11 ，这样可以将这个区间除最后一位其他所有位都变成 11 ，同时提供了下一个区间的左端点，这样反复操作后，一定可以变成形如 11..00..11..00.. 的二进制数。

确定了上述方法，可以用模拟来实现，也可以记录最后一个 11 的位置直接输出。

时间复杂度 O(n)O(n)

std

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

void solve(){
    int n;cin>>n;
    string s;cin>>s;s=' '+s;
    
    bool flag=false;
    int pos=-1;
    for(int i=1;i<=n;i++){
        if(s[i]=='0') flag=true;
        if(flag && s[i]=='1') pos=i;
    }

    if(pos==-1){
        for(int i=1;i<=n;i++) cout<<s[i];
    }
    else{
        for(int i=1;i<pos;i++) cout<<1;
        for(int i=pos;i<=n;i++) cout<<0;
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T5

bfs，模拟

不难发现小午拿钥匙、救小枫、单独找出口的过程其实一样的，那么这三个过程可以合在一起通过一次 bfsbfs 判断能否到达这三个点；若可以解救小枫，再通过一次 bfsbfs 判断能否到达出口，但这次 bfsbfs 的遍历过程需要多一个可以走 $ 的判断条件。

总体做 22 次 BFS ，第一次判断以小午为起始位置是否能走到钥匙所在位置、小枫所在位置以及出口所在位置，若既能走到钥匙处也能走到小枫处则进行第二次BFS，判断以小枫为起始位置能否走到迷宫处。

可以用 44 个变量表示是否能到达各个特殊位置，最后按照输出优先级输出对应答案即可。

时间复杂度 O(n×m)O(n\times m)

std

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

#define PII pair<int,int>
#define fi first
#define se second

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void solve(){
    int n,m;cin>>n>>m;
    vector<vector<char>>g(n+1,vector<char>(m+1));
    PII bg,posM,ed,key;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
            if(g[i][j]=='N') bg={i,j};
            if(g[i][j]=='M') posM={i,j};
            if(g[i][j]=='@') ed={i,j};
            if(g[i][j]=='!') key={i,j};
        }
    }

    bool flag1=false,flag2=false,flagKey=false,flagM=false;
    auto bfs=[&](PII bg,int type){
        queue<PII>q;
        vector<vector<bool>>st(n+1,vector<bool>(m+1));
        q.push({bg});
        st[bg.fi][bg.se]=true;
        
        while(!q.empty()){
            auto [x,y]=q.front();q.pop();
            
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx<1 || ny<1 || nx>n || ny>m || g[nx][ny]=='#' || st[nx][ny]) continue;
                if(g[nx][ny]=='$' && type==1) continue;

                st[nx][ny]=true;
                q.push({nx,ny});
            }
        }

        if(type==1){
            if(st[key.fi][key.se]) flagKey=true;
            if(st[posM.fi][posM.se]) flagM=true;
            if(st[ed.fi][ed.se]) flag1=true;
        }
        if(type==2){
            if(st[ed.fi][ed.se]) flag2=true;
        }
    };

    bfs(bg,1);
    if(flagKey && flagM) bfs(posM,2);

    if(flag2) cout<<"we were here together"<<endl;
    else if(flag1) cout<<"sorry"<<endl;
    else cout<<"NO"<<endl;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T6

DP

“既是 33 的倍数，又是 77 的倍数” 可以理解为 “是21的倍数”。

可以考虑 DP ，设 dp[i][j]dp[i][j] 表示前 ii 个数可以组成 jj 的方案数，其中 jj 最多只有 2121 种状态。设当前所选数综合模 2121 为 jj ，对于第 ii 个数都有选和不选两种情况，若不选，方案数为 dp[i−1][j]dp[i-1][j] ；若选，方案数为 dp[i−1][(j−a[i]+21)%21]dp[i-1][(j-a[i]+21)\%21] 。那么状态转移方程为 dp[i][j]=dp[i−1][j]+dp[i−1][(j−a[i]+21)%21]dp[i][j]=dp[i-1][j]+dp[i-1][(j-a[i]+21)\%21] 。

由于 nn 较大，可以考虑用滚动数组优化空间复杂度。（当然本题实际上并没有卡空间）

时间复杂度 O(21n)O(21n)

std

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

typedef long long ll;
const ll mod = 998244353;

void solve(){
    int n;cin>>n;
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=21;
    }

    vector<vector<ll>>dp(2,vector<ll>(21));
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<21;j++){
            (dp[i&1][j]=dp[(i&1)^1][j]+dp[(i&1)^1][(j-a[i]+21)%21])%=mod;
        }
    }

    cout<<dp[n&1][0]<<endl;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 1

热门讨论