AtCoder Beginner Contest 146解题报告

AtCoder Beginner Contest 146解题报告的完整攻略

AtCoder Beginner Contest 146是AtCoder举办的一场比赛，共有6道题目。本文将详细讲解AtCoder Beginner Contest 146解题报告的完整攻略，包括6道题目的解法和两个示例说明。

A - Can't Wait for Holiday

题目描述：给定一周中的某一天，计算距离下一个周六的天数。

解题思路：根据题意，可以先计算出当前是周几，然后计算距离下一个周六的天数。可以使用一个数组来存储一周中每一天的名称，然后使用循环查找当前是周几的索引，再计算距离下一个周六的天数。

days = ["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"]
today = input()
days_to_saturday = days.index("SAT") - days.index(today)
print(days_to_saturday if days_to_saturday >= 0 else days_to_saturday + 7)

B - ROT N

题目描述：给定一个字符串和一个整数N，将字符串中的每个字符向后移动N个位置。

解题思路：可以使用ASCII码来实现字符的移动。将字符转换为ASCII码，向后移动N个位置后再转换回字符即可。

n = int(input())
s = input()
result = ""
for c in s:
    ascii_code = ord(c)
    shifted_ascii_code = (ascii_code - ord("A") + n) % 26 + ord("A")
    result += chr(shifted_ascii_code)
print(result)

C - Buy an Integer

题目描述：给定三个整数A、B和X，计算满足A * N + B * d(N) <= X的最大的N。

解题思路：可以使用二分查找来实现。设N的取值范围为[1, X]，则可以使用二分查找来查找满足条件的最大的N。在二分查找的过程中，需要计算d(N)的值。

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

def d(n):
    return len(str(n))

left = 0
right = x
while left <= right:
    mid = (left + right) // 2
    if a * mid + b * d(mid) <= x:
        left = mid + 1
    else:
        right = mid - 1
print(right)

D - Coloring Edges on Tree

题目描述：给定一棵树，将树的边染成两种颜色，使得相邻的边颜色不同。计算染色方案的数量。

解题思路：可以使用DFS来实现。对于每个节点，可以将其与父节点的边染成一种颜色，然后递归处理其子节点。对于每个节点，需要记录其与父节点的边的颜色，以避免相邻的边颜色相同。

import sys
sys.setrecursionlimit(10**7)

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

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

def dfs(v, p, c):
    k = 1
    for u, i in edges[v]:
        if u == p:
            continue
        if k == c:
            k += 1
        colors[i] = k
        dfs(u, v, k)
        k += 1

dfs(0, -1, -1)
print(max(colors))
for c in colors:
    print(c)

E - Rem of Sum is Num

题目描述：给定一个整数N和一个整数S，计算满足sum(d(N)) = S的最小的N。

解题思路：可以使用DP来实现。设dp[i][j]表示使用i位数字，数字和为j的最小的N。可以使用数位DP的思想来实现。

n, s = map(int, input().split())

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

for i in range(n):
    for j in range(s + 1):
        for k in range(10):
            if j - k >= 0:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - k] * 10 + k)

print(dp[n][s] if dp[n][s] != float("inf") else -1)

F - Sugoroku

题目描述：给定一个长度为N的数组A和一个整数K，每次可以将数组中的一个元素加上K或减去K，求将数组中所有元素变为0的最小操作次数。

解题思路：可以使用贪心算法来实现。首先将数组A排序，然后从中间位置开始，将左边的元素加上K，将右边的元素减去K，直到数组中所有元素都变为0。

n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
left = 0
right = n - 1
ans = float("inf")
while left <= right:
    mid = (left + right) // 2
    cnt = 0
    for i in range(mid + 1):
        if a[i] > 0:
            cnt += (a[i] - k - 1) // k + 1
    for i in range(mid + 1, n):
        if a[i] < 0:
            cnt += (-a[i] - k - 1) // k + 1
    if cnt <= mid:
        ans = min(ans, mid)
        right = mid - 1
    else:
        left = mid + 1

print(ans)

示例1：A - Can't Wait for Holiday

问题描述：给定一周中的某一天，计算距离下一个周六的天数。

输入：WED

输出：4

解释：当前是周三，距离下一个周六还有4天。

示例2：B - ROT N

问题描述：给定一个字符串和一个整数N，将字符串中的每个字符向后移动N个位置。

输入：

2
ABCXYZ

输出：

CDEZAB

解释：将字符串中的每个字符向后移动2个位置，得到CDEZAB。

总结

AtCoder Beginner Contest 146是AtCoder举办的一场比赛，共有6道题目。本文详细讲解了AtCoder Beginner Contest 146解题报告的完整攻略，包括6道题目的解法和两个示例说明。这些题目涵盖了不同的算法和数据结构，包括字符串处理、二分查找、贪心算法、DP等。通过学习这些题目，可以提高算法和数据结构的应用能力。