10
前言
> 以下为欢乐赛#81的题解内容,各位小伙伴有什么问题与建议可以在帖子下方留言。
赛纲介绍
题目编号 题目名称 题目难度 T1 皓仔算平均数 入门 T2 皓仔看日历 入门 T3 皓仔的相邻字母 入门 T4 皓仔的俯瞰森林 入门 T5 皓仔逛超市 普及- T6 皓仔的苹果分级 普及-
T1 皓仔算平均数
题意简述
输入三个正整数 aaa、bbb 和 ccc,计算这三个数字的平均数,并将结果四舍五入保留 222 位小数。
解题思路
三个数的平均数就是三个数的和除以 333。
由于 aaa、bbb、ccc 最大可以达到 10910^9109,三个数的和最大为 3×1093\times 10^93×109,已经超过 int 的范围,因此需要使用 long long 存储这三个数。
计算平均数时除以 3.03.03.0,使计算结果为浮点数。
最后使用 printf("%.2f", ans) 输出,即可将结果四舍五入保留 222 位小数。
参考代码
T2 皓仔看日历
题意简述
输入三个年份 y1y_1y1 、y2y_2y2 和 y3y_3y3 ,判断每个年份是平年还是闰年,并计算这三个年份一共包含多少天。
闰年有 366366366 天,平年有 365365365 天。
解题思路
对于每一个年份 yyy,判断它是否为闰年。
一个年份是闰年,当且仅当满足下面两个条件之一:
* yyy 能被 400400400 整除;
* yyy 能被 444 整除,并且不能被 100100100 整除。
可以写成判断条件:
如果当前年份是闰年,就给答案加上 366366366,否则加上 365365365。
分别处理三个年份后,输出总天数即可。
参考代码
T3 皓仔的相邻字母
题意简述
给定一个只由大小写英文字母组成的字符串 sss。
如果一对相邻字符同为大写字母,或者同为小写字母,那么它们就是一对同类字符。
统计字符串中一共有多少对同类字符。
解题思路
从左到右枚举每一对相邻字符 sis_isi 和 si***_{i****i+1 。
用两个 bool 变量分别记录这两个字符是否为大写字母。
如果两个 bool 变量的值相同,说明两个字符要么都是大写字母,要么都是小写字母,此时答案加 111。
时间复杂度为 O(n)O(n)O(n)。
参考代码
T4 皓仔俯瞰森林
题意简述
给定一个 nnn 行 mmm 列的森林,每个位置的树木高度为 hi,jh_{i,j}hi,j 。
计算每一行所有树木的高度总和,并求出其中最大的行高度总和与最小的行高度总和。
解题思路
依次读入每一行的数据,并用变量 sumsumsum 记录当前这一行的高度总和。
一行读入完成后,用 sumsumsum 更新最大值 mxmxmx 和最小值 mnmnmn。
由于每个高度最大为 10910^9109,每行最多有 100010001000 个数,因此一行的高度总和最大可以达到 101210^{12}1012,需要使用 long long 存储。
不需要保存整个矩阵,只需要在读入时直接计算每一行的总和即可。
时间复杂度为 O(nm)O(nm)O(nm)。
参考代码
T5 皓仔逛超市
题意简述
皓仔有 MMM 元钱,需要按照顺序检查 nnn 件物品。
只有价格为质数的物品才会考虑购买。如果钱足够就购买,否则立即结束购物。若剩余的钱变为 000,也立即结束购物。
求皓仔最终购买了多少件物品。
解题思路
从前往后依次枚举每件物品。
对于当前物品价格 aia_iai ,先判断它是否为质数。判断质数时,只需要枚举到 ai\sqrt{a_i}ai :
* 如果 ai<2a_i<2ai <2,一定不是质数;
* 如果存在 222 到 ai\sqrt{a_i}ai 之间的整数能够整除 aia_iai ,则不是质数;
* 否则就是质数。
如果当前价格不是质数,直接跳过。
如果是质数,则判断剩余的钱 MMM 是否足够购买:
* 如果 M<aiM<a_iM<ai ,立即结束购物;
* 否则购买物品,将 MMM 减去 aia_iai ,购买数量加 111;
* 如果此时 M=0M=0M=0,立即结束购物。
由于 ai≤10000a_i\le 10000ai ≤10000,每次判断质数最多枚举约 10000=100\sqrt{10000}=10010000 =100 次,因此可以直接判断。
时间复杂度为 O(nai)O(n\sqrt{a_i})O(nai )。
参考代码
T6 皓仔的苹果分级
题意简述
有 nnn 筐苹果,第 iii 筐苹果有甜度 sis_isi 、大小 ziz_izi 和苹果数量 cic_ici 。
将所有苹果筐按照以下规则排序:
1. 按 si+zis_i+z_isi +zi 从大到小排序;
2. 如果相同,按 sis_isi 从大到小排序;
3. 如果仍然相同,按输入顺序从小到大排序。
排序后的前 mmm 筐中,每个苹果售价为 p1p_1p1 元,其余筐中每个苹果售价为 p2p_2p2 元,求卖出所有苹果后的总收入。
解题思路
使用结构体保存每筐苹果的甜度 sss、大小 zzz、苹果数量 ccc 和原来的编号 ididid。
按照题目要求编写排序规则:
* 如果 s+zs+zs+z 不同,则较大的排在前面;
* 如果 s+zs+zs+z 相同,则 sss 较大的排在前面;
* 如果 sss 也相同,则原编号 ididid 较小的排在前面。
排序完成后,枚举所有苹果筐:
* 前 mmm 筐的苹果数量乘以 p1p_1p1 ;
* 其余苹果筐的苹果数量乘以 p2p_2p2 。
将所有收入累加即可。
由于总收入可能很大,需要使用 long long 存储答案。
时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。
参考代码
有帮助,赞一个