题意

给一个只有1和2的序列，每次询问有没有一个子串的和为x

( 1≤n,m≤1 000 000 )kkk ( 1≤k≤2 000 000 )

题解

我觉得是道好题。

主要是证明一个性质：假如有一个字串的和为偶(奇）数,那么小于这个偶（奇）数的所有偶（奇）数一定等于这个串的某个字串的和。

我们考虑这个串的边界l，r

假设l==1,r==1那么l++,r--,和可以减2

假设l==2,r==1那么l++，和可以减2；

假设l==1,r==2那么r--，和可以减2；

假设l==2,r==2那么l++或r--和可以减2；

所以我们找到可以用一个串表示的最大偶(奇)数然后一直缩小这个区间就行。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int N=1000100; 8 const int M=2000100; 9 char s[M];10 int n,m,a[N],sum,head,tail,l,r,ll[M],rl[M];11 int main(){12     scanf("%d%d",&n,&m);13     cin>>s; 14     int len=strlen(s);15     for(int i=0;i
          
           =1)tail--;26 tail--;27 l=1;r=n;28 while(l<=r){29 // cout<
           
            <<" "<
            
             <<" "<
             
              <
              
               =1){44 if(head-1