官方题解 | 欢乐赛#57 题解

你好

2025-09-29 11:19:06

发布于：浙江

129阅读

0回复

0点赞

官方题解 | 欢乐赛#57 题解

赛纲介绍

本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目名称	题目难度
T1	小明的国庆假期	入门
T2	小明的食材选择	入门
T3	小明的字符串修改	入门
T4	小明的餐馆开业	入门
T5	小明打地鼠	入门
T6	小明的字符串排序	普及-

T1 小明的国庆假期

题目大意

国庆从 $10$ 月 $1$ 日开始到 $10$ 月 $7$ 日，而中秋节从 $10$ 月 $x$ 日开始放假 $3$ 天，国庆和中秋的重叠部分不会补休，问今年的中秋和国庆假期一共会放几天假期？

题解思路

在不重叠情况下一共会放假 $10$ 天，因此只需要扣掉重叠天数即可。重叠天数为 $7 - x + 1$ ，因此总天数为

$10 - (7 - x + 1) = x + 2$ ，并且总天数是大于等于 $7$ 的，因此答案为 $max(7, x + 2)$ 。

参考代码

#include <iostream>
using namespace std;
int main() {
    int x;
    cin >> x;
    if(x > 7) cout << 10 << endl;
    else cout << max(7, x + 2) << endl;
}

T2 小明的食材选择

题目大意

对于给定的数组，在其中找出三个数字 $x, y, z$ ，使得 $x^3 + y^2 + z$ 最大。

题解思路

为了使得结果最大，需要让 $x$ 为整个数组的最大值，让 $y$ 为整个数组的次大值, 让 $z$ 为整个数组的第三大值。

因此问题转化成求数组最大的三个数字。

学过排序的同学可以直接sort排序然后使用数组末尾最大的三个数字。

也可以通过三次遍历来找到最大的三个数：

第一趟遍历找到数组中最大的数字对应的下标，记录最大值之后将其修改为 $0$ ,

第二趟遍历继续找最大值，此时的最大值即为原数组的次大值，再将其修改为 $0$ ，

第三趟再遍历找最大值，此时的最大值就是原数组第三大的数字。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main() {
    int n, x, y, z;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int p = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] > a[p]) p = i; //寻找最大值的下标
    }
    x = a[p]; a[p] = 0; //记录最大值并且将其在数组中修改为0
    p = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] > a[p]) p = i; //寻找最大值的下标
    }
    y = a[p]; a[p] = 0; //记录次大值并且将其在数组中修改为0
    p = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] > a[p]) p = i; //寻找最大值的下标
    }
    z = a[p]; a[p] = 0; //记录第三大值
    cout << x * x * x + y * y + z;
    return 0;
}

T3 小明和字符串修改

题目大意

给定一个字符串 $s$ ，对于其中的所有的 a,c,g,o这四种字母都修改成大写，所有其他的 $22$ 种字母都修改成小写。

题解思路

为了方便判断字母的种类，我们先把整个字符串内所有字母都修改为小写。

然后再次遍历字符串，如果是 a,c,g,o 这四种字母之一，则修改为大写即可。

参考代码

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] <= 'Z') s[i] += 32;
    }
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'a' || s[i] == 'c' || s[i] == 'g' || s[i] == 'o') s[i] -= 32;
    }
    cout << s << endl;
    
    return 0;
}

T4 小明和餐馆开业

题目大意

在一张地图上存在 $n$ 个餐馆，选择其中之一可以得到该点和曼哈顿距离在 $D$ 以内所有餐馆的客流量总和的繁华值，求经过选择后可以得到的最大的繁华值。

题解思路

本题数据范围较小，餐馆数量 $n \le 1000$ ，因此可以枚举一下要选择的餐馆, 而后再遍历所有的餐馆，计算范围内所有餐馆的客流量总和，时间复杂度 $O(n^2)$ 。

参考代码

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

int n, d;
int x[1010], y[1010], z[1010];
int main() {
    cin >> n >> d;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> z[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int sum = 0;
        for(int j = 1; j <= n; j++) {
            if(abs(x[i] - x[j]) + abs(y[i] - y[j]) <= d) sum += z[j];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

T5 小明打地鼠

题目大意

给定一个 $n \times n$ 的二维数组 $a$ ，可以选择一个点 $(x, y)$ 后，得到出现在第 $x$ 行一整行和第 $y$ 列一整列的所有数字的总和，问经过选择后可以得到的数字总和的最大值。

题解思路

暴力解：

枚举所有的点 $(x, y)$ -- 复杂度 $O(n^2)$ ，

对于当前的点 $(x, y)$ ，出现在第 $x$ 行一整行和第 $y$ 列一整列的所有数字求总和 $--O(n)$ ,

总复杂度 $O(n^3)$ ，可以拿到 $20$ 分。

优化：

可以在输入时候记录一下每一行的总和 $row[i]$ 以及每一列的总和 $col[j]$ ，那么对于当前的点 $(x, y)$ ，出现在第 $x$ 行一整行和第 $y$ 列一整列的所有数字的总和即为 $row[x] + col[y] - a[x][y]$ 。

总复杂度 $O(n^2)$ 。

参考代码

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

int a[5010][5010];
int r[5010], c[5010];
int main(){
    int n, m;
    cin >> n >> m;
    while(m--) {
        int x, y;
        cin >> x >> y;
        a[x][y]++;
        r[x]++;
        c[y]++;
    }
    int ans = 0;
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            ans = max(ans, r[i] + c[j] - a[i][j]);
        }
    }
    cout << ans << endl;

}

T6 小明的字符串排序

题目大意

给定 $n$ 个只有大小写字母的字符串，并且准备按照以下三个优先级的规则进行排序。

1.只有小写或者只有大写的串需要排在大小写混杂的字符串前面。

2.如果两个字符串同为只有大写或者小写,或者同为大小写混杂，则长度较短的字符串需要排在长度较长的字符串前面。

3.长度相等的字符串直接按照字典序从小到大来排序。

把 $n$ 个字符串排序之后全部输出。

题解思路

本题的排序规则具有多个优先级，因此可以考虑自定义cmp函数作为排序的规则。

可以写一个自定义函数check来快速判定该字符串是否是一个大小写混杂的字符串。

cmp函数内部，先比较字符串是否是混杂的，再比较长度，最后比较字典序。直接调用sort函数并且传入自定义的比较函数cmp进行排序即可。

参考代码

#include <bits/stdc++.h>

using namespace std;
string a[100010];
bool check(string s) {
    bool c = 0, l = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] <= 'Z') c = true;
        else l = true;
    }
    return c + l == 1;
}

bool cmp(string a, string b) {
    bool cka = check(a), ckb = check(b);
    if(cka != ckb) return cka > ckb;
    if(a.size() != b.size()) return a.size() < b.size();
    return a < b;
}


int main()
{   
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n, cmp);
    for(int i = 1; i <= n; i++) cout << a[i] << '\n';
}