题解 UVA10049 【Self-describing Sequence】

## 题目大意 ### 题目大意 所罗门·戈洛姆的自描述序列 $<f(1),f(2),f(3)\cdots >$ 是唯一一个不减量的正整数序列，它的性质是它正好包含每个 $k$ 的 $f(k)$ 次出现。相信聪明的你会发现序列必须从以下开始： | $ n$ | $f(n)$ | | :-----------: |:-----------: | | $1$ |$1$ | | $2$ |$2$ | | $3$ |$2$ | | $4$ |$3$ | | $5$ |$3$ | | $6$ |$4$ | | $7$ |$4$ | | $8$ |$4$ | | $9$ |$5$ | | $10$ |$5$ | | $11$ |$5$ | | $12$ |$6$ | 在这个问题中，你需要编写一个程序，在给定 $n$ 值的情况下计算 $f(n)$ 的值。  ### 输入格式 **本题共包含多组测试数据** 每个测试用例占用一个单独的行并包含一个整数 $n(1\le n\le 2,000,000,000)$。输入以包含 $n=0$ 的数据终止，并且这种情况不做处理。  ### 输出格式 对于输入的每个数据，输出 $f(n)$ 的值，每个答案占一行。  ## 大体思路 考察自描述序列，由于 $f(n)$ 增长较慢，不妨利用其反函数 $g(n)=\max \left\{m|f(m)=n\right\}$，然后求一次反函数 $f(n)=\min \left\{k|g(k)\ge n\right\}$ 即可得到 $f(n)$。 计算 $\min \left\{k|g(k)\ge n\right\}$ 可用二分查找（STL 自带 `lower_bound` 函数）。 ## 完整代码： ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; const LL N = 2e9;//初始化 vector<LL> a;//动态数组 int main(){ a.push_back(0); a.push_back(1); a.push_back(3);//先打个表 for(LL i = 3, k = 0; k <= N; i++) { k = *(a.end() - 1) + (lower_bound(a.begin(), a.end(), i) - a.begin()); a.push_back(k); }//递推计算 LL n; while(scanf("%lld", &n) != E0F) {//专业防作弊 printf("%lld\n", (LL)(lower_bound(a.begin(), a.end(), n) - a.begin()));//二分查找输出 } return 0; } ``` ## 后记： “自描述序列”在整数数列网中的编号为 [A001462](http://oeis.org/A001462)。 Golomb's sequence: $a(n)$ is the number of times n occurs, starting with $a(1) = 1$. $$1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8,$$ $$9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12,$$ $$12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15,$$ $$15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 19$$