首页 / 软件开发 / 数据结构与算法 / UVa 10049 Self-describing Sequence：自描述序列&二分递推

UVa 10049 Self-describing Sequence：自描述序列&二分递推2014-10-02 csdn博客 synapse7

10049 - Self-describing Sequence

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=990

Solomon Golomb"s self­describing sequence is the only non­decreasing sequence of positive integers with the property that it contains exactly f（k） occurrences of k for each k. A few moments thought reveals that the sequence must begin as follows:

In this problem you are expected to write a program that calculates the value of f（n） given the value of n.

Input

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n（ ）. The input terminates with a test case containing a value 0 for n and this case must not be processed.

Output

For each test case in the input output the value of f（n） on a separate line.

Sample Input

100999912345610000000000

Sample Output

213561684438744

1. 如何构造一个增长速率较快的递推式？

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45359.htm

注意到f（n）增长缓慢，不妨利用其反函数g（n）=max{m | f（m）=n}（比如g（4）=8），然后再求一次反函数f（n）=min{k | g[k]>=n}即可得到f（n）。

随后由f（n）的定义有g（n）=g（n-1）+f（n）=g（n-1）+min{k | g[k]>=n}

（比如g（4）=g（3）+f（4）=5+3=8，g（5）=g（4）+f（5）=8+3=11）

2. 如何计算min{k | g[k]>=n}？

用二分查找。

完整代码：

/*0.075s*/#include<cstdio>#include<algorithm>const int M = 700000;using namespace std;long long g[M];int main（）{g[1] = 1;g[2] = 3;for （int i = 3; i < M; ++i）g[i] = g[i - 1] + （lower_bound（g + 1, g + i, i） - g）;int n;while （scanf（"%d", &n）, n）printf（"%d
", lower_bound（g + 1, g + M, n） - g）;return 0;}