官方题解｜排位赛#10
2024-07-22 10:59:52
发布于：广东
ACGO 第 10 次排位赛题解
本场排位赛的所有题目的难度评级为：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| ASCII 码 | 挑食的小码君 | 奇怪的机器 | 独特三元组 | 道路削减 | 分面包 |
| 入门 | 入门 | 普及- | 普及/提高- | 普及/提高- | 普及+/提高 |
题解简述
以下提供每道题目的思路简述和 代码，详细题解的 AC 代码与复杂度分析，请点击题目标题查看。
A - ASCII 码
对于任意给定的 值，我们可以使用强制类型转换，获取其字符形式。
print(chr(int(input())))
B - 挑食的小码君
可以将问题转化为：“在 中，有没有一种食物的美味度是 个食物中最高的（允许并列）？”
对于这个问题我们可以通过以下流程解决：
- 找出 种食物中的最高美味度（假设该值为 ）。
- 对于 ，判断是否存在 。
- 如果有一个或多个这样的 ，则答案为
Yes；否则，答案为No。
可以用 for 语句和 if 语句来编写。
注意数组下标的范围。此外，注意不要多次输出 Yes，或在 Yes 后输出 No。
这一点，对于 C++ 程序可以在找到满足条件的 之后使用 return 0 直接退出程序；对于 Python 程序可以使用 exit(0) 直接退出程序。
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
maxv = max(a)
for i in b:
if a[i - 1] == maxv:
print("Yes")
exit(0)
print("No")
C - 奇怪的机器
每个转轴一共只有 0, 1, , 9 共 个字符；
我们可以尝试枚举最终停下来显示的字符，最终从 个答案中取最小的即可。
对于转轴 若想其显示字符 ，那么根据题目意思，在每 秒一个周期中只能选择第 秒按下按钮。即时间 需要满足 。
又每秒只能按一次按钮，我们可以使用一个数组 st 来标记 秒是否按过按钮, 然后可以枚举 ，找到没有按按钮的最小的 ，将 标记为 。
对于每个字符 ，我们统计让所有的转轴停到 ，按下按钮最晚的时间 即可。最终的答案取所有 中最小的，即 。
n = int(input())
slots = [input() for i in range(n)]
res = n * 10
for i in range(10):
cur = 0
st = [0] * n * 10
for slot in slots:
p = slot.find(str(i))
while st[p]:
p += 10
st[p] = 1
cur = max(cur, p)
res = min(res, cur)
print(res)
D - 独特三元组
可以将问题转化为：“求满足 的三元组 的数量”。
对于满足题目原条件的三元组 ，有且仅有一个 的排列 ，使得 。
反之，对于有 的三元组 ，有且仅有一个 的排列 ，使得 。
考虑枚举 ，那么 和 可以独立选择。
满足条件的 的数量是 中数值小于 的元素个数；
满足条件的 的数量是 中数值大于 的元素个数。
因此，只要准备一个数组 cnt，令 cnt[x] 为 中小于等于 的数量，便可以很容易地计算出满足条件的 和 的数量。
N = 2 * 10**5
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (N + 1)
for x in a:
cnt[x] += 1
for i in range(1, N + 1):
cnt[i] += cnt[i - 1]
print(sum(cnt[x - 1] * (n - cnt[x]) for x in a))
E - 道路削减
令 为从城市 到城市 的最短距离。无论选择哪些道路，显然有 。
所以如果有选择道路的方案使得 成立，那么这就是最优解。事实上，这样的选择方法总是存在的。
对于每个 ，只需保留 “从城市 到城市 的最短路径中的最后一条道路” 即可。
答案可以通过记录 算法中到达每个城市前的最后一条道路来找到。
import heapq
n, m = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(1, m + 1):
u, v, w = map(int, input().split())
g[u].append((v, w, i))
g[v].append((u, w, i))
pq = [[0, 1]]
heapq.heapify(pq)
dist = [10**15] * (n + 1)
path = [0] * (n + 1)
dist[1] = 0
while pq:
d, u = heapq.heappop(pq)
if dist[u] < d:
continue
for v, w, i in g[u]:
if dist[v] <= d + w:
continue
dist[v] = d + w
path[v] = i
heapq.heappush(pq, (d + w, v))
print(" ".join(map(str, path[2:])))
F - 分面包
1. 首先考虑 的情况：
反转问题为：“使用 的成本将原本长度为 和 的面包拼接在一起，求将面包 合并为一个面包的最小费用。”
这个问题和原问题等价。
在这里，原问题的最小费用等于在多重集 上重复以下操作 次的成本之和：
- 令 和 为 中最小的两个元素。以 的成本将长度为 和 的两条面包拼接在一起。
- 从 中删除 和 ，并将 插入到 中。
由于每次操作后 的元素数量减少 ，显然完成以上操作后， 只会剩下一个元素。
2. 考虑 的情况：
对于 ，我们可以令 。
将剩余的部分当作一条面包，反转问题为：“使用 的成本将原本长度为 和 的面包拼接在一起，求将面包 合并为一条面包的最小费用。”
这个问题同样可以使用上述的方法解决。
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
tot = sum(a)
if tot < m:
a.append(m - tot)
heapq.heapify(a)
res = 0
while len(a) > 1:
u = heapq.heappop(a)
v = heapq.heappop(a)
heapq.heappush(a, u + v)
res += u + v
print(res)
有帮助，赞一个