笔试
笔试三道题目，限时 150 分钟。
题目一
题目简述：给出多支股票价格在多天内的趋势，以最大化收益为目标，要求出每天的买卖决策，及最后的收入。
输入：第一行 m，n，k，分别为为天数、股票数、初始金额。
接下来 i 行给出第 i 天、第 j 支股票的价格 w[i,j]。
允许购入非整数支股票。
输出：
第一行，输出最大的收益金额。
接下来每行给出每天的卖、买决策的股票序号，不操作则为 -1。
基本思路：采用贪婪，取每天增长率最高的买入，增长率小于 1 时不操作。
题目二
题目简述：
实现 2048 游戏的基本逻辑，左滑右滑及合并。
2048 游戏的矩阵为 4 * 4，可以进行上、左、下、右的操作。
输入：第一行输入数据组数 t。
接下来输入操作数量 c 及操作 0（上）、1（左）、2（下）、3（右）。
然后给出 2048 游戏当前的矩阵。
输出：经操作后的 2048 矩阵。
基本思路：对 2048 游戏中的合并与移动操作进行模拟，使用双指针算法。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| #include <iostream>
#include <vector>
using namespace std;
const int N = 4;
vector<vector<int>> mat(N, vector<int>(N));
vector<int> seq(N);
void get_seq() {
int j = 0, i = 1;
while (i != N) {
if (seq[i] == 0) {
i++;
}
else if (seq[j] == 0) {
seq[j] = seq[i];
seq[i] = 0;
}
else if (seq[j] == seq[i]) {
seq[j] <<= 1;
seq[i] = 0;
j++;
}
else {
seq[j + 1] = seq[i];
if (j + 1 != i) {
seq[i] = 0;
}
j++, i++;
}
}
}
void move_up() {
for (int j = 0; j < N; j++) {
for (int i = 0; i < N; i++) {
seq[i] = mat[i][j];
}
get_seq();
for (int i = 0; i < N; i++) {
mat[i][j] = seq[i];
}
}
}
void move_left() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
seq[j] = mat[i][j];
}
get_seq();
for (int j = 0; j < N; j++) {
mat[i][j] = seq[j];
}
}
}
void move_down() {
for (int j = 0; j < N; j++) {
for (int i = N - 1; i >= 0; i--) {
seq[N - 1 - i] = mat[i][j];
}
get_seq();
for (int i = N - 1; i >= 0; i--) {
mat[i][j] = seq[N - 1 - i];
}
}
}
void move_right() {
for (int i = 0; i < N; i++) {
for (int j = N - 1; j >= 0; j--) {
seq[N - 1 - j] = mat[i][j];
}
get_seq();
for (int j = N - 1; j >= 0; j--) {
mat[i][j] = seq[N - 1 - j];
}
}
}
void move(int op) {
switch (op) {
case 0:
move_up();
break;
case 1:
move_left();
break;
case 2:
move_down();
break;
case 3:
move_right();
break;
default:
break;
}
}
int main() {
int t, c;
cin >> t;
while (t--) {
cin >> c;
vector<int> ops(c);
for (auto &item : ops) {
cin >> item;
}
for (auto &row : mat) {
for (auto &item : row) {
cin >> item;
}
}
for (auto op : ops) {
move(op);
}
for (auto row : mat) {
for (auto item : row) {
cout << item << " ";
}
cout << endl;
}
}
return 0;
}
|
题目三
题目简述：
am + bn + cx + dy = N, 给出 a，b，c，d 和 N，求满足式子最小字典序的整数 m，n，x 和 y。要求 m, n, x, y <= 2500，若没有整数解，返回 -1。
输入：第一行为输入的 a，b，c，d，N。
输出：整数最小字典序 m，n，x，y。
基本思路：经典的多重背包问题，这里需要求具体方案，且限制字典序，那么需要开辟额外的数组记录方案，且要求靠后的解尽可能的大。
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
50
51
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 4, MAX = 2500;
vector<int> w(N + 1);
int W;
int main() {
int t = 0;
for (int i = 1; i <= N; i++) {
cin >> w[i];
t += w[i] * MAX;
}
cin >> W;
if (t < W) {
cout << "-1" << endl;
return 0;
}
vector<vector<bool>> dp(N + 1, vector<bool>(W + 1, false));
vector<vector<int>> n(N + 1, vector<int>(W + 1, 0));
vector<int> res;
dp[0][0] = true;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= W; j++) {
for (int k = 0; k <= MAX && j >= k * w[i]; k++) {
if (dp[i - 1][j - k * w[i]]) {
dp[i][j] = true;
n[i][j] = k;
}
}
}
}
if (!dp[N][W]) {
cout << "-1" << endl;
}
else {
for (int i = N, j = W; i > 0; i--) {
res.push_back(n[i][j]);
j -= n[i][j] * w[i];
}
reverse(res.begin(), res.end());
for (int i = 0; i < N; i++) {
cout << res[i] << " ";
}
cout << endl;
}
return 0;
}
|
反思
- 分配好做题的时间，这次因为在第二题上调试耗时太久导致没时间做第完三题。
- 题目不要完全不做，可以给出可以通过一些样例的解，拿一点分。
- 实际中的很多题目并不像 LeetCode 中那样直接的给出题目要求，而是需要做一些简单的阅读理解。在平常可以进行简单的文章阅读，增强自己相关的能力。
技术一面
