洛谷-P9574 题解

思路分析

分析样例：

== TTBT BTTBTB TTT BTTB
-> TTBT TBBTTB TTT BTTB
-> TTBT TBTBBT TTT BTTB
-> TTBT TBTBBT TTT TBBT
----1-----2-----3---4--

观察区块 2，发现 BTTB 进行操作后与右边的 TB 再次构成 BTTB，我们发现在这个区块内，可以从左向右不断操作，我们称这种特性为传递性，可以发现其具有方向。

假设区块 2 右边有更多的 TB，例如 BTTBTBTBTBTB，是否仍然存在传递性呢？没错，你可以在纸上试一下，答案肯定。

推论 1：具有 BTTB TBTB... 特征的区块中，可以向右不断操作，操作具有传递性，方向向右。

那我们再反过来看呢？难道就不能向左不断操作吗？

我们在区块 2 的左边加上一些 BT，可以发现可以不断向左传递。

推论 1.1：BTTB TBTB... 具有向右的传递性；...BTBT BTTB 具有向左的传递性。

综合一下：

推论 1.2：...BTBT BTTB TBTB... 具有双向的传递性，在它的右方传递性向右，左方则向左。

考虑极限思维，...BTBT BTTB TBTB... 舍去了它的尾巴，变成 BTTB。思考发现这也是具有双向传递性的，只不过只能连续操作 1 次。

推论 1.3：BTTB 也具有双向传递性。

那么，这有什么用呢？

再次观察样例（如上），可以发现通过传递性进行操作，区块 3 左边多加了一个 T，右边也多加了一个 T。是的，我们可以通过区块的传递性对某个连续 T 区间增加 T。

我们对推论 1.1 再次分析，对于区间 BTTB TBTB...，可以发现右边的 B 变成了 T；而对于区间 ...BTBT BTTB，左边的 B 变成了 T。

由于区块 3 在区块 2 右边，区块 2 表现出向右的传递性，通过操作区块 2 右边的 B 变成 T，由于两个区块相邻，区块 3 连续 T 的长度增加 1。同理区块 4 表现出向左的传递性，邻接于区块 3，使得区块 3 连续 T 在右边又增加了 1。

推论 2：对于一个具有传递性的区块，它可以使它表现出的传递性方向上的邻接连续 T 区块长度增加 1。

可以发现，当某个具有传递性的区块进行操作后，它将损失其传递性，不再可操作，不再能给邻接 T 区块提供新的 T。也就是说：

推论 3：一个具有传递性的区块只能对其表现出的传递性方向上的邻接连续 T 区块贡献一次。

综合推论 2 和推论 3，我们可以得出推论 4：一个连续 T 区块只能收到两次贡献，来自左和右的两个方向，也就是说，每个连续 T 区间长度最多增加 2，其增加的 T 分别来源于左边和右边两个方向的与其方向相反的连续性区块。

从推论 4 的视角，我们再来看一次样例，我们把表现出向右连续性的区块视为 ->，向左的视为 <-。

TTBT -> TTT <-

可以看出连续性的方向对答案是存在影响的。

如此，我们找到每个具有连续性的区块，区块左边表现出向左的连续性，并打上标记，向右也是如此，但注意要区分方向。

然后枚举一遍连续 T 区块，如果其某个边界处存在标记且该标记方向正确，则该方向使长度加 1，最后取所有区块这样执行后的长度的最大值即可。

蒟蒻已经尽力说清楚了 QAQ。

代码实现

#define by_wanguan
#include<iostream>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=5e5+7;
int t,n,le[N],ri[N],ans; char c[N];
int main(){
  ios::sync_with_stdio(false),cin.tie(0);
  cin>>t; while(t--){
  cin>>n; for(int i=2;i<=n+1;i++) cin>>c[i],le[i]=ri[i]=0;
  int l=1,r=l+3; ans=0; c[0]=c[1]=c[n+2]=c[n+3]='#';
  le[0]=le[1]=le[n+2]=le[n+3]=ri[0]=ri[1]=ri[n+2]=ri[n+3]=0;//初始化
  while(r<=n){//通过双指针查找有连续性的区间
    l++,r++;
    if(c[l]=='B'&&c[l+1]=='T'&&c[l+2]=='T'&&c[l+3]=='B'){
	  ri[r]++,le[l]++;//发现存在，则在两端打上标记，le的标记方向向左，ri向右
      while(c[r+1]=='T'&&c[r+2]=='B') r+=2,ri[r]++;//向左右扩展区块并打上标记（找尾巴）
      while(c[l-1]=='T'&&c[l-2]=='B') l-=2,le[l]++;
      l=r-1,r=l+3;//l跳到r的位置，在本次操作后l和r都会++，提前减1
    }
  }
  l=1,r=l;
  while(r<=n){
    l=r,l++,r++;
    if(c[l]!='T') continue;//查询连续T区间
    while(c[r+1]=='T') r++;//扩展连续T区间
    ans=max(r-l+1+ri[l-1]+le[r+1],ans);//查询是否存在标记，注意方向
  }
  cout<<ans<<'\n';
}
}

有点 DP 的味道，看不懂请狠狠踢我！蒟蒻会尽量解答的。

喵。