官方题解｜排位赛#9
2024-06-24 11:11:41
发布于：浙江
ACGO 第9次排位赛题解
写在前面
本次排位赛 题「隐藏元素」数据已加强。
本次排位赛再次对题目难度进行调整，同时赛后会统计大家的解题情况，以将排位赛的题目难度定在一个合理的档位。
本场排位赛的所有题目的难度评级为：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 捉迷藏 | 最长公共前缀 | 坏掉的数字键 | 奇怪的次方 | 隐藏元素 | 圣诞礼物 |
| 入门 | 入门 | 入门 | 普及- | 普及/提高- | 普及/提高- |
同时本次比赛作为 平台第一场接入 的比赛，鼓励所有使用 的同学参加，调整了时间限制，并增强数据「强度」。
非常感谢大家参加本场排位赛！
直播预告
直播时间：6月22日（周六）16:00 开始
直播地址：B站ACGO官方账号
直播内容：排位赛#9复盘
题解简述
以下提供每道题目的思路简述和 代码，详细题解的AC代码包括复杂度分析，请点击题目标题查看。
A - 捉迷藏
我们可以有很多种方法解决这个问题：可以使用循环枚举 之间的所有数字，也可以使用分支语句分类讨论，当然也有比较聪明一些的方法。
观察题目不难发现， 的结果只有 这几种结果，而 和 这两个数字是无法得到的。所以我们直接输出 或者 即可。
print(5)
B - 最长公共前缀
我们可以使用一个变量 从 开始依次比较两个字符串的当前字符，直到遇到不相等的字符，或者其中一个字符串遍历完毕停下来，此时 就是两个字符串的最长公共前缀的长度。
s, t = input(), input()
i = 0
while i < min(len(s), len(t)) and s[i] == t[i]:
i += 1
print(i)
C - 坏掉的数字键
对于读入的每个 检测其是否含有数字 ，有两种方法：1.数位分离判断是否出现 ；2. 把 当作字符串，在其中查找字符 是否存在即可。
for _ in range(int(input())):
n, d = input().split()
print(sum([d not in s for s in input().split()]))
D - 奇怪的次方
题目解析
显然 越大， 就越大，答案有单调性，所以我们可以使用二分来快速计算 的值。
for _ in range(int(input())):
n, y = map(int, input().split())
lo, hi = 0, y
while lo < hi:
mid = lo + hi >> 1
if mid**n < y:
lo = mid + 1
else:
hi = mid
print(lo if lo**n == y else -1)
E - 隐藏元素
题目解析
本题需要我们根据各个变量 和 的关系来推出 的值。
我们可以根据给出的 条信息来构建一个无向图：
对于 ，我们可以构建一条 的边权为 的边。
最后使用 从 开始遍历整个图，对于遍历到的每个点 其所有的邻接点 ，那么 。
遍历结束以后没有遍历到的点，说明无法判断其和 的关系，输出 即可。
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = map(int, input().split())
g[u].append([v, w])
g[v].append([u, w])
res = [-1] * (n + 1)
res[1] = 1
q = deque()
q.append(1)
while q:
u = q.popleft()
for v, w in g[u]:
if res[v] == -1:
res[v] = res[u] ^ w
q.append(v)
print(" ".join(map(str, res[1:])))
F - 圣诞礼物
如果我们直接忽略数据范围，不难发现可以使用完全背包的DP模型来解决这道问题，定义 为前 个礼物，使用 个糖果能够获得的最多金币。
但是注意到本题的数据范围 如果使用上述递推式，时间复杂度为 。会超出本题的时间限制。
那么进一步分析题目我们会发现对于每个礼物 ，制作出礼物需要的糖果为 ，其中 ，我们不难发现，；
而对于每个 由于可以重复制作同一种礼物，所以只需要取 即可。
所以我们可以转换 定义为制作需要糖果数量不超过 的礼物，使用 个糖果能够获得的最多金币。
那么此时的时间复杂度转化为 其中 。
使用 Python 的同学请不要使用
min/max函数，非常耗时，建议改用if语句。
cnt = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
K = 7 * 9
def f(x: int)->int:
return cnt[x] if x < 10 else f(x // 10) + cnt[x % 10]
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
val = [0] * (K + 1)
for i, v in enumerate(map(int, input().split())):
x = f(a[i])
if val[x] < v:
val[x] = v
dp = [0] * (m + 1)
for i in range(1, K + 1):
if val[i] == 0:
continue
for j in range(i, m + 1):
if dp[j - i] + val[i] > dp[j]:
dp[j] = dp[j - i] + val[i]
print(dp[m])
有帮助，赞一个