首页 > 代码库 > codeforces 359D 二分答案+RMQ

codeforces 359D 二分答案+RMQ

2024-07-25 21:14:02   219人阅读

上学期刷过裸的RMQ模板题，不过那时候一直不理解>_<

其实RMQ很简单:

设f[i][j]表示从i开始的，长度为2^j的一段元素中的最小值or最大值

那么f[i][j]=min/max{d[i][j-1], d[i+2^j-1][j-1]}

RMQ的ST算法：

 1 void ST()        //初始化 2 { 3     memset(RMQ,1,sizeof(RMQ)); 4  5     for(int i=1;i<=n;i++) 6         RMQ[i][0]=a[i]; 7     for(int j=1;(1<<j)<=n;j++) 8         for(int i=1;i+(1<<j)-1<=n;i++) 9         RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<(j-1))][j-1]);10 }11 12 int Query(int L,int R)    //求a[L..R]区间的最值13 {14     int k=0;15     while((1<<(k+1))<=R-L+1) k++;16     int tb=gcd(GCD[L][k],GCD[R-(1<<k)+1][k]);17     return tb;18 }

 

-----------------------------------------------

再回到这道题。要求输出r-l的最大值

可以使用二分答案。

注意：r-l的值可以为0（即r==l），可以这样写：

1         l=0;    r=n;2         while (r>=l)3         {4             int mid=(l+r)/2;    //mid: r-l5             if (calc(mid))        //calc(mid): 判断mid答案是否符合要求6                 l=mid+1;7             else8                 r=mid-1;9         }

记得原来还刷过求最小值的二分答案（NOIP2010提高组  关押罪犯），是这样的：

 1 //当年的代码略屎= = 2  3 sol:=false; 4 l:=0;   r:=mx; 5 while l<r do 6  begin 7  mid:=(l+r) div 2; 8  ok:=process(mid); 9  if ok then10   begin11   sol:=true;12   r:=mid;13   end14  else15   begin16   l:=mid+1;17   sol:=true;18   end;19  end;

----------------------------------------

如何求区间所有元素的gcd？

不难想出，其实gcd和min(求区间最小值)有个一样的性质：

设在区间[l..r]中，[l..k]的gcd为m，[k+1..r]的gcd为n，

则整个区间[l..r]的gcd等于gcd(m,n)

 

有了这个性质，就可以用ST算法求gcd了。

 

-------------------------------------------

借用了neopenx大神的RMQ模板，Orz

  1 #include <iostream>  2 #include <vector>  3 #include <cstring>  4 using namespace std;  5   6 vector<int> ans;  7 int RMQ[301000][20],GCD[301000][20];  8 int T,n,l,r,mx,num;  9 int a[301000]; 10  11 int gcd(int x,int y) 12 { 13     return (y==0)?x:gcd(y,x%y); 14 } 15  16 void ST() 17 { 18     memset(RMQ,1,sizeof(RMQ)); 19     memset(GCD,1,sizeof(GCD)); 20  21     for(int i=1;i<=n;i++) 22         RMQ[i][0]=GCD[i][0]=a[i]; 23     for(int j=1;(1<<j)<=n;j++) 24         for(int i=1;i+(1<<j)-1<=n;i++) 25     { 26         RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<(j-1))][j-1]); 27         GCD[i][j]=gcd(GCD[i][j-1],GCD[i+(1<<(j-1))][j-1]); 28     } 29 } 30  31 bool Query(int L,int R) 32 { 33     if (L==R) return true; 34     int k=0; 35     while((1<<(k+1))<=R-L+1) k++; 36     int ta=min(RMQ[L][k],RMQ[R-(1<<k)+1][k]); 37     int tb=gcd(GCD[L][k],GCD[R-(1<<k)+1][k]); 38     if (ta==tb)   return true; 39         else return false; 40 } 41  42  43 bool calc(int x)        //x: r-l 44 { 45     bool res=false; 46     for (int i=1;i<=n-x;i++) 47     { 48         bool ok=Query(i,i+x); 49         if (ok) 50         { 51             res=true; 52             //cout<<"----"<<i<<" "<<i+x<<" "<<x<<endl;  //record the answer,use vector 53             if (x==mx) 54             { 55                 num++; 56                 ans.push_back(i); 57             } 58             else if (x>mx) 59             { 60                 num=1; 61                 mx=x; 62                 ans.clear(); 63                 ans.push_back(i); 64             } 65         } 66     } 67     return res; 68 } 69  70 int main() 71 { 72         mx=-1; 73         num=0; 74         ans.clear(); 75         cin>>n; 76         for (int i=1;i<=n;i++) 77             cin>>a[i]; 78  79         ST(); 80  81         l=0;    r=n; 82         while (r>=l) 83         { 84             int mid=(l+r)/2;    //mid: r-l 85             if (calc(mid)) 86                 l=mid+1; 87             else 88                 r=mid-1; 89         } 90         cout<<num<<" "<<mx<<endl; 91             vector<int>::iterator ii; 92             for (ii=ans.begin();ii!=ans.end();ii++) 93                 cout<<*ii<<" "; 94         cout<<endl; 95  96     return 0; 97 } 98  99 100 /*101 注意特殊情况：102 5103 2 3 5 7 11104 计算时应把r-l=0也考虑进去105 (r==l)106 */
View Code

 

codeforces 359D 二分答案+RMQ


联系
我们