hdvsyu's blog

本题目给出的射击比赛的规则非常简单，谁打的弹洞距离靶心最近，谁就是冠军；谁差得最远，谁就是菜鸟。本题给出一系列弹洞的平面坐标(x,y)，请你编写程序找出冠军和菜鸟。我们假设靶心在原点(0,0)。

输入格式：

输入在第一行中给出一个正整数 N（≤ 10 000）。随后 N 行，每行按下列格式给出：

ID x y

其中 ID 是运动员的编号（由 4 位数字组成）；x 和 y 是其打出的弹洞的平面坐标(x,y)，均为整数，且 0 ≤ |x|, |y| ≤ 100。题目保证每个运动员的编号不重复，且每人只打 1 枪。

输出格式：

输出冠军和菜鸟的编号，中间空 1 格。题目保证他们是唯一的。

输入样例：

3
0001 5 7
1020 -1 3
0233 0 -1

输出样例：

0233 0001

使用一个结构存储运行打靶信息（运动员ID和距离原点距离的平方），使用sort函数从小到大排序后，第一个运动员就是菜鸟，最后一个运动员就是冠军。

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

#include <cstdio>
#include <algorithm>

struct athlete {
    int id, dist;

    athlete() {}
    athlete(int _id, int _dist) : id(_id), dist(_dist) {};
};

bool cmp(athlete a, athlete b) {
    return a.dist < b.dist;
}

int main() {
    int n = 0, id = 0, x = 0, y = 0;
    scanf("%d", &n);
    athlete athletes[10010];
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &id, &x, &y);
        athletes[i] = athlete(id, x * x + y * y);
    }
    std::sort(athletes, athletes + n, cmp);
    printf("%04d %04d", athletes[0].id, athletes[n - 1].id);
    return 0;
}

本题要求你帮助某网站的用户注册模块写一个密码合法性检查的小功能。该网站要求用户设置的密码必须由不少于6个字符组成，并且只能有英文字母、数字和小数点 .，还必须既有字母也有数字。

输入格式：

输入第一行给出一个正整数 N（≤ 100），随后 N 行，每行给出一个用户设置的密码，为不超过 80 个字符的非空字符串，以回车结束。

输出格式：

对每个用户的密码，在一行中输出系统反馈信息，分以下5种：

• 如果密码合法，输出Your password is wan mei.；
• 如果密码太短，不论合法与否，都输出Your password is tai duan le.；
• 如果密码长度合法，但存在不合法字符，则输出Your password is tai luan le.；
• 如果密码长度合法，但只有字母没有数字，则输出Your password needs shu zi.；
• 如果密码长度合法，但只有数字没有字母，则输出Your password needs zi mu.。

输入样例：

5
123s
zheshi.wodepw
1234.5678
WanMei23333
pass*word.6

输出样例：

Your password is tai duan le.
Your password needs shu zi.
Your password needs zi mu.
Your password is wan mei.
Your password is tai luan le.

题目没有说输入的字符串是否包含空格，所以要用字符串进行处理。对于数字、字母可以使用isdigit和isalpha进行判断。

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

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

bool contain_number(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) return true;
    }
    return false;
}

bool contain_alpha(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i])) return true;
    }
    return false;
}

bool contain_other_character(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (!isalpha(s[i]) && !isdigit(s[i]) && s[i] != '.') return true;
    }
    return false;
}

int main() {
    int n = 0;
    scanf("%d", &n);
    getchar();
    for (int i = 0; i < n; i++) {
        string s;
        getline(cin, s);
        if (s.size() < 6) {
            printf("Your password is tai duan le.\n");
        } else {
            if (!contain_number(s)) {
                printf("Your password needs shu zi.\n");
            } else if (!contain_alpha(s)) {
                printf("Your password needs zi mu.\n");
            } else if (contain_other_character(s)) {
                printf("Your password is tai luan le.\n");
            } else {
                printf("Your password is wan mei.\n");
            }
        }
    }
    return 0;
}

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table first. Then try to find another sequence of integer keys from the table and output the average search time (the number of comparisons made to find whether or not the key is in the table). The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions. Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 positive numbers: MSize, N, and M, which are the user-defined table size, the number of input numbers, and the number of keys to be found, respectively. All the three numbers are no more than 104​. Then N distinct positive integers are given in the next line, followed by M positive integer keys in the next line. All the numbers in a line are separated by a space and are no more than 105​.

Output Specification:

For each test case, in case it is impossible to insert some number, print in a line X cannot be inserted. where X is the input number. Finally print in a line the average search time for all the M keys, accurate up to 1 decimal place.

Sample Input:

4 5 4
10 6 4 15 11
11 4 15 2

Sample Output:

15 cannot be inserted.
2.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

#include <cstdio>

bool is_primer(int m_size) {
    for (int j = 2; j * j <= m_size; j++) {
        if (m_size % j == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int m_size = 0, n = 0, m = 0, num = 0, cnt = 0;;
    scanf("%d %d %d", &m_size, &n, &m);
    while (!is_primer(m_size)) {
        m_size++;
    }
    int *hash = new int[m_size];
    for (int i = 0; i < m_size; i++) hash[i] = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        int flag = 1;
        for (int j = 0; j < m_size; j++) {
            if (hash[(num + j * j) % m_size] == 0) {
                hash[(num + j * j) % m_size] = num;
                flag = 0;
                break;
            }
        }
        if (flag == 1) {
            printf("%d cannot be inserted.\n", num);
        }
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &num);
        for (int j = 0; j <= m_size; j++) {
            cnt++;
            if (hash[(num + j * j) % m_size] == num || hash[(num + j * j) % m_size] == 0) {
                break;
            }
        }
    }
    printf("%.1f", cnt * 1.0 / m);
    delete[] hash;
    return 0;
}

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 1,000), the number of vertices in the graph, and M (≤ 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (≤ 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.

Output Specification:

Print in a line all the indices of queries which correspond to “NOT a topological order”. The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.

Sample Input:

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

Sample Output:

3 4

题意：给出一个有向图，再给出一个所有结点排列的序列，判断这个序列是否是这个有向图的拓扑排序序列。 解题思路：拓扑排序是输出有向图中入度的结点，并将这个结点指向的结点入度减1，循环输出，直到所有结点入度为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
42
43
44
45
46
47
48
49
50

#include <cstdio>
#include <set>
#include <vector>

using namespace std;

vector<set<int>> vs(1010);

bool is_topological(int *query, int n) {
    int *in = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        in[i] = vs[i].size();
    }

    for (int i = 0; i < n; i++) {
        if (in[query[i]] != 0) return false;
        for (int j = 1; j <= n; j++) {
            if (vs[j].find(query[i]) != vs[j].end()) {
                in[j]--;
            }
        }
    }
    return true;
}

int main() {
    int n = 0, m = 0, start = 0, end = 0, k = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &start, &end);
        vs[end].insert(start);
    }
    scanf("%d", &k);
    vector<int> ans;
    for (int i = 0; i < k; i++) {
        int *query = new int[n + 1];
        for (int j = 0; j < n; j++) {
            scanf("%d", &query[j]);
        }
        if (!is_topological(query, n)) {
            ans.push_back(i);
        }
        delete[] query;
    }
    printf("%d", ans[0]);
    for (int i = 1; i < ans.size(); i++) {
        printf(" %d", ans[i]);
    }
    return 0;
}

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure) ) Your job is to tell if a given complete binary tree is a heap.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: M (≤ 100), the number of trees to be tested; and N (1 < N ≤ 1,000), the number of keys in each tree, respectively. Then M lines follow, each contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

Output Specification:

For each given tree, print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all. Then in the next line print the tree’s postorder traversal sequence. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line.

Sample Input:

3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56

Sample Output:

Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10

题意：给出一棵完全二叉树的层序序列，判断它是最大堆（父亲结点大于等于孩子结点）、最小堆（父亲节点小于等于孩子结点）或者不是堆，并输出这棵树的后序遍历序列。 解题思路：对于每个结点，判断它和左右孩子的大小，如果它比左右孩子都大，则是最大堆；如果它比左右孩子都小，则是最小堆；否则它就不是堆。

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

#include <cstdio>

// post order traversal sequence
void print_post_order(int *arr, int n, int cur) {
    if (cur > n) return;
    int left_child = 2 * cur, right_child = 2 * cur + 1;
    print_post_order(arr, n, left_child);
    print_post_order(arr, n, right_child);
    if (cur != 1) printf("%d ", arr[cur]);
}

bool min_heap(int *arr, int n, int cur) {
    if (cur >= n) return true;
    int left_child = cur * 2, right_child = cur * 2 + 1;
    if (right_child <= n) {
        if (arr[left_child] >= arr[cur] && arr[right_child] >= arr[cur]) {
            return min_heap(arr, n, left_child) && min_heap(arr, n, right_child);
        }
    } else if (left_child <= n) {
        if (arr[left_child] >= arr[cur]) {
            return min_heap(arr, n, left_child) && min_heap(arr, n, right_child);
        }
    } else {
        return true;
    }
    return false;
}

bool max_heap(int *arr, int n, int cur) {
    if (cur >= n) return true;
    int left_child = cur * 2, right_child = cur * 2 + 1;
    if (right_child <= n) {
        if (arr[left_child] <= arr[cur] && arr[right_child] <= arr[cur]) {
            return max_heap(arr, n, left_child) && max_heap(arr, n, right_child);
        }
    } else if (left_child <= n) {
        if (arr[left_child] <= arr[cur]) {
            return max_heap(arr, n, left_child) && max_heap(arr, n, right_child);
        }
    } else {
        return true;
    }
    return false;
}

int main() {
    int m = 0, n = 0;
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++) {
        int *arr = new int[1030];
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[j]);
        }
        if (max_heap(arr, n, 1)) {
            printf("Max Heap\n");
        } else if (min_heap(arr, n, 1)) {
            printf("Min Heap\n");
        } else {
            printf("Not Heap\n");
        }
        print_post_order(arr, n, 1);
        printf("%d\n", arr[1]);
        delete[] arr;
    }
    return 0;
}

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given {32, 321, 3214, 0229, 87}, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification:

Each input file contains one test case. Each case gives a positive integer N (<=10000) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the smallest number in one line. Do not output leading zeros.

Sample Input:

5 32 321 3214 0229 87

Sample Output:

22932132143287

将给出的数字片段合成一个最小的数字，这里很巧妙的运用了排序，将他们按照从小到大排序然后合成就可以了，这个排序参考我家票票的代码：https://www.liuchuo.net/archives/2303

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

#include <iostream>

using namespace std;

int cmp(const void *a, const void *b) {
    string arg1 = *static_cast<const string *>(a);
    string arg2 = *static_cast<const string *>(b);

    if (arg1 + arg2 > arg2 + arg1) return 1;
    if (arg1 + arg2 < arg2 + arg1) return -1;
    return 0;
}

int main() {
    int n = 0;
    cin >> n;
    string *num = new string[n];
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }

    qsort(num, n, sizeof(num[0]), cmp);
    string ans;
    for (int i = 0; i < n; i++) {
        ans += num[i];
    }
    while (ans.length() != 0 && ans[0] == '0') {
        ans.erase(ans.begin());
    }
    if (ans.size() == 0) {
        cout << "0";
    } else {
        cout << ans;
    }
    delete[] num;
    return 0;
}

One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format: Name1 Name2 Time where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:

8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10

Sample Output 1:

2
AAA 3
GGG 3

Sample Input 2:

8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10

Sample Output 2:

0

我是用深搜解决的，实际上是有个连通图的节点的个数要大于2，每个节点的权值是时间，一个连通图的节点的权值总和要大于给出的k

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

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int len = 27 * 27 * 27;

vector<vector<int> > net(len);
int times[len], isVisited[len];

struct Gang {
    int index, cnt;

    Gang(int m_index, int m_cnt) {
        index = m_index;
        cnt = m_cnt;
    }
};

bool cmp(struct Gang a, struct Gang b) {
    return a.index < b.index;
}

int getIndex(char *name) {
    int index = 0;
    for (int i = 0; i < 3; i++) { index = index * 26 + name[i] - 'A'; }
    return index;
}

void printName(int index) {
    printf("%c", index / (26 * 26) + 'A');
    printf("%c", index % (26 * 26) / 26 + 'A');
    printf("%c", index % 26 + 'A');
}

void dfs(int &cnt, int cur, int &head, int &total) {
    for (auto it = net[cur].begin(); it != net[cur].end(); it++) {
        if (!isVisited[*it]) {
            isVisited[*it] = 1;
            if (times[head] < times[*it]) head = *it;
            cnt++;
            total += times[*it];
            dfs(cnt, *it, head, total);
        }
    }
}

int main() {
    int n = 0, k = 0;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        char name1[4], name2[4];
        int time = 0;
        scanf("%s %s %d", name1, name2, &time);
        int index1 = getIndex(name1), index2 = getIndex(name2);
        net[index1].push_back(index2);
        net[index2].push_back(index1);
        times[index1] += time;
        times[index2] += time;
    }
    vector<struct Gang> ans;
    for (int i = 0; i < len; i++) {
        int cnt = 1, head = i, total = times[i];;
        if (!isVisited[i] && net[i].size() != 0) {
            isVisited[i] = 1;
            dfs(cnt, i, head, total);
        }
        if (cnt > 2 && total > 2 * k) {
            struct Gang g(head, cnt);
            ans.push_back(g);
        }
    }
    printf("%lu\n", ans.size());
    sort(ans.begin(), ans.end(), cmp);
    for (auto it = ans.begin(); it != ans.end(); it++) {
        printName(it->index);
        printf(" %d\n", it->cnt);
    }
    return 0;
}

Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options: 1. Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15). 2. Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15). 3. Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15). Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer. If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (<=105), the total number of diamonds on the chain, and M (<=108), the amount that the customer has to pay. Then the next line contains N positive numbers D1 … DN (Di<=103 for all i=1, …, N) which are the values of the diamonds. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print “i-j” in a line for each pair of i <= j such that Di + … + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i. If there is no solution, output “i-j” for pairs of i <= j such that Di + … + Dj > M with (Di + … + Dj - M) minimized. Again all the solutions must be printed in increasing order of i. It is guaranteed that the total value of diamonds is sufficient to pay the given amount.

Sample Input 1:

16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13

Sample Output 1:

1-5
4-6
7-8
11-11

Sample Input 2:

5 13
2 4 5 7 9

Sample Output 2:

2-4
4-5

这个题目要用二分法来做，直接判断的话会超时，二分查找与m相邻近的值，用数组存一个sum[i] = 1到i得和

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

#include <cstdio>

int findNearM(int *sum, int l, int r, int v) {
    int mid = 0;
    while (l < r) {
        mid = (l + r) / 2;
        if (sum[mid] >= v) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    int n = 0, m = 0;
    scanf("%d %d", &n, &m);
    int *sum = new int[n + 1];
    sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        int t = 0;
        scanf("%d", &t);
        sum[i] = sum[i - 1] + t;
    }

    int nearM = 100000;
    for (int i = 0; i < n; i++) {
        int j = findNearM(sum, 1, n, sum[i] + m);
        if (sum[j] - sum[i] - m >= 0 && sum[j] - sum[i] - m < nearM) nearM = sum[j] - sum[i] - m;
    }

    for (int i = 0; i < n; i++) {
        int j = findNearM(sum, 1, n, sum[i] + m + nearM);
        if (sum[j] - sum[i] - m == nearM) {
            printf("%d-%d\n", i + 1, j);
        }
    }
    delete[] sum;
    return 0;
}

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family members, and the estate（房产）info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000). Then N lines follow, each gives the infomation of a person who owns estate in the format: ID Father Mother k Child1 … Childk M_estate Area where ID is a unique 4-digit identification number for each person; Father and Mother are the ID’s of this person’s parents (if a parent has passed away, -1 will be given instead); k (0<=k<=5) is the number of children of this person; Childi’s are the ID’s of his/her children;M_estate is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format: ID M AVG_sets AVG_area where ID is the smallest ID in the family; M is the total number of family members; AVG_sets is the average number of sets of their real estate; and AVG_area is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID’s if there is a tie.

Sample Input:

10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100

Sample Output:

3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

并查集

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

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int len = 10010;
int father[len], empty[len], estates[len], areas[len];
vector<struct Family> family;

struct Family {
    int id, m;
    double estate, area;

    Family(int m_id, int m_m, double m_estate, double m_area) {
        id = m_id;
        m = m_m;
        estate = m_estate;
        area = m_area;
    }
};

bool cmp(struct Family a, struct Family b) {
    if (a.area > b.area) return true;
    if (a.area == b.area) {
        return a.id < b.id;
    }
    return false;
}

void init() {
    for (int i = 0; i < len; i++) {
        father[i] = i;
        empty[i] = 1;
        estates[i] = 0;
        areas[i] = 0;
    }
}

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

void unionFind(int a, int b) {
    if (b == -1) return;
    int fa = findFather(a), fb = findFather(b);
    if (fa < fb) father[fb] = fa;
    else if (fb < fa) father[fa] = fb;
}

void findFamily() {
    int f[len];
    fill(f, f + len, 0);
    for (int i = 0; i < len; i++) {
        f[findFather(i)]++;
        if (i != findFather(i)) {
            estates[findFather(i)] += estates[i];
            areas[findFather(i)] += areas[i];
        }
    }
    for (int i = 0; i < len; i++) {
        if (!empty[i] && f[i] != 0) {
            struct Family fy(i, f[i], estates[i] * 1.0 / f[i], areas[i] * 1.0 / f[i]);
            family.push_back(fy);
        }
    }
}

int main() {
    init();
    int n = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int id = 0, f = 0, m = 0, k = 0;
        scanf("%d %d %d %d", &id, &f, &m, &k);
        unionFind(id, f);
        unionFind(id, m);
        empty[id] = 0;
        if (f != -1) empty[f] = 0;
        if (m != -1) empty[m] = 0;
        for (int j = 0; j < k; j++) {
            int child = 0;
            scanf("%d", &child);
            unionFind(id, child);
            empty[child] = 0;
        }
        int estate = 0, area = 0;
        scanf("%d %d", &estate, &area);
        estates[id] = estate;
        areas[id] = area;
    }
    findFamily();

    sort(family.begin(), family.end(), cmp);
    printf("%lu\n", family.size());
    for (int i = 0; i < family.size(); i++) {
        struct Family t = family[i];
        printf("%04d %d %.3f %.3f\n", t.id, t.m, t.estate, t.area);
    }
    return 0;
}

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead. Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].

Sample Input 1:

8 9
5 9 8 7 2 3 4 1

Sample Output 1:

1 3 5

Sample Input 2:

4 8
7 2 4 3

Sample Output 2:

No Solution

参考女票的代码：https://www.liuchuo.net/archives/2323 用dp来做，然后打印路径

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

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp(int arg1, int arg2) {
    if (arg1 > arg2) return 1;
    return 0;
}

int main() {
    vector<int> coins;
    int n = 0, m = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        int c = 0;
        scanf("%d", &c);
        if (c <= m) {
            coins.push_back(c);
        }
    }
    sort(coins.begin(), coins.end(), cmp);
    n = coins.size();

    int *dp = new int[m + 1];
    int **s = new int *[n];
    for (int i = 0; i < n; i++) {
        s[i] = new int[m + 1];
        fill(s[i], s[i] + m, 0);
    }
    fill(dp, dp + m + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = m; j >= coins[i]; j--) {
            if (dp[j] <= dp[j - coins[i]] + coins[i]) {
                dp[j] = dp[j - coins[i]] + coins[i];
                s[i][j] = 1;
            }
        }
    }

    if (dp[m] != m) printf("No Solution");
    else {
        int i = n - 1, j = m;
        vector<int> result;
        while (i >= 0) {
            if (s[i][j] == 1) {
                result.push_back(coins[i]);
                j -= coins[i];
            }
            i--;
        }
        for (int i = 0; i < result.size(); i++) {
            printf("%d", result[i]);
            if (i != result.size() - 1) printf(" ");
        }
    }

    for (int i = 0; i < n; i++) {
        delete[] s[i];
    }
    delete[] s;
    delete[] dp;
    return 0;
}