题解 P6445 【[COCI2010-2011#1] SRETAN】

· · 题解

P6445

Description

定义由 4 和 7 组成的数为幸运数，求第 k 个幸运数。

Solution 1

只有 4 和 7？其实我们可以模拟成二进制数的，即求第 k 个二进制数，只不过 0 是 4，1 是 7。

  1. 将 (k)_{10} 转化为二进制
  2. 如果是 0 输出 4，是 1 输出 7，比如 0100111 就输出 4744777

Code 1

#include <bits/stdc++.h>

using namespace std;

long long j, a[100000];

void erzhi (long long i) {
    while (i) {
            j++;
            a[j] = i % 2;
            i /= 2;
    }
}

void ans (long long k) {
    erzhi(++k);
    for (long long i = j - 1; i >= 1; i--)
        if (a[i] == 0)
            printf("4");
        else
            printf("7");
}

int main () {
    long long k;
    scanf("%lld", &k);
    ans(k);
    return 0;
}

Solution 2

我们也可以直接不用二进制，用一种类似递归的方式来。

比如我们看第 8 个幸运数，447，是第 3 个幸运数加上一个 7，第 3 个幸运数又是第 1 个幸运数加上一个 4，这时候我们就可以发现一个规律，对于第 k 个幸运数，可以通过下面的公式得出（假设第 k 个幸运数是 a_k）

a_k=a_{\left\lfloor\frac{k-1}{2}\right\rfloor}\times 10+d\begin{cases}d=4(k\bmod 2=1)\\d=7(k\bmod 2=0)\end{cases}

初始化 a_1=4,a_2=7。

然后就可以打一份递归的代码了，这里建议用字符串存储。

By Shuchong
2020.8.7