hdvsyu's blog

Posted on Edited on In

一个分数一般写成两个整数相除的形式：N/M，其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。 现给定两个不相等的正分数 N1/M1 和 N2/M2，要求你按从小到大的顺序列出它们之间分母为K的最简分数。

输入格式：

输入在一行中按N/M的格式给出两个正分数，随后是一个正整数分母K，其间以空格分隔。题目保证给出的所有整数都不超过1000。

输出格式：

在一行中按N/M的格式列出两个给定分数之间分母为K的所有最简分数，按从小到大的顺序，其间以1个空格分隔。行首尾不得有多余空格。题目保证至少有1个输出。

输入样例：

7/18 13/20 12

输出样例：

5/12 7/12

首先这个介于之间不一定是前一个比后一个大，这里可能会有坑，然后是分子分母的最大公约数只能是1，比较分式可能比较麻烦，转成小数来比较就方便许多了

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] one = sc.next().split("/");
        double a = Double.parseDouble(one[0]) / Double.parseDouble(one[1]);
        String[] two = sc.next().split("/");
        double b = Double.parseDouble(two[0]) / Double.parseDouble(two[1]);
        int fm = sc.nextInt();
        sc.close();
        boolean isSpace = false;
        for (int i = 1; i < fm; i++) {
            int g = gcd(i, fm);
            if (g == 1 && (isBetween(a, b, i * 1.0 / fm))) {
                if (isSpace) {
                    System.out.print(" ");
                }
                System.out.print(i + "/" + fm);
                isSpace = true;
            }
        }
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static boolean isBetween(double a, double b, double c) {
        if (c > Math.min(a, b) && c < Math.max(a, b)) {
            return true;
        }
        return false;
    }
}

Posted on Edited on In

“Damn Single (单身狗)” is the Chinese nickname for someone who is being single. You are supposed to find those who are alone in a big party, so they can be taken care of.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=50000), the total number of couples. Then N lines of the couples follow, each gives a couple of ID’s which are 5-digit numbers (i.e. from 00000 to 99999). After the list of couples, there is a positive integer M (<=10000) followed by M ID’s of the party guests. The numbers are separated by spaces. It is guaranteed that nobody is having bigamous marriage (重婚) or dangling with more than one companion.

Output Specification:

First print in a line the total number of lonely guests. Then in the next line, print their ID’s in increasing order. The numbers must be separated by exactly 1 space, and there must be no extra space at the end of the line.

Sample Input:

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

Sample Output:

5
10000 23333 44444 55555 88888

先用一个couple记录一对情侣，比如couple[11111]=22222，然后用一个guest数组存储接下来的一行guest，guest[i]表示这个guest的id，如果这个guest[i]的另一半不是-1，那么就设就告诉另一半，你来了，比如guest[i] != -1, 则设 isSCoupleAttent[guest[i]] = 1，比如guest[i] = 11111，那么isCoupleAttent[22222] = 1，表示是在guest数组里面的，最后遍历一下guest，看一下guest[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
39
40
#include <cstdio>
#include <set>
#include <iterator>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    int *couple = new int[100000];
    int *isCoupleAttent = new int[100000];
    for (int i = 0; i < 100000; i++) {
        couple[i] = -1;
        isCoupleAttent[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        couple[a] = b;
        couple[b] = a;
    }
    int m = 0;
    scanf("%d", &m);
    int *guest = new int[m];
    for (int i = 0; i < m; i++) {
        scanf("%d", &guest[i]);
        if (couple[guest[i]] != -1) { isCoupleAttent[couple[guest[i]]] = 1; }
    }
    set<int> s;
    for (int i = 0; i < m; i++) { if (!isCoupleAttent[guest[i]]) { s.insert(guest[i]); }}
    printf("%d\n", s.size());
    for (auto it = s.begin(); it != s.end(); it++) {
        if (it != s.begin()) { printf(" "); }
        printf("%05d", *it);
    }
    delete[] isCoupleAttent;
    delete[] guest;
    delete[] couple;

}

Posted on Edited on In

Two integers are called “friend numbers” if they share the same sum of their digits, and the sum is their “friend ID”. For example, 123 and 51 are friend numbers since 1+2+3 = 5+1 = 6, and 6 is their friend ID. Given some numbers, you are supposed to count the number of different friend ID’s among them. Note: a number is considered a friend of itself.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N. Then N positive integers are given in the next line, separated by spaces. All the numbers are less than 104.

Output Specification:

For each case, print in the first line the number of different frind ID’s among the given integers. Then in the second line, output the friend ID’s in increasing order. The numbers must be separated by exactly one space and there must be no extra space at the end of the line.

Sample Input:

8
123 899 51 998 27 33 36 12

Sample Output:

4
3 6 9 26

把一个数字的每个位都相加，得到一个数，这个数就是friend 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
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numOfInteger = scanner.nextInt();
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < numOfInteger; i++) {
            int temp = scanner.nextInt();
            set.add(getFriendId(temp));
        }
        scanner.close();
        System.out.println(set.size());
        boolean isFirst = true;
        for (int id : set) {
            if (!isFirst) {
                System.out.print(" ");
            }
            System.out.print(id);
            isFirst = false;
        }
    }

    private static int getFriendId(int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

Posted on Edited on In

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print “YES” if the tree is complete, or “NO” if not.

Sample Input 1:

5
88 70 61 63 65

Sample Output 1:

70 63 88 61 65
YES

Sample Input 2:

8
88 70 61 96 120 90 65 68

Sample Output 2:

88 65 96 61 70 90 120 68
NO

这里实际上是把AVL树和层序遍历两个考点放到了一起，判断是不是完全二叉树，就看在出现了一个孩子为空的结点之后，时候还会出现孩子结点不为空的结点，如果出现了就不是完全二叉树。AVL树理解起来可能比较复杂，但仔细看看就能够明白，一共有四种情况，这里我把发现树不平衡的那个结点叫做A结点，A发现树不平衡无非就是四种情况：

  1. 新来的结点插入到A的左子树的左子树
  2. 新来的结点插入到A的左子树的右子树
  3. 新来的结点插入到A的右子树的左子树
  4. 新来的结点插入到A的右子树的右子树

发现了不平衡那就要处理了，第1种情况只要简单的右旋就可以解决了，第4种情况只需左旋一下，剩下的第2、3种情况稍微复杂一点，第2种情况需要先对A的左子树左旋一下，然后对A右旋，同理第3种情况需要对A的右子树右旋一下，然后对A左旋，其他就没有什么大问题了，代码如下

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

using namespace std;

struct Node {
    int val;
    struct Node *left, *right;
};

struct Node *leftRotate(struct Node *tree) {
    struct Node *temp = tree->right;
    tree->right = temp->left;
    temp->left = tree;
    return temp;
}

struct Node *rightRotate(struct Node *tree) {
    struct Node *temp = tree->left;
    tree->left = temp->right;
    temp->right = tree;
    return temp;
}

int getHeight(struct Node *tree) {
    if (tree == NULL) {
        return 0;
    } else {
        int l = getHeight(tree->left);
        int r = getHeight(tree->right);
        return l > r ? l + 1 : r + 1;
    }
}

struct Node *leftRightRotate(struct Node *tree) {
    tree->left = leftRotate(tree->left);
    tree = rightRotate(tree);
    return tree;
}

struct Node *rightLeftRotate(struct Node *tree) {
    tree->right = rightRotate(tree->right);
    tree = leftRotate(tree);
    return tree;
}

struct Node *insert(struct Node *tree, int val) {
    if (tree == NULL) {
        tree = new struct Node();
        tree->val = val;
        return tree;
    }
    if (tree->val > val) {
        tree->left = insert(tree->left, val);
        int l = getHeight(tree->left);
        int r = getHeight(tree->right);
        if (l - r >= 2) {
            if (val < tree->left->val) {
                tree = rightRotate(tree);
            } else {
                tree = leftRightRotate(tree);
            }
        }
    } else {
        tree->right = insert(tree->right, val);
        int l = getHeight(tree->left);
        int r = getHeight(tree->right);
        if (r - l >= 2) {
            if (val > tree->right->val) {
                tree = leftRotate(tree);
            } else {
                tree = rightLeftRotate(tree);
            }
        }
    }
    return tree;
}

int isComplete = 1, after = 0;

vector<int> levelOrder(struct Node *tree) {
    vector<int> v;
    queue<struct Node *> queue;
    queue.push(tree);
    while (queue.size() != 0) {
        struct Node *temp = queue.front();
        queue.pop();
        v.push_back(temp->val);
        if (temp->left != NULL) {
            if (after) {
                isComplete = 0;
            }
            queue.push(temp->left);
        } else {
            after = 1;
        }
        if (temp->right != NULL) {
            if (after) {
                isComplete = 0;
            }
            queue.push(temp->right);
        } else {
            after = 1;
        }
    }

    return v;
}

void print(vector<int> v) {
    for (int i = 0; i < v.size(); i++) {
        if (i == 0) {
            printf("%d", v[i]);
        } else {
            printf(" %d", v[i]);
        }
    }
    printf("\\n");
}

int main() {
    int n = 0;
    scanf("%d", &n);
    struct Node *tree = NULL;
    for (int i = 0; i < n; i++) {
        int temp = 0;
        scanf("%d", &temp);
        tree = insert(tree, temp);
    }

    vector<int> v = levelOrder(tree);
    print(v);
    if (isComplete) {
        printf("YES");
    } else {
        printf("NO");
    }
    return 0;
}

Posted on Edited on In

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。

输入格式：

输入第一行给出一个正整数N（<=50000），是已知夫妻/伴侣的对数；随后N行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个ID号，为5位数字（从00000到99999），ID间以空格分隔；之后给出一个正整数M（<=10000），为参加派对的总人数；随后一行给出这M位客人的ID，以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式：

首先第一行输出落单客人的总人数；随后第二行按ID递增顺序列出落单的客人。ID间用1个空格分隔，行的首尾不得有多余空格。

输入样例：

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

输出样例：

5
10000 23333 44444 55555 88888

先用一个couple记录一对情侣，比如couple[11111]=22222，然后用一个guest数组存储接下来的一行guest，guest[i]表示这个guest的id，如果这个guest[i]的另一半不是-1，那么就设就告诉另一半，你来了，比如guest[i] != -1, 则设 isSCoupleAttent[guest[i]] = 1，比如guest[i] = 11111，那么isCoupleAttent[22222] = 1，表示是在guest数组里面的，最后遍历一下guest，看一下guest[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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <set>
#include <iterator>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    int *couple = new int[100000];
    int *isCoupleAttent = new int[100000];
    for (int i = 0; i < 100000; i++) {
        couple[i] = -1;
        isCoupleAttent[i] = 0;

    }
    for (int i = 0; i < n; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        couple[a] = b;
        couple[b] = a;

    }

    int m = 0;
    scanf("%d", &m);
    int *guest = new int[m];

    for (int i = 0; i < m; i++) {
        scanf("%d", &guest[i]);
        if (couple[guest[i]] != -1) {
            isCoupleAttent[couple[guest[i]]] = 1;
        }
    }

    set<int> s;
    for (int i = 0; i < m; i++) {
        if (!isCoupleAttent[guest[i]]) {
            s.insert(guest[i]);
        }
    }

    printf("%d\n", s.size());
    for (auto it = s.begin(); it != s.end(); it++) {
        if (it != s.begin()) {
            printf(" ");
        }
        printf("%05d", *it);
    }
    delete[] isCoupleAttent;
    delete[] guest;
    delete[] couple;

}

Posted on Edited on In

如果两个整数各位数字的和是一样的，则被称为是“朋友数”，而那个公共的和就是它们的“朋友证号”。例如123和51就是朋友数，因为1+2+3 = 5+1 = 6，而6就是它们的朋友证号。给定一些整数，要求你统计一下它们中有多少个不同的朋友证号。注意：我们默认一个整数自己是自己的朋友。

输入格式：

输入第一行给出正整数N。随后一行给出N个正整数，数字间以空格分隔。题目保证所有数字小于104。

输出格式：

首先第一行输出给定数字中不同的朋友证号的个数；随后一行按递增顺序输出这些朋友证号，数字间隔一个空格，且行末不得有多余空格。

输入样例：

8
123 899 51 998 27 33 36 12

输出样例：

4
3 6 9 26

把一个数字的每个位都相加，得到一个数，这个数就是friend 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
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numOfInteger = scanner.nextInt();
        Set<Integer> set = new TreeSet<Integer>();
        for (int i = 0; i < numOfInteger; i++) {
            int temp = scanner.nextInt();
            set.add(getFriendId(temp));
        }
        scanner.close();
        System.out.println(set.size());
        boolean isFirst = true;
        for (int id : set) {
            if (!isFirst) {
                System.out.print(" ");
            }
            System.out.print(id);
            isFirst = false;
        }
    }

    private static int getFriendId(int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

Posted on Edited on In

判断题的评判很简单，本题就要求你写个简单的程序帮助老师判题并统计学生们判断题的得分。

输入格式：

输入在第一行给出两个不超过100的正整数N和M，分别是学生人数和判断题数量。第二行给出M个不超过5的正整数，是每道题的满分值。第三行给出每道题对应的正确答案，0代表“非”，1代表“是”。随后N行，每行给出一个学生的解答。数字间均以空格分隔。

输出格式：

按照输入的顺序输出每个学生的得分，每个分数占一行。

输入样例：

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

输出样例：

13
11
12

这个题目比较简单，就没写思路了

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] score = new int[m];
        for (int i = 0; i < m; i++) {
            score[i] = scanner.nextInt();
        }
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            ans[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = 0; j < m; j++) {
                int t = scanner.nextInt();
                if (t == ans[j]) {
                    s += score[j];
                }
            }
            System.out.println(s);
        }
        scanner.close();
    }
}

Posted on Edited on In

在数学中，矩阵的“谱半径”是指其特征值的模集合的上确界。换言之，对于给定的n个复数空间的特征值{a1+b1_i_, …, an+bn_i_}，它们的模为实部与虚部的平方和的开方，而“谱半径”就是最大模。 现在给定一些复数空间的特征值，请你计算并输出这些特征值的谱半径。

输入格式：

输入第一行给出正整数N（<= 10000）是输入的特征值的个数。随后N行，每行给出1个特征值的实部和虚部，其间以空格分隔。注意：题目保证实部和虚部均为绝对值不超过1000的整数。

输出格式：

在一行中输出谱半径，四舍五入保留小数点后2位。

输入样例：

5
0 1
2 0
-1 0
3 3
0 -3

输出样例：

4.24

模是复数的实部的平方加上虚部的平方开根号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <cmath>

double getModule(int a, int b) {
    return sqrt(a * a + b * b);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    double module = -1;
    for (int i = 0; i < n; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        double m = getModule(a, b);
        module = module > m ? module : m;
    }
    printf("%.2f", module);
    return 0;
}

Posted on Edited on In

本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。

输入格式：

输入第一行给出2个正整数N（2 <= N <= 200，城镇总数）和K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后N-1行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有K行，每行按格式“城镇1 城镇2 距离”给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由3个大写英文字母组成的字符串。

输出格式：

按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式“己方大本营->城镇1->…->敌方大本营”输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以1个空格分隔，行首尾不得有多余空格。

输入样例：

10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10

输出样例：

PAT->PTA->PDS->DBY
3 30 210

多级最短路径问题，可以用Dijkstra，这里我用的是DFS求解的。相比Dijkstra而言，DFS逻辑简单，实现起来方便快速，但是也牺牲了许多的代码可读性。

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

using namespace std;

const int inf = 65535;

map<string, int> s_to_i; // 把城镇名映射为一个数字
map<int, string> i_to_s; // 把数字映射位一个城镇名

bool visited[210]; // 标记一个顶点是否已经访问，已经访问置true
/**
 * ans_len 表示保存是距离最短长度
 * ans_kill 保存的是杀敌数量最多的
 * defend数组是每一个城镇的守卫数量
 * ans_path_cnt是距离最短路径的数目
 * city_map是图的邻接矩阵表示
 */
int ans_len = inf, ans_kill = -1, defend[210], ans_path_cnt = 0, city_map[210][210];
deque<int> ans_p; // ans_p保存一个路径的访问次序

/**
 * 
 * @param cur 表示当前正在访问的节点下标
 * @param e 表示敌方大本营
 * @param n 是整个图的顶点数目
 * @param len 是从起点到当前点的距离
 * @param kill 是从起点到当前点的杀敌数量
 * @param p 是访问的路径
 */
void dfs(int cur, int e, int n, int len, int kill, deque<int> p) {
    if (cur == e) { // 当访问到敌方大本营时
        if (len < ans_len) { // 距离比保存的还要短，则更新距离，杀敌数量，访问次序并把
            ans_len = len;
            ans_kill = kill;
            ans_p = p;
            ans_path_cnt = 1;
        } else if (len == ans_len) {
            ans_path_cnt++;
            if (p.size() > ans_p.size()) {
                ans_kill = kill;
                ans_p = p;
            } else if (p.size() == ans_p.size()) {
                if (kill > ans_kill) {
                    ans_kill = kill;
                    ans_p = p;
                }
            }
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i] && city_map[cur][i] != inf) {
            visited[i] = true;
            p.push_back(i);
            dfs(i, e, n, len + city_map[cur][i], kill + defend[i], p);
            p.pop_back();
            visited[i] = false;
        }
    }
}

void init(int n) {
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        for (int j = 0; j < n; j++) {
            city_map[i][j] = inf;
        }
    }
}

void printAns() {
    printf("%s", i_to_s[0].c_str());
    while (!ans_p.empty()) {
        printf("->%s", i_to_s[ans_p.front()].c_str());
        ans_p.pop_front();
    }
    printf("\\n%d %d %d\\n", ans_path_cnt, ans_len, ans_kill);
}

int main() {
    int n = 0, k = 0, l = 0;
    char own[4], enemy[4], town[4], city1[4], city2[4];
    scanf("%d %d %s %s", &n, &k, own, enemy);
    init(n);
    s_to_i[own] = 0;
    i_to_s[0] = own;
    for (int i = 1; i < n; i++) {
        scanf("%s %d", town, &defend[i]);
        s_to_i[town] = i;
        i_to_s[i] = town; // 根据城镇出现的次序，用map来做一一映射
    }
    for (int i = 0; i < k; i++) {
        scanf("%s %s %d", city1, city2, &l);
        city_map[s_to_i[city1]][s_to_i[city2]] = city_map[s_to_i[city2]][s_to_i[city1]] = l;
    }

    deque<int> p;
    visited[0] = true;
    // dfs(int cur, int e, int n, int len, int kill, deque<int> p) 下方函数的调用对应参数
    dfs(0, s_to_i[enemy], n, 0, 0, p);
    printAns();
    return 0;
}

Posted on Edited on In

在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。

输入格式：

输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好： Ki: hi[1] hi[2] … hi[Ki] 其中Ki（>0）是第i个人的兴趣的数量，hi[j]是第i个人的第j项兴趣的编号，编号范围为[1, 1000]内的整数。

输出格式：

首先在第一行输出整个网络中集群的数量，然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

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

输出样例：

3
4 3 1

把存在相同爱好的人归为一个群，如上面的例子，2、4、6、8是一个集群，3、5、7是一个集群，1是一个集群，这里的数字是每个人的编号，由此可以得到存在三个集群，且数量分别是4 3 1。 从题中可以看出，这个题目可以用并查集求解。 init_father、find_father和union_father函数分别是并查集的三个基本操作，不理解并查集的可以看维基百科-并查集，这里我用了较多的容器，是为了方便求解，set是为了快速判断两个人是否存在相同的兴趣点，map是为了统计有几个社交集群，priority_queue是为了按非递增顺序输出社交集群的数量。 

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
#include <cstdio>
#include <vector>
#include <set>
#include <iterator>
#include <functional>
#include <map>
#include <queue>

using namespace std;

int *father;

void init_father(int n) {
    father = new int[n + 1];
    for (int i = 0; i <= n; i++) father[i] = i;
}

int find_father(int x) {
    if (father[x] == x) return x;
    return find_father(father[x]);
}

void union_father(int arg1, int arg2) {
    int fa = find_father(arg1);
    int fb = find_father(arg2);
    father[fa] = fb;
}

int main() {
    int n = 0, ki = 0, hobby = 0;
    scanf("%d", &n);
    init_father(n);
    vector<set<int> > hobbies(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d:", &ki);
        for (int j = 0; j < ki; j++) {
            scanf("%d", &hobby);
            hobbies[i].insert(hobby);
            for (int k = 1; k < i; k++) {
                if (hobbies[k].find(hobby) != hobbies[k].end()) {
                    union_father(i, k);
                }
            }
        }
    }

    map<int, int> m;
    for (int i = 1; i <= n; i++) {
        m[find_father(i)]++;
    }
    printf("%ld\n", m.size());

    priority_queue<int, vector<int>, less<int>> q;
    for (auto it = m.begin(); it != m.end(); it++) {
        q.push(it->second);
    }
    while (q.size() > 1) {
        printf("%d ", q.top());
        q.pop();
    }
    printf("%d", q.top());
    return 0;
}
0%