P9574 「TAOI-2」Break Through the Barrier

· · 个人记录

思路

首先我们可以肯定的是，无论如何变化，答案最多比原序列的连续 T 的个数多 2。

理由很简单，对于 ...BT...TB...，最好的可能就是前后两个 B 可以变成 T，因为只可能是 BTTB 变成 TBBT，所以变了以后再外面就一定是 B 了，且无法再变。

所以我们可以先找到可能成为答案的一段连续 T，然后暴力向前和向后判断能否增加答案，然后更新答案即可。

那么，什么时候可以增加答案呢？

当然是前面或者后面是 BTTB 的时候啦，于是我满心欢喜地以为自己找到了正解，然后交了一发，然后 WA 了。

嗯，当时自己确实有点狂妄，都没发现样例最后一组都错了。

再仔细观察了样例后，发现如果出现了 BTTBTBTBTB... 的情况，就可以从左至右依次变化，最后也能使答案增加。

所以形如前面有至少一个 BT，后面有若干个 TB 也能增加答案，反过来也同理。

所以我又不假思索地直接写了发暴力判断前后能否增加答案，然后 TLE 了。

嗯，至少没有 WA，这至少是一件好事，代表这个做法没有问题，那么如何优化呢，思考了一下，如果出现了 BTTBTBTBTB... 的情况，每个 T 都会去暴力判断一次（因为最长 T 的长度是 2，那所有长度为 1 的都有可能加 2 超过最长的，所以必须判断），那这样的话就重复判断了很多次。如果数据比较特殊，那必然会 TLE。

所以我们需要优化代码，来让上面的情况不会出现。

于是，我想到了预处理。

只要出现了 BT，那么，后面的所有连续的 TB 的 B 位置都可以变成 T 来让答案增加一，反过来也差不多，就跑两边就好。

只是这次我看了下样例，居然错了，形如 BTTB 的测试点，程序会把左右两个 B 都搞成可以增加答案的情况了。

所以，我们还需要区分是方向，就用两个数组存就行。

终于，在这一波三折的猪脑过载调试下，终于把这道题目过了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int T,n,ans,num,p,kkk;
bool can1[100005],can2[100005];
char ch[100005];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(can1,0,sizeof(can1)),memset(can2,0,sizeof(can2));//记得清零
        scanf("%d%s",&n,ch),p=-1,ans=num=0;//记得赋初始值
        for(int i=0;i<n;++i)
        {
            if(ch[i]=='B'&&ch[i+1]=='T')//如果出现了BT
            {
                int kkk=i+2;
                while(kkk<n-1&&ch[kkk]=='T'&&ch[kkk+1]=='B')
                    can1[kkk+1]=1,i=kkk,kkk+=2;//就把所有后面连续的TB的B位置上标记为正向可增加答案
            }
        }
        for(int i=n-1;i>=0;--i)
        {
            if(ch[i]=='B'&&ch[i-1]=='T')//同上，只是顺序反了
            {
                int kkk=i-2;
                while(kkk>0&&ch[kkk]=='T'&&ch[kkk-1]=='B')
                    can2[kkk-1]=1,i=kkk,kkk-=2;
            }
        }
        //这里的kkk赋值给i是为了让循环少几次，不然就和直接暴力没什么区别了
        for(int i=0;i<n;++i)
        {
            if(ch[i]=='T')//如果是T就增加，p是为了标记这段连续的T的第一个位置
            {
                ++num;
                if(p==-1) p=i;
            }
            else
            {
                /*下面三行可替换为ans=max(ans,num+can1[p-1]+can2[i]);*/ 
                if(can1[p-1]) ++num;
                if(can2[i]) ++num;
                ans=max(ans,num);
                num=0,p=-1; 
            }
        }
        /*下面四行可替换为printf("%d\n",max(ans,num+can1[p-1]+can2[n-1]));*/
        if(can1[p-1]) ++num;
        if(can2[n-1]) ++num;
        ans=max(ans,num);
        printf("%d\n",ans);
        //最后还可能有一段没有判断到，需要再max一遍
    }
    return 0;
}