当前位置： 首页 > news >正文

北京在线建站模板,腾讯云wordpress密码,网络推广公司营销策划,广东企业网站建设推荐题目一 试题编号#xff1a; 202305-1 试题名称#xff1a; 重复局面 时间限制#xff1a; 1.0s 内存限制#xff1a; 512.0MB 问题描述#xff1a; 题目背景 国际象棋在对局时#xff0c;同一局面连续或间断出现3次或3次以上#xff0c;可由任意一方提出和棋。 问题…题目一 试题编号 202305-1 试题名称 重复局面 时间限制 1.0s 内存限制 512.0MB 问题描述 题目背景 国际象棋在对局时同一局面连续或间断出现3次或3次以上可由任意一方提出和棋。 问题描述 国际象棋每一个局面可以用大小为 8*8的字符数组来表示其中每一位对应棋盘上的一个格子。六种棋子王、后、车、象、马、兵分别用字母 k、q、r、b、n、p 表示其中大写字母对应白方、小写字母对应黑方。棋盘上无棋子处用字符 * 表示。两个字符数组的每一位均相同则说明对应同一局面。 现已按上述方式整理好了每步棋后的局面试统计每个局面分别是第几次出现。 输入格式 从标准输入读入数据。 输入的第一行包含一个正整数 n表示这盘棋总共有 n 步。 接下来 8×n 行依次输入第 1 到第 n 步棋后的局面。具体来说每行包含一个长度为 8 的字符串每 8 行字符串共 64 个字符对应一个局面。 输出格式 输出到标准输出中。 输出共 n 行每行一个整数表示该局面是第几次出现。 样例输入 8

******pk ***r*p p*pQ**

**b*B*PP **qP RK

******pk ***r*p p*pQ** *b****** ****B*PP **qP RK

******pk ***r*p p*p*** bQ ****B*PP **qP RK *****k *****p ***r*p p*p*** bQ ****B*PP **qP RK *****k *****p ***r*p p*pQ** *b****** ****B*PP **qP RK

******pk ***r*p p*pQ** *b****** ****B*PP **qP RK

******pk ***r*p p*p*** bQ ****B*PP **qP RK

******pk ****rp p*p*** bQ ****B*PP **qP R*K*样例输出 1 1 1 1 1 2 2 1 样例说明 第 6、7 步后的局面分别与第 2、3 步后的局面相同。第 8 步后的局面与上图相对应。 子任务 输入数据满足 n≤100。 提示 判断重复局面仅涉及字符串比较无需考虑国际象棋实际行棋规则。 题目分析个人理解 题目挺长但是很水直接看样例输入输出即可知道题意就是第一行输入n个局面,一个局面有8行8列输出每一个局面出现的次数。我的核心思想是这样的将每个局面存入一个容器当再出现相同局面的时候计数器加一将计数器的每一步都存入列表count[]最后遍历输出count的元素即可。第一种方法我选择将每个局面用temp(str型)表示并且全部存入列表l[]用.append()方法追加写入每追加写入一个局面就判断一次前面是否出现过如果出现计数器加一存入存放计数器的列表。上代码 temp l[] nint(input()) count[1]n for i in range(n):for j in range(8):tempinput()l.append(temp)for x in range(i):if temp in l[x]:count[i]1temp for i in count:print(i) 当然用字典更简单一些用字典的keys表示每一个局面values表示出现的次数只需要每一步都输出然后更新字典即可。上代码 n int(input()) chess {} for i in range(n):temp for j in range(8):temp input()if temp not in chess:chess[temp] 1else:chess[temp] 1print(chess[temp]) 题目二 试题编号 202305-2 试题名称 矩阵运算 时间限制 5.0s 内存限制 512.0MB 问题描述 题目背景
是 Transformer 中注意力模块的核心算式其中 Q、K 和 V 均是 n 行 d 列的矩阵KT 表示矩阵 K 的转置× 表示矩阵乘法。 问题描述 为了方便计算顿顿同学将 Softmax 简化为了点乘一个大小为 n 的一维向量 W(W⋅(Q×KT))×V 点乘即对应位相乘记 W(i) 为向量 W 的第 i 个元素即将 (Q×KT) 第 i 行中的每个元素都与 W(i) 相乘。 现给出矩阵 Q、K 和 V 和向量 W试计算顿顿按简化的算式计算的结果。 输入格式 从标准输入读入数据。 输入的第一行包含空格分隔的两个正整数 n 和 d表示矩阵的大小。 接下来依次输入矩阵 Q、K 和 V。每个矩阵输入 n 行每行包含空格分隔的 d 个整数其中第 i 行的第 j 个数对应矩阵的第 i 行、第 j 列。 最后一行输入 n 个整数表示向量 W。 输出格式 输出到标准输出中。 输出共 n 行每行包含空格分隔的 d 个整数表示计算的结果。 样例输入 3 2 1 2 3 4 5 6 10 10 -20 -20 30 30 6 5 4 3 2 1 4 0 -5 样例输出 480 240 0 0 -2200 -1100 子任务 70 的测试数据满足n≤100 且 d≤10输入矩阵、向量中的元素均为整数且绝对值均不超过 30。 全部的测试数据满足n≤104 且 d≤20输入矩阵、向量中的元素均为整数且绝对值均不超过 1000。 提示 请谨慎评估矩阵乘法运算后的数值范围并使用适当数据类型存储矩阵中的整数。 题目分析个人理解 读到题目先和大家复习一下线性代数的矩阵转置很简单一句话行变列列变行。设矩阵m n则转置矩阵就是n*m。要求(W⋅(Q×KT))×V再看输入只让输入k那么必须要实现转置的操作有以下几种方法实现第一种双重循环

python 双重循环arr [[ 1, 2, 3],[ 4, 5, 6],[ 7, 8, 9],[10, 11, 12]]arr2 []

数组的第二维维度

for i in range(len(arr[0])):#len(arr[0])3 temp []# 数组的第一维维度for j in range(len(arr)):#len(arr)4temp.append(arr[j][i])arr2.append(temp) print(arr2)

输出结果为

[[1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 第二种列表推导式和第一种没啥区别就是看上去更简洁

python 列表表达式

使用嵌套的列表表达式

arr [[ 1, 2, 3],[ 4, 5, 6],[ 7, 8, 9],[10, 11, 12]]

i 为第二个维度j 为第一个维度

arr2 [[arr[j][i] for j in range(len(arr))] for i in range(len(arr[0]))] print(arr2)# 输出结果为 [[1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]]第三种使用python zip函数

python zip函数

arr [[ 1, 2, 3],[ 4, 5, 6],[ 7, 8, 9],[10, 11, 12]]

zip(* )在这里是解压的作用

将arr 看做是一个打包后的数组

arr2 zip(* arr) print(list(arr2))# 输出结果为 [(1, 4, 7, 10), (2, 5, 8, 11), (3, 6, 9, 12)]5.第四种使用numpy转置

使用numpy转置

import numpy as nparr [[ 1, 2, 3],[ 4, 5, 6],[ 7, 8, 9],[10, 11, 12]] arr np.array(arr)

这里可以三种方法达到转置的目的

第一种方法

print(arr.T)

第二种方法

print(arr.transpose())

第三种方法

print(arr.swapaxes(0, 1))

上面三种方法等价# 三种方法的输出结果均为

[[ 1 4 7 10][ 2 5 8 11][ 3 6 9 12]]言归正传还是再看输入第一行输入n,d表示矩阵n行d列然后下面的几行依次输入矩阵QKV还是选择列表存储吧类矩阵惯用二维列表表示。直接用列表推导式。接着就是运算了这道题其实只用按照逆矩阵的顺序做点乘即可就是 W(i) 为向量 W 的第 i 个元素即将 (Q×KT) 第 i 行中的每个元素都与 W(i) 相乘。上代码 n, d map(int, input().split()) Q [[i for i in map(int, input().split())] for j in range(n)] K [[i for i in map(int, input().split())] for j in range(n)] V [[i for i in map(int, input().split())] for j in range(n)] W [i for i in map(int, input().split())] tmp []#存放 计算 K的转置 * V ans []# 计算 Q * tmp ans# 计算 K的转置 * V tmp for i in range(d):tmp.append([])#print(tmp)for j in range(d):tmp[i].append(0)#把每一步的初始计算 K的转置 * V先赋值为0#print(tmp)for k in range(n):#k表示行注意这里只按照逆矩阵的顺序遍历运算即可n是原矩阵的行tmp[i][j] K[k][i]*V[k][j]#矩阵的运算相乘再相加#print(tmp)

计算 Q * tmp ans

for i in range(n):ans.append([])for j in range(d):ans[i].append(0)for k in range(d):ans[i][j] Q[i][k]*tmp[k][j]ans[i][j] * W[i]for i in range(n):a []for j in range(d):a.append(ans[i][j])print(*a)#输出的时候空格隔开每一个元素 总结