# 官方题解｜欢乐赛#42

userId_undefined

桌子乱的反义词

荣耀黄金

2025-03-12 15:39:24

发布于：浙江

88阅读
0回复
0点赞

官方题解｜欢乐赛#42

T1

思路分析

本题主要考察求解最大公约数的暴力做法，可以从大到小枚举所有的数，第一个出现的就是最大公约数，那么第二个出现的就是次大公约数了。也可以求出所有的公约数，然后通过下标去寻找次大的公约数。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t -- ){
        int a, b;
        cin >> a >> b;
        vector<int>q;//递减的顺序存储所有公约数
        for(int i = a; i >= 1; i -- ){
            if(a % i == 0 && b % i == 0) q.push_back(i);
        }
        //q[0]是最大公约数, q[1]是次大公约数
        if(q.size() >= 2) cout << q[1] << endl;
        else cout << "-1" << endl;;        
    }
    return 0;
}

T2

思路分析

本题是一个简单的思维题，我们能发现 4!4! 是第一个2424 的倍数，后面更大的数的阶乘又一定是 4!4! 的倍数，因为n!=1×2×3×4……×nn! = 1 \times 2 \times 3 \times 4 …… \times n。所以当 n≤3n \leq 3 的时候，输出 "NO",否则输出 "YES"。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int x;
    cin >> x;
    if(x <= 3) cout << "NO";
    else cout << "YES";
    return 0;
}

T3

本题考查双重循环，类似于考级的题目，我们可以从下标为 11 开始读入字符串，然后对于第 ii 个字符嵌套一个循环输出 ii 遍即可。

#include <bits/stdc++.h>
using namespace std;

int n;
string s;

int main(){
    cin >> n >> s;
    s = " "  + s;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= i; j ++ ){
            cout << s[i];
        }
    }
    return 0;
}

T4

本题是一个很经典的问题，你可以暴力按照字典序搜索到第 mm 小的数字，也可以直接灵活运用 next_permutation 来进行求解，如果选择后者那么你要先构造一个长度为 nn 的字典序最小的序列。

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
int a[N];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) a[i] = i;
    int cnt = 0;
    do{
        cnt ++;
        if(cnt == m){
            for(int i = 1; i <= n; i ++) {
                cout << a[i] << " ";
            }
            break;
        }
    }while(next_permutation(a + 1, a + 1 + n));
    return 0;
}

T5

思路分析

本题是一道类似于2024csp-jT3的一道题，需要分类讨论。要想yy最大，我们肯定要想 yy 最长，所以我们尽可能的通过一些小的阶乘来替换大的阶乘。例如6!=5!∗3!6! = 5! * 3!，我们可以通过 55 和 33 来替换 66 从产生的贡献，还有一些类似的替换方法，详细见代码。我们统计出每个数最多可以出现的次数，然后按照字典序最大的方式输出即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
int n, cnt[N];
string s;

int main(){
    cin >> s;
    for(auto it : s){
        if(it == '1') cnt[1] ++;
        if(it == '2') cnt[2] ++;
        if(it == '3') cnt[3] ++;
        if(it == '4') cnt[3] ++, cnt[2] += 2;//4!=3!*2!*2!
        if(it == '5') cnt[5] ++;
        if(it == '6') cnt[5] ++, cnt[3] ++;//6!=5!*3!
        if(it == '7') cnt[7] ++;
        if(it == '8') cnt[7] ++, cnt[2] += 3;//8!=7!*2!*2!*2!
        if(it == '9') cnt[7] ++, cnt[3] += 2, cnt[2] ++;
    }
    for(int i = 9; i >= 2; i -- ){
        for(int j = 1; j <= cnt[i]; j ++ ){
            cout << i;
        }
    }
    return 0;
}

T6

思路分析

本题考查贪心，数据范围很小，可以采用 O(n2)O(n^2) 的时间复杂度。我们可以先把所有的元素排个序，然后依次从前往后选，如果满足当前选的比前一个选的大就选上，并统计答案，记得把选过的标记一下，一直选到不能选为止即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int a[N], n;
bool st[N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    bool f = 0;//f等于0的时候，表示一个还没选，等于1表示前面已经有选的了
    int x, sum = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            if(st[j] == 0){
                if(f == 0) {//等于0的时候代表现在要选第一个，所以不产生贡献
                    x = a[j], f = 1;
                    st[j] = 1;
                }
                else if(a[j] > x){
                    x = a[j];
                    sum ++;
                    st[j] = 1;
                }
            }
            if(j == n) f = 0;
        }
    }
    cout << sum;
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 2

热门讨论