官方题解 | 【基础组】ACGO“飞翔杯”第三届季度赛
赛纲介绍
本次题目的总体题目难度如下,各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 求和 入门 T2 字符串价值 入门 T3 数位和 入门 T4 减少荒地开垦 普及-
T1 求和
题目大意
在长度求所有末尾数字是 555 或者 000 的数字的总和。
题解思路
所有末尾数字是 555 或者 000 的数字 ,都是 555 的倍数。因此可以直接循环遍历整个数组, 计算所有可以整除 555 的数字的总和即可。(数据范围较大,记得开 long longlong\ longlong long 。
参考代码
T2 字符串价值
题目大意
字符串价值的定义是 每种字母的出现次数 ×\times× 该字母的 ASCIIASCIIASCII 码值。 求给定字符串的字符串价值。
题解思路
每种字母的出现次数 ×\times× 该字母的 ASCIIASCIIASCII 码值,其实等于字符串内所有字母的ASCIIASCIIASCII 码值总和。遍历整个字串计算所有字母的和即可。
参考代码
T3 数位和
题目大意
给定两个日期 AAA 和BBB, 请计算两个日期之间的所有日期里,一共有多少种不同的数位和。
例如:2024-12-01 和 2024-11-02 数位和相同都是 121212。
题解思路
本题需要考虑的内容较多:
对于单个日期求数位和, 需要将 年, 月, 日,分别计算数位和再求和。
为了从日期 AAA 遍历到 日期 BBB, 需要每次手动求一下第二天的日期是多少
当本月已经来到最后一天,则要到下一个月的第一天, 如果本月是今年的最后一个月, 则要到第二年的 111 月 111 日。
对于整个范围内所有的日期, 计算数位和之后在桶数组中标记该数字出现过。最后遍历桶数组统计不同数位和出现的次数就好。
为了计算第二天的日期,比较方便的方法是开一个数组存储一下每个月有多少天。 但是二月份需要特殊判断,需要先判断是否是闰年才能决定二月份的天数是 282828 还是 292929 天。
参考代码
T4 减少荒地开垦
题目大意
在一片 n×mn \times mn×m 的田地中, '.' 代表荒地, '#' 代表杂物。一片空地如果四周都没有杂物则可以开垦。
小明为了尽可能减少开垦的数量, 因此他决定往田里放一个杂物,求最终的最少开垦数量。
题解思路
是否可以开垦取决于周边的杂物数量, 因此我们可以先计算一下,没有放置杂物的情况下,能够开垦的土地数量。
我们可以对于每一个位置 (i,j)(i, j)(i,j),分别判断一下上下左右是不是杂物,统计一下该点周边杂物的数量存储到 cnt[i][j]cnt[i][j]cnt[i][j]。如果杂物数量为000, 并且该点是一块荒地,则初始可以开垦的数量 ans +=1ans\ += 1ans +=1 。
为了获取最终的最少开垦数量, 我们需要求放一个杂物之后可以减少的最大可开垦荒地数量 subsubsub ,显然我们只会把杂物放在荒地上。
对于所有的荒地,我们求一下把杂物放在上面之后能够减少的可开垦荒地数量,并且求取最大值即为我们的目标。
当对一块荒地放上杂物之后会带来的影响有: 四周的荒地如果原先可以开垦, 则现在不可以开垦了,减少的数量 + 1。 而这块荒地本身,如果原先也是可以开垦的( cnt[i][j]=0cnt[i][j] = 0cnt[i][j]=0 ),则减少的数量 + 1。
参考代码