非官方题解|欢乐赛#71

༺ཌༀ我要上浙大ༀད༻

2026-04-15 15:51:35

发布于：浙江

7阅读

0回复

0点赞

先叠甲：本人第一次写题解，误喷
T1
本题十分简单，只需要输入数组，再逆序输出即可，代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[5];
    for(int i=1;i<=4;i++){
        cin>>a[i];//输入
    }
    for(int i=4;i>=1;i--){
        cout<<a[i]<<" ";//逆序输出
    }
}

时间复杂度: $O(1)$
T2
本题依旧简单，只需要做一下判断,题解如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,ans=0;
    cin>>a>>b>>c;
    ans=a+b+c;
    if(a>=90&&b>=90&&c>=90){
        cout<<"一等奖";//一等奖的情况
    }
    else{
        if(ans>=270){
            cout<<"二等奖";//二等奖的情况
        }
        else if(ans>=240){
            cout<<"三等奖";//三等奖的情况
        }
        else if(ans>=180){
            cout<<"优秀奖";//优秀奖的情况
        }
        else{
            cout<<"未获奖";//未获奖的情况
        }
    }
    return 0;
}

时间复杂度: $O(1)$
T3
本题应为长度<=1000,所以可以直接暴力，直接将字符加入字符串，代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,s1; // s:输入串；s1:结果串（未预分配空间）
    cin>>s;
    for(int i=0;i<s.size();i+=2){// 步长为2，遍历所有字母位置
        char c=s[i];// 当前字母
        int r=s[i+1]-'0';// 对应数字（'1'→1, ..., '9'→9）
        for(int j=0;j<r;j++){
            s1.push_back(c); // 重复添加r次
        }
    }
    cout<<s1;
    return 0;
}

时间复杂度: $O(n)$
T4
给定两个 n×m 的 0/1 字符矩阵 a和b。
对每个位置如果a[i][j]!=b[i][j],个数++。
匹配程度 = n×m匹配成功的位置数。判断该比值是否 ≥x，输出 YES 或 NO。
代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    double x;
    cin>>n>>m>>x;
    vector<string> a(n),b(n);//用字符更简单
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    int match=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]!=b[i][j]){
                match++;//计数
            }
        }
    }
    if(match*1.0/(n*m)>=x){
        cout<<"YES";
    } 
    else{
        cout<<"NO";//判断
    }
    return 0;
}

时间复杂度: $O(nm)$
T5
本题因为n<=100,所以直接暴力是最优解，直接三重循环即可，代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x,a[105];
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(a[i]+a[j]+a[k]==x){
                    cnt++;
                }  
            }
        }
    }
    cout<<cnt;
    return 0;
}

时间复杂度: $O(n^3)$
T6
因为题目数据范围最大到 $10^5$ ，所以我们需要判断的数最大也就是 $10^5$ 以内的数，以及它们在数位和过程中的中间结果。
因此可以用筛法（埃氏筛或线性筛）预处理出 $10^5$ 以内的所有质数。
对每个数，反复计算数位和，每一步都判断是否为质数，如果某一步不是质数，则不是好数。由于数据范围不大，我们可以直接对 $[l, r]$ 中的每个数逐一判断，时间复杂度完全可行。代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000;
vector<bool> is(MAXN+1,true);
// 筛法预处理质数
void sieve(){
    is[0]=is[1]=false;
    for(int i=2;i*i<=MAXN;i++){
        if(is[i]){
            for(int j=i*i;j<=MAXN;j+=i){
                is[j]=false;
            }
        }
    }
}
// 计算数位和
int sum(int x){
    int sum=0;
    while(x>0){
        sum+=x%10;
        x/=10;
    }
    return sum;
}
// 判断是否为好数
bool good(int x){
    while(true){
        if(!is[x])return false;
        if(x<10)break;
        x=sum(x);
    }
    return true;
}
int main(){
    sieve();
    int l,r;
    cin>>l>>r;
    int count=0;
    for(int i=l;i<=r;i++){
        if(good(i))
            count++;
    }
    cout<<count;
    return 0;
}

时间复杂度: $10^5$

有帮助，赞一个

去预览

0/2000

全部评论 1

梦瑶
厉害

3天前来自浙江
0

全部评论 1

热门讨论