9
赛纲介绍
本次题目的总体题目难度如下,各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 皓仔画三角形 入门 T2 皓仔拼角 入门 T3 皓仔整理数组 入门 T4 皓仔的字母串 入门 T5 皓仔的数字操作 普及- T6 皓仔的最近数字 普及-
T1 皓仔画三角形
题意简述
输入一个可见字符 ccc,使用这个字符输出一个高为 333、底边宽度为 555 的空心三角形。
解题思路
三角形的大小是固定的,因此不需要使用循环,可以直接按照每一行的格式输出。
* 第 111 行输出 222 个空格和 111 个字符 ccc;
* 第 222 行输出 111 个空格、字符 ccc、111 个空格和字符 ccc;
* 第 333 行连续输出 555 个字符 ccc。
参考代码
T2 皓仔拼角
题意简述
输入两个锐角的度数 aaa 和 bbb,将它们拼在一起后,新角的度数为 a+ba+ba+b。
根据新角与 909090 度的大小关系,判断它是锐角、直角还是钝角。
解题思路
先计算新角的度数 a+ba+ba+b。
* 如果 a+b<90a+b<90a+b<90,输出 锐角;
* 如果 a+b=90a+b=90a+b=90,输出 直角;
* 如果 a+b>90a+b>90a+b>90,输出 钝角。
直接使用 if 语句进行判断即可。
时间复杂度为 O(1)O(1)O(1)。
参考代码
T3 皓仔整理数组
题意简述
给定一个长度为 nnn 的数组 aaa。
先按照编号从小到大的顺序输出所有奇数编号的元素,再按照编号从大到小的顺序输出所有偶数编号的元素。
解题思路
先读入整个数组。
第一次从前往后枚举所有奇数编号 1,3,5,…1,3,5,\dots1,3,5,…,依次输出对应元素。
第二次从后往前枚举所有偶数编号,并依次输出对应元素。
因为数组下标从 111 开始,所以直接按照题目中的编号进行处理即可。
时间复杂度为 O(n)O(n)O(n)。
参考代码
T4 皓仔的字母串
题意简述
给定 nnn 个字符串,对于每个字符串,判断其中是否只包含大写英文字母和小写英文字母。
如果所有字符都是英文字母,输出 yes,否则输出 no。
解题思路
依次处理每个字符串 sss。
枚举字符串中的每一个字符,判断它是否为大写字母或小写字母。
如果发现某个字符既不是大写字母,也不是小写字母,就说明这个字符串不符合要求。
可以使用一个 bool 变量记录当前字符串是否合法,最后根据结果输出 yes 或 no。
时间复杂度为 O(∑∣si∣)O(\sum |s_i|)O(∑∣si ∣)。
参考代码
T5 皓仔的数字操作
题意简述
一共有 nnn 次操作,每次给出操作编号 opopop 和两个正整数 a,ba,ba,b。
* 当 op=1op=1op=1 时,求 a,ba,ba,b 的最大公约数;
* 当 op=2op=2op=2 时,求 a,ba,ba,b 的最小公倍数。
对于每次操作输出对应的结果。
解题思路
求最大公约数可以使用辗转相除法。
设当前两个数为 a,ba,ba,b。每轮先计算并保存余数 r=a mod br=a\bmod br=amodb,再令 a=ba=ba=b、b=rb=rb=r。重复以上操作,直到 b=0b=0b=0,此时 aaa 就是最大公约数。
设 a,ba,ba,b 的最大公约数为 ggg,则最小公倍数为:
ag×b\dfrac{a}{g}\times bga ×b
由于最小公倍数可能超过 int 的范围,因此使用 long long 存储数据。
每次求最大公约数的时间复杂度为 O(logmin(a,b))O(\log \min(a,b))O(logmin(a,b))。
参考代码
T6 皓仔的最近数字
题意简述
有 nnn 个数字,需要进行 mmm 次查询。
每次给出一个数字 xxx,在当前还没有被移除的数字中,找到与 xxx 的绝对差最小的数字并将其移除。
如果有多个数字的绝对差相同,则选择数值较小的数字。
解题思路
由于 n<5000n<5000n<5000,可以直接模拟每一次查询。
使用数组 visvisvis 记录每个位置的数字是否已经被移除。
对于每次查询 xxx,枚举所有还没有被移除的数字,计算:
∣ai−x∣|a_i-x|∣ai −x∣
记录当前绝对差最小的数字。
如果当前数字与 xxx 的绝对差更小,就更新答案;如果绝对差相同,则选择数值更小的数字。
找到答案后输出,并将对应位置标记为已经移除。
每次查询最多枚举 nnn 个数字,因此时间复杂度为 O(nm)O(nm)O(nm)。
参考代码
有帮助,赞一个