题解：AT_agc078_c [AGC078C] AB vs. BA

Feather_Moon · 2026-09-28 13:11:39 · 题解

超大罚时最后 15min 极限场切了。非常感动，人生中第一次场切银牌题。下面是一个和官解不一样的做法，也是我的赛时做法。可能没有官解这么优美，但是会比较容易想到。

两个人都希望自己多取，让对方少取。所以两个人的策略都是在取自己子串的时候，尽可能去破坏对方的子串。

寻找一些比较容易处理的结构，比如中间的连续段长度为 1 的结构，即 ABA 和 BAB 形。根据上面的策略，两个人都会去取里面的 AB 和 BA 子串，从而破坏掉对方的子串，并且获得一步的优势，和博弈中的 \texttt{*} 局面非常相似。所以我们先考虑简化所有的 \texttt{*} 局面，把 ABA、BAB 分别变成 A 和 B，并且由于 \texttt{*} + \texttt{*} = 0，我们只需要记录 \texttt{*} 局面数量的奇偶性。这种操作可以缩去连续段为 1 的非开头，结尾段。我们把这种操作记录为 \texttt{*} 操作。

现在每个连续段的长度都大于 1 了，考虑减少段的长度使其出现 \texttt{*} 局面从而进行简化。一个想法是，每一个连续段两边都会产生一个 1（即 AB） 和 -1（即 BA），我们把这个连续段的长度 -2，两侧的连续段长度 -1，然后把 1 和 -1 抵消掉。但是很可惜，这个想法是错的。

上面那个想法为什么错呢？原因就在于这样操作还会影响其他连续段的交界处。局部的操作不行，我们就考虑整体操作，对每一个交界处的 1 和 -1 一起操作，用一个数记录和即可，也就是开头和结尾两个段长度 -1，中间的段长度 -2，并且记录 AB 和 BA 数量的差。这样操作尽可能保留了段之间长度的差，让保留的优势尽可能不发生改变。至于两端，也只能产生几乎独立的 1 和 -1 的贡献，已经记录在数中了。写一发暴力，果然是对的。

现在我们有了两种操作：\texttt{*} 操作和全局减操作。这两种操作一种可以消去长度为 1 的中间段，另一种可以缩短所有段的长度。反复执行这两种操作，最后会化成连续段数量小于等于 2 的形式。两个连续段的情况记得把其中能贡献的所有 AB 和 BA 都记录到和里面。

最后就是答案的判定，和博弈是一样的，如果和大于 0 或和为 0 且 \texttt{*} 数量为奇那么 Abel 胜，否则 Bart 胜。

::::::success[Code] 赛时代码是从暴力和猜结论的代码逐步改过来的，没有可读性，可能还有地方写错的，不建议大家看。简化版代码应该会好一点。 :::info[赛时代码]

#include<bits/stdc++.h>
using namespace std;
const int N=18,V=(1<<17)+5;
int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int f[N][V][2];
inline void dfs(int n,int S,int t){
    if(f[n][S][t]!=-1)return;
    vector<int> vec;
    for(int i=0;i<n;i++)vec.push_back((S>>i)&1);
    int now=1-t;
    for(int i=1;i<n;i++){
        if(vec[i-1]==t && vec[i]==1-t){
            int nxtS=(S&((1<<(i-1))-1))|((S>>(i+1))<<(i-1));
            dfs(n-2,nxtS,1-t);if(f[n-2][nxtS][1-t]==t)now=t;
            if(now==t)break;
        }
    }
    f[n][S][t]=now;return;
}
int n;
int a[V];
int stk[V],top;
int len[V],tot;
int B[V],num,C[V];
int col[V]; 
signed main(){
    memset(f,-1,sizeof f);
    for(int i=0;i<=16;i++)
    for(int S=0;S<(1<<i);S++)
        dfs(i,S,0),dfs(i,S,1);
    int T=read();
    while(T--){
        string S;n=read();cin>>S;S=" "+S;
        for(int i=1;i<=n;i++)a[i]=S[i]-'A';
        top=0;
        for(int i=1;i<=n;i++){
            while(top>=2&&stk[top]!=a[i]&&stk[top-1]==a[i])top-=2;
            stk[++top]=a[i];
        }
//      if(top<=16){
//          int now=0;
//          for(int i=1;i<=top;i++)now|=stk[i]<<(i-1);
//          cout<<(f[top][now][(((n-top)/2)&1)]==0?"Abel":"Bart")<<endl;
//          continue;
//      }
        int now=stk[1],st=stk[1],cnt=0;tot=0;
        for(int i=1;i<=top;i++){
            if(stk[i]==now)cnt++;
            else len[++tot]=cnt,cnt=1,now=stk[i];
        }
        if(cnt>=1)len[++tot]=cnt;
        if(tot==1){
            cout<<((((n-top)/2)&1)?"Abel":"Bart")<<endl;
            continue;
        }
        if(tot==2){
            if(st==0)cout<<"Abel"<<endl;
            if(st==1)cout<<"Bart"<<endl;
            continue;
        }
        int op=0; 
        int al=((n-top)/2)&1;
        while(1){
            top=0;col[1]=st;
            for(int i=2;i<=tot;i++)col[i]=1-col[i-1];
            int flg=1;
            for(int i=2;i<tot;i++)if(len[i]<2)flg=0;
            if(flg==0)break;
            if(tot<=2)break;
            if(tot%2==0){
                if(st==0)op++;
                else op--;
            }
            for(int i=2;i<tot;i++)len[i]-=2;len[1]--;len[tot]--;
            num=0;int lst=-1;cnt=0;
            for(int i=1;i<=tot;i++){
                if(len[i]==0)continue;
                if(lst==-1){
                    st=col[i];lst=col[i];cnt=len[i];
                    continue;
                }
                if(col[i]==lst)cnt+=len[i];
                else lst=col[i],B[++num]=cnt,cnt=len[i];
            }
            if(cnt>=1)B[++num]=cnt;
            tot=num;
            for(int i=1;i<=tot;i++)len[i]=B[i];
            col[1]=st;
            for(int i=2;i<=tot;i++)col[i]=1-col[i-1];
            num=0;lst=-1;
            for(int i=1;i<=tot;i++){
                while(num>=2&&C[num]!=col[i]&&C[num-1]==col[i]&&B[num]==1){
                    B[num-1]--;num--;lst=1-lst;al=1-al; 
                    if(B[num]==0)num--,lst=1-lst;
                    if(num==0)lst=-1; 
                }
                if(len[i]==0)continue;
                if(lst!=col[i])B[++num]=len[i],C[num]=col[i];
                else B[num]+=len[i];
                lst=col[i];
            }
            tot=num;
            for(int i=1;i<=tot;i++)len[i]=B[i],col[i]=C[i];
            st=col[1];
        }
        if(tot<=1){
            if(op>=1){cout<<"Abel"<<endl;continue;}
            if(op<=-1){cout<<"Bart"<<endl;continue;}
            cout<<((al)?"Abel":"Bart")<<endl;
            continue;
        }
        if(tot==2){
            if(st==0)op+=min(len[1],len[2]);
            else op-=min(len[1],len[2]); 
            if(op>=1){cout<<"Abel"<<endl;continue;}
            if(op<=-1){cout<<"Bart"<<endl;continue;}
            cout<<((al)?"Abel":"Bart")<<endl;
            continue;
        }
        now=st;vector<int> F;
        for(int i=1;i<=tot;i++){
            int geshu=len[i];
            while(geshu--)F.push_back(now);
            now=1-now;
        }
        if(F.size()<=16){
            now=0;
            for(int i=0;i<F.size();i++)now|=F[i]<<i;
            cout<<(f[F.size()][now][al]==0?"Abel":"Bart")<<endl;
            continue; 
        }
        exit(-1);
    }
    return 0;
}

::: :::success[简化版代码]

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n;
int a[N];
int stk[N],top;
int len[N],tot;
int B[N],num,C[N];
int col[N]; 
signed main(){
    int T=read();
    while(T--){
        string S;n=read();cin>>S;S=" "+S;
        for(int i=1;i<=n;i++)a[i]=S[i]-'A';
        top=0;
        for(int i=1;i<=n;i++){
            while(top>=2&&stk[top]!=a[i]&&stk[top-1]==a[i])top-=2;
            stk[++top]=a[i];
        }
        int now=stk[1],st=stk[1],cnt=0;tot=0;
        for(int i=1;i<=top;i++){
            if(stk[i]==now)cnt++;
            else len[++tot]=cnt,cnt=1,now=stk[i];
        }
        if(cnt>=1)len[++tot]=cnt;
        int op=0,al=((n-top)/2)&1;
        while(1){
            top=0;col[1]=st;for(int i=2;i<=tot;i++)col[i]=1-col[i-1];
            int flg=1;for(int i=2;i<tot;i++)if(len[i]<2)flg=0;
            if(flg==0||tot<=2)break;if(tot%2==0)if(st==0)op++;else op--;
            for(int i=2;i<tot;i++)len[i]-=2;len[1]--;len[tot]--;
            num=0;int lst=-1;cnt=0;
            for(int i=1;i<=tot;i++){
                if(len[i]==0)continue;
                if(lst==-1){st=col[i];lst=col[i];cnt=len[i];continue;}
                if(col[i]==lst)cnt+=len[i];
                else lst=col[i],B[++num]=cnt,cnt=len[i];
            }
            if(cnt>=1)B[++num]=cnt;
            tot=num;for(int i=1;i<=tot;i++)len[i]=B[i];
            col[1]=st;for(int i=2;i<=tot;i++)col[i]=1-col[i-1];
            num=0;lst=-1;
            for(int i=1;i<=tot;i++){
                while(num>=2&&C[num]!=col[i]&&C[num-1]==col[i]&&B[num]==1){
                    B[num-1]--;num--;lst=1-lst;al=1-al; 
                    if(B[num]==0)num--,lst=1-lst;
                    if(num==0)lst=-1; 
                }
                if(len[i]==0)continue;
                if(lst!=col[i])B[++num]=len[i],C[num]=col[i];
                else B[num]+=len[i];
                lst=col[i];
            }
            tot=num;
            for(int i=1;i<=tot;i++)len[i]=B[i],col[i]=C[i];
            st=col[1];
        }
        if(tot==2)op+=(st?-1:1)*min(len[1],len[2]);
        cout<<((op>=1||(op==0&&al))?"Abel":"Bart")<<endl;
    }
    return 0;
}