欢乐赛43题解

‮‮༺དༀ༒∞░∞༒ༀཌ༻

2025-03-19 17:27:32

发布于：浙江

62阅读

0回复

0点赞

先报下个人难度：红红红红红/橙红
本人未接触算法，如有错误望大神指出！本人会迅速改正！ ACGO_gif_加油喝彩 ~~这次的欢乐赛真水~~

T1:

只需要简单的分支结构判断即可

#include <iostream>
using namespace std;
int main(){
    int a;
    cin >> a;
    if(a<=100)cout << a;
    else if(a>100 and a<=200)cout << a-10;
    else if(a>200 and a<=300)cout << a-20;
    else cout << a-50;
    return 0;
}

时间复杂度: $O(1)$

T2：

本题先读取数组长度，在读取需要交换的元素索引，注意，下标是从一开始的，所以我们也从1开始：

#include <iostream>
using namespace std;
int main(){
    int a,n,m,sz[100000]={};
    cin >> a >> n >> m;
    for(int i=1;i<=a;i++)
        cin >> sz[i];
    //交换数组
    int k=sz[n];
    sz[n]=sz[m];
    sz[m]=k;
    for(int i=1;i<=a;i++)cout << sz[i]<<" ";
    return 0;
}

时间复杂度: $O(n)$

T3：

本题需要在左上角、右上角、左下角、右下角的位置跳过，假设二维数组的行和列为a，下标从1开始，那么只需要在（1，a） (a，a) (1，1) （a，1）的位置跳过即可。剩下的位置我们用num变量相加。最后输出。

#include <iostream>
using namespace std;
int main(){
    long long num=0,a,sz[1005][1005]={};//定义二维数组
    cin >> a;
    for(int i=1;i<=a;i++){
        for(int j=1;j<=a;j++){
            cin >> sz[i][j];
            if((i==1 and j==a) or (i==a and j==a) or (i==1 and j==1)or (i==a and j==1)){//在相应的位置跳过
                sz[i][j]=0;
            }num+=sz[i][j];
        }
    }cout << num;
    return 0;
}

时间复杂度: $O(n^2)$

T4:

本题可以先创建一个函数来分解数位，可以用while逐个拆解并相加,或者转换成字符串，之后用for相加，再减去'0'。最后在主函数里判断即可：

#include <iostream>
using namespace std;
//返回数位之和
bool m(int i,int n){
    int num=0;
    string a=to_string(i);
    for(int i=0;i<=a.size()-1;i++){
        num+=a[i];
        num-='0';
    }if(num==n){
        return true;
    }else return false;
}
int main(){
    int a,b,n,num;//a和b为区间，n为数位之和
    cin >> a >> b >> n;
    for(int i=a;i<=b;i++){
        if(m(i,n)){
            num++;
        }
    }cout << num;
    return 0;
}

时间复杂度: $O(n)$

T5:

通过题面我们不难看出，整个字符串只会出现一次M，所以子串的个数就是M左边的K的数量乘以M右边的P的数量：

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long num=0,sum=0;//num为M左边K的数量，sum为M右边P的数量
    string a;cin >> a;
    int n=0;
    for(int i=0;i<=a.size()-1;i++){
        if(a[i]=='M'){
            n=i;
            break;
        }
    }
    for(int i=0;i<=n;i++){
        if(a[i]=='K')num++;
        
    }for(int i=n;i<=a.size()-1;i++){
        if(a[i]=='P'){
            sum++;
        }
    }
    cout << sum*num;
    return 0;
}

T6:

本题由于数据量不大，所以暴力完全可以（要注意的是小于n，不是小于等于）：

#include <bits/stdc++.h>
using namespace std;
bool m(int i){
    for(int j=2;j<=(int)sqrt(i)+1;j++){//由于sqrt函数的特性，所以最好加上一，或者for(int i=2;i*i<=n;i++)
        if(i!=j and i%j==0){
            return false;
        }
    }return true;
}
int main(){
    int t;
    cin >> t;
    for(int k=1;k<=t;k++){
        long long n;
        cin >> n;
        for(int i=n-1;i>=2;i--){
            if(m(i)){
                cout << i<<endl;
                break;
            }
        }
    }
    return 0;
}