120min, 5题。本菜鸡怒跪。
- 变身程序员
1 | (读取时可以按行读取,直到读到空行为止,再对读取过的所有行做转换处理) |
此题与rotting-oranges类似。
基本思想就是将所有的程序员入队,BFS所有的产品经理,最后检查是否还有产品经理存在。
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
using namespace std;
struct node {
int x, y;
int time;
node() {}
node(int xx, int yy, int t) :x(xx), y(yy), time(t) {}
};
queue<node> q;
int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };
int main()
{
int grid[10][10];
int row = 0, col = 0;
string str;
/*按行读取输入*/
while (getline(cin, str))
{
col = 0;
for (int i = 0; str[i]; i++)
{
if (str[i] != ' ')
{
grid[row][col++] = str[i] - '0';
}
}
row++;
}
for(int i = 0;i < row;i++)
for (int j = 0; j < col; j++)
{
if (grid[i][j] == 2)
{
//将所有程序员入队
q.push(node(i, j, 0));
}
}
node s;
while (!q.empty())
{
s = q.front();
/*四个方向遍历*/
for (int i = 0; i < 4; i++)
{
int newx = s.x + dir[i][0];
int newy = s.y + dir[i][1];
//没有越界并且找到一枚产品经理
if (newx >= 0 && newx < row && newy >= 0 && newy < col && grid[newx][newy] == 1)
{
grid[newx][newy] = 2;
q.push(node(newx, newy, s.time + 1));
}
}
q.pop();
}
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
{
if (grid[i][j] == 1)
{
printf("-1\n");
return 0;
}
}
printf("%d\n", s.time);
return 0;
}
- 特征提取
1 | 示例: |
可以使用pair存储当前特征,使用map存储当前特征上一次出现的行数以及当前特征连续出现的长度。
还是对C++不熟唉
1 |
|
- 机器人跳跃
1 | 示例1: |
据说是小学数学,还想了半天。 根据题意可推出:\(dp[k + 1] = 2*dp[k] - H[k + 1]\)
1 |
|
- 毕业旅行问题
1
2
3
4
5
6
7
8
9示例:
输入:
4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0
输出:
13
典型的TSP问题,据说动态规划能够得到理论最优解,然而本渣看不懂状态转移方程。
贪心算法:从某城市出发,每次在未到达的城市中选择最近的一个,直到遍历完所有城市,最后回到出发地。
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
using namespace std;
int main()
{
int n, m[20][20], res = 0;
int edge_count = 0, flag[20] = { 1,0 };
int cur = 0, next;
scanf("%d", &n);
for(int i = 0;i < n;i++)
for (int j = 0; j < n; j++)
{
scanf("%d", &m[i][j]);
}
while (edge_count < n)
{
int min = INF;
for (int j = 0; j < n; j++)
{
if (!flag[j] && m[cur][j] && m[cur][j] < min)
{
next = j;
min = m[cur][j];
}
}
res += m[cur][next];
flag[next] = 1;
edge_count++;
cur = next;
}
res += m[cur][0];
return 0;
}
- 过河
1 | 示例: |
每次过河只能2个或3个人,这种过河问题遵循能者多劳原则,即花费时间少的人折返去接其他人。
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
using namespace std;
int a[100010], dp[100010];
int main()
{
int n, N;
scanf("%d", &N);
while (N--)
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
sort(a, a + n);
dp[2] = a[1], dp[3] = a[2];
for (int i = 4; i <= n; i++)
{
//前i个人过河的最短时间
dp[i] = min( dp[i - 1] + a[0] + a[i - 1],dp[i - 2] + a[1] + a[i - 1] );
}
printf("%d\n", dp[n]);
}
return 0;
}