CF1451B Non-Substring Subsequence题解
llzer
2020-11-23 22:24:14
## 题目大意：
给你一个长度为$n$的二进制序列$s$,有$q$次询问，第$i$组询问包含两个数$l_i$和$r_i$，求是否存在一个不同的子序列和子序列$s[l_i,r_i]$相同。
## 分析：
其实这道题目还是很良心的，只要判断在$s[1,l_i-1]$中有一元素与$s[l_i]$相等或在$s[r_i+1,n]$中有一元素与$s[r_i]$相同即可。
## 证明：
我们考虑只改变$l$或$r$，如果无法找到相同的子序列，那就无法找到相同的子序列了，因为首或尾都不一样了。
所以我们只需要寻找是否存在$s[1,l_i-1]$中有一元素与$s[l_i]$相等或在$s[r_i+1,n]$中有一元素与$s[r_i]$相同即可。
一次询问的时间复杂度大概O(n)。
## Code:
```cpp
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);i++)
#define ReFor(i,r,l) for(int i=(r);i>=(l);i--)
const int MAXN=110;
using namespace std;
int n,t,q;
int a[110];
bool flag;
string s;
inline int read()
{
int f=1,x=0;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}//快读
int main()
{
t=read();
For(i,1,t)
{
n=read();
q=read();
cin>>s;
For(j,1,n)
a[j]=s[j-1]-'0';//字符串转数字
For(j,1,q)
{
flag=false;
int x,y;
x=read();
y=read();
For(k,1,x-1)
{
if(a[k]==a[x])
{
flag=true;
break;
}
}
For(k,y+1,n)
{
if(a[k]==a[y])
{
flag=true;
break;
}
}//判断是否满足题意
if(flag==true)
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
```