题目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;
}