官方题解 | 挑战赛21题解

NoonMaple

2025-08-11 09:03:57

发布于：浙江

148阅读

0回复

0点赞

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	午枫的切蛋糕	入门
T2	午枫的卡片游戏	普及-
T3	午枫的分割数组	普及-
T4	小午的构造	普及-
T5	午枫的mex	普及/提高-
T6	午枫的陪伴时间	普及+/提高

T1 午枫的切蛋糕

题目大意

有 $n+1$ 个人分蛋糕，蛋糕可以沿着直径或半径切开，问平均分配最少需要切几刀。

解题思路

因为需要平均分且切蛋糕时只能沿着直径或者半径切开，所以我们可以考虑人数的奇偶性。

如果有偶数个人分蛋糕，则每一刀可以沿着直径切开；如果有奇数的人分蛋糕，则每一刀只能沿着半径切开。

注意总人数为 $n+1$ 人，当只有一个人的时候，不需要切蛋糕。

时间复杂度 $O(1)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

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

T2 午枫的卡片游戏

题目大意

双方都有 $n$ 卡片，小枫告诉了小午自己的出牌顺序，双方进行比较点数，如果小午点数大本轮小午获胜，否则小枫获胜。求最终谁的胜场多。

解题思路

我们可以通过“田忌赛马”的思想，用自己尽量小点数的卡片和对方尽量大点数的卡片进行比较，最大化的减少敌方战力的同时最小化减少己方战力。让我们赢的时候尽量也选取最接近对方点数的卡片。

因此原本的卡片顺序已经不重要了，我们可以将双方的卡片排序，通过双指针模拟比较双方的点数。

时间复杂度 $O(nlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n;cin>>n;
    vector<int>a(n+1),b(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(a.begin()+1,a.end(),greater<int>());
    sort(b.begin()+1,b.end());

    int resa=0,resb=0;
    int l=1,r=n;
    for(int i=1;i<=n;i++){
        if(a[i]>=b[r]){
            l++;
            resb++;
        }
        else{
            r--;
            resa++;
        }
    }
    if(resa>resb) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

T3 午枫的分割数组

题目大意

小午可以将一个数组分成前后两部分，第一部分给小午，第二部分给小枫，之后小午和小枫分别可以在各自的数组中选取 $k_1$ 和 $k_2$ 个数，然后比较两人选出的数的众数，大的一方获胜。判断小午是否可以获胜。

解题思路

题目中所选的数中数量最多的数称为众数，以下都称众数。

考虑当前有一个数组，最多选 $k$ 个数，如何让选出来的数的众数最大，显然，我们只要选一个最大的数即可。

那么对于小午来说，他需要让小枫拿到的数尽可能少，因为小枫拿到越少的数，能选出比小午大的数的可能就更小。所以小午的最优选择一定是把前 $n-1$ 个数分给自己，最后一个数分给小枫。

时间复杂度 $O(n)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n,k1,k2;cin>>n>>k1>>k2;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    int mx=*max_element(a.begin()+1,a.begin()+n);
    if(mx>a[n]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

T4 小午的构造

题目大意

有 a 、c 、w 三个字母若干个，有 ac 、wa 、aa 三种组合，求最多能得到多少组合，并且在得到最多组合的情况下，wa 的个数最少是多少?

解题思路

首先考虑组合出最多数量的单词：由于 c 和 w 只会被用于组成 ac 和 wa ，所有我们优先消耗 c 和 w ，最后剩下的 a 两两组合。

再来考虑如何让 wa 的个数尽量少：

在消耗 c 和 w 的情况下，我们一定优先消耗 c ，再消耗 w ；
当 w 被消耗完且 a 两两组合成 aa ，a 还有剩余时，我们可以将 wa 拆开，用其中的 a 去和剩余的 a 组合。

对于上述第二点，我们会发现最终如果有 a 剩余，那么一定只会剩下一个 a ，所有我们最后要拆 wa 时也只会拆一个，那么我们只需要判断组合完 ac 之后的 a 和 w 的奇偶性就可确定是否需要拆 wa 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int x,y,z;cin>>x>>y>>z;
    //先组合 ac
    int res=min(x,y);
    x=max(0ll,x-y);
    
    //如果 w 比 a 多，则将所有 a 与 w 组合
    if(x<z){
        res+=x;
        cout<<res<<" "<<x<<endl;
    }
    //否则，考虑最后是否需要拆 wa
    else{
        if((x&1)!=(z&1)) z=max(0ll,z-1);

        res+=z+(x-z)/2;
        cout<<res<<" "<<z<<endl;
    }
}

signed main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}

T5 午枫的mex

题目大意

求 $mex\{i\oplus j \mid i\in [1,n],j\in[1,n] \}$ .

解题思路

通过打表，善于观察的同学可能会发现一定规律： $\begin{cases} \begin{aligned} 1,n\leq 2\\ 2^{\lceil\log{n}\rceil},n>2 \end{aligned} \end{cases}$ 。

证明：对于 $n$ 的最高位 $1$ ，仅保留这一位 $1$ ，对于低位可以任取，此时覆盖了 $n$ 最高位为 $1$ 的所有情况；然后 $n$ 的最高位 $1$ 这一位为 $0$ ，次高位为 $1$ ，对于低位可以任取，此时覆盖了 $n$ 次高位为 $1$ 的所有情况。依次类推，所以最小的不能被表示的就是 $2^{\lceil\log{n}\rceil}$ ， $n=1,2$ 特判。

时间复杂度 $O(Tlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int n;cin>>n;
    if(n<=2){
        cout<<1<<endl;
        return;
    }

    int now=4;
    while(now<n){
        now<<=1;
    }
    cout<<now<<endl;
}

signed main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}

T6 午枫的陪伴时间

题目大意

有 $n$ 个开始陪伴的时间，每次陪伴必续连续陪 $t$ 天，期间不能进行别的陪伴的任务，如果陪伴需要花费 $cost$ 元，否则需要花费 $val$ 元，求最少花费。

解题思路

首先我们可以考虑按照 $a_i$ 从小到大排序，然后考虑通过DP如何解决。

设 $dp_{i,0}$ 表示前 $i$ 个选项，其中没选第 $i$ 项的最小花费； $dp_{i,1}$ 表示前 $i$ 个选项，其中选择了第 $i$ 项的最小花费。

其中 $dp_{i,0}$ 的状态转移很简单： $dp_{i,0}=min(dp_{i-1,0},dp_{i-1,1})+v_i$ 。

令 $s_i$ 为 $v_i$ 的前缀和， $pos$ 为 $i$ 左侧第一个小于 $a_i-m$ 的下标。那么 $dp_{i,1}$ 的状态转移为： $dp_{i,1}=min(dp_{pos,0},dp_{pos,1})+s_{i-1}-s_{pos}+cost_i$

最后答案取 $dp_{i,0}$ 和 $dp_{i,1}$ 的最小值即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(x) x.begin(),x.end()

signed main(){
    int n,m;cin>>n>>m;
    vector<array<int,3>>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i][0];
    for(int i=1;i<=n;i++) cin>>a[i][1]>>a[i][2];
    
    sort(a.begin()+1,a.end());
    vector<int>id(n+1);
    for(int i=1;i<=n;i++) id[i]=a[i][0];

    vector<int>s(n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i][2];

    vector<vector<int>>dp(n+1,vector<int>(2)); // 0 - 不选 , 1 - 选
    for(int i=1;i<=n;i++){
        dp[i][0]=min(dp[i-1][0]+a[i][2],dp[i-1][1]+a[i][2]);

        int pos=upper_bound(all(id),max(0ll,a[i][0]-m))-id.begin()-1;
        dp[i][1]=min(dp[pos][0]+s[i-1]-s[pos]+a[i][1],dp[pos][1]+s[i-1]-s[pos]+a[i][1]);
    }
    
    cout<<min(dp[n][0],dp[n][1])<<endl;
}