抽卡系统（Gacha System）

抽卡系统

题目描述

构造一个长度为 n 的序列，仅包含 A、B、C、D 四种字符，满足：

• 每 10 次抽卡：至少一个 B、C 或 D
• 每 90 次抽卡：至少一个 C 或 D
• 每 180 次抽卡：至少一个 D
• 已知 B、C、D 的数量分别为 x、y、z

解题思路

核心观察

题目要求的是保底机制：

• 第 180 抽：D
• 第 90 抽：C 或 D
• 第 10 抽：B、C 或 D

贪心分配

从后往前分配，保证每个保底位置都被满足：

1. 分配 D（第 180, 360, … 位置）
2. 分配 C（第 90, 180, 270, … 位置，如果 C 不够则用 D）
3. 分配 B（第 10, 20, 30, … 位置，优先 B，不够则用 C/D）
4. 剩余位置：从前往后分配 D → C → B → A

位置规律

间隔	起始位置	保底内容
180	179	D
90	89	C 或 D
10	9	B、C 或 D

代码实现

n, x, y, z = map(int, input().split())

s = ["E"] * n

pos = 179
while z > 0 and pos < n:
    if s[pos] == "E":
        s[pos] = "D"
        z -= 1
    pos += 180

pos = 89
while pos < n:
    if s[pos] == "E":
        if y > 0:
            s[pos] = "C"
            y -= 1
        elif z > 0:
            s[pos] = "D"
            z -= 1
    pos += 90

pos = 9
while pos < n:
    if s[pos] == "E":
        if x > 0:
            s[pos] = "B"
            x -= 1
        elif y > 0:
            s[pos] = "C"
            y -= 1
        elif z > 0:
            s[pos] = "D"
            z -= 1
    pos += 10

for i in range(n):
    if s[i] == "E":
        if z > 0:
            s[i] = "D"
            z -= 1
        elif y > 0:
            s[i] = "C"
            y -= 1
        elif x > 0:
            s[i] = "B"
            x -= 1
        else:
            s[i] = "A"

print("".join(s))

代码详解

四个分配阶段

1. 阶段1：从位置 179 开始，每隔 180 分配 D（最高保底）
2. 阶段2：从位置 89 开始，每隔 90 分配 C，优先 C，不够则用 D
3. 阶段3：从位置 9 开始，每隔 10 分配 B，优先 B，不够则用 C/D
4. 阶段4：剩余位置从前往后分配，顺序为 D → C → B → A

关键点

• 从后往前：先满足高保底要求，再满足低保底要求
• 保底累加：满足高层保底的位置同时也满足低层保底
• 优先级：D > C > B > A（从高到低）

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)