「TAOI-2」Break Through the Barrier

CJ_Fu · 2023-08-21 09:10:25 · 个人记录

题面

P9574

题意

给定一个字符串 s，若 s 的字串 t=\texttt{TBBT}，则可以选择将 t\gets\texttt{BTTB}，当然也可以不操作。

求操作若干次（可以零次）后，s 内连续 \texttt T 的长度的最大值。

证明直接模拟即可。这告诉我们 若干 \texttt{BT}+\texttt{BTTB}+\text{}\! 若干 \texttt{TB} 和 \texttt{BTTB} 其实是等价的。

看到 \texttt{BTTB}\to\texttt{TBBT} 这个操作，若 \texttt{BTTB} 的左右两边有连续的 \texttt T 串，那对于这个串，进行了这次操作之后，它的长度就会 \!\text{}+1，而又因为操作之后出现了 \texttt{BB}，因此不能再继续操作。所以对于 \texttt T 串的一边长度最多 \!\text{}+1，即该串的长度在若干次操作后最多变成原长度 \!\text{}+2。

举个例子：

两端都是 \texttt{BB}，无法继续扩展。

证明完毕。

所以一种朴素的做法就出现了。

记录原串中长度 \ge l_{\max}-1 的 \texttt{T} 串位置（长度 < l_{\max}-1 的 \texttt T 串不可能成为答案），然后对于每个串，向左遍历 \texttt{TB}，若终止时此时的串为 \texttt{BT}，则答案 \!\text{}+1，右侧同理。

赛时本以为只能过 \sum n\le 5000 的数据，没想到直接过了。

为什么能过呢？考虑证明复杂度。

空间复杂度显然 O(n)。

首先，当 l_{\max}\ge 3，无论如何遍历了多少对于其中一个可能成为答案的 \texttt T 串，总会在 1、n、上一个可能成为答案的 \texttt T 串、下一个可能成为答案的 \texttt T 串、连续的 \texttt{B} 串，这些位置停下来，因为在这些位置总会出现连续的 \texttt{T} 或 \texttt{B} 串导致遍历停止。所以每两个可能成为答案的 \texttt T 串之间的区间最多被遍历 2 次，时间复杂度 O(n)。

当 l_{\max}=2，如果长度为 2 的 \texttt T 串很少，可以卡到 O(n^2)，但是良心出题人没有卡，当然也可以先判长度为 2 的 \texttt T 串是否可以扩展，然后对于长度为 1 的 \texttt T 串，可以做到 O(n)。

当 l_{\max}=1，这种已经被 Subtask 3 判掉了。

代码

常数巨大。

#include<bits/stdc++.h>
using namespace std;
int n,T;
int s[100003];
struct node{
    int l,r;
}t[100003]; int cnt;
signed main(){
    cin>>T;
    while(T--){
        int flag=1; cnt=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            char c;
            cin>>c;
            s[i]=c=='T';
        }
        for(int i=1;i<=n;i++){ // 判断是否存在 BTTB 串
            if(!s[i]&&s[i+1]&&s[i+2]&&!s[i+3]){
                flag=0;
                break;
            }
        }
        int mx=0,lastmx=0,len=0;
        for(int i=1;i<=n;i++){
            if(s[i]) len++;
            else mx=max(mx,len),len=0;
        }
        mx=max(mx,len); len=0; lastmx=mx; // 找最长的 T 串
        if(flag){
            cout<<mx;
        }else{
            for(int i=1;i<=n;i++){ 
                if(s[i]) len++;
                else{
                    if(len>=mx-1) t[++cnt]={i-len,i-1};
                    len=0;
                }
            }
            if(len>=mx-1) t[++cnt]={n-len+1,n};
            len=0; // 找所有长度大于等于 mx-1 的 T 串
            for(int i=1;i<=cnt;i++){
                int l=t[i].l-1,r=t[i].r+1,add=0;
                while(l>1&&!s[l]&&s[l-1]) l-=2; // 遍历找左边的 TB
                if(l>1&&s[l]&&!s[l-1]) add++;   // 找左边是否存在 BT
                while(r<n&&!s[r]&&s[r+1]) r+=2; // 遍历右边的 BT
                if(r<n&&s[r]&&!s[r+1]) add++;   // 找右边是否存在 TB
                mx=max(mx,t[i].r-t[i].l+1+add); // 更新答案
                if(lastmx==mx-2) break;
            }
            cout<<mx;
        }
        cout<<"\n";
    }
    return 0;
} 

Rising sun traxx 里面的欸。