分数: 300 点
问题陈述
给你一个长度为 N+1 组成 A 和 B: S = S_0\cdots S_N。
对于每个 k=1, \ldots, N,解决以下问题。
Alice 和 Bob 将使用一组玩游戏 X,最初是空的。对于 t=1,\ldots, k 按照此顺序,他们将执行以下操作:
- if t 是奇数,Alice 会选择一个非负整数 x 并替换 X 与 X\cup \{x\};
- if t 是偶数,Bob 会选择一个非负整数 x 并替换 X 与 X\cup \{x\}.
让 x be \mathrm{mex}(X) 毕竟 k 行动。如果角色 S_x is
A,爱丽丝获胜;如果 S_x isB,鲍勃获胜。请注意 X 最多有 k 元素,所以 x = \mathrm{mex}(X) \leq k 和角色 S_x 存在。当两名玩家都发挥最佳状态时打印获胜者的姓名。
什么是 \mathrm{mex}(X)?
对于有限集 X 由非负整数组成, \mathrm{mex}(X) 是最小的非负整数 x 这样 x\notin X.约束
- 1\leq N\leq 2\times 10^5
- S 是一个长度为 N+1 组成
A和B.
输入
输入由标准输入按以下格式给出:
N S
输出
打印 N 行。的 i- 第行应包含获胜者的姓名 (Alice or Bob)当双方都在游戏中发挥最佳水平时 k=i.
示例输入 1
2 ABB
示例输出 1
Alice Bob
这是游戏的可能进展 k=1.
- 爱丽丝选择 x=10.
- \mathrm{mex}(X)=\mathrm{mex}(\lbrace 10\rbrace) = 0,和 S_0 is
A,所以爱丽丝获胜。
这是游戏的可能进展 k=2.
- 爱丽丝选择 x=2.
- 鲍勃选择 x=0.
- \mathrm{mex}(X)=\mathrm{mex}(\lbrace 0,2\rbrace) = 1,和 S_1 is
B,所以鲍勃获胜。
示例输入 2
4 AAAAA
示例输出 2
Alice Alice Alice Alice
示例输入 3
7 BBAABABA
示例输出 3
Bob Bob Alice Bob Alice Bob Alice