[Offer收割]编程练习赛98

题目1 : 推断上下级

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

H公司包括CEO在内,一共有N名员工,编号1~N,其中CEO的编号是1。除了CEO之外,其他员工都有唯一一名直接上司,形成了一种树形的上下级关系。

现在小Hi知道H公司所有的上下级关系,一共M对。换句话说,只要两名员工A和B之间存在上下级关系(直接或者间接),那么A和B一定在这M对关系之中。

请你帮小Hi推断出每个人的直接上级是谁。

输入

第一行包含两个整数N和M。

以下M行,每行包含两个整数Ai和Bi,代表Ai是Bi的上级。

2 <= N <= 1000

1 <= M <= 499500

输出

输出N行,其中第i行包含一个整数Pi,代表i号员工的上级。(对CEO输出0)

样例输入

3 2 1 2 1 3

样例输出

0 1 1

题解

不能直接套用并查集去解,因为题目要求输出的是每一个员工的直接上级。员工之间的关系是树形关系,不存在回路,使用拓扑排序就可以得到每个员工的直接上级。因为拓扑排序会从这个树形结构的根结点(CEO)开始,当弹出一个节点时,如果相邻节点此时入度为0,则此节点的直接上级就是弹出的节点

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ll long long
const int maxn = 1005;
int in[maxn], fa[maxn];
vector<int> p[maxn];
queue<int> q;
int main(int argc, char const *argv[])
{
int n, m, a, b;
scanf("%d %d", &n, &m);
memset(in, 0, sizeof in);

while (m--) {
scanf("%d %d", &a, &b);
p[a].push_back(b);
in[b]++;
}
q.push(1);
while (!q.empty()) {
int top = q.front();
q.pop();
for (auto it : p[top]) {
in[it]--;
if (in[it] == 0) {
fa[it] = top;
q.push(it);
}
}
}
printf("0\n");
for (int i = 2; i <= n; i++) {
printf("%d\n", fa[i]);
}
return 0;
}


题目2 : 数组划分游戏

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi在玩一个有关数组划分的游戏。给定一个整数K和一个长度为N的数组A=[A1, A2, … AN],小Hi需要将它划分为K个连续子数组,并对每个子数组求和。

不妨设这K个子数组的和依次是S1, S2, … SK,则小Hi的得分是其中的最小值即min(S1, S2, … SK)。

例如对于A=[1, 2, 3, 4]和K=2,小Hi可以划分成[1, 2]和[3, 4],这样得分是3;也可以划分成[1, 2, 3]和[4],这样得分是4。

对于给定的K和数组A,你能帮助小Hi算出他最多能得多少分吗?

输入

第一行包含两个整数N和K。

第二行包含N个整数A1, A2, … AN。

对于60%的数据,1 <= N <= 1000

对于100%的数据,1 <= K <= N <= 100000 1 <= Ai <= 1000000

输出

一个整数代表答案

样例输入

1
2
4 2
1 2 3 4

样例输出

1
4

题解

二分法解决,二分每块区域的最小值是多少。

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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int n, k;
int a[maxn];
ll res = 0;
inline bool ok(int x) {
ll sum = 0, mina = 0x7f7f7f;
int m = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
if (sum >= x) {
mina = min(sum, mina);
sum = 0;
m++;
}
}
if (m >= k) res = max(res, mina);
return m >= k;
}
int main(int argc, char const *argv[])
{
ll sum = 0;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", a+i);
sum += a[i];
}
ll l = 1, r = sum, mid;
while (l <= r) {
mid = (l+r)>>1;
if (ok(mid)) l = mid+1;
else r = mid-1;
}
printf("%lld\n", res);
return 0;
}


题目3 : H市规划

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

H市的平面地图可以看成是一个NxM的方格矩阵,每一个格子代表H市的一个区域。

H市的市长给每一个方格都标记了一个0~2的数字,2代表该区域包含高校,1代表该区域包含创业园,0代表该区域既不包含高校也不包含创业园。(没有区域既包含高校也包含创业园)

现在H市长希望选出一片连续的区域(若干上下左右连在一起的方格)进行特别规划,要求

1)这片区域需要既包含高校也要包含创业园

2)这片区域面积尽量小,即包含方格的数目尽量少

请你帮H市长找出满足条件的一片区域,并且输出其包含方格的数目。

输入

第一行包含两个整数N和M。

以下N行包含一个NxM的矩阵。

1 <= N, M <= 1000

输出

一个整数代表答案

样例输入

1
2
3
4
5
4 5
00100
10002
10000
00020

样例输出

1
4

题解

解法一:

区域包含高校也要包含创业园,而且尽可能小。问题可以转换为求两点的最短路径,使用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
#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ll long long
const int maxn = 1005;
int e[maxn][maxn];
int n, m;
int nxt[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int vis[maxn][maxn];
struct node {
int x, y, step;
node(int _x, int _y, int _step) {
x = _x;
y = _y;
step = _step;
}
};
int bfs(int x, int y) {
memset(vis, 0, sizeof vis);
queue<node> q;
q.push(node(x, y, 0));

while (!q.empty()) {
node top = q.front();
q.pop();

for (int i = 0; i < 4; i++) {
int nx = top.x+nxt[i][0];
int ny = top.y+nxt[i][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) continue;
if (e[nx][ny] == 2) {
return top.step+1;
}
vis[nx][ny] = 1;
q.push(node(nx, ny, top.step+1));
}
}
return 0;
}
int main(int argc, char const *argv[])
{
char str[maxn];
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%s", str);
for (int j = 0; j < m; j++)
e[i][j] = str[j] - '0';
}
int mina = 0x3f3f3f3f;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
if (e[i][j] == 1) {
mina = min(mina, bfs(i, j)+1);
}
}
printf("%d\n", mina);

return 0;
}

解法二:

实际上,没必要写成BFS,因为这条路径一定是一条直线或者说是两条直线,只要求出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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ll long long
const int maxn = 1005;
struct node {
int x, y;
} A[maxn], B[maxn];
int main(int argc, char const *argv[])
{
char str[maxn];
int n, m;
int id, id1;
id = id1 = 0;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%s", str);
for (int j = 0; j < m; j++) {
if (str[j] - '0' == 1) A[id++] = (node)<%i,j%>;
if (str[j] - '0' == 2) B[id1++] = (node)<%i,j%>;
}
}
int mina = 0x3f3f3f3f;
for (int i = 0; i < id; i++)
for (int j = 0; j < id1; j++)
mina = min(mina, abs(A[i].x-B[j].x)+abs(A[i].y-B[j].y)+1);
printf("%d\n", mina);
return 0;
}


题目4 : 占领树节点

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi和小Ho在玩一个双人对弈游戏。

给定一棵树,第一回合先手一方先选择一个树的节点”占领”,后手一方再选择另一个树的节点”占领”。

之后先手和后手依次完成本方回合。每回合行动的一方需要选择一个尚未被任何一方占领,并且与至少一个己方已占领节点相邻(有一条边相连)的节点,将其占领。

如果某回合某一方无节点可占领,则这一方这回合轮空,对方继续进行。

直到双方都无节点可占领,游戏结束。占领节点多的一方获胜,如占领节点数目相同,则为平局。

给定一棵树,小Hi想知道如果自己是先手并且要获胜,第一回合有哪些节点可以选择。

例如对于如下的树,第一回合选择1号节点才有必胜策略,选择2、3号节点都没有必胜策略。

1
2
3
  1
/ \
2 3

输入

第一行包含一个整数N。

以下N行每行包含一个整数Pi,代表i号节点的父节点编号。特别的,根的父节点是0。

1 <= N <= 100000

输出

第一行包含一个整数K,代表可选节点的数目。

第二行包含K个整数,代表可选节点的编号。注意编号应按从小到大的顺序输出。

样例输入

1
2
3
4
3
0
1
1

样例输出

1
2
1
1

题解

这个题关键在于明白规则:

即除了第一个点,其余的点放的时候都要连接到相邻的点, 所以选定第一个点后,就把树分为了三部分,如果后手选的是最大的一部分并且紧挨着先手第一个点,就有可能赢。 因为最大的一部分被后手堵住后, 先手都到不了了。因此问题转换为树上选一个点,这个点相邻的点的最大子树大小(后手可占据的最多点数)是否小于 n减去 最大子树的大小(先手可占据的最少点数),如果满足的话这个点就可选。

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int n;
int su[maxn];
vector<int> g[maxn];
vector<int> res;

void dfs(int u, int v) {
su[u] = 1;
int maxa = 0;
for (int i = 0; i < (int)g[u].size(); i++) {
int e = g[u][i];
if (e == v) continue;
dfs(e, u);
su[u] += su[e];
maxa = max(maxa, su[e]);
}
maxa = max(maxa, n-su[u]);
if (maxa < n-maxa)
res.push_back(u);
}

int main(int argc, char const *argv[])
{
int x;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
if (x) {
g[x].push_back(i);
g[i].push_back(x);
}
}
dfs(1, 0);
sort(res.begin(), res.end());
printf("%d\n", (int)res.size());
for (int i = 0; i < (int)res.size(); i++)
printf("%d\n", res[i]);
return 0;
}
文章作者: Sshpark
文章链接: http://sshpark.com.cn/2019/03/31/Offer收割-编程练习赛98/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Sshpark