1.10 京东2024校招笔试真题

1.10.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;

}

1.10.2 滚球游戏

【题目描述】

某滚球游戏规则如下：球从入口处（第一层）开始向下滚动，每次可向下滚动一层，直到滚至最下面一层为止。球每次可滚至左下、下方或右下三个方格中的任意一个，每个方格都有一个得分，如下图所示。第1层有1个方格，第2层有3个方格，……，以此类推，第n层有2*n-1个方格。设计一个算法，使得球从入口滚至最下面一层的总得分和最大。

输入描述：

第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