「TAOI-2」Break Through the Barrier

Luogu

IDLGP9574

Time1000ms

Memory512MB

DifficultyP4

模拟贪心洛谷原创O2优化洛谷月赛

有一个由 $\tt B$ 和 $\tt T$ 组成的字符串。你可以进行如下操作：选择一个长度为 $4$ 的子串，其恰好等于 $\texttt{BTTB}$，并将其修改为 $\texttt{TBBT}$。你可以进行这种操作任意多次（也可以不操作）。定义一个字符串的权值为最长的 $\texttt{T}$ 连续段长度。你需要通过如上操作使得字符串的权值尽可能大。输出这个最大值。 + 子串的定义：一个字符串 $b$ 被称为字符串 $a$ 的子串，当且仅当可以通过删除 $a$ 开头若干个（可以是 $0$ 个，下同）字符和结尾若干个字符得到 $b$。 + $\texttt{T}$ 连续段的定义：一个原字符串的仅由 $\texttt{T}$ 构成的子串。 ## Input 第一行一个正整数 $T$ 表示数据组数。接下来每组数据，第一行一个正整数 $n$ 表示字符串长度，第二行一个长度为 $n$ 的字符串 $S$，表示题目中的字符串。 ## Output $T$ 行，每行一个非负整数，表示最长 $\texttt{T}$ 连续段的长度。 [samples] ## Note **本题采用捆绑测试。** 记 $\sum n$ 为所有数据中的 $n$ 的和。 + Subtask 0（5 pts）：$n \leq 7$。 + Subtask 1（20 pts）：$T \leq 10$，$n \leq 10$。 + Subtask 2（25 pts）：$\sum n \leq 5000$。 + Subtask 3（5 pts）：保证给定的字符串无法进行任何操作。 + Subtask 4（45 pts）：无特殊限制。对于所有数据，$1 \leq T \leq 10^3$，$1 \leq n \leq 10^5$，$1 \leq \sum n \leq 5\times 10^5$，字符串只包含字符 `B` 和 `T`。

Samples

Input #1

6
3
TTT
4
BTTB
5
TBBTT
6
BTBTBB
7
BTTBTTB
17
TTBTBTTBTBTTTBTTB

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「TAOI-2」Break Through the Barrier",
    "description": {
      "content": "有一个由 $\\tt B$ 和 $\\tt T$ 组成的字符串。 你可以进行如下操作：选择一个长度为 $4$ 的子串，其恰好等于 $\\texttt{BTTB}$，并将其修改为 $\\texttt{TBBT}$。你可以进行这种操作任意多次（也可以不操作）。 定义一个字符串的权值为最长的 $\\texttt{T}$ 连续段长度。你需要通过如上操作使得字符串的权值尽可能大。输出这个最大值。 + 子串的定义",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9574"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个由 $\\tt B$ 和 $\\tt T$ 组成的字符串。\n\n你可以进行如下操作：选择一个长度为 $4$ 的子串，其恰好等于 $\\texttt{BTTB}$，并将其修改为 $\\texttt{TBBT}$。你可以进行这种操作任意多次（也可以不操作）。\n\n定义一个字符串的权值为最长的 $\\texttt{T}$ 连续段长度。你需要通过如上操作使得字符串的权值尽可能大。输出这个最大值。\n\n+ 子串的定义...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments