#非官方题解#挑战赛#28

Srobot

2026-02-22 22:00:12

发布于：广东

16阅读

0回复

0点赞

这次挑战赛就我而言难度不大，大概是下面这个样子：

题目	难度
T1	入门
T2	入门
T3	普及-
T4	入门
T5	普及/提高-
T6	普及-

T1 午枫的翻转

题目大意：给定一个字符串 $s$ ，翻转 $s$ 从 $l$ 到 $r$ 所构成的子串，并输出最终的 $s$ 。
我们很容易想到，可以先输出 $s_1$ ~ $s_{l-1}$ ，再逆序输出 $s_r$ ~ $s_l$ ，最后输出 $s_{r+1}$ ~ $s_n$ 。
以下是参考代码，时间复杂度为 $O(n)$ 。

// T1 午枫的翻转 参考代码
#include <iostream>
using namespace std;
int main(){
    int l,r;
    cin>>l>>r;
    string s;
    cin>>s; // 输入
    for(int i=0;i<l-1;i++)
        cout<<s[i];
    for(int i=r-1;i>=l-1;i--)
        cout<<s[i];
    for(int i=r;i<s.size();i++)
        cout<<s[i]; // 按序输出
    return 0;
}

T2 午枫的卡片交换

题目大意：现有 $2$ 个字符串 $s$ 和 $t$ ，且 $|s|=|t|$ ，询问是否可以通过最多一次交换 $s$ 中 $2$ 个相邻的字符使得 $s=t$ 。
因为 $s$ 和 $t$ 的长度不大，可以直接枚举交换 $s_i$ 和 $s_{i+1}$ ，并判断是否与 $t$ 相等，注意还要判断不交换的情况。
以下是参考代码，时间复杂度为 $O(n)$ 。

// T2 午枫的卡片交换 参考代码
#include <iostream>
using namespace std;
int main(){
    string s,t;
    cin>>s>>t; // 输入
    bool b=false;
    if(s==t){
        cout<<"Yes";
        return 0; // 如果本就一样直接输出 Yes
    }
    for(int i=0;i<s.size()-1;i++){ // 枚举 i
        swap(s[i],s[i+1]);
        if(s==t){
            cout<<"Yes";
            return 0; // 判断交换后是否一样
        }
        swap(s[i],s[i+1]);
    }
    cout<<"No"; // 如果一直不一样就输出 No
    return 0;
}

T3 午枫的石头剪刀布大赛

题目大意：有 $2n$ 名选手进行石头剪刀布比赛，总共有 $m$ 轮比赛，每轮都有 $n$ 场 $1v1$ 的比赛，在第 $i$ 轮比赛结束时，会进行重新排名，胜场数多的排名更高，胜场数一样编号小的排名更高，然后开始编排对战，排名第 $2k-1$ 的选手和排名第 $2k$ 的选手进行对战，现在已知所有人在每一轮比赛中出的手势，每场比赛结果只有胜、负、和三种，求最终的比赛排名。
这题本质上就是大模拟，用结构体记录每个人的编号和胜场数，模拟比赛的进行，判断胜负然后重新排名，最后输出即可。
以下是参考代码，时间复杂度为 $O(mnlogn)$ 。

// T3 午枫的石头剪刀布大赛 参考代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[110][110]; // 记录选手每轮比赛出的手势
struct mc{
    int id,sc;
}us[110]; // 选手信息结构体
bool cmp(mc x,mc y){
    if(x.sc==y.sc)
        return x.id<y.id;
    return x.sc>y.sc;
} // 定义比较函数
int hw(int x,int y){ // 判断胜（1）、负（-1）、和（0）
    if(x==y)
        return 0;
    if(x==1){ // 1、2、3 分别表示石头、剪刀、布
        if(y==2)
            return 1;
        return -1;
    }
    if(x==2){
        if(y==1)
            return -1;
        return 1;
    }
    if(x==3){
        if(y==1)
            return 1;
        return -1;
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n*2;i++){
        us[i].id=i;
        us[i].sc=0;
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='G')
                a[i][j]=1;
            if(c=='C')
                a[i][j]=2;
            if(c=='P')
                a[i][j]=3;
        }
    } // 输入
    for(int i=1;i<=m;i++){ // 模拟每轮比赛的进行
        for(int j=1;j<=n;j++){ // 模拟第 i 轮的每场比赛
            int e=hw(a[us[j*2-1].id][i],a[us[j*2].id][i]);
            if(e==1)
                us[j*2-1].sc++;
            if(e==-1)
                us[j*2].sc++; // 判断胜负并更改胜场数
        }
        sort(us+1,us+n*2+1,cmp); // 最后重新排名
    }
    for(int i=1;i<=n*2;i++)
        cout<<us[i].id<<endl; // 输出最终排名
    return 0;
}

T4 午枫的复制魔法

题目大意：给定一个长度为 $n$ 的数组 $a$ ，对其无限复制拼接后得到数组 $b$ ，其中 $b_i=a_{(i-1)\%n+1}$ ，记 $S_k=b_1+b_2+...+b_{k-1}+b_k=\sum_{i=1}^{k}b_i$ ，求满足 $S_k>x$ 的最小的 $k$ 。
不妨先将数组 $a$ 中所有元素加起来记为 $S$ ，那么 $k$ 应不小于 $u=x/S*n$ ，此时的 $S_k$ 要达到 $x$ 还差 $v=x-S_u=x\%S$ ，这里可以先预处理一个前缀和数组 $s$ ， $s_1=a_1$ 且 $s_i=s_{i-1}+a_i$ ，在 $s$ 中寻找第一个大于 $v$ 的元素下标 $w$ ，即最终答案为 $u+w$ 。
以下是参考代码，时间复杂度为 $O(n)$ 。

// T4 午枫的复制魔法 参考代码
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
ll a[100010]; // 原数组
ll s[100010]; // 前缀和数组
int main(){
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    ll x;
    cin>>x; // 输入
    ll ans=x/s[n]*n; // 初始化答案
    ll u=x%s[n]; // 计算剩余部分
    ans+=upper_bound(s+1,s+n+1,u)-s; // 使用二分上界快速定位正确的下标
    cout<<ans; // 输出
}

T5 午枫的用户记录

题目大意：系统中记录了 $n$ 位用户的登陆情况，第 $i$ 位用户第 $t_i$ 天起开始登陆，连续登陆了 $c_i$ 天，其余时间无登陆，求对于每一个合法的 $k$ ，恰好有 $k$ 个人登陆的天数。
看到题目，很自然会想到差分数组，但庞大的数据范围使得用标准差分将直接 $TLE$ ，因此我们需要对差分算法进行优化，注意到用户的数量远远小于登陆天数，所以可以使用哈希表对差分进行优化，简单来说就是先用一个数组记录差分数组中每个非 $0$ 元素的位置，再用哈希表对应记录这些元素的数值，最后通过遍历统计恰好有 $k$ 个人登陆时的天数即可。
以下是参考代码，时间复杂度为 $O(nlogn)$ 。

// T5 午枫的用户记录 参考代码
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define ll long long
map<ll,ll> p; // 用于记录差分数组中非 0 元素数值的哈希表
map<ll,bool> k; // 用于记录该非 0 元素是否已在差分数组中的哈希表
ll nd[400010],ct; // 用于记录差分数组中非 0 元素位置的数组
ll res[200010]; // 最后的结果数组
int main(){
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++){
        ll a,b;
        cin>>a>>b;
        b+=a; // 将 b 转为结束登陆的后一天
        if(!k[a])
            nd[++ct]=a;
        if(!k[b])
            nd[++ct]=b;
        p[a]++;
        p[b]--; // 经典的差分操作
        k[a]=true;
        k[b]=true;
    } // 输入
    sort(nd+1,nd+ct+1); // 对非 0 元素位置进行排序
    ll nw=0,ls=1; // nw 是当前在线人数，ls 是上一个非 0 元素的位置
    for(ll i=1;i<=ct;i++){ // 枚举每一个非 0 元素
        res[nw]+=nd[i]-ls; // 增加恰好有 nw 人在线时的天数
        ls=nd[i]; // 更新上一个非 0 元素的位置
        nw+=p[nd[i]]; // 更新当前在线人数
    }
    for(ll i=1;i<=n;i++)
        cout<<res[i]<<' '; // 遍历输出
    return 0;
}

T6 午枫的数字分离

题目大意：给定一个正整数 $n$ ，将 $n$ 的各位数字重新排列后分成 $2$ 个不带有前导 $0$ 的正整数，求这 $2$ 个正整数乘积的最大值。
由于 $n$ 的大小很小，因此完全可以用二进制枚举所有可能的拆分组合，并统计其乘积最大值即可。
以下是参考代码，时间复杂度为 $O(lgn2^{lgn})$ 。

// T6 午枫的数字分离 参考代码
#include <iostream>
using namespace std;
#define ll long long
ll a[20],x[20],y[20]; // 分别记录 n 的各位数字、拆出来的两个数 1~9 的数量
int main(){
    ll n;
    cin>>n; // 输入
    ll p=0; // p 为 n 的长度
    while(n){
        p++;
        a[p]=n%10;
        n/=10;
    } // 初始化数组 a
    ll ans=0;
    for(ll s=0;s<(1<<p);s++){ // 二进制枚举所有拆分组合
        for(ll i=0;i<=9;i++)
            x[i]=y[i]=0;
        for(ll i=1;i<=p;i++){
            if((s>>(i-1))&1)
                x[a[i]]++;
            else
                y[a[i]]++;
        } // 初始化数组 x 和 y
        ll qx=0,qy=0;
        for(ll i=9;i>=0;i--){
            for(ll j=1;j<=x[i];j++){
                qx*=10;
                qx+=i;
            }
            for(ll j=1;j<=y[i];j++){
                qy*=10;
                qy+=i;
            }
        } // 计算拆出来两数的值
        ans=max(ans,qx*qy); // 统计最大值
    }
    cout<<ans; // 输出
    return 0;
}