前言：比賽前去做牙齒矯正，回來晚了 10 分鐘……做比賽的運氣全用在了一路綠燈上了（無語）。第二題切了兩個半小時。決定寫篇題解來抒發一下再記得憤怒愉悅之情。

AC 的想法很簡單，就是表示出每一串連續的 \(\texttt{T}\)，其長度分別為 \(l_1 \sim l_m\)。明顯的，對于任何一個 \(l_i\)，在一系列操作后，它的長度頂多加 \(2\)，也就是左邊多一個，右邊多一個。明顯的貪心，將 \(\texttt{T}\) 子串按長度從大到小排，然后只要枚舉到 \(l_i < ans-1\)，就可以結束了。因為它既是加兩個，也只能等于 \(ans\)。然后每次更新 \(ans\)。

對于判斷左右是否能增加一個，不是只判斷有沒有 \(\texttt{BTTB}\) 那么簡單。拿左邊來說，他可能長這樣：

他可以一路猛操作變成：

我嗎，蠢蠢地使用了暴力，然后喜提 \(2\mathcal{WA}+4\mathcal{TLE}\)。加個記憶化，喜提 \(2\mathcal{WA}\)。

兩次的翻車記錄在這里：4TLE+2WA，2WA。

為什么呢？因為這個樣例：\(1 \texttt{B}\)，要特判一下。（大概也只有我會漏掉這個樣例的情況吧，悲。）

\(\mathcal{AC} \texttt{CODE}\)：

#include <bits/stdc++.h>
using namespace std;

int T,n,cnt;
struct Node {
	int l,r,mm;
	Node(int L=0,int R=0,int m=0) {
		l=L,r=R,mm=m;
		return ;
	}
	friend bool operator <(const Node a,const Node b) {
		return a.mm>b.mm;
	}
};
const int MS=100005;
Node node[MS];
char s[MS];
int pr[MS][2];
bool GO(int p,int drct) {
	if(p<1||p>n-1) return 0;
	if(pr[p][drct-1]!=-1) return pr[p][drct-1];
	if(drct&1) {
		if(p>2&&s[p]=='B'&&s[p-1]=='T'&&s[p-2]=='T'&&s[p-3]=='B') return pr[p][drct-1]=true;
		if(s[p]=='B'&&s[p-1]=='T') return pr[p][drct-1]=GO(p-2,drct);
	}
	else {
		if(p<n-3&&s[p]=='B'&&s[p+1]=='T'&&s[p+2]=='T'&&s[p+3]=='B') return pr[p][drct-1]=true;
		if(s[p]=='B'&&s[p+1]=='T') return pr[p][drct-1]=GO(p+2,drct);
	}
	return pr[p][drct-1]=false;
}

int main() {
	scanf("%d",&T);
	while(T--) {
		memset(pr,-1,sizeof(pr));
		scanf("%d%s",&n,s);
		int l=-1;
		cnt=0;
		for(int i=0;i<n;i++) {
			if(s[i]=='B'&&l>=0) node[++cnt]=Node(l,i-1,i-l),l=-1;
			if(s[i]=='T'&&l<0) l=i;
		}
		if(l>=0) node[++cnt]=Node(l,n-1,n-l);
		if(cnt==0) {
			printf("0\n");
			continue;
		}
		sort(node+1,node+1+cnt);
		int ans=node[1].mm;
		for(int i=1;i<=cnt&&node[i].mm>=ans-1;i++) {
			if(GO(node[i].l-1,1)) node[i].mm++;
			if(GO(node[i].r+1,2)) node[i].mm++;
			ans=max(ans,node[i].mm);
		}
		printf("%d\n",ans);
	}
	return 0;
}

為什么辣么簡單的暴力題要切兩個半小時呢？因為我一直往 DP 和暴搜上考慮，浪費了兩個小時。警鐘長鳴。