CF1796A Typical Interview Problem

FB-string 的构造方式如下：初始时字符串为空。我们从 $1$ 开始，依次遍历所有正整数，对于每个整数，执行以下操作： - 如果当前整数能被 $3$ 整除，则在 FB-string 末尾添加一个 F； - 如果当前整数能被 $5$ 整除，则在 FB-string 末尾添加一个 B。 注意，如果某个整数同时能被 $3$ 和 $5$ 整除，先添加 F，再添加 B，顺序不能颠倒。 FB-string 的前 $10$ 个字符为 FBFFBFFBFB：第一个 F 来自整数 $3$，下一个字符 B 来自 $5$，下一个 F 来自 $6$，以此类推。显然，这个字符串是无限长的。设 $f_i$ 表示 FB-string 的第 $i$ 个字符；因此，$f_1$ 是 F，$f_2$ 是 B，$f_3$ 是 F，$f_4$ 也是 F，依此类推。 现在给定一个只包含 F 和/或 B 的字符串 $s$，请判断它是否为 FB-string 的一个子串（即是否存在一对整数 $l$ 和 $r$，满足 $1 \le l \le r$，使得 $f_l f_{l+1} f_{l+2} \dots f_r$ 恰好等于 $s$）。 例如： - FFB 是 FB-string 的一个子串：取 $l=3$，$r=5$，则 $f_3 f_4 f_5$ 恰好为 FFB； - BFFBFFBF 是 FB-string 的一个子串：取 $l=2$，$r=9$，则 $f_2 f_3 f_4 \dots f_9$ 恰好为 BFFBFFBF； - BBB 不是 FB-string 的一个子串。

第一行包含一个整数 $t$（$1 \le t \le 2046$），表示测试用例的数量。 每个测试用例包含两行。第一行包含一个整数 $k$（$1 \le k \le 10$），表示字符串 $s$ 的长度。第二行包含一个恰好为 $k$ 个字符的字符串 $s$，每个字符均为 F 或 B。

对于每个测试用例，如果 $s$ 是 FB-string 的一个子串，输出 YES；否则输出 NO。 你可以以任意大小写输出答案（YES、yes、Yes 都视为正解，NO、no、nO 都视为负解）。

由 ChatGPT 4.1 翻译