题解 UVA10049 【Self-describing Sequence】
Mars_Dingdang
2020-09-13 15:21:07
## 题目大意
### 题目大意
所罗门·戈洛姆的自描述序列 $<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)$ 的值。
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10049/00e6f1a83379aa5c8a35ef0a6d49ca313fa6d7b9.png)
### 输入格式
**本题共包含多组测试数据**
每个测试用例占用一个单独的行并包含一个整数 $n(1\le n\le 2,000,000,000)$。输入以包含 $n=0$ 的数据终止,并且这种情况不做处理。
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10049/25bd3fceb96ed68cdfc3c55845c87fe0fce29dcc.png)
### 输出格式
对于输入的每个数据,输出 $f(n)$ 的值,每个答案占一行。
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10049/b2de7638d356059cf82353ec23ab33f6e11e87bb.png)
## 大体思路
考察自描述序列,由于 $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$$