京东2021校招笔试真题

1、第n个数

【题目描述】

自从学了素数以后，小明喜欢上了数字2、3和5。当然，如果一个数字里面只出现2、3和5这三个数字，他也一样喜欢，例如222、2355、223355。

现在他希望你能够帮他编写一个程序，快速计算出由2、3、5这三个数字组成的由小到大的第n个数，当然也包括2、3和5。

输入描述：

单组输入。

每组输入数据占1行，每行输入一个正整数n。（n<=1000

输出描述：

每组输出数据占1行，即满足要求的第n个数。

输入样例：

3

输出样例：

5

【解题思路】
按位深搜枚举，然后对深搜数量进行计数，到第n个截止。

【参考代码】
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e3 + 5;
int ans[maxn], a[] = {0, 2, 3, 5};
int t = 0, cnt;
void dfs(int i, int num) {
    if (t > 1000)
        return;
    if (i == cnt + 1) {
        ans[++t] = num;
        return;
    }
    for (int j = 1; j <= 3; j++) {
        dfs(i + 1, num * 10 + a[j]);
    }
}
int main() {
    cnt = 1;
    while (t <= 1000) {
        dfs(1, 0);
        cnt++;
    }
    int n;
    scanf("%d", &n);
    printf("%d\n", ans[n]);
    return 0;
}

2、滚球游戏

【题目描述】

输入描述：

第1行的正整数n表示数字三角形的层数。（n<=100)

接下来n行包含一个数字三角形，每一行包含2*n-1个方格，对应有2*n-1个表示得分的正整数（不超过10^5），每两个数字之间用空格隔开。

输出描述：

球从入口（第一层）滚至最下面一层的最大得分和。

输入样例：

3

    1

  2 1 2

3 4 2 1 3

输出样例：

7

【解题思路】
动态规划。经典数塔问题变种。

【参考代码】
#include <bits/stdc++.h>

using namespace std;
int n;
int a[201][201];
int b[201][201];
void solve() {
    for (int j = 1; j <= 2 * n - 1; j++)
        b[n][j] = a[n][j];