官方题解 | 欢乐赛#57 题解
赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 小明的国庆假期 入门 T2 小明的食材选择 入门 T3 小明的字符串修改 入门 T4 小明的餐馆开业 入门 T5 小明打地鼠 入门 T6 小明的字符串排序 普及-
T1 小明的国庆假期
题目大意
国庆从 101010 月 111 日开始到 101010 月 777 日， 而中秋节从 101010 月 xxx 日开始放假 333 天，国庆和中秋的重叠部分不会补休，问今年的中秋和国庆假期一共会放几天假期？
题解思路
在不重叠情况下一共会放假 101010 天， 因此只需要扣掉重叠天数即可。 重叠天数为 7−x+17 - x + 17−x+1 ，因此总天数为
10−(7−x+1)=x+210 - (7 - x + 1) = x + 210−(7−x+1)=x+2，并且总天数是大于等于 777 的，因此答案为 max(7,x+2)max(7, x + 2)max(7,x+2)。
参考代码
T2 小明的食材选择
题目大意
对于给定的数组，在其中找出三个数字 x,y,zx, y, zx,y,z，使得 x3+y2+zx^3 + y^2 + zx3+y2+z 最大。
题解思路
为了使得结果最大，需要让 xxx 为整个数组的最大值，让 yyy 为整个数组的次大值, 让 zzz 为整个数组的第三大值。
因此问题转化成求数组最大的三个数字。
学过排序的同学可以直接sort排序然后使用数组末尾最大的三个数字。
也可以通过三次遍历来找到最大的三个数：
第一趟遍历找到数组中最大的数字对应的下标， 记录最大值之后将其修改为 000,
第二趟遍历继续找最大值，此时的最大值即为原数组的次大值， 再将其修改为 000，
第三趟再遍历找最大值，此时的最大值就是原数组第三大的数字。
参考代码
T3 小明和字符串修改
题目大意
给定一个字符串 sss， 对于其中的所有的 a,c,g,o这四种字母都修改成大写，所有其他的 222222 种字母都修改成小写。
题解思路
为了方便判断字母的种类，我们先把整个字符串内所有字母都修改为小写。
然后再次遍历字符串， 如果是 a,c,g,o 这四种字母之一，则修改为大写即可。
参考代码
T4 小明和餐馆开业
题目大意
在一张地图上存在 nnn 个餐馆， 选择其中之一可以得到该点和曼哈顿距离在 DDD 以内所有餐馆的客流量总和的繁华值，求经过选择后可以得到的最大的繁华值。
题解思路
本题数据范围较小， 餐馆数量 n≤1000n \le 1000n≤1000， 因此可以枚举一下要选择的餐馆, 而后再遍历所有的餐馆， 计算范围内所有餐馆的客流量总和，时间复杂度 O(n2)O(n^2)O(n2) 。
参考代码
T5 小明打地鼠
题目大意
给定一个 n×nn \times nn×n 的二维数组 aaa，可以选择一个点 (x,y)(x, y)(x,y)后， 得到出现在第 xxx 行一整行和第 yyy 列一整列的所有数字的总和，问经过选择后可以得到的数字总和的最大值。
题解思路
暴力解：
枚举所有的点 (x,y)(x, y)(x,y)-- 复杂度 O(n2)O(n^2)O(n2)，
对于当前的点(x,y)(x, y)(x,y) ，出现在第 xxx 行一整行和第 yyy 列一整列的所有数字求总和−−O(n)--O(n)−−O(n),
总复杂度O(n3)O(n^3)O(n3) ，可以拿到 202020 分。
优化：
可以在输入时候记录一下每一行的总和 row[i]row[i]row[i]以及每一列的总和 col[j]col[j]col[j] ， 那么对于当前的点(x,y)(x, y)(x,y) ，出现在第 xxx 行一整行和第 yyy 列一整列的所有数字的总和即为 row[x]+col[y]−a[x][y]row[x] + col[y] - a[x][y]row[x]+col[y]−a[x][y]。
总复杂度 O(n2)O(n^2)O(n2)。
参考代码
T6 小明的字符串排序
题目大意
给定 nnn 个只有大小写字母的字符串， 并且准备按照以下三个优先级的规则进行排序。
1.只有小写或者只有大写的串需要排在大小写混杂的字符串前面。
2.如果两个字符串同为只有大写或者小写,或者同为大小写混杂，则长度较短的字符串需要排在长度较长的字符串前面。
3.长度相等的字符串直接按照字典序从小到大来排序。
把 nnn 个字符串排序之后全部输出。
题解思路
本题的排序规则具有多个优先级，因此可以考虑自定义cmp函数作为排序的规则。
可以写一个自定义函数check来快速判定该字符串是否是一个大小写混杂的字符串。
cmp函数内部，先比较字符串是否是混杂的，再比较长度，最后比较字典序。直接调用sort函数并且传入自定义的比较函数cmp进行排序即可。
参考代码
