Typical Interview Problem

题意翻译

有一个包含 F 和 B 的字符串，最开始是空的。我们开始从 $1$ 向后遍历所有整数，按照下面的规则构成字符串： - 如果该整数能被 $3$ 整除，则在该字符串后加入 F - 如果该整数能被 $5$ 整除，则在该字符串后加入 B 特别的，如果该整数能同时被 $3$ 和 $5$ 整除，则先加入 F 再加入 B。 现在有 $t$ $(1\le t\le2046)$ 次询问，每个给出一个长度为 $k$ $(1\le k \le 10)$ 的字符串 $s$，请回答该字符串是否是上面字符串的子串（需要连续）。（保证给出的字符串仅包含 F 和 B）

题目描述

The FB-string is formed as follows. Initially, it is empty. We go through all positive integers, starting from $ 1 $ , in ascending order, and do the following for each integer: - if the current integer is divisible by $ 3 $ , append F to the end of the FB-string; - if the current integer is divisible by $ 5 $ , append B to the end of the FB-string. Note that if an integer is divisible by both $ 3 $ and $ 5 $ , we append F, and then B, not in the opposite order. The first $ 10 $ characters of the FB-string are FBFFBFFBFB: the first F comes from the integer $ 3 $ , the next character (B) comes from $ 5 $ , the next F comes from the integer $ 6 $ , and so on. It's easy to see that this string is infinitely long. Let $ f_i $ be the $ i $ -th character of FB-string; so, $ f_1 $ is F, $ f_2 $ is B, $ f_3 $ is F, $ f_4 $ is F, and so on. You are given a string $ s $ , consisting of characters F and/or B. You have to determine whether it is a substring (contiguous subsequence) of the FB-string. In other words, determine if it is possible to choose two integers $ l $ and $ r $ ( $ 1 \le l \le r $ ) so that the string $ f_l f_{l+1} f_{l+2} \dots f_r $ is exactly $ s $ . For example: - FFB is a substring of the FB-string: if we pick $ l = 3 $ and $ r = 5 $ , the string $ f_3 f_4 f_5 $ is exactly FFB; - BFFBFFBF is a substring of the FB-string: if we pick $ l = 2 $ and $ r = 9 $ , the string $ f_2 f_3 f_4 \dots f_9 $ is exactly BFFBFFBF; - BBB is not a substring of the FB-string.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 2046 $ ) — the number of test cases. Each test case consists of two lines. The first line contains one integer $ k $ ( $ 1 \le k \le 10 $ ) — the number of characters in $ s $ . The second line contains $ s $ , which is a string of exactly $ k $ characters. Each character of $ s $ is either F or B.

输出格式

For each test case, print YES if $ s $ is a substring of the FB-string, or NO otherwise. You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

输入输出样例

输入样例 #1

3
3
FFB
8
BFFBFFBF
3
BBB

输出样例 #1

YES
YES
NO

**题目大意**：

给定一个按照特定规则生成的字符串，该字符串初始为空，随后遍历所有正整数，对于每个整数：

- 如果该整数能被3整除，则在字符串后添加字符F；
- 如果该整数能被5整除，则在字符串后添加字符B；

如果该整数同时能被3和5整除，则先添加F再添加B。

现在有t个询问，每个询问包含一个长度为k的字符串s，要求判断s是否为上述字符串的子串。

**输入输出数据格式**：

**输入格式**：
- 第一行包含一个整数t（1≤t≤2046），表示测试用例的数量。
- 每个测试用例包含两行，第一行是一个整数k（1≤k≤10），表示字符串s的长度。第二行是字符串s，由恰好k个字符F或B组成。

**输出格式**：
- 对于每个测试用例，如果s是上述字符串的子串，则输出YES，否则输出NO。
- 输出的每个字母大小写不限（YES, yes, Yes都被认为是肯定回答，NO, no, nO都被认为是否定回答）。

**输入输出样例**：

**输入样例 #1**：
```
3
3
FFB
8
BFFBFFBF
3
BBB
```

**输出样例 #1**：
```
YES
YES
NO
```**题目大意**： 给定一个按照特定规则生成的字符串，该字符串初始为空，随后遍历所有正整数，对于每个整数： - 如果该整数能被3整除，则在字符串后添加字符F； - 如果该整数能被5整除，则在字符串后添加字符B； 如果该整数同时能被3和5整除，则先添加F再添加B。 现在有t个询问，每个询问包含一个长度为k的字符串s，要求判断s是否为上述字符串的子串。 **输入输出数据格式**： **输入格式**： - 第一行包含一个整数t（1≤t≤2046），表示测试用例的数量。 - 每个测试用例包含两行，第一行是一个整数k（1≤k≤10），表示字符串s的长度。第二行是字符串s，由恰好k个字符F或B组成。 **输出格式**： - 对于每个测试用例，如果s是上述字符串的子串，则输出YES，否则输出NO。 - 输出的每个字母大小写不限（YES, yes, Yes都被认为是肯定回答，NO, no, nO都被认为是否定回答）。 **输入输出样例**： **输入样例 #1**： ``` 3 3 FFB 8 BFFBFFBF 3 BBB ``` **输出样例 #1**： ``` YES YES NO ```