欢乐赛#44题解

你是不是喜欢c++

2025-04-06 22:07:14

发布于：广东

22阅读

0回复

0点赞

ACGO欢乐赛#44题解

前言

这是本蒟蒻第一次写题解，请各位大佬们多多指点

注：个人代码习惯不喜欢写空格，敬请谅解。

本场欢乐赛整体难度太水了较为简单，评级如下。

题目	真实难度	个人难度
O	入门	入门
行图	入门	入门
罚时计算	入门	入门
困难的字符串改造问题	普及-	入门
追求更多的玫瑰花	入门	入门
进制转换	入门	普及-

话不多说，直接开始——

题目解析

T1 -- O
知识点：输入输出
题目描述：要求出100以内的所有数中，哪一个数的“O”最多，数字 0,4,6,9 里面有 1 个 "O"，数字 8 中有 2 个 "O"。

解析：其实题目中已经说得很明确了，对单一一个数字来说，8是有最多“O”的数，所以两位数88所含有的“O”最多，直接输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout << 88 << endl;
    return 0;
}

时间复杂度：O(1)

T2 -- 行图
知识点：循环结构，条件语句
题目描述：输入n个整数，第二个数开始，对于每个数，判断这个数是否为上一个数的因数，累计总数。

解析：定义一个num用来记录上一个数，一个sum用来统计数量，每次判断并累计数量。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[100005];
    cin>>n;
    int num,sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    num=a[1];
    for(int i=2;i<=n;i++)
    {
        if(num%a[i]==0)
        {
            sum++;
            num=a[i];
        }
        else num=a[i];
    }
    cout<<sum<<endl;
    return 0;
}

时间复杂度：O(n)

T3 -- 罚时计算
知识点：循环结构
题目描述：输入n表示有n个人，随后对于每个人，输入m个数，表示每道题提交的次数，每道题除第一次提交外，随后的提交每多一次，罚时20min,求出每个人的总罚时。

解析：直接循环遍历即可，注意每次累加器清零。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int sum=0;
        for(int j=1;j<=m;j++)
        {
            int a;
            cin>>a;
            sum+=(a-1)*20;
        }
        cout<<sum<<" ";
    }
    return 0;
}

时间复杂度：O(n*m)

T4 -- 困难的字符串改造问题
知识点：字符串
题目描述：输入一个字符串，每遇到一个空格，就将它替换成下一个字母（A到Z，Z下一个是A）。

解析：定义一个num记录目前遇到的空格数量，每次遇到空格就求现在应该替换的字母，并替换。注意输入处理，用getline，否则输入不了空格。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    int num=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]==' ')
        {
            num++;
            s[i]=char('A'+num-1);
            num=num%26;
        }
        cout<<s[i];
    }
    return 0;
}

时间复杂度：O(|s|)

T5 -- 追求更多的玫瑰花
知识点：输入输出，条件语句
题目描述：给定一个n个数的数组，其中的每一个数只能是1或-1，再有m次询问，每次给出两个数l和r，判断能否调整数组顺序使得[l,r]中的数加起来为0（即1与-1的数量相等），输出"happy"或"sad"。

解析：思维题。统计数组中1(变量zheng)与-1(变量fu)的数量，若区间有奇数个数，则直接输出"sad"，否则判断有没有区间数量/2个1与-1，输出。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int zheng,fu;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        if(a==1) zheng++;
        else fu++;
    }
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        int len=b-a+1;
        if(len%2==1) cout<<"sad"<<endl;
        else
        {
            len/=2;
            if(zheng>=len&&fu>=len) cout<<"happy"<<endl;
            else cout<<"sad"<<endl;
        }
    }
    return 0;
}

时间复杂度：O(n+m)

T6 -- 进制转换
知识点：进制转换，sort排序
题目描述：给定n个数，先将它们转换成八进制，随后：

先按照的最低位从大到小排序。
如果最低位的数一样，那么就按这个数进行从小到大排序。

解析：将八进制的数存在数组b中（用十进制的方式存储，方便排序），再排序（用sort,写一个cmp）,注意一定要开long long，否则会WA!!

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[200005],b[200005],x;
long long f(long long num) 
{
    long long res=0,sum=1;
    while (num>0) 
    {
        res+=(num%8)*sum;
        num/=8;
        sum*=10;
    }
    return res;
}
bool cmp(long long a,long long b)
{
    if(a%10!=b%10) return a%10>b%10;
    else return a<b;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=f(a[i]);
    }
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++) cout<<b[i]<<" ";
    return 0;
}