hdvsyu's blog

Posted on Edited on In

Some scientists took pictures of thousands of birds in a forest. Assume that all the birds appear in the same picture belong to the same tree. You are supposed to help the scientists to count the maximum number of trees in the forest, and for any pair of birds, tell if they are on the same tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (<= 104) which is the number of pictures. Then N lines follow, each describes a picture in the format: K B1 B2 … BK where K is the number of birds in this picture, and Bi’s are the indices of birds. It is guaranteed that the birds in all the pictures are numbered continuously from 1 to some number that is no more than 104. After the pictures there is a positive number Q (<= 104) which is the number of queries. Then Q lines follow, each contains the indices of two birds.

Output Specification:

For each test case, first output in a line the maximum possible number of trees and the number of birds. Then for each query, print in a line “Yes” if the two birds belong to the same tree, or “No” if not.

Sample Input:

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

Sample Output:

2 10
Yes
No

用并查集来做，然后统计，有几棵树，每棵树有多少只鸟，查询的话直接写个findFather判断相等

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
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX = 10010;
int father[MAX], bird[MAX];

void init() {
    for (int i = 0; i < MAX; i++) {
        father[i] = i;
        bird[i] = 0;
    }
}

int findFather(int f) {
    while (f != father[f]) {
        f = father[f];
    }
    return f;
}

void unionFind(int a, int b) {
    int fa = findFather(a);
    int fb = findFather(b);

    if (fa < fb) {
        father[fb] = fa;
    } else {
        father[fa] = fb;
    }
}

void getRoot() {
    int child[MAX];
    fill(child, child + MAX, 0);
    for (int i = 1; i < MAX; i++) {
        if (bird[i]) {
            child[findFather(i)]++;
        }
    }

    int sum = 0, cnt = 0;
    for (int i = 1; i < MAX; i++) {
        if (child[i] != 0) {
            cnt++;
            sum += child[i];
        }
    }
    printf("%d %d\n", cnt, sum);
}

int main() {
    init();
    int n = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int k = 0, f = 0;
        scanf("%d %d", &k, &f);
        bird[f] = 1;
        for (int j = 1; j < k; j++) {
            int b = 0;
            scanf("%d", &b);
            bird[b] = 1;
            unionFind(f, b);
        }
    }
    getRoot();
    int q = 0;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        if (bird[a] && bird[b]) {
            if (findFather(a) == findFather(b)) {
                printf("Yes\n");
            } else {
                printf("No\n");
            }
        } else {
            printf("No\n");
        }
    }
    return 0;
}

Posted on Edited on In

“Let’s C” is a popular and fun programming contest hosted by the College of Computer Science and Technology, Zhejiang University. Since the idea of the contest is for fun, the award rules are funny as the following: 0. The Champion will receive a “Mystery Award” (such as a BIG collection of students’ research papers…). 1. Those who ranked as a prime number will receive the best award – the Minions (小黄人)! 2. Everyone else will receive chocolates. Given the final ranklist and a sequence of contestant ID’s, you are supposed to tell the corresponding awards.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=10000), the total number of contestants. Then N lines of the ranklist follow, each in order gives a contestant’s ID (a 4-digit number). After the ranklist, there is a positive integer K followed by K query ID’s.

Output Specification:

For each query, print in a line “ID: award” where the award is “Mystery Award”, or “Minion”, or “Chocolate”. If the ID is not in the ranklist, print “Are you kidding?” instead. If the ID has been checked before, print “ID: Checked”.

Sample Input:

6
1111
6666
8888
1234
5555
0001
6
8888
0001
1111
2222
8888
2222

Sample Output:

8888: Minion
0001: Chocolate
1111: Mystery Award
2222: Are you kidding?
8888: Checked
2222: Are you kidding?

根据给出的要查询的ID，得到它的名词，根据名词得到结果

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
#include <cstdio>
#include <algorithm>

using namespace std;

int isPrime(int num) {
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int n = 0;
    scanf("%d", &n);
    int rank[10000];
    fill(rank, rank + 10000, -1);
    for (int i = 1; i <= n; i++) {
        int t = 0;
        scanf("%d", &t);
        rank[t] = i;
    }
    int k = 0;
    scanf("%d", &k);
    int checked[10000];
    fill(checked, checked + 10000, 0);
    for (int i = 0; i < k; i++) {
        int query = 0;
        scanf("%d", &query);

        if (rank[query] == -1) {
            printf("%04d: Are you kidding?\n", query);
        } else {
            if (checked[query] == 1) {
                printf("%04d: Checked\n");
            } else if (rank[query] == 1) {
                printf("%04d: Mystery Award\n", query);
                checked[query] = 1;
            } else {
                if (isPrime(rank[query])) {
                    printf("%04d: Minion\n", query);
                    checked[query] = 1;
                } else {
                    printf("%04d: Chocolate\n", query);
                    checked[query] = 1;
                }
            }
        }

    }
    return 0;
}

Posted on Edited on In

One important factor to identify acute stroke (急性脑卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive integers: M, N, L and T, where M and N are the sizes of each slice (i.e. pixels of a slice are in an M by N matrix, and the maximum resolution is 1286 by 128); L (<=60) is the number of slices of a brain; and T is the integer threshold (i.e. if the volume of a connected core is less than T, then that core must not be counted). Then L slices are given. Each slice is represented by an M by N matrix of 0’s and 1’s, where 1 represents a pixel of stroke, and 0 means normal. Since the thickness of a slice is a constant, we only have to count the number of 1’s to obtain the volume. However, there might be several separated core regions in a brain, and only those with their volumes no less than T are counted. Two pixels are “connected” and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.

Output Specification:

For each case, output in a line the total volume of the stroke core.

Sample Input:

3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0

Sample Output:

26

这里的每个切片是二维的，然后所有的切片是一层一层叠加起来的，也就是变成了三维的图的遍历问题，我一开始用的深度优先搜索，最后两个测试点出现了段错误，应该是递归的层次太多了，后来想了一下可以直接广度优先搜索，然后就AC了

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
#include <cstdio>
#include <queue>

using namespace std;

int acute[60][1286][128], m = 0, n = 0, l = 0;

struct Index {
    int i, j, k;

    Index(int m_i, int m_j, int m_k) {
        i = m_i;
        j = m_j;
        k = m_k;
    }
};

void bfs(int i, int j, int k, int &temp) {
    queue<struct Index> q;
    q.push(Index(i, j, k));
    while (q.size() != 0) {
        struct Index t = q.front();
        q.pop();
        i = t.i;
        j = t.j;
        k = t.k;
        if (k > 0 && acute[i][j][k - 1] == 1) { // left
            temp += 1;
            acute[i][j][k - 1] = 0;
            q.push(Index(i, j, k - 1));
        }

        if (k < n - 1 && acute[i][j][k + 1] == 1) { // right
            temp += 1;
            acute[i][j][k + 1] = 0;
            q.push(Index(i, j, k + 1));
        }

        if (i > 0 && acute[i - 1][j][k] == 1) { // up
            temp += 1;
            acute[i - 1][j][k] = 0;
            q.push(Index(i - 1, j, k));
        }

        if (i < l - 1 && acute[i + 1][j][k] == 1) { // down
            temp += 1;
            acute[i + 1][j][k] = 0;
            q.push(Index(i + 1, j, k));

        }

        if (j > 0 && acute[i][j - 1][k] == 1) { // front
            temp += 1;
            acute[i][j - 1][k] = 0;
            q.push(Index(i, j - 1, k));
        }

        if (j < m - 1 && acute[i][j + 1][k] == 1) { // back
            temp += 1;
            acute[i][j + 1][k] = 0;
            q.push(Index(i, j + 1, k));
        }
    }
}

int main() {
    int t = 0;
    scanf("%d %d %d %d", &m, &n, &l, &t);
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < n; k++) {
                scanf("%d", &acute[i][j][k]);
            }
        }
    }

    int cnt = 0;
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < n; k++) {
                if (acute[i][j][k] == 1) {
                    int temp = 1;
                    acute[i][j][k] = 0;
                    bfs(i, j, k, temp);
                    if (temp >= t) cnt += temp;
                }
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}

Posted on Edited on In

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N-1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print “Error: K components” where K is the number of connected components in the graph.

Sample Input 1:

5
1 2
1 3
1 4
2 5

Sample Output 1:

3
4
5

Sample Input 2:

5
1 3
1 4
2 5
3 4

Sample Output 2:

Error: 2 components

先用深搜判断有几个连通子图，如果不只有一个连通子图，直接输出；如果只有一个连通子图，那么就要求最深的根，最深用对每个节点进行广搜求层次的方法求得

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
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <iterator>

using namespace std;

vector<vector<int> > m;

int *visited, *level;

void dfs(int cur) {
    for (int i = 0; i < m[cur].size(); i++) {
        if (visited[m[cur][i]] == 0) {
            visited[m[cur][i]] = 1;
            dfs(m[cur][i]);
        }
    }
}

int getMax(int n) {
    int maxValue = level[1];
    for (int i = 2; i <= n; i++) {
        if (level[i] > maxValue) {
            maxValue = level[i];
        }
    }
    return maxValue;
}

int bfs(int cur, int n) {
    queue<int> r;
    r.push(cur);
    fill(visited, visited + n + 1, 0);
    fill(level, level + n + 1, 0);
    level[cur] = 1;
    visited[cur] = 1;
    while (r.size() != 0) {
        cur = r.front();
        r.pop();
        for (int i = 0; i < m[cur].size(); i++) {
            int c = m[cur][i];
            if (visited[c] == 0) {
                visited[c] = 1;
                r.push(c);
                level[c] = level[cur] + 1;
            }
        }
    }
    return getMax(n);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    m.resize(n + 1);
    for (int i = 1; i < n; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        m[a].push_back(b);
        m[b].push_back(a);
    }

    int k = 0;
    visited = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            dfs(i);
            k++;
        }
    }

    if (k != 1) printf("Error: %d components\n", k);
    else {
        level = new int[n + 1];
        int maxValue = -1;
        vector<int> ans;
        for (int i = 1; i <= n; i++) {
            int v = bfs(i, n);
            if (v > maxValue) {
                ans.clear();
                ans.push_back(i);
                maxValue = v;
            } else if (v == maxValue) {
                ans.push_back(i);
            }
        }
        for (int i = 0; i < ans.size(); i++) {
            printf("%d\n", ans[i]);
        }
    }
    delete[] level;
    delete[] visited;
    return 0;
}

Posted on Edited on In

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (2 <= N <= 500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format: V1 V2 one-way length time where V1 and V2 are the indices (from 0 to N-1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street. Finally a pair of source and destination is given.

Output Specification:

For each case, first print the shortest path from the source to the destination with distance D in the format: Distance = D: source -> v1 -> … -> destination Then in the next line print the fastest path with total time T: Time = T: source -> w1 -> … -> destination In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique. In case the shortest and the fastest paths are identical, print them in one line in the format: Distance = D; Time = T: source -> u1 -> … -> destination

Sample Input 1:

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5

Sample Output 1:

Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5

Sample Input 2:

7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5

Sample Output 2:

Distance = 3; Time = 4: 3 -> 2 -> 5

用两个Dijkstra就好了，注意如果距离一样，选取时间较短的哪一个；如果时间相等，选取经过的点最少的那个；

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 500;

struct City {
    int dis, time;
} cities[MAX][MAX];

int dis[MAX], collect[MAX], n, disPath[MAX], disTime[MAX], tt[MAX], timePath[MAX], timeUnit[MAX];
vector<int> final_dis_path, final_time_path;

int getIndexForDistance() {
    int index = -1, i = 0;
    for (i = 0; i < n; i++) {
        if (!collect[i]) {
            index = i;
            break;
        }
    }
    for (i += 1; i < n; i++) {
        if (!collect[i] && dis[i] < dis[index]) {
            index = i;
        }
    }
    return index;
}

int getIndexForTime() {
    int index = -1, i = 0;
    for (i = 0; i < n; i++) {
        if (!collect[i]) {
            index = i;
            break;
        }
    }
    for (i += 1; i < n; i++) {
        if (!collect[i] && tt[i] < tt[index]) {
            index = i;
        }
    }
    return index;
}

void dijkstraForTime(int s) {
    fill(tt, tt + MAX, 65536);
    fill(collect, collect + MAX, 0);
    tt[s] = 0;
    timeUnit[s] = 0;

    for (int i = 0; i < n; i++) {
        timePath[i] = i;
    }
    while (true) {
        s = getIndexForTime();
        if (s == -1) break;
        collect[s] = 1;
        for (int i = 0; i < n; i++) {
            if (!collect[i] && cities[s][i].time != 0) {
                if (tt[i] > tt[s] + cities[s][i].time) {
                    tt[i] = tt[s] + cities[s][i].time;
                    timePath[i] = s;
                    timeUnit[i] = timeUnit[s] + 1;
                } else if (tt[i] == tt[s] + cities[s][i].time && timeUnit[i] > timeUnit[s] + 1) {
                    timePath[i] = s;
                    timeUnit[i] = timeUnit[s] + 1;
                }
            }
        }
    }
}

void dijkstraForDistance(int s) {
    fill(dis, dis + MAX, 65536);
    fill(collect, collect + MAX, 0);
    dis[s] = 0;
    disTime[s] = 0;

    for (int i = 0; i < n; i++) {
        disPath[i] = i;
    }
    while (true) {
        s = getIndexForDistance();
        if (s == -1) break;
        collect[s] = 1;
        for (int i = 0; i < n; i++) {
            if (!collect[i] && cities[s][i].dis != 0) {
                if (dis[i] > dis[s] + cities[s][i].dis) {
                    dis[i] = dis[s] + cities[s][i].dis;
                    disPath[i] = s;
                    disTime[i] = disTime[s] + cities[s][i].time;
                } else if (dis[i] == dis[s] + cities[s][i].dis && disTime[i] > disTime[s] + cities[s][i].time) {
                    disPath[i] = s;
                    disTime[i] = disTime[s] + cities[s][i].time;
                }
            }
        }
    }
}

void getDisPath(int s, int e) {
    if (s == e) {
        final_dis_path.push_back(s);
        return;
    }
    getDisPath(s, disPath[e]);
    final_dis_path.push_back(e);
}

void getTimePath(int s, int e) {
    if (s == e) {
        final_time_path.push_back(s);
        return;
    }
    getTimePath(s, timePath[e]);
    final_time_path.push_back(e);
}

void printTimePath() {
    printf("%d", final_time_path[0]);
    for (int i = 1; i < final_time_path.size(); i++) {
        printf(" -> %d", final_time_path[i]);
    }
}

void printDisPath() {
    printf("%d", final_dis_path[0]);
    for (int i = 1; i < final_dis_path.size(); i++) {
        printf(" -> %d", final_dis_path[i]);
    }
}

int main() {
    int m = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int v1 = 0, v2 = 0, oneWay = 1;
        scanf("%d %d %d", &v1, &v2, &oneWay);
        scanf("%d %d", &cities[v1][v2].dis, &cities[v1][v2].time);
        if (!oneWay) {
            cities[v2][v1] = cities[v1][v2];
        }
    }
    int s = 0, e = 0;
    scanf("%d %d", &s, &e);
    dijkstraForDistance(s);
    getDisPath(s, e);
    dijkstraForTime(s);
    getTimePath(s, e);

    if (final_dis_path != final_time_path) {
        printf("Distance = %d: ", dis[e]);
        printDisPath();
        printf("\n");
        printf("Time = %d: ", tt[e]);
        printTimePath();

    } else {
        printf("Distance = %d; Time = %d: ", dis[e], tt[e]);
        printTimePath();
    }
    return 0;
}

Posted on Edited on In

The “travelling salesman problem” asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. (Quoted from “https://en.wikipedia.org/wiki/Travelling_salesman_problem“.) In this problem, you are supposed to find, from a given list of cycles, the one that is the closest to the solution of a travelling salesman problem.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<N≤200), the number of cities, and M, the number of edges in an undirected graph. Then M lines follow, each describes an edge in the format City1 City2 Dist, where the cities are numbered from 1 to N and the distance Dist is positive and is no more than 100. The next line gives a positive integer K which is the number of paths, followed by K lines of paths, each in the format: n C​1​​ C​2​​ … C​n​​ where n is the number of cities in the list, and C​i​​’s are the cities on a path.

Output Specification:

For each path, print in a line Path X: TotalDist (Description) where X is the index (starting from 1) of that path, TotalDistits total distance (if this distance does not exist, output NA instead), and Description is one of the following:

  • TS simple cycle if it is a simple cycle that visits every city;
  • TS cycle if it is a cycle that visits every city, but not a simple cycle;
  • Not a TS cycle if it is NOT a cycle that visits every city.

Finally print in a line Shortest Dist(X) = TotalDist where X is the index of the cycle that is the closest to the solution of a travelling salesman problem, and TotalDist is its total distance. It is guaranteed that such a solution is unique.

Sample Input:

6 10
6 2 1
3 4 1
1 5 1
2 5 1
3 1 8
4 1 6
1 6 1
6 3 1
1 2 1
4 5 1
7
7 5 1 4 3 6 2 5
7 6 1 3 4 5 2 6
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 2 5 4 3 1
7 6 3 2 5 4 1 6

Sample Output:

Path 1: 11 (TS simple cycle)
Path 2: 13 (TS simple cycle)
Path 3: 10 (Not a TS cycle)
Path 4: 8 (TS cycle)
Path 5: 3 (Not a TS cycle)
Path 6: 13 (Not a TS cycle)
Path 7: NA (Not a TS cycle)
Shortest Dist(4) = 8

判断给出的一条路径是否是旅行商回路。 先判断这条路径是否形成了一个环且是否图中每个点都被访问过，如果不满足这两个条件，则它便不是一个旅行商环。 再判断这条路径是否是一个简单旅行商环，即是否图中每个点都仅被访问过一次。 最后输出最短路径和路径编号。

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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int graph[210][210];
const int inf = 99999;

void init_graph() {
    for (int i = 0; i < 210; i++) {
        fill(graph[i], graph[i] + 210, inf);
    }
}

bool is_cycle(int *arr, int m, int n, int &path_dist) {
    int start = arr[0];
    vector<int> cnt(n + 1, 0);
    cnt[arr[0]] += 1;
    for (int i = 1; i < m; i++) {
        cnt[arr[i]] += 1;
        if (graph[arr[i]][start] == inf) {
            path_dist = -1;
            return false;
        } else {
            path_dist += graph[arr[i]][start];
            start = arr[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 0)
            return false;
    }
    return arr[0] == arr[m - 1];
}

bool is_simple_cycle(int *arr, int m, int n) {
    vector<int> cnt(n + 1, 0);
    for (int i = 1; i < m; i++) {
        cnt[arr[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (cnt[i] > 1) return false;
    }
    return true;
}

int main() {
    init_graph();
    int n = 0, m = 0, a = 0, b = 0, dist = 0, k = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &dist);
        graph[a][b] = graph[b][a] = dist;
    }
    scanf("%d", &k);
    map<int, int> short_path;
    for (int i = 0; i < k; i++) {
        scanf("%d", &m);
        int *arr = new int[m];
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[j]);
        }
        int path_dist = 0;
        if (!is_cycle(arr, m, n, path_dist)) {
            if (path_dist == -1) {
                printf("Path %d: NA (Not a TS cycle)\n", i + 1);
            } else {
                printf("Path %d: %d (Not a TS cycle)\n", i + 1, path_dist);
            }
        } else {
            short_path[path_dist] = i + 1;
            if (is_simple_cycle(arr, m, n)) {
                printf("Path %d: %d (TS simple cycle)\n", i + 1, path_dist);
            } else {
                printf("Path %d: %d (TS cycle)\n", i + 1, path_dist);
            }
        }
    }
    printf("Shortest Dist(%d) = %d\n", short_path.begin()->second, short_path.begin()->first);
    return 0;
}

Posted on Edited on In

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants. Given any two nodes in a binary tree, you are supposed to find their LCA.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: M (≤ 1,000), the number of pairs of nodes to be tested; and N (≤ 10,000), the number of keys in the binary tree, respectively. In each of the following two lines, N distinct integers are given as the inorder and preorder traversal sequences of the binary tree, respectively. It is guaranteed that the binary tree can be uniquely determined by the input sequences. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.

Output Specification:

For each given pair of U and V, print in a line LCA of U and V is A. if the LCA is found and A is the key. But if A is one of U and V, print X is an ancestor of Y. where X is A and Y is the other node. If U or V is not found in the binary tree, print in a line ERROR: U is not found. or ERROR: V is not found. or ERROR: U and V are not found..

Sample Input:

6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99

Sample Output:

LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

这个题目把LCA算法和前序+中序转树的算法结合起来考了。 关于LCA算法可以练练LeetCode上面两个关于这个算法的题目：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/ 和 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/ 在PAT的题库里也有LCA和二叉搜索树结合的题目: https://pintia.cn/problem-sets/994805342720868352/problems/994805343727501312 将一棵树抽象为三个结点，分别为根结点和左子树结点以及右子树结点，那么a和b的最近公共祖先有三种状态，即a和b都在左子树结点或者都在右子树结点、a和b分别在左右子树结点、a或者b是当前根结点，对于第一种状态，最近公共祖先就可以在左子树或者右子树进行查找了，这样递归进去又是一颗新的树；对于第二种状态，当前根结点就是a和b的公共祖先；对于第三种状态，a(b)是b(a)的祖先。 代码的主体就是一个前序+中序转后序的算法，只要在每一层判断在中序序列中，当前层的根结点和a与b两个结点的状态（LCA）即可。

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
#include <cstdio>
#include <map>

using namespace std;

map<int, int> pos;

int *in, *pre;

void lca(int inl, int inr, int pre_root, int a, int b) {
    if (inl > inr) return;
    int in_root = pos[pre[pre_root]], a_in_index = pos[a], b_in_index = pos[b];
    if (a_in_index < in_root && b_in_index < in_root) {
        lca(inl, in_root - 1, pre_root + 1, a, b);
    } else if ((a_in_index < in_root && b_in_index > in_root) ||
               (a_in_index > in_root && b_in_index < in_root)) {
        printf("LCA of %d and %d is %d.\n", a, b, in[in_root]);
    } else if (a_in_index > in_root && b_in_index > in_root) {
        lca(in_root + 1, inr, pre_root + 1 + (in_root - inl), a, b);
    } else {
        if (a_in_index == in_root) {
            printf("%d is an ancestor of %d.\n", a, b);
        } else if (b_in_index == in_root) {
            printf("%d is an ancestor of %d.\n", b, a);
        }
    }
}

int main() {
    int m = 0, n = 0, a = 0, b = 0;
    scanf("%d %d", &m, &n);
    in = new int[n + 1];
    pre = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        scanf("%d", &in[i]);
        pos[in[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &pre[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        if (pos[a] == 0 && pos[b] == 0) {
            printf("ERROR: %d and %d are not found.\n", a, b);
        } else if (pos[a] == 0) {
            printf("ERROR: %d is not found.\n", a);
        } else if (pos[b] == 0) {
            printf("ERROR: %d is not found.\n", b);
        } else {
            lca(1, n, 1, a, b);
        }
    }
    return 0;
}

Posted on Edited on In

When shipping goods with containers, we have to be careful not to pack some incompatible goods into the same container, or we might get ourselves in serious trouble. For example, oxidizing agent （氧化剂） must not be packed with flammable liquid （易燃液体）, or it can cause explosion. Now you are given a long list of incompatible goods, and several lists of goods to be shipped. You are supposed to tell if all the goods in a list can be packed into the same container.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: N (≤10​4​​), the number of pairs of incompatible goods, and M (≤100), the number of lists of goods to be shipped. Then two blocks follow. The first block contains N pairs of incompatible goods, each pair occupies a line; and the second one contains M lists of goods to be shipped, each list occupies a line in the following format:

K G[1] G[2] … G[K]

where K (≤1,000) is the number of goods and G[i]‘s are the IDs of the goods. To make it simple, each good is represented by a 5-digit ID number. All the numbers in a line are separated by spaces.

Output Specification:

For each shipping list, print in a line Yes if there are no incompatible goods in the list, or No if not.

Sample Input:

6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333

Sample Output:

No
Yes
Yes

 对每一号物体，使用set存储与它不相容的物体，这样子在判断一堆物品是否相容的时候使用两层for循环遍历查找对于每一号物体它的不相容物体是否在这堆物品中。

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
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

bool is_cluster(vector<set<int>> v, int g[], int k) {
    for (int i = 0; i < k; i++) {
        for (int j = i + 1; j < k; j++) {
            if (i != j && v[g[i]].find(g[j]) != v[g[i]].end())
                return false;
        }
    }
    return true;
}

int main() {
    vector<set<int>> v(100010);
    int n = 0, m = 0, a = 0, b = 0, k = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a, &b);
        v[a].insert(b);
        v[b].insert(a);
    }
    int g[1010];
    for (int i = 0; i < m; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &g[j]);
        }
        printf("%s\n", is_cluster(v, g, k) ? "Yes" : "No");
    }
    return 0;
}

Posted on Edited on In

Werewolf（狼人杀） is a game in which the players are partitioned into two parties: the werewolves and the human beings. Suppose that in a game,

  • player #1 said: “Player #2 is a werewolf.”;
  • player #2 said: “Player #3 is a human.”;
  • player #3 said: “Player #4 is a werewolf.”;
  • player #4 said: “Player #5 is a human.”; and
  • player #5 said: “Player #4 is a human.”.

Given that there were 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liers. Can you point out the werewolves? Now you are asked to solve a harder version of this problem: given that there were N players, with 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liers. You are supposed to point out the werewolves.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (5≤N≤100). Then N lines follow and the i-th line gives the statement of the i-th player (1≤i≤N), which is represented by the index of the player with a positive sign for a human and a negative sign for a werewolf.

Output Specification:

If a solution exists, print in a line in ascending order the indices of the two werewolves. The numbers must be separated by exactly one space with no extra spaces at the beginning or the end of the line. If there are more than one solution, you must output the smallest solution sequence – that is, for two sequences A=a[1],…,a[M] and B=b[1],…,b[M], if there exists 0≤k<M such that a[i]=b[i] (i≤k) and a[k+1]<b[k+1], then A is said to be smaller than B. In case there is no solution, simply print No Solution.

Sample Input 1:

5
-2
+3
-4
+5
+4

Sample Output 1:

1 4

Sample Input 2:

6
+6
+3
+1
-5
-2
+4

Sample Output 2 (the solution is not unique):

1 5

Sample Input 3:

5
-2
-3
-4
-5
-1

Sample Output 3:

No Solution

首先指定n个人中有两个狼人，用sign数组表示每一号玩家的状态（人用1表示或者狼人用-1表示），然后for循环遍历所有玩家，寻找说谎的玩家，即如果sign数组中指定的某个玩家的状态和当前玩家说的某个玩家的状态不一致，则当前玩家在说谎。最后判断说谎的人数是否等于2，并且这两个说谎的玩家里面，是否一个是人一个是狼人。

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 <cstdio>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) { // two wolfware
            vector<int> sign(n + 1, 1), lier;
            sign[i] = sign[j] = -1;
            for (int k = 1; k <= n; k++) {
                if (sign[abs(v[k])] * v[k] < 0) { // sb lie
                    lier.push_back(k);
                }
            }
            if (lier.size() == 2 && sign[lier[0]] * sign[lier[1]] < 0) {
                printf("%d %d\n", i, j);
                return 0;
            }
        }
    }
    printf("No Solution\n");
    return 0;
}

Posted on Edited on In

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？ 本题是这个问题的升级版：已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？

输入格式：

输入在第一行中给出一个正整数 N（5≤N≤100）。随后 N 行，第 i 行给出第 i 号玩家说的话（1≤i≤N），即一个玩家编号，用正号表示好人，负号表示狼人。

输出格式：

如果有解，在一行中按递增顺序输出 2 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 A=a[1],…,a[M] 和 B=b[1],…,b[M]，若存在 0≤k<M 使得 a[i]=b[i] （i≤k），且 a[k+1]<b[k+1]，则称序列 A 小于序列 B。若无解则输出 No Solution。

输入样例 1：

5
-2
+3
-4
+5
+4

输出样例 1：

1 4

输入样例 2：

6
+6
+3
+1
-5
-2
+4

输出样例 2（解不唯一）：

1 5

输入样例 3：

5
-2
-3
-4
-5
-1

输出样例 3：

No Solution

首先指定n个人中有两个狼人，用sign数组表示每一号玩家的状态（人用1表示或者狼人用-1表示），然后for循环遍历所有玩家，寻找说谎的玩家，即如果sign数组中指定的某个玩家的状态和当前玩家说的某个玩家的状态不一致，则当前玩家在说谎。最后判断说谎的人数是否等于2，并且这两个说谎的玩家里面，是否一个是人一个是狼人。

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 <cstdio>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) { // two wolfware
            vector<int> sign(n + 1, 1), lier;
            sign[i] = sign[j] = -1;
            for (int k = 1; k <= n; k++) {
                if (sign[abs(v[k])] * v[k] < 0) { // sb lie
                    lier.push_back(k);
                }
            }
            if (lier.size() == 2 && sign[lier[0]] * sign[lier[1]] < 0) {
                printf("%d %d\n", i, j);
                return 0;
            }
        }
    }
    printf("No Solution\n");
    return 0;
}
0%