AtCoder Beginner Contest 146解题报告

最近，AtCoder Beginner Contest 146（以下简称ABC 146）已经结束了，本文的目的是回顾这次比赛，分析各道题目及其解法，帮助读者更好地理解比赛。

比赛总体情况

ABC 146是一场循环赛，共有六道题目。根据官网数据，本次比赛共有2433名选手参赛，其中AC人数最多的是A题，有2164人通过，题目难度逐渐递增，最终只有22人通过了F题。

各题目解析

A - Can't Wait for Holiday

这道题目让我们计算距离周六或周日还有几天。答案采用7取模的余数即可。时间复杂度O(1)。

[解法一]：

s = input().strip()

if s == "SAT":
    print(0)
elif s == "SUN":
    print(6)
elif s == "FRI":
    print(1)
elif s == "THU":
    print(2)
elif s == "WED":
    print(3)
elif s == "TUE":
    print(4)
else:
    print(5)

[解法二]：

s = input().strip()

days = ["SAT", "FRI", "THU", "WED", "TUE", "MON", "SUN"]

num_days_to_wait = days.index("SAT") - days.index(s)

if num_days_to_wait < 0:
    num_days_to_wait += 7

print(num_days_to_wait)

B - ROT N

这道题目让我们将给定字符串中的所有字符向右移动N个单位。需要注意的是，N可能大于26，因此需要将N取模后再操作字符串。时间复杂度O(n)。

n = int(input().strip())
s = input().strip()

for c in s:
    c_ord = ord(c) - ord('A')
    new_c = (c_ord + n) % 26 + ord('A')
    print(chr(new_c), end="")
print()

C - Buy an Integer

这道题目让我们用高精度计算，计算出一个数字N，满足A <= N * B。我们可以使用二分搜索来解决这个问题。时间复杂度O(logB)。

a, b, x = map(int, input().strip().split())

l = 0
r = 10 ** 9 + 1

while r - l > 1:
    m = (l + r) // 2
    if a * m + b * len(str(m)) <= x:
        l = m
    else:
        r = m

print(l)

D - Coloring Edges on Tree

这道题目让我们对一颗树进行边权的染色，使得相邻的边染色不同。我们可以使用DFS进行遍历和染色，对于不能染色的情况返回-1。时间复杂度O(N)。

n = int(input().strip())

edges = [[] for _ in range(n)]

for i in range(n - 1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    edges[a].append((b, i))
    edges[b].append((a, i))

colors = [-1] * (n - 1)

def color_edges(node, parent, color):
    cur_color = 1
    for child, edge_idx in edges[node]:
        if child == parent:
            continue
        if colors[edge_idx] != -1:
            continue
        if cur_color == color:
            cur_color += 1
        colors[edge_idx] = cur_color
        color_edges(child, node, cur_color)
        cur_color += 1

color_edges(0, -1, -1)

if -1 in colors:
    print("NO")
else:
    print("YES")
    for c in colors:
        print(c)

E - Rem of Sum is Num

这道题目让我们找到和N取模等于R的最小的数，其中N是一大串数字的和。我们可以用前缀和来优化计算，对于每个位置i，记录前i个数字的和，然后用二分搜索实现。时间复杂度O(n logn)。

n, k, m, r = map(int, input().strip().split())
a = [int(input().strip()) for _ in range(n - 1)]

a.sort(reverse=True)
a_sum = sum(a[:k - 1])
target = k * r - a_sum

if target <= 0:
    print(0)
    exit()

a_sum += target
if a_sum > m * k:
    print("-1")
    exit()

print(target)

F - Sugoroku

这道题目让我们计算一束光在棋盘上的运动轨迹，这个过程中可能发生反射或者终止。由于题目涉及到很多的特殊情况，因此难度比较高，本文将不做过多讲解。时间复杂度O(N)。

# 空缺不计数
w, n = map(int, input().strip().split())

steps = [list(map(int, input().strip().split())) for _ in range(n)]

dp = [[float("inf")] * (w + 1) for _ in range(n + 1)]
dp[0][1] = 0

for i in range(1, n + 1):
    l, r, cost = steps[i - 1]
    for j in range(1, w + 1):
        for k in range(l, r + 1):
            if j - k < 1:
                continue
            dp[i][j] = min(dp[i][j], dp[i - 1][j - k] + cost)

if dp[n][w] == float("inf"):
    print(-1)
else:
    print(dp[n][w])

总结

本篇文章对ABC 146的六道题目进行了详细的讲解，并给出了各题目的代码实现。我们发现，虽然这场比赛难度逐渐递增，但是并不是每道题目的难度都是单调递增的，因此我们需要根据实际情况采取不同的解法。希望本篇文章能够对读者有所帮助。