devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【蓝桥杯2024】省赛PA_题目描述 数学家们发现了两种用于召唤强大的数学精灵的仪式。 这两种仪式分别被称

作者：Monodyee | 2024-06-12 02:14:04

赞

踩

题目描述 数学家们发现了两种用于召唤强大的数学精灵的仪式。 这两种仪式分别被称

前言

20240413更新，刚打完，属于是菜鸟写算法。

试题 A: 拼正方形

【问题描述】 小蓝正在玩拼图游戏，他有 7385137888721 个 2 × 2 的方块和 10470245 个 1 × 1 的方块，他需要从中挑出一些来拼出一个正方形，比如用 3 个 2 × 2 和 4 个 1 × 1 的方块可以拼出一个 4 × 4 的正方形，用 9 个 2 × 2 的方块可以拼出一 个 6 × 6 的正方形，请问小蓝能拼成的最大的正方形的边长为多少。

【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

思路：题目挺小学奥数的，简单思考一下即可。考场我先计算了一下总面积开方：

  1. import math
  2.  
  3. a = 7385137888721
  4. b = 10470245
  5. print(math.sqrt(a*4+b))

结果输出为整数，那答案就是它了。

答案：5435123

试题 B: 召唤数学精灵

【问题描述】 数学家们发现了两种用于召唤强大的数学精灵的仪式，这两种仪式分别被 称为累加法仪式 A(n) 和累乘法仪式 B(n)。 累加法仪式 A(n) 是将从 1 到 n 的所有数字进行累加求和，即：A(n) = 1 + 2 + · · · + n 。 累乘法仪式 B(n) 则是将从 1 到 n 的所有数字进行累乘求积，即：B(n) = 1 × 2 × · · · × n 。 据说，当某个数字 i 满足 A(i) − B(i) 能被 100 整除时，数学精灵就会被召 唤出来。 现在，请你寻找在 1 到 2024041331404202 之间有多少个数字 i，能够成功 召唤出强大的数学精灵。

【答案提交】 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个 整数，在提交答案时只填写这个整数，填写居中对齐多余的内容将无法得分。

我召唤了20+分钟，反正我没召唤出来，最后，随便填写了一个数字。

试题 C: 数字诗意

时间限制: 10.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】 在诗人的眼中，数字是生活的韵律，也是诗意的表达。 小蓝，当代顶级诗人与数学家，被赋予了 “数学诗人” 的美誉。他擅长将冰 冷的数字与抽象的诗意相融合，并用优雅的文字将数学之美展现于纸上。 某日，小蓝静坐书桌前，目光所及，展现着 n 个数字，它们依次为 a1, a2, . . . , an，熠熠生辉。小蓝悟到，如果一个数能够以若干个（至少两个） 连续的正整数相加表示，那么它就蕴含诗意。例如，数字 6 就蕴含诗意，因为 它可以表示为 1 + 2 + 3。而 8 则缺乏诗意，因为它无法用连续的正整数相加表 示。 小蓝希望他面前的所有数字都蕴含诗意，为此，他决定从这 n 个数字中删 除一部分。请问，小蓝需要删除多少个数字，才能使剩下的数字全部蕴含诗意？

【输入格式】 输入的第一行包含一个整数 n，表示展示的数字个数。 第二行包含 n 个整数 a1, a2, . . . , an，相邻整数之间使用一个空格分隔，表示 展示的数字。

【输出格式】 输出一行包含一个整数，表示小蓝需要删除的数字个数，以使剩下的数字 全部蕴含诗意。

【样例输入】

3

3 6 8

【样例输出】 1

【样例说明】 在样例中，数字 3 可以表示为 1 + 2，数字 6 可以表示为 1 + 2 + 3，数字 8 无法表示为连续的正整数相加，因此，需要删除的数字个数为 1。

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ n ≤ 10^3，1 ≤ ai ≤ 10^3。

对于所有评测用例，1 ≤ n ≤ 2 × 10^5，1 ≤ ai ≤ 10^16。

思路：想不出来好的思路，直接打表了。对于n=1000这部分的分数死活能拿到手。

  1. n = int(input())
  2. q = list(map(int, input().split(" ")))
  3. table = []
  4. # 打表
  5. table_len = 300
  6. for i in range(1, table_len):
  7.     for j in range(i + 2, table_len):
  8.         t = 0
  9.         for k in range(i, j):
  10.             t += k
  11.         table.append(t)
  12. table = set(table)
  13. res = 0
  14. for i in q:
  15.     if i not in table:
  16.         res += 1
  17. print(res)

试题 D: 回文数组

时间限制: 10.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】 小蓝在无聊时随机生成了一个长度为 n 的整数数组，数组中的第 i 个数为 ai，他觉得随机生成的数组不太美观，想把它变成回文数组，也是就对于任意 i ∈ [1, n] 满足 ai = an−i+1 。小蓝一次操作可以指定相邻的两个数，将它们一起加 1 或减 1 ；也可以只指定一个数加 1 或减 1 ，请问他最少需要操作多少次能把 这个数组变成回文数组？

【输入格式】 输入的第一行包含一个正整数 n 。 第二行包含 n 个整数 a1, a2, · · · , an ，相邻整数之间使用一个空格分隔。

【输出格式】 输出一行包含一个整数表示答案。

【样例输入】

4

1 2 3 4

【样例输出】 3

【样例说明】

第一次操作将 a1, a2 加 1 ，变为 2, 3, 3, 4 ；

后面两次操作将 a1 加 1 ，变为 4, 3, 3, 4 。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n ≤ 10；

对于所有评测用例，1 ≤ n ≤ 10^5 ，−10^6 ≤ ai ≤ 10^6 。

思路：一开始想着区间差分数组的解法来着，感觉很简单，不过这只能改相邻的两个的条件，我死活没想出好的解法，然后暴力了。

暴力的思路也很简单，遍历列表，每次看看左边有没有一起带走的数，然后递归，代码没怎么优化，常数估计很大，估计只能拿20%的分。

代码：

  1. from math import inf
  2.  
  3.  
  4. def sgn(n, ln):
  5.     if n > 0 and ln > 0:
  6.         return "+"
  7.     elif n < 0 and ln < 0:
  8.         return "-"
  9.     else:
  10.         return "None"
  11.  
  12.  
  13. def dfs(pivot):
  14.     if pivot >= len(lst):
  15.         return
  16.     global res, final
  17.     n, ln = lst[pivot], lst[pivot - 1]
  18.     final = min(final, res + sum(map(abs, lst)))
  19.     if sgn(n, ln) == "+":  # 同号
  20.         min_t = min(n, ln)
  21.         lst[pivot] -= min_t
  22.         lst[pivot - 1] -= min_t
  23.         res += min_t
  24.         final = min(final, res + sum(map(abs, lst)))
  25.         dfs(pivot + 1)  # 递归
  26.         # 还原现场
  27.         lst[pivot] += min_t
  28.         lst[pivot - 1] += min_t
  29.         res -= min_t
  30.     elif sgn(n, ln) == "-":
  31.         max_t = max(n, ln)
  32.         lst[pivot] -= max_t
  33.         lst[pivot - 1] -= max_t
  34.         res -= max_t
  35.         final = min(final, res + sum(map(abs, lst)))
  36.         dfs(pivot + 1)  # 递归
  37.         # 还原现场
  38.         lst[pivot] += max_t
  39.         lst[pivot - 1] += max_t
  40.         res += max_t
  41.     # print(lst)
  42.     dfs(pivot + 1)  # 递归
  43.  
  44.  
  45. n = int(input())
  46. lst = list(map(int, input().split(" ")))
  47. # 数据预处理
  48. first = []
  49. second = []
  50. if n % 2 == 0:  # 偶数
  51.     first = lst[:n // 2]
  52.     second = lst[n // 2:]
  53. else:
  54.     first = lst[:n // 2]
  55.     second = lst[n // 2 + 1:]
  56. second.reverse()
  57. for i in range(len(first)):
  58.     first[i] = first[i] - second[i]
  59. lst = first
  60. # 下面进行暴搜，差分的方法想不出来，我不确定差分能不能求解
  61. res = 0
  62. final = inf
  63. dfs(0)
  64. print(final)

试题 E: 吊坠

时间限制: 10.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】 小蓝想制作一个吊坠，他手上有 n 个长度为 m 的首尾相连的环形字符串 {s1, s2, · · · , sn} ，他想用 n − 1 条边将这 n 个字符串连接起来做成吊坠，要求所 有的字符串连完后形成一个整体。连接两个字符串 si , sj 的边的边权为这两个字 符串的最长公共子串的长度（可以按环形旋转改变起始位置，但不能翻转），小 蓝希望连完后的这 n − 1 条边的边权和最大，这样的吊坠他觉得最好看，请计算 最大的边权和是多少。

【输入格式】 输入的第一行包含两个正整数 n, m ，用一个空格分隔。 接下来 n 行，每行包含一个长度为 m 的字符串，分别表示 s1, s2, · · · , sn 。

【输出格式】 输出一行包含一个整数表示答案。

【样例输入】

4 4

aabb

abba

acca

abcd

【样例输出】

8

【样例说明】

连接 < 1, 2 >, < 2, 3 >, < 2, 4 > ，边权和为 4 + 2 + 2 = 8

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n, m ≤ 10 ；

对于所有评测用例，1 ≤ n ≤ 200 ，1 ≤ m ≤ 50 。所有字符串由小写英文字 母组成。

思路：几个常见的算法结合起来即可：

1.最长公共子序列（dp解决）

2.最小生成树（该题要改成最大生成树）

3.最小生成树的并查集

题目有个麻烦就是，环形旋转，要处理一下。

代码：

  1. def find(parent, vertex):
  2.     if parent[vertex] == vertex:
  3.         return vertex
  4.     return find(parent, parent[vertex])
  5.  
  6.  
  7. def union(parent, rank, vertex1, vertex2):
  8.     root1 = find(parent, vertex1)
  9.     root2 = find(parent, vertex2)
  10.  
  11.     if root1 != root2:
  12.         if rank[root1] > rank[root2]:
  13.             parent[root2] = root1
  14.         else:
  15.             parent[root1] = root2
  16.             if rank[root1] == rank[root2]:
  17.                 rank[root2] += 1
  18.  
  19.  
  20. def kruskal_algorithm(graph):
  21.     # 初始化结果
  22.     minimum_spanning_tree = []
  23.  
  24.     # 初始化并查集
  25.     parent = {vertex: vertex for vertex in graph.keys()}
  26.     rank = {vertex: 0 for vertex in graph.keys()}
  27.  
  28.     # 获取所有的边
  29.     edges = []
  30.     for vertex, neighbors in graph.items():
  31.         for neighbor, weight in neighbors.items():
  32.             edges.append((vertex, neighbor, weight))
  33.  
  34.     # 按权值排序边
  35.     edges.sort(key=lambda edge: edge[2], reverse=True)  # 反转取最大的边
  36.  
  37.     # 不断取出权值最小的边并判断是否形成环
  38.     for edge in edges:
  39.         vertex1, vertex2, weight = edge
  40.         if find(parent, vertex1) != find(parent, vertex2):
  41.             union(parent, rank, vertex1, vertex2)
  42.             minimum_spanning_tree.append(edge)
  43.  
  44.         if len(minimum_spanning_tree) == len(graph) - 1:
  45.             break
  46.  
  47.     return minimum_spanning_tree
  48.  
  49.  
  50. # 动态规划求解，存储解及解的计算过程
  51. def lcs(x, y):  # 求解并存储箭头方向，x，y为字符串、列表等序列
  52.     m = len(x)  # x的长度
  53.     n = len(y)  # y的长度
  54.     c = [[0 for i in range(n + 1)] for _ in range(m + 1)]  # 二维数组，初始值为0，用于存储长度结果
  55.     d = [[0 for i in range(n + 1)] for _ in range(m + 1)]  # 二维数组，初始值为0，用于存储箭头方向,1表示左上，2表示上，3表示左
  56.     for i in range(1, m + 1):  # 按行遍历二维数组
  57.         for j in range(1, n + 1):  # 每行的各数值遍历， c0j和ci0相关的值都为0，所以均从1开始
  58.             if x[i - 1] == y[j - 1]:  # xi=yi的情况，二维数组中i，j=0时，都为0已经确定，但字符串x，y仍需从0开始遍历
  59.                 c[i][j] = c[i - 1][j - 1] + 1  # 递推式
  60.                 d[i][j] = 1  # 箭头方向左上方
  61.             elif c[i][j - 1] > c[i - 1][j]:  # 递推式，选择更大的
  62.                 c[i][j] = c[i][j - 1]
  63.                 d[i][j] = 3  # 箭头左边
  64.             else:  # c[i-1][j] >= c[i][j-1]
  65.                 c[i][j] = c[i - 1][j]
  66.                 d[i][j] = 2  # 箭头上方
  67.     return c[m][n], d
  68.  
  69.  
  70. def longest_dis(i, j):
  71.     a, b = lst[i], lst[j]
  72.     res = 0
  73.     for i in range(len(a)):
  74.         t = a[i:] + a[:i]
  75.         c, d = lcs(t, b)
  76.         res = max(c, res)
  77.     return res
  78.  
  79.  
  80. # 求解距离矩阵
  81. def distance():
  82.     dis = dict()
  83.     for i in range(1, n + 1):
  84.         dis[lst[i]] = {}
  85.     for i in range(1, n + 1):
  86.         for j in range(i, n + 1):
  87.             tt = longest_dis(i, j)
  88.             dis[lst[i]][lst[j]] = tt
  89.             dis[lst[j]][lst[i]] = tt
  90.     return dis
  91.  
  92.  
  93. n,m = map(int,input().split())
  94. lst = ["#"] + [input() for _ in range(n)]
  95. dis = distance()  # 获得距离矩阵
  96.  
  97. p = kruskal_algorithm(dis)  # 求最大生成树
  98. res = 0
  99. for a, b, v in p:
  100.     res += v
  101. print(res)

有些地方复杂度写得很高，希望多过点样例吧！

试题 F: 砍柴

时间限制: 10.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

小蓝和小乔正在森林里砍柴，它们有 T 根长度分别为 n1, n2, · · · , nT 的木 头。对于每个初始长度为 n 的木头，小蓝和小乔准备进行交替砍柴，小蓝先出 手。每次砍柴时，若当前木头长度为 x ，需要砍下一截长度为 p 的木头，然后 换另一个人继续砍，其中 2 ≤ p ≤ x 且 p 必须为质数。当轮到某一方时 x = 1 或 x = 0 ，它就没法继续砍柴，它就输了。它们会使用最优策略进行砍柴。请对每 根木头判断是小蓝赢还是小乔赢，如果小蓝赢请输出 1 （数字 1），如果小乔赢 请输出 0 （数字 0）。

【输入格式】

输入的第一行包含一个正整数 T， 接下来 T 行，每行包含一个正整数，其中第 i 的整数为 ni 。

【输出格式】

输出 T 行，每行包含一个整数，依次表示对于每一根木头的答案。

【样例输入】

3

1

2

6

【样例输出】

0

1

1

【样例说明】

对于 n1 = 1 ，由于当前长度 x = 1 ，小蓝直接输掉，小乔赢； 对于 n2 = 2 ，小蓝选择 p = 2 ，轮到小乔时当前长度 x = 2 − 2 = 0 ，小乔 输掉，小蓝赢； 对于 n3 = 6 ，小蓝选择 p = 5 ，轮到小乔时 x = 6 − 5 = 1 ，小乔输掉，小 蓝赢。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ ni ≤ 10^3；

对于所有评测用例，1 ≤ ni ≤ 10^5 ，1 ≤ T ≤ 10^4。

思路：这题代码倒不是很难很难，属于可以写的回溯（dfs），但是我题目看半天，只能说我对这种要文字理解的题目脑子容易抽筋，主要是它样例就给最简单的，复杂的不给，要我自己推，可恶！！！

代码注释给的思路我觉得是清楚的。

代码：

  1. import math
  2.  
  3.  
  4. def is_prime(x):
  5.     if x <= 3:
  6.         return True
  7.     for i in range(2, int(math.sqrt(x)) + 1):
  8.         if x % i == 0:
  9.             return False
  10.     return True
  11.  
  12.  
  13. def solve(x, turn):  # 小兰的回合则为False,不是为True
  14.     if x == 0 or x == 1:
  15.         return turn  # 是小兰的回合则为输了,反之则赢了
  16.     if x != 0 and x != 1 and is_prime(x):
  17.         return not turn  # 是小兰的回合则为赢了，反之则输了
  18.     # 下面进行暴搜
  19.     flag = False
  20.     for i in range(x - 1, 1, -1):
  21.         if is_prime(i):
  22.             # print("turn={}".format(turn))
  23.             # print("i={}".format(i))
  24.             flag = solve(x - i, not turn)
  25.             if flag:  # 有赢的机会
  26.                 return True  # 终止
  27.     return False  # 尝试所有机会，没有赢的可能
  28.  
  29.  
  30. n = int(input())
  31. lst = []
  32. for i in range(n):
  33.     lst.append(int(input()))
  34.  
  35. res = []
  36. for i in range(n):
  37.     t = solve(lst[i], False)  # 0表示小蓝回合，1表示小乔回合
  38.     if t:
  39.         res.append(1)
  40.     else:
  41.         res.append(0)
  42. for i in range(n):
  43.     print(res[i])

试题 G: 智力测试

时间限制: 10.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

小蓝考上了世界上最好的魔法师学校，然而入学第一件事就是智力测试， 老师给出了一个 n × m 大小的棋盘，同时对每行每列设置了权重 {R1, R2, · · · , Rn} 和 {C1,C2, · · · ,Cm} ，因此，对于第 r 行第 c 列的格子 (r, c) ，其权重为一个二 元组 (Rr ,Cc) 。 小蓝可以在格子之间进行移动，若某时刻小蓝在格子 (r, c) ，那么他可以一 步走到任意的格子 (r ′ , c) 或 (r, c ′ ) ，其中 r ′ , c ′ 满足:

（1）Rr ′ > Rr ,Cc ′ > Cc ，

（2）@r ′′ .Rr ′ > Rr ′′ > Rr ; @c ′′ .Cc ′ > Cc ′′ > Cr 。 之后，老师提出了 T 个问题，第 i 个问题为：假设小蓝从格子 (s i r , s i c ) 出 发，移动到格子 (t i r , t i c ) 有多少种不同的走法，答案对 1000000007 取模。

【输入格式】 输入的第一行包含三个正整数 n, m, T ，相邻整数之间使用一个空格分隔。 第二行包含 n 个正整数 R1, R2, · · · , Rn ，相邻整数之间使用一个空格分隔。 第三行包含 m 个正整数 C1,C2, · · · ,Cm ，相邻整数之间使用一个空格分隔。 接下来 T 行，第 i 行包含四个正整数 s i r , s i c , t i r , t i c ，相邻整数之间使用一个 空格分隔。

【输出格式】 输出 T 行，每行包含一个整数，依次表示每个问题的答案。

【样例输入】

4 4 2

4 2 3 1

2 1 2 1

4 4 1 1

2 2 2 4

【样例输出】

4

0

【样例说明】

询问 1：

(4, 4) → (2, 4) → (3, 4) → (1, 4) → (1, 1);

(4, 4) → (2, 4) → (3, 4) → (3, 1) → (1, 1);

(4, 4) → (2, 4) → (2, 1) → (3, 1) → (1, 1);

(4, 4) → (4, 1) → (2, 1) → (3, 1) → (1, 1)。

询问 2：

不存在方案可以从 (2, 2) 走到 (2, 4) 。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n, m, T ≤ 10^3 ；

对于所有评测用例，1 ≤ n, m, T ≤ 10^5 ，1 ≤ Ri ,Ci ≤ 10^8 ，1 ≤ s i r , t i r ≤ n ， 1 ≤ s i c , t i c ≤ m 。

没时间思考了，我被智力测试了，很明显我被刷了。

不过我觉得这道题目应该是dp。

试题 H: 最大异或结点

时间限制: 10.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

小蓝有一棵树，树中包含 N 个结点，编号为 0, 1, 2, · · · , N − 1 ，其中每个 结点上都有一个整数 Xi 。他可以从树中任意选择两个不直接相连的结点 a 、b 并获得分数 Xa ⊕ Xb ，其中 ⊕ 表示按位异或操作。 请问小蓝可以获得的最大分数是多少？

【输入格式】 输入的第一行包含一个整数 N ，表示有 N 个结点。 第二行包含 N 个整数 X1, X2, · · · , XN ，相邻整数之间使用一个空格分隔。 第三行包含 N 个整数 F1, F2, · · · , FN ，相邻整数之间使用一个空格分隔， 其中第 i 个整数表示 i 的父结点编号，Fi = −1 表示结点 i 没有父结点。

【输出格式】 输出一行包含一个整数表示答案。

【样例输入】

5

1 0 5 3 4

-1 0 1 0 1

【样例输出】

7

【样例说明】

选择编号为 3 和 4 的结点，x3 = 3 ，x4 = 4 ，他们的值异或后的结果为 3 ⊕ 4 = 7 。

【评测用例规模与约定】

对于 50% 的评测用例，1 ≤ N ≤ 1000 ；

对于所有评测用例，1 ≤ N ≤ 10^5 , 0 ≤ Xi ≤ 2^31 − 1 ，−1 ≤ Fi ≤ N ，Fi , 0 。

思路：这种题目，我不暴搜都对不起N<1000的50%的情况，主要是我也想不出好的方法。

代码：

  1. n = int(input())
  2. node = list(map(int, input().split(" ")))
  3. pivot = list(map(int, input().split(" ")))
  4. res = 0 # 防止只有一个节点
  5. for i in range(n):
  6.     for j in range(n):
  7.         if i != j:  # 选择2个节点
  8.             if pivot[j] != i and pivot[i] != j:  # 不相连
  9.                 res = max(res, node[i] ^ node[j])
  10. print(res)

 起码有50%的分好吧。

总结

感觉总体来讲，今年的我写出来的题目偏dfs，剪枝，图，可惜我剪枝不是很熟练，时间复杂度偏高，只会暴搜，不过有些题目也能写出来。

对一些常见的算法也考察了，比如吊坠，感觉出的很好，就是我写的挺拉跨的。

后记

20240507更新

拿了陕西省蓝桥杯省一，后面去算法网站核对了一下所有代码的准确性

填空第一题想错了，准确答案为：5435122

写了的题目都没有拿满分的，不过步骤分都拿到了。算法时间复杂度都很高，不少都超时了哎...

不过结果还行

备战国赛了！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/705680
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号