官方题解 | 欢乐赛#76题解
赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 皓仔的动物园门票 入门 T2 皓仔的动物园参观 入门 T3 皓仔统一大小写 入门 T4 皓仔的森林施法 入门 T5 皓仔的进制求和 普及- T6 皓仔的三段数组 普及-
T1 皓仔的动物园门票
题意简述
给定总票价 w 和参加活动的人数 n。
要求计算平均每张动物园门票的价格，并保留 222 位小数输出。
也就是计算：
w÷nw \div n w÷n
解题思路
这是一道简单的实数除法题。
因为总票价 w 可能是实数，所以需要使用 double 类型存储。
读入 w 和 n 后，直接计算 w / n，再使用 printf("%.2f", ...) 输出保留 222 位小数即可。
时间复杂度为 O(1)O(1)O(1)。
参考代码
T2 皓仔的动物园参观
题意简述
给定皓仔到达动物园的时间 t。
根据不同时间段输出能看到的动物：
* 8≤t<108 \le t < 108≤t<10，输出 熊猫
* 10≤t<1210 \le t < 1210≤t<12，输出 猴子
* 12≤t<1512 \le t < 1512≤t<15，输出 大象
* 15≤t<1815 \le t < 1815≤t<18，输出 老虎
如果不在这些时间段内，输出 动物园已关闭。
解题思路
这是一道简单的条件判断题。
因为每个时间段都是左闭右开，所以判断时需要注意右端点不能取到。
按照题目给出的时间段依次使用 if else 判断即可。
时间复杂度为 O(1)O(1)O(1)。
参考代码
T3 皓仔的统一大小写
题意简述
给定一个只包含英文字母的字符串 s。
每次可以修改一个字符，目标是让字符串变成以下两种情况之一：
所有字母都是大写字母；
所有字母都是小写字母。
输出最少需要修改的字符数量。
解题思路
统计字符串中大写字母的数量 cnt1，以及小写字母的数量 cnt2。
如果要全部变成大写字母，就需要修改所有小写字母，次数为 cnt2。
如果要全部变成小写字母，就需要修改所有大写字母，次数为 cnt1。
答案就是两者的较小值。
时间复杂度为 O(∣s∣)O(|s|)O(∣s∣)。
参考代码
T4 皓仔的森林施法
题意简述
有一个 n×nn \times nn×n 的森林，最开始每棵树高度都是 000。
接下来有 mmm 次施法，每次给出 a、b、x，表示第 a 行第 b 列的树长高 xxx 米。
同一棵树可能被多次施法，高度会累加。
最后输出最高的树所在的位置，题目保证最终最高的树唯一。
解题思路
用二维数组 h 记录每棵树当前的高度。
每次读入一次施法操作后，执行：
然后判断这棵树的高度是否超过当前记录的最大高度。
如果超过，就更新最高树的位置。
由于 xxx 最大可以到 10910^9109，并且同一棵树可能多次累加，所以高度要使用 long long 存储。
时间复杂度为 O(m)O(m)O(m)。
参考代码
T5 皓仔的进制求和
题意简述
给定 nnn 个数字，每个数字由字符串 s 和进制 b 表示。
需要把每个数字从 b 进制转换成十进制，然后求出所有数字的总和。
数字中可能出现：
0 到 9 表示 000 到 999；
A 到 F 表示 101010 到 151515。
解题思路
对于每个字符串 s，从左到右依次处理每一位。
假设当前已经转换出的十进制值为 num，当前字符对应的数值为 x，那么更新方式为：
num=num×b+xnum=num\times b+x num=num×b+x
这样就可以将整个 b 进制数字转换为十进制。
由于答案最大不超过 101810^{18}1018，所以总和以及每个转换后的数字都要使用 long long 存储。
时间复杂度为 O(n×∣s∣)O(n\times |s|)O(n×∣s∣)。
参考代码
T6 皓仔的三段数组
题意简述
给定一个长度为 nnn 的正整数数组。
现在需要选择两个分割位置，把数组分成连续的三段，并且每一段都不能为空。
对于每一种分法，分别计算三段元素和 s1、s2、s3。
要求最小化：
max(s1,s2,s3)−min(s1,s2,s3)\max(s1,s2,s3)-\min(s1,s2,s3) max(s1,s2,s3)−min(s1,s2,s3)
输出这个最小值。
解题思路
因为 n≤500n \le 500n≤500，可以直接枚举两个分割位置。
设第一个分割位置为 i，第二个分割位置为 j，那么三段分别是：
第 111 段：111 到 i
第 222 段：i + 1 到 j
第 333 段：j + 1 到 n
为了快速求每一段的和，可以先预处理前缀和数组 s。
这样每一段的和都可以 O(1)O(1)O(1) 求出。
最后枚举所有合法分法，更新答案即可。
时间复杂度为 O(n2)O(n^2)O(n2)。
参考代码
