非官方题解|挑战赛#21 题解

userId_undefined

忘川秋库

小有名气7月全勤卷王时空双修者荣耀黄金题解仙人传道者

2025-08-13 12:41:14

发布于：湖北

313阅读
0回复
0点赞

开始之前出题人先辟谣

T1午枫的切蛋糕

  • 难度：入门

  • 思路分析

  1. （特判情况）如只有 11 人，不用切
  2. 偶数人情况下，直径切法，切 nn 次，可得到 2n2^n 份
  3. 奇数人情况下，半径切法，切 nn 次，可得到 nn 份

  • 通过代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    int people=n+1;
    if(people==1){
        //只有1人，不切 
        cout<<0<<endl;
    }else if (people%2==0){
        // 偶数人，用直径切法，刀数为people / 2 
        cout<<people/2<<endl;
    }else{
        // 奇数人，用半径切法，刀数为people
        cout<<people<<endl;
    }
}

  • 时间复杂度分析

此代码不涉及循环，时间复杂度 O(1)O(1) 。

T2午枫的卡片游戏

  • 前言：集训营同鞋应该有做过TJZ之王的（主人公是xiaoshuai和009的），题目是差不多的

  • 难度：普及-

  • 思路分析

  1. 将小枫和小午的卡片数组分别进行升序排序
    排序后的数组 a1∼ana_1 \sim a_n 和 b1∼bnb_1 \sim b_n 按点数从小到大排列

  2. 初始化w=0记录小午胜场，l=0记录小枫胜场，r=n-1指向小午当前最大牌
    从 nn 到 11 逆序遍历小枫的牌
    比较小午当前最大牌 brb_r 和小枫当前牌 aia_i
    如果b[r]>a[i]，则小午胜，w++，rr 左移,否则小枫胜，l++。

  3. 若 w>n/2w>n/2 输出YES，否则输出NO

  • 通过代码

#include<bits/stdc++.h>
using namespace std;
int a[1000010],b[1000010]; 
 
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    
    sort(a+1,a+n); //对应思路分析1
    sort(b+1,b+n); //对应思路分析1
    
    int w=0;  //对应思路分析2
    int l=0;  //对应思路分析2
    int r=n-1; //对应思路分析2

    for(int i=n;i>=1;i--){
        if(b[r]>a[i]){ //小午当前最大牌能赢
            w++; //小午胜场+1
            r--; //使用小午当前最大牌 
        }else{
            l++; //小枫胜场+1 
        }
    } 

    if(w>n/2){// 获胜次数过半 
        cout<<"YES"; 
    }else{
        cout<<"NO"; 
    }
}

  • 时间复杂度分析

sortsort 排序时间复杂度为 O(n log n)O(n~log~n)

T3午枫的分割数组

  • 难度：普及-

  • 思路分析

  1. 准备部分
    从左到右扫描数组，计算每个位置的前子表最大值lm[]及其出现次数lc[]
    从右到左扫描数组，计算每个位置的后子表··最大值rm[]及其出现次数rc[]
  2. 枚举所有可能的分割方案
    对于每个可能的分割点 m（2≤m≤n）m（2 ≤ m ≤ n）
    将数组分为两部分：前 m−1m-1 个元素给小午，后 n−m+1n-m+1 个元素给小枫
    根据预处理结果：
    小午部分的最大值为 lmm−1lm_{m-1}，可选数量为min(lc[m-1],k1)
    小枫部分的最大值为 rmmrm_m，可选数量为min(rc[m],k2)
  3. 胜负判断
    对于每个分割方案：
    比较小午部分最大值 wmwm 和小枫部分最大值 fmfm
    只要找到一个分割方案满足 wm>fmwm > fm ，则立即返回YES，若检查完所有分割方案都没有找到满足条件的，则返回NO

  • 通过代码

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int lm[1000010],lc[1000010];
int rm[1000010],rc[1000010];
 
int main(){
    int n,k1,k2;
    cin>>n>>k1>>k2;
    for(int i=1;i<=n;i++)cin>>a[i];
 
    //计算前子表最大值及出现次数 
    lm[1]=a[1];
    lc[1]=1;
    for(int i=2;i<=n;i++){
        if(a[i]>lm[i-1]){
            lm[i]=a[i];//更新最大值
            lc[i]=1;
        }
        else if(a[i]==lm[i-1]){//等于当前最大值 
            lm[i]=a[i];
            lc[i]=lc[i-1]+1;//计数
        }
        else{//小于当前最大值 
            lm[i]=lm[i-1];
            lc[i]=lc[i-1];
        }
    }
 
    //计算后子表最大值及出现次数 
    rm[n]=a[n];
    rc[n]=1;
    for(int i=n-1;i>=1;i--){
        if(a[i]>rm[i+1]){//当前元素大于之后最大值
            rm[i]=a[i];
            rc[i]=1;
        }
        else if(a[i]==rm[i+1]){//等于当前最大值 
            rm[i]=a[i];
            rc[i]=rc[i+1]+1;
        }
        else{//小于当前最大值
            rm[i]=rm[i+1];
            rc[i]=rc[i+1];
        }
    }
 
    //枚举所有可能的分割点 
    for(int m=2;m<=n;m++){
        int wm=lm[m-1];//小午部分的最大值 
        int wt=min(lc[m-1],k1);//小午可选该最大值的数量 
        int fm=rm[m];//小枫部分的最大值 
        int ft=min(rc[m],k2);//小枫可选该最大值的数量 
 
        if(wm>fm){//判断是否小午必胜 
            cout<<"YES";
            return 0;
        }
    }
    cout<<"NO";
}

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

T4小午的构造

  • 难度：普及-

  • 思路分析

  1. 优先构造ac单词：
    首先计算能构造的ac单词数量 cc ，取 xx 和 yy 的最小值
    这样能同时消耗 aa 和 cc ，保证不浪费 cc 字母（cc字母仅能构造ac）
  2. 处理剩余字母：
    计算构造ac后剩余的 aa 数量 r=x−cr=x-c
    计算能构造的 wa 数量 ww ，取 zz 和 rr 的最小值
    调整 ww 使得剩余的 aa 能两两组合成 aa
    wa尽可能的少
  3. 构造aa单词：
    剩余 aa 数量为 r−wr-w ，计算能构造的aa数量a=(r−w)/2a=(r-w)/2
    确保所有字母被用完且wa数量最少

  • 通过代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int x,y,z; //a,c,w的数量 
        cin>>x>>y>>z;
        
        //构造所有可能的ac单词 
        int c=min(x,y);//ac数量取a和c的较小值 
        int r=x-c;    //构造ac后剩余的a数量
        
        //计算可能的wa数量 
        int w=min(z,r);//wa数量取w和剩余a的较小值
        //调整w使剩余a能两两组合
        w=max(w-(r-w)%2,0);//确保(r-w)是偶数 
        
        //计算aa数量
        int a=(r-w)/2; // 剩余a构造的aa数量 

        cout<<c+a+w<<' '<<w<<endl;
    } 
}

  • 时间复杂度分析：

仅有处理 tt 组测试用例是涉及循环，时间复杂度 O(t)O(t)。

T5午枫的mex

  • 难度：普及/提高- ？

  • 思路分析

  1. 化简
    需要计算所有 i⊕j(i,j∈[1,n])i⊕j (i,j∈[1,n]) 的 mexmex（最小未出现的非负整数）
    （特判情况） n=1n=1 的特殊情况，直接输出 11 （因为只有 1⊕1=01⊕1=0 ，mexmex 是 11 ）

  2. 瞪眼：
    当 n≥2n≥2 时，最大的异或结果会接近但不小于2k2^k，说人话就是最大异或结果 ≥2k≥2^k（其中2k−1≤n<2k2^{k-1} ≤ n < 2^k）
    mexmex 值实际上是这个 2k2^k

  3. 计算：
    找到大于 nn 的最小 22 的幂次方 mm
    mexmex 结果就是这个 mm

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        //特判情况
        if(n==1){ 
            cout<<"1"<<endl; // mex{0}=1
            continue;
        }
        
        //计算大于n的最小2的幂次方
        long long m=1; //初始化为1
        while(m<=n)m*=2;//找到大于n的最小2^k 
        cout<<m<<endl;
    }
}

  • 时间复杂度分析

此代码仅涉及 tt 次测试样例循环，以及while(m<=n)m*=2; ，复杂度为log nlog~n
总复杂度：O(t×log n)O(t ×log~n)

T6午枫的陪伴时间

  • 官方再次辟谣

  • 难度：普及+/提高 ？

  • 思路分析

  1. 准备阶段
    输入 nn 个选项的起始时间 aia_i
    计算总礼物成本 vv（所有 viv_i 之和）
    筛选出"可接受选项"（当 vi>costiv_i > cost_i 时）：
    结束时间em=ai+t−1e_m = a_i+t-1
    节省金额sm=vi−costis_m= v_i - cost_i
  2. 区间排序：
    对所有可接受选项按结束时间 eme_m 进行升序
    使用下表数组 ix[] 来保持原数组与排序后数组的关系
  3. dp数组：
    初始化：dp[1] =第一个区间的节省值
    状态转移方程（递推是）：
    dp[i] = max(dp[i-1], s[i]+dp[j])
  4. 结算：
    最优解 = 总礼物成本 v−v - 最大节省金额 dpmdp_m
    若无可接受选项 (m=0)(m=0) ，直接输出总礼物成本 vv

  • 通过代码

#include<bits/stdc++.h>
using namespace std;
int e[100010],s[100010];
int a[100010],ix[100010],es[100010]; 
long long dp[100010]; 
bool cp(int x,int y) {return e[x]<e[y];}//比较函数叫cmp在这题叫cp有自己的的道理
int main() {
    int n,t; 
    cin>>n>>t;
    for(int i=1;i<=n;i++) cin>>a[i]; 
    long long v=0;
    int m=0;    
    // 处理每个选项
    for(int i = 1; i <= n; i++) {
        int c, vi;
        cin>>c>>vi;//读取陪伴成本和礼物价格 
        v+=vi;//累计总礼物成本
        
        int si=vi-c;//节省
        if(si>0){//更划算
            m++;
            e[m]=a[i]+t-1;// 记录结束时间
            s[m]=si;//记录节省金额 
        }
    }   
 for(int i=1; i<=m; i++) ix[i]=i; 
    sort(ix+1,ix+m+1,cp); 
    if(!m){
        cout<<v<<endl;
        return 0;
    }
    for(int i=1;i<=m;i++)es[i]=e[ix[i]];
    //初始化
    dp[1]=s[ix[1]];
    
    for(int i=2;i<=m;i++) {
        int ce=es[i],cs=s[ix[i]];
        int tar=ce-t;//计算不重叠前驱地最晚结束时间
        int j=upper_bound(es+1,es+i,tar)-es-1;
        long long tmp=cs;
        if(j>=1)tmp+=dp[j];
        dp[i]=max(dp[i-1],tmp);
    }
    cout<<v-dp[m];
}

  • 时间复杂度分析

O(n+m log m)O(n+m~log~m)

userId_undefined
去预览
0/2000

全部评论 10

热门讨论