Luobuyu's Blog

0%

D-自描述序列

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.4k 阅读时长 ≈ 1 分钟
国赛的确比省赛要难，ipad上的code app写代码是不错，但是最近更新一次后经常闪退

D.自描述序列

题目描述：

定义自描述序列为 $ G(n) $ ：

  • 对于任意正整数n，n在整个序列中恰好出现 $ G(n) $ 次。
  • 该序列是不下降的

前几项为

$ n $123456789
$ g(n) $122334445

求第 $ n $ 项

数据范围：
$ 1\le n \le 2\times 10^{15} $

题解：

数据范围非常大，肯定不能直接求。观察 $ G(n) $ 数组，发现 $ G(n) $ 里面的数比较小，而且呈阶梯状，可以考虑使用 $ F(n) $ 表示 $ G(n) $ 中 $ n $ 的最大下标。前几项为

$ n $123456789
$ g(n) $122334445
$ f(n) $13581115192328

然后对 $ F(n) $ 中的直接使用二分查找，找到对应的下标即可。比如 $ g(6) $ ，在 $ F(n) $ 中找大于等于 $ 6 $ 的数的下标，为 $ 4 $ ，可以得到答案。但是经过运算发现根本存不下，数量级增加的有点慢

还可以考虑什么 $ n $ 达到什么数的时候，数据量超过 $ maxn $ 。经过打表发现， $ n $ 在 $ 10^6 $ 内，这样应该可以。使用 last_cnt 表示当前的 $ g(n) $ 的数字总量，last_p 表示当前 $ g(n) $ 数组的最后一个阶梯的数。同时 $ last\_cnt = \sum{i \times g(i)}，last_p = \sum{g(i)} $ 。直接枚举 $ i $ 计算 last_cnt 和 last_p 的值，当超过 $ n $ 的时候，减掉最后一项，此时小于 $ n $ ，判断从 last_p 开始需要几个即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
md,写完还没测呢，code app直接崩了，代码忘保存，直接没了
**/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;
const int N = maxn - 10;
ll n, m, k;
ll g[maxn] = {0, 1, 2};
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%lld", &n);
    int cnt = 2;
    for(int i = 2; i <= N; i++)
    {
        for(int j = 1; j <= g[i] && cnt <= N; j++)
        {
            g[cnt++] = i;         
        }
    }
    ll last_cnt = 0, last_p = 0, ans = 0;
    for(int i = 1; i <= N; i++)
    {
        last_cnt += (ll) i * g[i];
        last_p += g[i];
        if(last_cnt == n)
        {
            ans = last_p;
            break;
        }
        else if(last_cnt > n)
        {
            last_cnt -= (ll) i * g[i];
            last_p -= g[i];
            ans = last_p + (n - last_cnt - 1) / i + 1;
            break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}