CF1451B Non-Substring Subsequence题解

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:

#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;
}