蓝桥杯2018年第九届真题-自描述序列-题解（C++代码）S

解题思路:

S

第一种思路，就是暴力求解，根据题目给出的规律，很容易用O(n)的时间求出1*10^6的数据，这样就已经获得30%的分数了，再往后就会超时。

第二种思路，g[]数据表示相应的下标出现的次数，那我们可以对g[]数组求和。在求和的过程中判断求出的与目标数据的相比的大小。如果累加的和已经大于目标数据n，则求解的数字就是当前的i,这一部分核心代码如下：

for(int i=1;i<=1000000;i++){

    s+=g[i];

    if(s>=n)

        cout<<i;

}

但是这一种方法需要刚才第一种方法提供的数据，因此计算出的数据范围受第一种是方法范围的影响，只能完成10^9左右的数据。也就是70%的数据。

第三种，因为第i个数据会在g[]数组中出现g[i]次，那么那么就相当于在g[]数组中会出现g[i]段长度为i且这i个数字相等的数字段，这样的话，就可以根据n在那一个数字段中求解。实现代码如下：

for(int i=1;;i++){

s+=i*(LL)g[i];

    if(s>=n){

        .....

    } 

}

如果将n确定在第i个数据段，那么需要将前i-1个数据段包含的数据相加。每个数据段包含g[]数据，则相当对数组g前i-1项求和。

n在第i个数据段中，是第n-m个数字。在第i个段中，每一个数据会重复i次。那么n-m就是在这个段中的位置就是roundup(（n-m）/i)。因为在c++中没有向上取整，但是有个取整公式roundup((n-m)/i)==rounddown((n-m+i-1)/i).核心代码如下：

for(int i=1;;i++){

    s+=i*(LL)g[i];

    if(s>=n){

        s-=i*(LL)g[i];

        cout<<t+(n-s+i-1)/i;

        break;

    } 

    t+=g[i];

}

注意事项:

参考代码:

#include"iostream"

using namespace std;

typedef long long LL;

const int N=1000010; 

int g[N];

int main(){

    g[1]=1,g[2]=2;

    for(int i=2,j=2;i<N;i++){

        for(int k=0;k<g[i]&&j<N;k++)

            g[j++]=i;

    }

    LL s,n,t;

    cin>>n;

    s=t=0;

    for(int i=1;;i++){

        s+=i*(LL)g[i];

        if(s>=n){

             s-=i*(LL)g[i];

             cout<<t+(n-s+i-1)/i;

             break;

        } 

        t+=g[i];

    } 

    return 0;

}