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

时间：2021-09-19 05:53:41

题目链接: 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 20

template <class T>

inline bool read(T &ret)

{

    char c;

    int sgn;

    if(c=getchar(),c==EOF) return ; //EOF

    while(c!='-'&&(c<''||c>'')) c=getchar();

    sgn=(c=='-')?-:;

    ret=(c=='-')?:(c-'');

    while(c=getchar(),c>=''&&c<='') ret=ret*+(c-'');

    ret*=sgn;

    return ;

}

int gcd(int a,int b) {if(b!=) 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=;i<=n;i++) RMQ[i][]=GCD[i][]=val[i];

    for(int j=;(<<j)<=n;j++)

        for(int i=;i+(<<j)-<=n;i++)

    {

        RMQ[i][j]=min(RMQ[i][j-],RMQ[i+(<<(j-))][j-]);

        GCD[i][j]=gcd(GCD[i][j-],GCD[i+(<<(j-))][j-]);

    }

}

bool Query(int L,int R)

{

    int k=;

    while((<<(k+))<=R-L+) k++;

    int a=min(RMQ[L][k],RMQ[R-(<<k)+][k]);

    int b=gcd(GCD[L][k],GCD[R-(<<k)+][k]);

    if(a==b) return true;

    else return false;

}

bool judge(int v) //枚举r-l

{

    int cc=;

    vector<int> tt;

    for(int i=; v+i<=n; i++)

    {

        if(Query(i,i+v)) //L=i,R=i+v;

        {

            cc++;

            tt.push_back(i);

        }

    }

    if(cc>)

    {

        ans=tt;

        cnt=cc;

        range=v;

        return true;

    }

    return false;

}

int main()

{

    memset(RMQ,,sizeof(RMQ));

    memset(GCD,,sizeof(GCD));

    read(n);

    for(int i=; i<=n; i++)

        read(val[i]);

    ST();

    int l=,r=n-,mid;

    while(l<=r)  //二分

    {

        mid=(l+r)>>;

        if(judge(mid)) l=mid+;

        else r=mid-;

    }

    printf("%d %d\n",cnt,range);

    for(int i=;i<ans.size();i++) {if(i>) printf(" ");printf("%d",ans[i]);};

    printf("\n");

}
2808371 neopenx CodeForces 359D Accepted 51924 KB 358 ms GNU C++ 4.6 1981 B 2014-10-03 15:00:32

相关文章