题目链接：https://atcoder.jp/contests/agc063/tasks/agc063_a

做法

显然，如果我是 $A$ ，我一定会把数字放在最小的没被堵上的 $B$ 。

$B$ 同理，最终结果为最小的没有被堵上的位置上面的字符。

时间复杂度：$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<cstring>
#define N 210000
using namespace std;
char st[N];int n;
int now1,now2,now3;
bool v[N];
int main(){
    scanf("%d",&n);
    scanf("%s",st);
    for(int i=1;i<=n;i++){
        if(i&1){
            while(now1<n && st[now1]!='B')now1++;
            if(now1<=n)v[now1++]=1;
        }
        else{
            while(now2<n && st[now2]!='A')now2++;
            if(now2<=n)v[now2++]=1;
        }
        while(now3<=n && v[now3])now3++;
        if(!v[now3]){
            if(st[now3]=='A')printf("Alice\n");
            else printf("Bob\n");
        }
    }
    return 0;
}