官方题解 | 欢乐赛#51 题解
赛纲介绍
本次题目的总体题目难度如下,各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 石头剪刀布 入门 T2 小明的购物计划 入门 T3 ac字符串 入门 T4 四舍五入 入门 T5 小明的bingo 入门 T6 3倍 普及-
T1 石头剪刀布
题目大意
输出一个字符使得小明获取胜利。
题解思路
对方出石头,显然我们需要出布,因此输出'C'。
参考代码
T2 小明的购物计划
题目大意
小明去商店购物,不同的结账金额对应了不同的折扣力度,求最终的实际结账金额。
题解思路
使用多分支结构,判断当前的结账金额对应的打折力度,则答案等于结账金额 ×\times× 折扣。
题目要求保留一位小数输出,因此使用printf进行格式化输出。
参考代码
T3 AC字符串
题目大意
对于给定的字符串 sss, 求其中有多少个子串为 "ac"并输出。
题解思路
由于想要判断的子串长度只有 222,因此可以直接遍历整个字符串, 如果 a[i]a[i]a[i] 和 a[i+1]a[i + 1]a[i+1] 恰好构成了目标子串"ac",则答案+1。
参考代码
T4 四舍五入
题目大意
对于给定的数字 nnn (数位很长,需要使用string来进行读入),求将 nnn 按照四舍五入保留 mmm 位的结果?
题解思路
使用桶数组来存储一下每个密码能够打开的宝箱的数量。 对于每个宝箱, 使得该宝箱的 mmm 个密码能够解开的宝箱数量+1.
将数字保留 mmm 位进行四舍五入,取决于 第 m+1m + 1m+1 位,如果第 m+1m + 1m+1位大于等于 555 , 则第 mmm 位数值加一。
由于在数字 +1+1+1 之后可能会产生进位, 因此需要从后往前维护一下数字的进位, 如果某一位的数字大于 999, 则需要设为 000 ,并且让上一位+1+1+1。
参考代码
T5 小明的BINGO
题目大意
给定一个 n×nn \times nn×n 的二维数组,对于任何一条长度为 nnn 的直线(包括对角线), 如果直线上数字的总和为一个奇数的话,则可以算是一次 bingo,求bingo的数量。
题解思路
长度为nnn 的直线一共只有 n+2n + 2n+2 条,即 nnn 行, nnn列, 主对角线, 副对角线。 因此可以按顺序循环遍历 nnn 行, nnn列, 主对角线, 副对角线,并且计算总和,看本条线上的总和是否是一个奇数,是的话使得答案 +1。
参考代码
T6 3倍
题目大意
给定一个长度是 nnn 的数组, 对于其中所有的差值为 333 的倍数的数对 ai,aj(1≤i,j≤n)a_i,a_j(1\le i,j≤n)ai ,aj (1≤i,j≤n), 求其最大的差值并且输出.
题解思路
如果直接枚举所有的数对 (i,j)(i, j)(i,j) ,则复杂度为 O(n2)O(n^2)O(n2), nnn的上界为100000100000100000,显然超时。
考虑到如果两个数字 ai,aja_i, a_jai ,aj 的差值为 333, 则 ai%3==aj%3a_i \% 3 == a_j \% 3ai %3==aj %3。
因此可以将所有数字对 333 取模, 对于余数是 0,1,20, 1, 20,1,2 三种情况分别求最大值和最小值。
最后对三个情况分别使用最大值减去最小值获取对应的最大差值, 在三种结果中取最大即可。
参考代码