考虑 dp，设 \(f_{i,0/1}\) 表示考虑到前 \(i\) 位，且第 \(i\) 位填入 A/B 可能的答案集合，显然地朴素转移时间复杂度 \(O(n^2)\)。
试分析 dp 性质，观察发现所有 dp 中得到的集合为区间内抠去至多一个点。
证明
我们首先来观察转移过程是怎样的。第一种是第二行中 $i-1$ 填入的字母与第一行中 $i$ 填入的字母相同的情况，此时根据我们填入的字母与其相同与否，集合会整体平移 $0$ 或 $2$；第二种是不同的情况，此时无论我们如何填入字母，集合都会整体平移 $1$。由于我们只关心集合的相对位置关系，我们可以将转移视为将 $f_{i-1,0/1}$ 固定不动，将 $f_{i-1,1/0}$ 平移 $1$ 以及 $-1$，分别进行取或操作，得到 $f_{i}$。首先容易发现，\(f_i\) 的两个集合两侧端点的差的绝对值分别不超过 \(2\)。这是由于这两个集合是由一个固定的集合或上另外一个集合平移 \(1/-1\) 得到的。现在，我们可以归纳说明一个更强的结论：\(f_i\) 的两个集合中至多存在一个集合中存在且恰存在一个空位。
显然 \(1\) 满足条件。假设 \(i-1\) 满足此条件。由于区间过小时的情况比较神秘，我们在此只讨论 \(r-l+1\ge5\) 的情况。对于区间更小的情况打表可证。在这种情况下，最坏是 \(f_{i-1,x}\) 为 \([l,r]\) 抠去 \(p(p\in(l,r))\)，\(f_{i-1,1-x}\) 为 \([l+2,r-2]\)。此时，若 \(i\) 不满足此条件，则存在一个 \(p\) 使得 \([l+2,r-2]\) 无论平移 \(1\) 还是 \(-1\) 都无法覆盖到，而这显然无解。
故证毕。证得比原结论更强的结论，故原结论也证毕。
褐自落谷题解
所以说对于每个 \(f_{i,0/1}\) 只需要维护 \((l,r,p)\)，即（左端点，右端点，中间挖去的点）
时间复杂度 \(O(n)\)。
code：
#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
int T;
int n,k;
char s[NN],S[NN];
struct Node{
int l,r,p;
Node operator + (int x){
return {l+x,r+x,p==-1?-1:p+x};
}
bool ckin(int x){
return l <= x && x <= r && x != p;
}
}f[NN][2];
Node operator ^ (Node a, Node b){
if(a.l > b.l) swap(a,b);
Node res = {min(a.l,b.l),max(a.r,b.r),-1};
if(a.r + 2 == b.l) res.p = a.r + 1;
else{
if(a.p != -1 && !b.ckin(a.p)) res.p = a.p;
if(b.p != -1 && !a.ckin(b.p)) res.p = b.p;
}
return res;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
scanf("%s",s+1);
for(int i = 1; i < n; ++i) k -= (s[i]!=s[i+1]);
if(k < 0){puts("NO");continue;}//判第一行
int type = s[1] - 'A';
f[1][type^1] = {1,1,-1}; f[1][type] = {0,0,-1};
int ty;
for(int i = 2; i <= n; ++i){
ty = s[i]-'A';
f[i][ty] = f[i-1][ty] ^ f[i-1][ty^1]+1;
f[i][ty^1] = f[i-1][ty]+2 ^ f[i-1][ty^1]+1;
}
ty = -1;
if(f[n][0].ckin(k)) ty = 0;
if(f[n][1].ckin(k)) ty = 1;
if(ty == -1) {puts("NO");continue;}
puts("YES");
for(int i = n; i; --i){
S[i] = 'A' + ty;
if(i == 1) break;
k -= (S[i]!=s[i]);
if(f[i-1][ty].ckin(k)) continue;//只要有答案就走
ty ^= 1, --k;
}
printf("%s\n",S+1);//ans collecting
for(int i = 1; i <= n; ++i) S[i] = '\000';
}
}