挑战赛#21 前五题题解

userId_undefined

编程之神

7月全勤卷王出道萌新时间刺客空间掌握者时空双修者秩序白银

2025-08-10 22:02:57

发布于：北京

10阅读
0回复
0点赞

编程之神题解 | 挑战赛#21 前五题题解

题目目录

题目编号 题目名称
T1 午枫的切蛋糕
T2 午枫的卡片游戏
T3 午枫的分割数组
T4 小午的构造
T5 午枫的mex
T6 午枫的陪伴时间

T1 午枫的切蛋糕
题目描述：小枫要把蛋糕分给n个朋友，切蛋糕时，每一刀都是沿着直径或者半径切开，最少要切几刀？
参考代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int total = n + 1;
    if (total == 1) {
        cout << 0 << endl;
    } else if (total % 2 == 0) {
        cout << total / 2 << endl;
    } else {
        cout << total << endl;
    }
    return 0;
}

T2 午枫的卡片游戏
题目描述：已知对手固定出牌序列且平局判对手胜，问己方是否存在一种出牌策略使总胜场占优。
参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    int wins = 0;
    int i = 0, j = 0;
    while (i < n && j < n) {
        if (b[j] > a[i]) {
            wins++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    
    if (wins > n / 2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}

T3 午枫的分割数组
题目大意：小午能否通过合理分割数组并选择不超过 k 个数，使得其众数值严格大于小枫（选择不超过 k 个数）的众数值，从而确保胜利。
参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k1, k2;
    cin >> n >> k1 >> k2;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    
    int M = *max_element(a.begin(), a.end());
    
    
    int last_index = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] == M) {
            last_index = i;
            break;
        }
    }

    
    if (last_index == n - 1) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
    
    return 0;
}

T4 小午的构造
题目大意：小午需要利用现有的 x 个 a、y 个 c 和 z 个 w，通过组合 ​ac、aa、wa​ 三种单词，在用完所有字母的前提下，​最大化单词总数，并在此条件下最小化 wa 单词的数量
参考代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        long long x, y, z;
        cin >> x >> y >> z;
        long long K = min(x, y + z);
        long long m = K + (x - K) / 2;
        long long min_wa;
        if (x <= y) {
            min_wa = 0;
        } else if (x <= y + z) {
            min_wa = x - y;
        } else {
            if ((x - y - z) % 2 == 1 && z >= 1) {
                min_wa = z - 1;
            } else {
                min_wa = z;
            }
        }
        cout << m << " " << min_wa << "\n";
    }
    return 0;
}

T5 午枫的mex
题目大意：小枫有 1 到 n 这 n 个整数，他想知道 mex{i⊕j∣i∈[1,n],j∈[1,n]} 是多少。其中 ⊕ 表示按位异或；mex 表示集合中不存在的最小非负整数。
参考代码

#include <iostream>
using namespace std;

long long solve(long long a) {
    for (long long b = 0; ; b++) {
        long long c = (1LL << b);
        if (a < c) {
            return c;
        }
        bool d = false;
        
        if (a - c >= 1) {
            if (b >= 1) {
                d = true;
            } else {
                if (a - c >= 2) {
                    d = true;
                }
            }
        }
        if (d) {
            continue;
        }
        
        if (a >= c + 1) {
            if (b >= 1) {
                d = true;
            } else {
                if (a >= 3) {
                    d = true;
                }
            }
        }
        
        if (d) {
            continue;
        } else {
            return c;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a;
    cin >> a;
    while (a--) {
        long long b;
        cin >> b;
        cout << solve(b) << '\n';
    }
    return 0;
}

T6 午枫的陪伴时间
题目大意：小枫需要从 n 个时间段选项中选择若干互不重叠的区间（每个区间长度为 t 天），以最小化总花费（未选选项的礼物价值 v_i 与所选选项的陪伴成本 cost_i 之和）。
参考代码

可以把自己的代码发在评论区
userId_undefined
去预览
0/2000

全部评论 1

  • userId_undefined

    ༺ཌ𝓒𝓾𝓷𝓽𝓪𝓲ད༻

    尊贵铂金
    #include <bits/stdc++.h>
using namespace std;
struct O{
    int a,end,cost,v,wei;
    O(int a,int end,int cost,int v):a(a),end(end),cost(cost),v(v),wei(cost-v){}
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,t;
    cin>>n>>t;
    vector<int>a(n);
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    vector<O>o;
    long long sum=0;
    for(int i=0;i<n;++i){
        int cost,v;
        cin>>cost>>v;
        sum+=v;
        int end=a[i]+t-1;
        o.emplace_back(a[i],end,cost,v);
    }
    sort(o.begin(),o.end(),[](const O&x,const O&y){
        if(x.end!=y.end)return x.end<y.end;
        return x.a<y.a;
    });
    vector<int>ends;
    ends.reserve(n);
    for(const auto&opt:o){
        ends.push_back(opt.end);
    }
    vector<long long>dp(n+1,0);
    for(int i=1;i<=n;++i){
        const auto&opt=o[i-1];
        int target=opt.a-1;
        auto it=upper_bound(ends.begin(),ends.end(),target);
        int idx=it-ends.begin()-1;
        long long take=(idx>=0?dp[idx+1]:0)+opt.wei;
        long long ake=dp[i-1];
        dp[i]=min(take,ake);
    }
    cout<<sum+dp[n];
    return 0;
}

    昨天 来自 浙江

    1

热门讨论