首页 > 代码库 > CodeForces 359D (数论+二分+ST算法）

CodeForces 359D (数论+二分+ST算法）

2024-07-25 11:18:54   218人阅读

题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=47319

题目大意：给定一个序列，要求确定一个子序列，①使得该子序列中所有值都能被其中一个值整除，②且子序列范围尽可能大（r-l尽可能大）。

解题思路：

对于要求1，不难发现只有min(L,R)=gcd(L,R)时才行。其中gcd是L,R范围内的最大公约数，min是L，R范围内的最小值。

对于要求2，传统思路是r-l从大到小枚举，每次确定一个（L,R）范围，进行判断，直到可行。复杂度O(n^2)铁定TLE。

由于r-l的值是有序的，固采用二分。先枚举r-l的中间值，如果符合要求，则向右考虑，看看有没有更大的。否则向左。

当然这题的难度不止于此，尽管采用二分，但是光是枚举复杂度就有O(nlogn)了，再加上查询orz。

最初我使用的是线段树完成RMQ、以及GCD的Query , 复杂度O(n*logn*logn), CF跑到Test10就TLE了。

看了题解才发现要使用ST算法在O(1)的时间内完成RMQ和GCD。也是第一次碰到ST算法，看见刘汝佳的炒鸡简洁ST，给跪了。

 

#include "cstdio"#include "iostream"#include "vector"#include "algorithm"#include "math.h"#include "cstring"using namespace std;#define lson l,mid,root<<1#define rson mid+1,r,root<<1|1#define maxn 3*100005#define maxp 20template <class T>inline bool read(T &ret){    char c;    int sgn;    if(c=getchar(),c==EOF) return 0; //EOF    while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar();    sgn=(c==‘-‘)?-1:1;    ret=(c==‘-‘)?0:(c-‘0‘);    while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘);    ret*=sgn;    return 1;}int gcd(int a,int b) {if(b!=0) return gcd(b,a%b);else return a;}int RMQ[maxn][maxp],GCD[maxn][maxp],val[maxn],n,cnt,range;vector<int> ans;void ST(){    for(int i=1;i<=n;i++) RMQ[i][0]=GCD[i][0]=val[i];    for(int j=1;(1<<j)<=n;j++)        for(int i=1;i+(1<<j)-1<=n;i++)    {        RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<(j-1))][j-1]);        GCD[i][j]=gcd(GCD[i][j-1],GCD[i+(1<<(j-1))][j-1]);    }}bool Query(int L,int R){    int k=0;    while((1<<(k+1))<=R-L+1) k++;    int a=min(RMQ[L][k],RMQ[R-(1<<k)+1][k]);    int b=gcd(GCD[L][k],GCD[R-(1<<k)+1][k]);    if(a==b) return true;    else return false;}bool judge(int v) //枚举r-l{    int cc=0;    vector<int> tt;    for(int i=1; v+i<=n; i++)    {        if(Query(i,i+v)) //L=i,R=i+v;        {            cc++;            tt.push_back(i);        }    }    if(cc>0)    {        ans=tt;        cnt=cc;        range=v;        return true;    }    return false;}int main(){    memset(RMQ,1,sizeof(RMQ));    memset(GCD,1,sizeof(GCD));    read(n);    for(int i=1; i<=n; i++)        read(val[i]);    ST();    int l=0,r=n-1,mid;    while(l<=r)  //二分    {        mid=(l+r)>>1;        if(judge(mid)) l=mid+1;        else r=mid-1;    }    printf("%d %d\n",cnt,range);    for(int i=0;i<ans.size();i++) {if(i>0) printf(" ");printf("%d",ans[i]);};    printf("\n");}

 

2808336

neopenx

CodeForces 359D

Accepted

51924 KB

327 ms

GNU C++ 4.6

1976 B

2014-10-03 14:55:49

 

 

   

 

CodeForces 359D (数论+二分+ST算法）


联系
我们