A40816. 自描述序列
填空题
困难
知识点
题目描述
自描述序列
题目描述
小明在研究一个序列，叫Golomb自描述序列，不妨将其记作{G(n)}。这个序列有2个很有趣的性质:
对于任意正整数n，n在整个序列中恰好出现G(n)次。
这个序列是不下降的。
以下是{G(n)}的前几项：
n 1 2 3 4 5 6 7 8 9 10 11 12 13
G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6
给定一个整数n，你能帮小明算出G(n)的值吗？
输入
一个整数n。
对于30%的数据，1 <= n <= 1000000
对于70%的数据，1 <= n <= 1000000000
对于100%的数据，1 <= n <= 2000000000000000
输出
一个整数G(n)
样例输入
13
样例输出
6
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
参考答案
#include<bits/stdc++.h>
using namespace std;
// n 1 2 3 4 5 6 7 8 9 10 11 12 13
// G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6
const int N=1e6+5;
typedef long long ll;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n; ll g[N]; cin>>n;
g[1]=1, g[2]=2;
for (ll i=2, j=2; i<N; i++)
for (int c=0; c<g[i]&&j<N; c++) {
g[j++]=i;
}
cout << g[n];
return 0;
}
上一题
下一题