P8676 [蓝桥杯 2018 国 A] 自描述序列

· · 题解

感谢 zhanghao 给我的帮助。

题目大意

思路

1 暴力

最多卡到 40 分。

const int N=6e7+5;
a[0]=3,a[1]=1,a[2]=2,a[3]=2;
for(int i=3;i<=N;i++)
    for(int j=1;j<=a[i];j++){
        a[++a[0]]=i;
        if(a[0]==N)
            goto end;
    }

end:cin>>n;
cout<<a[n];

2 优化

用范围来代表每个数的位置。

用二分查找出 G_i 没有其他优化的方案了

struct node{
    int l,r,i;
}G[N];

int find_x(int x){
    int mid=0,l=1,r=x;
    while(l<=r){
        mid=(l+r)/2;

        if((G[mid].l<=x&&G[mid].r>=x)||l==r)
            return G[mid].i;
        if(G[mid].l>x)
            r=mid-1;
        if(G[mid].r<x)
            l=mid+1;
    }
}

for(int i=3;i<=N;i++){  
    G[i].l=l,G[i].r=r,G[i].i=i;
    l=r+1,r=l+find_x(i+1)-1;

    if(G[i].l<=n&&G[i].r>=n){
        cout<<i<<"\n";
        return 0;
    }
}

3 正解

我们不妨扩大代表的范围。

对于每一个 i 都是其他的 i 衍生出的。（除了前 2 项。）

注意：衍生和产生在文中不一样！产生是指 G_n=i 时，n 和 i 的关系。衍生是指 G_{G_n}=i 时，n 和 i 的关系。

所以，我们可以确定 n 与之衍生的 i 和在总数据段中的第几段。

例：

因为 G_{12}=6,G_6=4。

对于 n=12，可以推断它是由 i=4 衍生出的而且它在总数据段中的第 1 位。

推断：

因为数据段有 i 组，所以 n 在总数据段中的位置：

枚举 $i$ 的衍生总数据长度。如果它超过了 $n$，则超出了 $n$ 的总数据段的范围，所以 $n$ 就在 $m-i \times G_i$ 和 $m+i \times G_i$ 之间。 * $m-i \times G_i \le n \le m+i \times G_i

我们已经知道了 n 在总数据段中的位置，衍生出 n 的 i。

则我们只需要求出当 G_x=i 时的 \min(x)-1

因为我们 G_n 是由 x_n 产生的，所以求出 x_n 就行了，所以求出总产生段前一个数再加上 n 在总数据段中的第几段就是答案。

答案为：\min(x)-1 + \lceil (n-m)/i \rceil

g[0]=2,g[1]=1,g[2]=2;
for(int i=2;i<=N;i++)
    for(int j=1;j<=g[i];j++){
        g[g[0]++]=i;
        if(g[0]>=N-1)
            goto end;
    }
end: cin>>n;

int t=0,q=0;
for(int i=1;;i++){
    t+=g[i]*i;
    if(t>=n){
        t-=g[i]*i;//ceil((n-t)*1.0/i) 我也不知道这样写为什么不可以
        cout<<q+(n-t+i-1)/i<<"\n";
        break;
    }
    q+=g[i];
}