2023012的真题
202312-1 | 仓库规划 |
5415. 仓库规划 - AcWing题库高质量的算法题库
https://www.acwing.com/problem/content/5418/
解题思路：
其实就是对比（x.y,z.....）需要找到一个每个元素都大于这个坐标得坐标，本题可以直接暴力求解，主要需要了解其python得数据结构，怎么能够方便的比较坐标括号中得每个元素我们采用zip
解题代码
n, m = map(int, input().split())
coding = [tuple(map(int, input().split())) for _ in range(n)]
results = []
for i in range(n): # 枚举每个仓库for j in range(n): # 枚举它的上级仓库if i != j and all(x < y for x, y in zip(coding[i], coding[j])): # 满足上级仓库的定义results.append(j+1)if len(results) == 0:print(0)else:print(min(results))results=[]
知识点1：对于输入得灵活运用控制台（map）
n, m = map(int, input().split())其中 int这个位置代表一个操作函数，后面是input通过空格划分
-
将输入的多个字符串转换为其他类
# 使用 map(float, input().split()) 将输入的字符串转换为浮点数 numbers = list(map(float, input().split())) print(numbers) # 输出：[3.14, 2.71, 1.41]# 使用 map() 将输入的单词转换为大写 words = list(map(str.upper, input().split())) print(words) # 输出：['HELLO', 'WORLD'] - 对输入的每个元素应用自定义函数
# 定义一个自定义函数 def add_one(x):return x + 1# 输入数字并转换为整数 numbers = list(map(int, input().split()))# 对每个数字应用自定义函数 result = list(map(add_one, numbers)) print(result) # 输出：[2, 3, 4, 5] - 使用
map()处理多行输入# 读取第一行的数字 n n = int(input())# 使用 map() 读取接下来的 n 行输入，并将每行转换为整数 numbers = list(map(int, (input() for _ in range(n)))) print(numbers) # 输出：[10, 20, 30] - 多个输入的逐元素操作知识点1：对于输入得灵活运用控制台（map）
# 输入两个列表 list1 = list(map(int, input().split())) list2 = list(map(int, input().split()))# 使用 map() 和 lambda 函数逐元素相加 result = list(map(lambda x, y: x + y, list1, list2)) print(result) # 输出：[5, 7, 9]
知识点2：zip得运用
zip()是 Python 中一个非常强大的函数，用于将多个可迭代对象（如列表、元组等）“打包”成一个由元组组成的迭代器。每个元组包含来自每个输入可迭代对象的对应元素。
zip()是一个非常灵活的函数，可以用于：
打包多个可迭代对象：将对应元素组合成元组。
同时遍历多个列表：简化代码逻辑。
解包：恢复为原来的多个列表。解包的过程是通过
*运算符完成的，它可以将zip对象中的元组重新拆分为多个独立的列表。输出为按照列排列得元组matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9] ]# 遍历每一列 for col in zip(*matrix):print("列：", col)# 可以对每一列进行操作，例如计算列的和col_sum = sum(col)print("列的和：", col_sum) 列： (1, 4, 7) 列的和： 12如果想要进行遍历得转化为列表
matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9] ]# 交换第 1 行和第 2 行 matrix[0], matrix[1] = matrix[1], matrix[0]# 交换第 1 列和第 2 列 transposed = list(zip(*matrix)) transposed[0], transposed[1] = transposed[1], transposed[0] matrix = list(zip(*transposed))print("交换后的矩阵：") for row in matrix:print(row)创建字典：通过
dict(zip(keys, values))。排序：根据一个列表的值对多个列表进行排序。
举例说明
202312-2 | 因子化简 |
5416. 因子化简 - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5419/
解题思路
题目写的比较晦涩难懂，但是看懂样例就比较简单了，主要掌握怎么求素数，怎么能在低时间复杂度下求素数（质数）。素数就是能被1或者它本身整除得，那2就是最小得素数。求素数就枚举，类似于辗转相除法，小素数除不尽了在试试大点得。一般情况下是在数字得一半就能找完，比如10=2*5，如果超过一般那跟小的一半是倍数关系了，但是特殊情况是如果这个数字本身就是质数例如7，那就是特例了，需要注意。
解题代码
q = int(input())
for _ in range(q):n, k = map(int, input().split())prime_factors = {}# 只需要检查到 sqrt(n)i = 2while i * i <= n:while n % i == 0:n = n // iprime_factors[i] = prime_factors.get(i, 0) + 1i = i + 1# 如果 n 仍然大于 1，说明 n 本身是一个质因数if n > 1:prime_factors[n] = prime_factors.get(n, 0) + 1result = 1for factor, exponent in prime_factors.items():if exponent >= k:result *= factor ** exponentprint(result)知识点1：对于字典得灵活运用
题目中有个要求就是幂小于m得时候就给删除了，我们可以用字典实现这个操作：
1使用
dict()构造函数# 从键值对列表创建字典 person = dict([("name", "Alice"), ("age", 25), ("city", "New York")])# 从关键字参数创建字典 person = dict(name="Alice", age=25, city="New York")2. 访问字典中的值
person = {"name": "Alice", "age": 25, "city": "New York"}# 访问键 "name" 对应的值 print(person["name"]) # 输出：Aliceprint(person.get("name")) # 输出：Alice# 如果键不存在，get() 方法可以返回一个默认值 print(person.get("gender", "Unknown")) # 输出：Unknownprime_factors.get(i, 0)#获取当前i的值，如果不存在则默认为 0 prime_factors[i] = prime_factors.get(i, 0) + 1 prime_factors[i] = ...：更新字典中的计数。 这种写法非常适合在质因数分解或其他需要统计频率的场景中使用。3.遍历字典
person = {"name": "Alice", "age": 25, "city": "New York"}# 遍历字典的键 for key in person:print(key) # 输出：name, age, city # 遍历字典的值 for value in person.values():print(value) # 输出：Alice, 25, New York # 遍历字典的键值对 for key, value in person.items():print(key, value) # 输出：name Alice, age 25, city New York
202309的真题
202309-1 | 坐标变换（其一） |
5297. 坐标变换（其一） - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5300/
解题思路
此题没有难度
解题代码
n,m=map(int,input().split())
b=list()
c=list()
for i in range(n):a=list(map(int,input().split()))b.append(a)
for i in range(m):d=list(map(int,input().split()))c.append(d)
all=list()
for i in range(m):#操作需要改变的for j in range(n):#操作改变的次数c[i][0]=c[i][0]+b[j][0]c[i][1]=c[i][1]+b[j][1]for element in c[i]:print(element,end=" ")print()知识点1：输出得控制
end=" "是 Python 中print()函数的一个参数设置，用于指定输出内容后的结束符。默认情况下，print()函数在输出内容后会自动换行（即end="\n"）。通过设置end=" "，可以让输出内容在同一行后继续输出，而不是换行。print("Hello", end=" ") print("World") # 输出：Hello World 自定义分隔符：可以将 end 设置为其他字符，用于特定格式的输出。 print("Hello", end=",") print("World") # 输出：Hello,World
202309-2 | 坐标变换（其二） |
5298. 坐标变换（其二） - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5301/
解题思路
此题没有难度，但是有点烦人得是他操作从1开始，但是我们平时存储得列表索引是从0开始，容易绕混了，直接暴力解决多开一位。主要是不能被他给绕进去了，我们要知道度数变化不影响长度得变化，长度得变化不影响度数变化.然后就是理解题意i到 j 是经过一系列得操作
解题代码
import math# 读取输入的 n 和 m n, m = map(int, input().split())# 定义结构体 OP 对应的列表，存储操作信息 op = [] # 初始化 op 列表，索引从 1 开始，第一个元素用 None 占位 op.append(None)# 初始化 s 和 ss 列表，用于存储中间结果 s = [0] * (n + 1) ss = [0] * (n + 1) # 初始化 s[0] 和 ss[0] s[0] = 1 ss[0] = 0# 读取 n 个操作信息 for i in range(1, n + 1):id_, x = map(float, input().split())id_ = int(id_)op.append((id_, x))if id_ == 1:s[i] = s[i - 1] * xss[i] = ss[i - 1]elif id_ == 2:ss[i] = ss[i - 1] + xs[i] = s[i - 1]# 处理 m 次查询 for _ in range(m):i, j, a, b = map(float, input().split())i = int(i)j = int(j)# 计算乘法因子cheng = s[j] / s[i - 1]# 计算度数差dushu = ss[j] - ss[i - 1]# 计算中间结果 aa 和 bbaa = a * chengbb = b * cheng# 进行坐标转换a = aa * math.cos(dushu) - bb * math.sin(dushu)b = aa * math.sin(dushu) + bb * math.cos(dushu)# 输出结果，保留三位小数print(f"{a:.3f} {b:.3f}")
知识点1： 避免重复计算
为了避免重复计算，可以开个列表把需要重复计算得数值存进去，如果需要从i到j之间得变化率
s[j] / s[i - 1]#计算变化率，为什么是i-1呢，因为是从i开始算的知识点1： 避免重复计算
解决索引跟顺序不一致得情况直接暴力多开一位数组
s=[0]*(n+1) ss=[0]*(n+1)
2023005的真题
202305-1 | 重复局面 |
5081. 重复局面 - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5084/
解题思路
这题别看题目复杂，其实上就是字符串得判断，因为他输出那一大堆其实就是一串字符串嘛
解题代码
import sysdef main():# 读取输入n = int(sys.stdin.readline().strip()) # 读取总步数positions = [] # 用于存储每一步的棋盘局面counts = {} # 用于存储每个局面出现的次数for _ in range(n):# 读取 8 行棋盘局面board = [sys.stdin.readline().strip() for _ in range(8)]# 将棋盘局面拼接成一个字符串board_str = ''.join(board)# 更新局面出现次数if board_str in counts:counts[board_str] += 1else:counts[board_str] = 1# 输出当前局面是第几次出现print(counts[board_str])if __name__ == "__main__":main()知识点1：' '.join(s)，其中s是字符串列表，可以直接进行字符串拼接
board_str = ''.join(s)知识点2：对于着这种换行输入直接用input()即可，不要用map容易出错，如果非要用map那么可以用一下代码来解决
场景1：如果两个单词之间有空格，如果没有空格把.split())去掉，不然单词要被切分为字母
3 hello world foo bar baz abc def ghi b = [] # 初始化一个空列表，用于存储所有输入的行 n = int(input()) # 输入的第一行是一个整数，表示有多少行输入for _ in range(n):a = list(map(str, input().split())) # 使用 map() 将每行分割为字符串列表b.append(a) # 将每行的字符串列表添加到 b 中# 打印结果以验证 ['hello', 'world'] ['foo', 'bar', 'baz'] ['abc', 'def', 'ghi']
202305-2 | 矩阵运算 |