#11167. A. Typical Interview Problem典型的面试问题
A. Typical Interview Problem典型的面试问题
题目:典型的面试问题
每个测试的时间限制: 2 秒 ⏳ 内存限制: 512 兆字节 💾
FB字符串是按如下方式形成的。最初,它是空的。我们从1开始,以升序遍历所有正整数,并对每个整数执行以下操作:
- 如果当前整数可以被3整除,则在FB字符串的末尾附加F;
- 如果当前整数可以被5整除,则在FB字符串的末尾附加B。
请注意,如果一个整数可以同时被3和5整除,我们先附加F,然后附加B,而不是相反的顺序。
FB字符串的前10个字符是FBFFBFFBFB:第一个F来自整数3,下一个字符(B)来自整数5,下一个F来自整数6,依此类推。很容易看出这个字符串是无限长的。设fi是FB字符串的第i个字符;因此,f1是F,f2是B,f3是F,f4是F,以此类推。
给定一个由字符F和/或B组成的字符串s。你必须确定它是否是FB字符串的一个子串(连续子序列)。换句话说,确定是否可以选择两个整数l和r(1≤l≤r),使得字符串flfl+1fl+2…fr正好是s。
例如:
- FFB是FB字符串的一个子串:如果我们选择l=3和r=5,字符串f3f4f5正好是FFB;
- BFFBFFBF是FB字符串的一个子串:如果我们选择l=2和r=9,字符串f2f3f4…f9正好是BFFBFFBF;
- BBB不是FB字符串的一个子串。
输入
第一行包含一个整数t(1≤t≤2046)——测试用例的数量。🌟
每个测试用例包含两行。第一行包含一个整数k(1≤k≤10)——字符串s的字符数。第二行包含字符串s,正好有k个字符。s的每个字符都是F或B。
输出
对于每个测试用例,如果s是FB字符串的一个子串,则打印YES,否则打印NO。
你可以用任意大小写输出。例如,字符串 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。
示例
输入
3
3
FFB
8
BFFBFFBF
3
BBB
输出
YES
YES
NO