问题2751--XZQ与字符串

2751: XZQ与字符串

时间限制: 1 Sec  内存限制: 128 MB
提交: 82  解决: 42
[状态] [讨论版] [提交] [命题人:]
题目描述
XZQ对长度为n的二进制字符串s执行q次查询。二进制字符串是只包含字符“0”和“1”的字符串。,查询由一对整数li,ri(1≤li<ri≤n)来描述。
对于每个查询,XZQ必须确定s中是否存在一个与子串s[li…ri]相等的子序列。
->字符串s的子字符串s[i…j]是由字符si  si+1…  sj组成的字符串。
->如果a可以通过删除一些字符而不改变其余字符的顺序从b获得a,则称字符串a是字符串b的子序列。
->如果子序列不连续且长度≥2,则认为该子序列是好的。例如,如果s为“ 1100110”,则子序列s1 s2 s4(“110”)和s1 s5 s7(“ 110”)很好,而s1 s2 s3(“ 110”)不好 (因为s1 s2 s3是连续的)。
您可以帮助XZQ回答每个查询吗?

输入
输入的第一行包含单个整数t(1≤t≤100)——测试用例的数量。以下是对每种情况的描述。
第一行包含两个整数n(2≤n≤100)和q(1≤q≤100)——字符串的长度和查询数。
第二行包含字符串s。
接下来q行的第i行包含两个整数li和ri(1≤li<ri≤n)。
输出
对于每个测试用例,输出q行。如果存在与子串s[li…ri]相等的良好子序列,则每个测试用例输出的第i行应包含“YES”,否则应包含“NO”。
样例输入 Copy
2
6 3
001000
2 4
1 3
3 5
4 2
1111
1 4
2 3
样例输出 Copy
YES
NO
YES
NO
YES
提示
样例解释:
对于001000:s[2~4]为序列“010”,整个序列存在的“010”的不连续的子序列(良好子序列)有s1s3s4、s1s3s5,s2s3s5,s2s3s6等等,它们都可以组成“010”且不连续,所以符合要求。
但s[1~3]为序列“001”,在整个序列中只有s1s2s3可以组成“001”但s1s2s3连续,所以不合要求。
同样s[3~5]为序列“100”,在整个序列中可以找到s3s4s6和s3s5s6两个不连续的序列,因此符合要求。

对于1111:s[1~4]为序列“1111”,但只能找到s1s2s3s4为序列“1111”, 但s1s2s3s4连续,所以不符合要求。
s[2~3]为序列“11”,所以可以找到不连续的序列s1s3、s1s4、s2s4等等不连续的序列使之成为“11”,所以符合要求。
来源/分类