bzoj3136: [Baltic2013]brunhilda

这个题为什么会放在数据结构啊

首先因为有决策包容性，对于一个n每次必然选择一个n%p最大的p，令n减n%p

设fi表示i变成0的步数的话，同样我们可以知道f是有单调性的

假如fd能转移到fk，首先d一定是某个p的倍数，并且k-d+1<pi才能够转移

对于一个合法的d，它能够影响的长度就是pp，其中pp|d并且在给出的质数中是最大的，设它为s(d)

由于f有单调性，并且决策点影响的是由它开始往后的一段，那么决策也有单调性，假如我们知道了这个就可以O(n)指针扫决策点更新了

考虑如何求s

我们可以线性筛一次数，并把每个数被那个点标记记录下来，记为gi

先把每个给出的质数标记为自己，那么s(i)=max(s(i/gi),s(gi)) 好妙啊！

gb卡我空间

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=1e5+;

const int maxp=1e7+;

int n,p[maxn];            int m,q[maxn];

int f[maxp],s[maxp];

int pr,g[maxp];bool v[maxp];

void dddd(int mx)

{

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

    {

        if(v[i]==false)

        {

            f[++pr]=i;

            g[i]=i;

        }

        for(int j=;j<=pr&&i*f[j]<=mx;j++)

        {

            v[i*f[j]]=true;

            g[i*f[j]]=f[j];

            if(i%f[j]==)break;

        }

    }

}

int main()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    scanf("%d%d",&n,&m);

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

        scanf("%d",&p[i]),s[]=max(s[],p[i]);

    int mx=;

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

        scanf("%d",&q[i]),mx=max(mx,q[i]);

    //.....read......

    dddd(mx);

    s[]=-;

    for(int i=;i<=n;i++)s[p[i]]=p[i];

    for(int i=;i<=mx;i++)s[i]=max(s[i/g[i]],s[g[i]]);

    //.....gets......

    f[]=;int j=;

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

    {

        while(j<i&&(s[j]==-||f[j]==-||j+s[j]-<i))j++;

        if(j==i)f[i]=-;

        else f[i]=f[j]+;

    }

    //.....getf.....

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

    {

        if(f[q[i]]==-)puts("oo");

        else printf("%d\n",f[q[i]]);

    }

    //.....print.....

    return ;

}

巴特西

bzoj3136: [Baltic2013]brunhilda

最新文章

热门文章