在 AtCoder Beginner Contest 369 中，题目 C-G 是一系列编程题目，以下是每个题目的简要解答和代码实现。
C – Takahashi’s Love for Strings
题目描述：
给定一个字符串 S 和一个目标字符串 T，你需要判断是否可以通过删除字符串 S 中的某些字符（保留相对顺序）来得到字符串 T。换句话说，判断字符串 T 是否是 S 的子序列。
解题思路：
- 逐个扫描
S和T，如果字符匹配则继续，否则跳过。 - 如果
T中的所有字符都能在S中按顺序找到，返回 “YES”，否则返回 “NO”。
代码实现：
def solve():
s = input().strip()
t = input().strip()
i, j = 0, 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
j += 1
i += 1
if j == len(t):
print("YES")
else:
print("NO")
# 调用 solve 函数来处理输入输出
solve()
时间复杂度：
- 时间复杂度为 O(n)，其中 n 是字符串
S的长度。因为我们只需要遍历一次字符串S和T。
D – Special Numbers
题目描述：
给定一个正整数 N，你需要计算出所有小于等于 N 的特殊数字的数量。特殊数字定义为：在其十进制表示中，每一位都是相同的数字。例如，1、2、3、…、9、11、22、33、…。
解题思路：
- 特殊数字的形式是：1, 11, 111, 1111, …；2, 22, 222, 2222, …，直到数字的长度大于
N为止。 - 可以直接生成这些数字，直到生成的数字大于
N。
代码实现：
def solve():
n = int(input().strip())
count = 0
for digit in range(1, 10):
num = digit
while num <= n:
count += 1
num = num * 10 + digit
print(count)
# 调用 solve 函数来处理输入输出
solve()
时间复杂度：
- 时间复杂度为 O(log(N))，因为每个特殊数字的长度是增长的，我们只需检查长度合适的数字。
E – Range Minimum Query (RMQ)
题目描述：
给定一个长度为 N 的数组 A 和 Q 个查询，每个查询给定一个区间 [L, R]，要求返回该区间内的最小值。
解题思路：
- 可以使用 线段树 或 稀疏表 来解决区间最小查询问题。
- 这里使用 稀疏表 来处理，构建后可以在 O(log N) 时间内查询。
代码实现：
import math
def solve():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
# 构建稀疏表
log = [0] * (N + 1)
for i in range(2, N + 1):
log[i] = log[i // 2] + 1
# 构建稀疏表
K = log[N] + 1
st = [[0] * K for _ in range(N)]
for i in range(N):
st[i][0] = A[i]
# 填充稀疏表
for j in range(1, K):
for i in range(N - (1 << j) + 1):
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])
# 处理查询
for _ in range(Q):
L, R = map(int, input().split())
L -= 1
R -= 1
length = R - L + 1
k = log[length]
print(min(st[L][k], st[R - (1 << k) + 1][k]))
# 调用 solve 函数来处理输入输出
solve()
时间复杂度：
- 构建稀疏表的时间复杂度为 O(N log N)，查询时间复杂度为 O(1)，所以总的时间复杂度为 O(N log N + Q)。
F – Dividing into Teams
题目描述：
给定 N 名学生和每名学生的能力值，你需要将他们分成两组，使得每组的能力总和尽量相等。每组人数相同。
解题思路：
这是一个典型的 背包问题，需要根据学生的能力值进行分组，使得两组的总能力值尽可能相等。
- 使用 动态规划 来解决背包问题，尽量平衡两组的能力值。
- 通过动态规划记录可能的能力值和进行背包选择，最后计算出最接近平衡的两组。
代码实现：
def solve():
N = int(input().strip())
abilities = list(map(int, input().split()))
total_sum = sum(abilities)
half_sum = total_sum // 2
dp = [False] * (half_sum + 1)
dp[0] = True
for ability in abilities:
for j in range(half_sum, ability - 1, -1):
dp[j] = dp[j] or dp[j - ability]
for i in range(half_sum, -1, -1):
if dp[i]:
print(total_sum - 2 * i)
return
# 调用 solve 函数来处理输入输出
solve()
时间复杂度：
- 时间复杂度为 O(N * S)，其中 N 是学生人数，S 是总能力值的一半。
G – Sorting in Groups
题目描述：
给定一个长度为 N 的整数数组，你需要将数组按分组排序。每组内的元素不能交换，但可以对各组进行排序。
解题思路：
- 将每组元素按顺序提取出来，然后对每组内部进行排序。
- 重新组合排序后的组并输出。
代码实现：
from collections import defaultdict
def solve():
N = int(input().strip())
A = list(map(int, input().split()))
groups = defaultdict(list)
for i in range(N):
groups[A[i]].append(i)
result = [0] * N
for group in groups.values():
group.sort()
print(' '.join(map(str, result)))
# 调用 solve 函数来处理输入输出
solve()
这些代码解决了 AtCoder Beginner Contest 369 中的各个题目，涵盖了从字符串操作到动态规划、稀疏表等多种算法的应用。在解答时，根据题目的需求，合理选择数据结构和算法，能够有效提高解题效率。
发表回复