官方题解 | 欢乐赛#80题解
赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 皓仔的旗杆 入门 T2 皓仔和水 入门 T3 皓仔选数字 入门 T4 皓仔的数字朋友 入门 T5 皓仔的进制统计 普及- T6 皓仔的字符串匹配 普及-
T1 皓仔的旗杆
题意简述
本题没有输入。
只需要严格按照题目给出的格式，输出指定的小旗杆图案。
解题思路
直接使用多次 cout 输出对应的星号 * 和空格即可。
参考代码
T2 皓仔和水
题意简述
给定水的温度 ttt，根据温度判断水当前所处的状态。
共有 555 种情况：
* 当 t<0t<0t<0 时，输出 固体
* 当 t=0t=0t=0 时，输出 固液共存
* 当 0<t<1000<t<1000<t<100 时，输出 液体
* 当 t=100t=100t=100 时，输出 液气共存
* 当 t>100t>100t>100 时，输出 气体
解题思路
使用 if、else if 和 else 按照温度范围依次判断即可。
需要特别注意 000 和 100100100 这两个边界值，它们分别对应 固液共存 和 液气共存。
时间复杂度为 O(1)O(1)O(1)，空间复杂度为 O(1)O(1)O(1)。
参考代码
T3 皓仔选数字
题意简述
给定一个整数 xxx 和一个长度为 nnn 的整数数组 aaa。
需要从数组中选择一个数字 yyy，使得 x×yx\times yx×y 的值尽可能大。
输出能够得到的最大乘积。
注意，答案可能是负数。
解题思路
直接枚举数组中的每一个数字 aia_iai ，计算 x×aix\times a_ix×ai ，并维护当前最大的乘积即可。
由于 −231≤x,ai≤231−1-2^{31}\leq x,a_i\leq 2^{31}-1−231≤x,ai ≤231−1，两个数相乘后可能超过 int 的范围，因此需要使用 long long 存储。
另外，因为所有乘积都有可能是负数，所以不能把答案初始值设为 000，可以直接使用第一个乘积初始化答案。
时间复杂度为 O(n)O(n)O(n)，空间复杂度为 O(1)O(1)O(1)。
参考代码
T4 皓仔的数字朋友
题意简述
给定一个 nnn 行 mmm 列的整数矩阵。
对于每个位置，只考虑它的上、下、左、右四个相邻位置。
如果某个相邻位置中的数字与当前位置相同，那么这个相邻位置就是它的一个好朋友。
要求输出矩阵中每个位置拥有的好朋友数量。
解题思路
直接枚举矩阵中的每一个位置 (i,j)(i,j)(i,j)。
对于当前位置，分别检查上、下、左、右四个方向：
* 如果相邻位置没有越界；
* 并且相邻位置的数字与当前数字相同；
那么当前格子的好朋友数量加 111。
因为每个位置最多只检查 444 个方向，所以总时间复杂度为 O(nm)O(nm)O(nm)，空间复杂度为 O(nm)O(nm)O(nm)。
参考代码
T5 皓仔的进制统计
题意简述
给定一个长度为 nnn 的非负整数数组，以及一个进制 RRR。
需要将数组中的每个数字转换成 RRR 进制，并统计所有数位中数字 1 一共出现了多少次。
解题思路
对于每一个数字 xxx，可以使用短除法不断取出它在 RRR 进制下的每一位。
每次计算 x % R，就可以得到当前最低位。
如果这一位等于 111，答案加 111。
然后令 x /= R，继续处理下一位，直到 x=0x=0x=0。
例如十进制数 101010 转换成 333 进制：
* 10 mod 3=110\bmod 3=110mod3=1
* 3 mod 3=03\bmod 3=03mod3=0
* 1 mod 3=11\bmod 3=11mod3=1
所以得到 101101101，其中有 222 个数字 1。
需要注意，数字 000 转换成任意进制仍然是 0，其中不会出现数字 1，因此不需要特殊处理。
由于 ai≤1018a_i\leq 10^{18}ai ≤1018，需要使用 long long 存储。
时间复杂度为 O(nlogRA)O(n\log_R A)O(nlogR A)，其中 AAA 表示数组中数字的最大值，空间复杂度为 O(1)O(1)O(1)。
参考代码
T6 皓仔的字符串匹配
题意简述
给定 TTT 组字符串，每组包含两个字符串 aaa 和 bbb。
对于两个字符串，都需要先进行以下处理：
* 删除所有数字；
* 将剩余字母全部转换成大写字母。
处理完成后，统计字符串 aaa 在字符串 bbb 中出现了多少次。
匹配允许重叠。
解题思路
先对两个字符串进行预处理。
对于字符串中的每一个字符：
* 如果字符满足 '0' <= c && c <= '9'，说明它是数字，直接跳过；
* 如果字符满足 'a' <= c && c <= 'z'，说明它是小写字母，可以通过 c -= 32 将其转换成对应的大写字母；
* 如果本身就是大写字母，则直接保留。
处理完成后，枚举字符串 bbb 中每一个可能的匹配起点。
对于每个起点 iii，逐个比较后面的字符是否与字符串 aaa 相同。
如果全部相同，答案加 111。
因为每个位置都作为起点进行判断，所以可以正确统计重叠出现的情况。
时间复杂度为 O(∣a∣×∣b∣)O(|a|\times|b|)O(∣a∣×∣b∣)，空间复杂度为 O(∣a∣+∣b∣)O(|a|+|b|)O(∣a∣+∣b∣)。
参考代码
