atcoder#AGC062A. [AGC062A] Right Side Character

[AGC062A] Right Side Character

题目描述

A,B のみからなる長さ n (2 n) n\ (2\leq\ n) の文字列 T=T1T2 Tn T=T_1T_2\dots\ T_n に対し、長さ n1 n-1 の文字列 f(T) f(T) を以下のように定めます。

  • Ti= T_i={} A が成り立つ i (1 i  n1) i\ (1\leq\ i\ \leq\ n-1) 全体を a1 < a2 <  < am a_1\ <\ a_2\ <\ \dots\ <\ a_{m} とし、 Ti= T_i={} B が成り立つ i (1 i  n1) i\ (1\leq\ i\ \leq\ n-1) 全体を b1 < b2 <  < bk b_1\ <\ b_2\ <\ \dots\ <\ b_k とする。このとき、 $ f(T)=T_{a_1+1}T_{a_2+1}\dots\ T_{a_m+1}T_{b_1+1}T_{b_2+1}\dots\ T_{b_k+1} $ と定める。

例えば文字列 T= T={} ABBABA について、Ti= T_i={} A が成り立つ i (1 i  5) i\ (1\leq\ i\ \leq\ 5) 全体は i=1,4 i=1,4 , Ti= T_i={} B が成り立つ i (1 i  5) i\ (1\leq\ i\ \leq\ 5) 全体は i=2,3,5 i=2,3,5 であるため、f(T) f(T) T1+1T4+1T2+1T3+1T5+1= T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={} BBBAA になります。

A,B のみからなる長さ N N の文字列 S S が与えられます。

S S f(S) f(S) で置き換えることを N1 N-1 回行った後の S S を求めてください。

T T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

T T case1 \mathrm{case}_1 \vdots caseT \mathrm{case}_T

各ケースは以下の形式で与えられます。

N N S S

输出格式

T T 行出力してください。i i 行目には i i 番目のテストケースに対する答えを出力してください。

题目大意

对于一个长为 n2n\ge 2 的只由 AB 组成的字符串 S[1n]S[1…n],定义 f(S)f(S)SS 中从左到右所有 A 右边的第一个字符组成的字符串加上 SS 中从左到右所有 B 右边的第一个字符组成的字符串。由于 SS 中除了最右边的字符之外右边都有字符,所以 f(S)f(S) 的长度为 n1n-1

TT 组数据,给出 SS,将 SS 反复执行 Sf(S)S\to f(S) 直到 SS 长度为 11,问你最后的这个字符是 A 还是 B

  • n3×105\sum n\le 3\times 10^5
3
2
AB
3
AAA
4
ABAB
B
A
A

提示

制約

  • 1  T  105 1\ \leq\ T\ \leq\ 10^5
  • 2  N  3 × 105 2\ \leq\ N\ \leq\ 3\ \times\ 10^5
  • S S A,B のみからなる長さ N N の文字列
  • 入力される数値はすべて整数
  • 1 1 つの入力に含まれるテストケースについて、 N N の総和は 3 × 105 3\ \times\ 10^5 以下

Sample Explanation 1

1 1 つ目のテストケースについて、S S AB  {}\rightarrow\ {} B と変化します。 2 2 つ目のテストケースについて、S S AAA   {}\ \rightarrow\ {} AA   {}\ \rightarrow\ {} A と変化します。 3 3 つ目のテストケースについて、S S ABAB  {}\rightarrow\ {} BBA   {}\ \rightarrow\ {} BA   {}\ \rightarrow\ {} A と変化します。