hdvsyu's blog

Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

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 K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N-1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format “City1 City2 Cost”. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.

Output Specification:

For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommended. If such a route is still not unique, then we output the one with the maximum average happiness – it is guaranteed by the judge that such a solution exists and is unique. Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommended route. Then in the next line, you are supposed to print the route in the format “City1->City2->…->ROM”.

Sample Input:

6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1

Sample Output:

3 3 195 97
HZH->PRS->ROM

图的遍历问题，我用的是深搜，把地名和数字作一个一一映射，就成了普通的图的求最短路的问题了

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

#include <string>
#include <map>
#include <iostream>
#include <vector>

using namespace std;

map<string, int> si;
vector<string> itos(200);
int happiness[200], cities[200][200], isVisited[200];
int routes, final_cost = 100000, final_happiness = 1000000, final_unit = 100000;
vector<int> final_path;

void dfs(int cur, int dest, int cost, int happy, int unit, vector<int> path, int n) {
    if (cur == dest) {
        if (cost < final_cost) {
            final_cost = cost;
            final_unit = unit;
            final_happiness = happy;
            routes = 1;
            final_path = path;
        } else if (cost == final_cost) {
            routes += 1;
            if (happy > final_happiness) {
                final_happiness = happy;
                final_unit = unit;
                final_path = path;
            } else if (happy == final_happiness) {
                if (happy / unit > final_happiness / final_unit) {
                    final_unit = unit;
                    final_path = path;
                }
            }
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!isVisited[i] && cities[cur][i] != 0) {
            isVisited[i] = true;
            path.push_back(i);
            dfs(i, dest, cost + cities[cur][i], happy + happiness[i], unit + 1, path, n);
            path.pop_back();
            isVisited[i] = false;
        }
    }
}

void printPath() {
    cout << itos[final_path[0]];
    for (int i = 1; i < final_path.size(); i++) {
        cout << "->" << itos[final_path[i]];
    }
}

int main() {
    int n = 0, k = 0;
    string s;
    cin >> n >> k >> s;
    si[s] = 0;
    itos[0] = s;
    for (int i = 1; i < n; i++) {
        cin >> s >> happiness[i];
        si[s] = i;
        itos[i] = s;
    }
    for (int i = 0; i < k; i++) {
        string a, b;
        cin >> a >> b;
        cin >> cities[si[a]][si[b]];
        cities[si[b]][si[a]] = cities[si[a]][si[b]];
    }

    isVisited[0] = true;
    vector<int> path;
    path.push_back(0);
    dfs(0, si["ROM"], 0, 0, 0, path, n);
    cout << routes << " " << final_cost << " " << final_happiness << " " << (final_happiness / final_unit) << endl;
    printPath();
    return 0;
}

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers. Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484. Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers N and K, where N (<= 1010) is the initial numer and K (<= 100) is the maximum number of steps. The numbers are separated by a space.

Output Specification:

For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.

Sample Input 1:

67 3

Sample Output 1:

484
2

Sample Input 2:

69 3

Sample Output 2:

1353
3

用long会溢出，有两个测试点会过不了，用字符串就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

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string add(string t, string n) {
    string s;
    int temp = 0;
    int i = t.size() - 1, j = n.size() - 1;
    while (i >= 0 && j >= 0) {
        int num = temp + t[i] - '0' + n[j] - '0';
        s = to_string(num % 10) + s;
        temp = num / 10;
        i--;
        j--;
    }
    while (i >= 0) {
        int num = temp + t[i] - '0';
        s = to_string(num % 10) + s;
        temp = num / 10;
        i--;
    }

    while (j >= 0) {
        int num = temp + n[j] - '0';
        s = to_string(num % 10) + s;
        temp = num / 10;
        j--;
    }

    if (temp == 1) s = "1" + s;
    return s;
}

int main() {
    int k = 0;
    string n;
    cin >> n >> k;
    bool state = false;
    for (int i = 0; i < k; i++) {
        string t = n;
        reverse(t.begin(), t.end());
        if (t == n) {
            cout << n << endl << i << endl;
            state = true;
            break;
        }
        n = add(t, n);
    }
    if (!state) cout << n << endl << k << endl;
    return 0;
}

A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (<=500) is the number of cities (and hence the cities are numbered from 0 to N-1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format: City1 City2 Distance Cost where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:

For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

Sample Output

0 2 3 3 40

简单的深搜就可以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

#include <cstdio>
#include <vector>

using namespace std;

struct City {
    int dis, cost;
};

struct City **cities;
int *isVisited;


int final_len = 100000, final_cost;
vector<int> final_path;

void dfs(int cur, int dest, int len, int cost, vector<int> &path, int n) {
    if (cur == dest) {
        if (len < final_len) {
            final_len = len;
            final_cost = cost;
            final_path = path;
        } else if (len == final_len && cost < final_cost) {
            final_cost = cost;
            final_path = path;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        struct City c = cities[cur][i];
        if (c.dis != -1 && !isVisited[i]) {
            isVisited[i] = 1;
            path.push_back(i);
            dfs(i, dest, len + c.dis, cost + c.cost, path, n);
            path.pop_back();
            isVisited[i] = 0;
        }
    }
}

void printPath() {
    for (int i = 0; i < final_path.size(); i++) {
        printf("%d ", final_path[i]);
    }
}

int main() {
    int n = 0, m = 0, s = 0, d = 0;
    scanf("%d %d %d %d", &n, &m, &s, &d);

    cities = new struct City *[n];
    isVisited = new int[n];
    for (int i = 0; i < n; i++) {
        cities[i] = new struct City[n];
        isVisited[i] = 0;
        for (int j = 0; j < n; j++) {
            cities[i][j].dis = cities[i][j].dis = -1;
        }
    }

    for (int i = 0; i < m; i++) {
        int a = 0, b = 0, dis = 0, cost = 0;
        scanf("%d %d %d %d", &a, &b, &dis, &cost);
        cities[a][b].dis = cities[b][a].dis = dis;
        cities[a][b].cost = cities[b][a].cost = cost;
    }

    vector<int> path;
    path.push_back(s);
    isVisited[s] = 1;
    dfs(s, d, 0, 0, path, n);

    printPath();
    printf("%d %d", final_len, final_cost);

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

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine. The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order: S1, S2, …, S13, H1, H2, …, H13, C1, C2, …, C13, D1, D2, …, D13, J1, J2 where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer K (<= 20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.

Sample Input:

2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47

Sample Output:

S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

这里是移动两张牌，不是交换两张牌

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

#include <cstdio>
#include <vector>

using namespace std;

void swp(int *poker, const vector<int> &order) {
    int *temp = new int[55];
    for (int i = 1; i < 55; i++) temp[i] = 0;
    for (int i = 0; i < order.size(); i++) {
        temp[order[i]] = poker[i + 1];
    }

    for (int i = 1; i < 55; i++) {
        if (temp[i] != 0) poker[i] = temp[i];
    }
    delete[] temp;
}

void printPoker(int *poker) {
    char c[] = {'S', 'H', 'C', 'D', 'J'};
    for (int i = 1; i < 55; i++) {
        if (poker[i] % 13 == 0) {
            printf("%c13", c[poker[i] / 13 - 1]);
        } else {
            printf("%c%d", c[poker[i] / 13], poker[i] % 13);
        }
        if (i != 54) printf(" ");
    }
}

int main() {
    int k = 0;
    scanf("%d", &k);
    int *poker = new int[55];
    for (int i = 1; i < 55; i++) poker[i] = i;
    vector<int> order;
    int t = 0;
    while (~scanf("%d", &t)) {
        order.push_back(t);
    }

    for (int i = 0; i < k; i++) {
        swp(poker, order);
    }

    printPoker(poker);
    delete[] poker;
    return 0;
}

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given “Is PAT&TAP symmetric?”, the longest symmetric sub-string is “s PAT&TAP s”, hence you must output 11.

Input Specification:

Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification:

For each test case, simply print the maximum length in a line.

Sample Input:

Is PAT&TAP symmetric?

Sample Output:

11

这个题目首先可以想到暴力破解法，我是用动态规划做的，在时间复杂度上比暴力破解法低一个数量级，但在空间上多出了开销，典型的以空间换时间的方法 我们用dp[i, j] = 1 表示s[i]到s[j]是回文串，且有dp[i, i] = 1和if (s[i] == s[j]) dp[i, j] = dp[i + 1, j - 1]，还有if (s[i] == s[i - 1]) dp[i, i - 1] = 1这个就是比如PAAT的情况，接下来就是填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

#include <string>
#include <iostream>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    int n = s.size();
    int **len = new int *[n];
    for (int i = 0; i < n; i++) {
        len[i] = new int[n];
    }
    for (int i = 0; i < n; i++) {
        len[i][i] = 1;
        if (i > 0 && s[i] == s[i - 1]) len[i][i - 1] = 1;
    }

    int maxLen = 1;
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                len[i][j] = len[i + 1][j - 1];
                if (len[i][j] == 1) maxLen = max(maxLen, j - i + 1);
            } else len[i][j] = 0;
        }
    }
    printf("%d", maxLen);
    for (int i = 0; i < n; i++) {
        delete[] len[i];
    }
    delete[] len;
    return 0;
}

A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID’s.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the total number of books. Then N blocks follow, each contains the information of a book in 6 lines:

• Line #1: the 7-digit ID number;
• Line #2: the book title – a string of no more than 80 characters;
• Line #3: the author – a string of no more than 80 characters;
• Line #4: the key words – each word is a string of no more than 10 characters without any white space, and the keywords are separated by exactly one space;
• Line #5: the publisher – a string of no more than 80 characters;
• Line #6: the published year – a 4-digit number which is in the range [1000, 3000].

It is assumed that each book belongs to one author only, and contains no more than 5 key words; there are no more than 1000 distinct key words in total; and there are no more than 1000 distinct publishers. After the book information, there is a line containing a positive integer M (<=1000) which is the number of user’s search queries. Then M lines follow, each in one of the formats shown below:

1: a book title
2: name of an author
3: a key word
4: name of a publisher
5: a 4-digit number representing the year

Output Specification:

For each query, first print the original query in a line, then output the resulting book ID’s in increasing order, each occupying a line. If no book is found, print “Not Found” instead.

Sample Input:

3
1111111
The Testing Book
Yue Chen
test code debug sort keywords
ZUCS Print
2011
3333333
Another Testing Book
Yue Chen
test code sort keywords
ZUCS Print2
2012
2222222
The Testing Book
CYLL
keywords debug book
ZUCS Print2
2011
6
1: The Testing Book
2: Yue Chen
3: keywords
4: ZUCS Print
5: 2011
3: blablabla

Sample Output:

1: The Testing Book
1111111
2222222
2: Yue Chen
1111111
3333333
3: keywords
1111111
2222222
3333333
4: ZUCS Print
1111111
5: 2011
1111111
2222222
3: blablabla
Not Found

题目看起来信息量比较多，但简的来说，查找某个书的id，查找的条件可能是author, title或者其他的信息。使用map可以很方便的处理这个查找的过程，我这里创建几个map<string, set>类型的变量，用来存储某个author对应的id的集合，即某个作者可能写了多本书；某个title对应的id的集合，某个publisher对应的id的集合, etc。 在查询的时候，匹配查询条件，输出map中对应的书的所有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
55
56
57
58
59
60

#include <string>
#include <iostream>
#include <map>
#include <set>

using namespace std;

void print_ids(set<int> &ids) {
    bool flag = false;
    for (auto it = ids.begin(); it != ids.end(); it++) {
        printf("%07d\n", *it);
        flag = true;
    }
    if (!flag) printf("Not Found\n");
}

int main() {
    int n = 0, m = 0, k = 0, id = 0, publish_year = 0;
    string title, author, publisher, keyword;
    scanf("%d", &n);
    map<string, set<int>> author_m, title_m, publisher_m, publish_year_m, keyword_m;
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        getchar();
        getline(cin, title);
        getline(cin, author);
        while (cin >> keyword) {
            keyword_m[keyword].insert(id);
            if (getchar() == '\n') break;
        }
        getline(cin, publisher);
        scanf("%d", &publish_year);
        author_m[author].insert(id);
        title_m[title].insert(id);
        publisher_m[publisher].insert(id);
        publish_year_m[to_string(publish_year)].insert(id);
    }

    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d: ", &k);
        string str;
        getline(cin, str);
        printf("%d: %s\n", k, str.c_str());
        if (k == 1) {
            print_ids(title_m[str]);
        } else if (k == 2) {
            print_ids(author_m[str]);
        } else if (k == 3) {
            print_ids(keyword_m[str]);
        } else if (k == 4) {
            print_ids(publisher_m[str]);
        } else {
            print_ids(publish_year_m[str]);
        }
    }

    return 0;

}

Given a non-empty tree with root R, and with weight Wi assigned to each tree node Ti. The weight of a path from R to Lis defined to be the sum of the weights of all the nodes along the path from R to any leaf node L. Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let’s consider the tree showed in Figure 1: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in Figure.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 0 < N <= 100, the number of nodes in a tree, M (< N), the number of non-leaf nodes, and 0 < S < 230, the given weight number. The next line contains N positive numbers where Wi (<1000) corresponds to the tree node Ti. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]

where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 00.

Output Specification:

For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line. Note: sequence {A1, A2, …, An} is said to be greater than sequence {B1, B2, …, Bm} if there exists 1 <= k < min{n, m} such that Ai = Bifor i=1, … k, and Ak+1 > Bk+1.

Sample Input:

20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19

Sample Output:

10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2

树的遍历，用string保存它的路径，用深搜去求长度

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

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int *weight;
vector<vector<int> > tree;

bool cmp(int a, int b) {
    return weight[a] > weight[b];
}

void dfs(int node, string path, int s) {
    if (tree[node].size() == 0 && s == weight[node]) {
        path += " " + to_string(weight[node]);
        cout << path << endl;
        return;
    }
    for (int i = 0; i < tree[node].size(); i++) {
        dfs(tree[node][i], path + " " + to_string(weight[node]), s - weight[node]);
    }
}

int main() {
    int n = 0, m = 0, s = 0;
    scanf("%d %d %d", &n, &m, &s);
    weight = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight[i]);
    }
    tree.resize(n);
    for (int i = 0; i < m; i++) {
        int id = 0, k = 0;
        scanf("%d %d", &id, &k);
        tree[id].resize(k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &tree[id][j]);
        }
        sort(tree[id].begin(), tree[id].end(), cmp);
    }
    if (tree[0].size() == 0 && weight[0] == s) printf("%d", s);
    for (int i = 0; i < tree[0].size(); i++) {
        string path = to_string(weight[0]);
        dfs(tree[0][i], path, s - weight[0]);
    }
    delete[] weight;
    return 0;
}

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A “social cluster” is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (<=1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format: Ki: hi[1] hi[2] … hi[Ki] where Ki (>0) is the number of hobbies, and hi[j] is the index of the j-th hobby, which is an integer in [1, 1000].

Output Specification:

For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-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
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4

Sample Output:

3
4 3 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
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>
#include <vector>
#include <algorithm>

using namespace std;

int getFather(int *father, int x) {
    if (father[x] == x) return x;
    return getFather(father, father[x]);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    vector<vector<int> > hobbies(1001);
    for (int i = 1; i <= n; i++) {
        int k = 0;
        scanf("%d:", &k);
        for (int j = 0; j < k; j++) {
            int t = 0;
            scanf("%d", &t);
            hobbies[t].push_back(i);

        }

    }

    int *father = new int[n + 1];
    for (int i = 0; i <= n; i++) father[i] = i;
    for (int i = 1; i <= 1000; i++) {
        if (hobbies[i].size() != 0) {
            int v = getFather(father, hobbies[i][0]);
            for (int j = 1; j < hobbies[i].size();
                 j++) {
                int u = getFather(father, father[hobbies[i][j]]);
                if (v != u) father[u] = v;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        father[i] = getFather(father, i);
    }

    int *cluster = new int[n + 1];
    fill(cluster, cluster + n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cluster[father[i]]++;
    }

    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (cluster[i] > 0) ans.push_back(cluster[i]);
    }
    sort(ans.begin(), ans.end());

    printf("%ld\n", ans.size());
    for (auto i = ans.rbegin(); i != ans.rend(); i++) {
        if (i != ans.rbegin()) printf(" ");
        printf("%d", *i);

    }
    delete[] cluster;
    delete[] father;
    return 0;
}

According to Wikipedia: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining. Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. 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.

Sample Input 1:

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

Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:

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

Sample Output 2:

Merge Sort
1 2 3 8 4 5 7 9 0 6

插入排序和归并排序，首先判断是否是插入排序，就是检测前一部分是否是有序后一部分是和原来的序列相等的就行了，否则就是归并排序。归并排序主要的问题就是在于如何确定它是每几个元素归并的，我是用按照2，4， 8， 16….的次序去检测的

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

#include <cstdio>
#include <algorithm>

using namespace std;

bool isInsert(int *init, int *part, int n) {
    int i = 1;
    while (i < n && part[i] >= part[i - 1]) i++;
    while (i < n && init[i] == part[i]) i++;
    return i == n;
}

void insertSort(int *part, int n) {
    int i = 1;
    while (i < n && part[i] >= part[i - 1]) i++;
    sort(part, part + i + 1);
}

bool isEqual(int *a, int *b, int n) {
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

void mergeSort(int *init, int *part, int n) {
    int k = 2;
    for (k = 2; k < n; k = 2 * k) {
        int i = 0;
        for (i = 0; i + k < n; i += k) {
            sort(init + i, init + i + k);
        }
        sort(init + i, init + n);
        if (isEqual(part, init, n)) break;
    }
    k = 2 * k;
    int i = 0;
    for (i = 0; i + k < n; i += k) {
        sort(part + i, part + i + k);
    }
    sort(part + i, part + n);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    int *init = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &init[i]);
    }
    int *part = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &part[i]);
    }
    bool insert = isInsert(init, part, n);
    if (insert) {
        printf("Insertion Sort\n");
        insertSort(part, n);
        printf("%d", part[0]);
        for (int i = 1; i < n; i++) {
            printf(" %d", part[i]);
        }
    } else {
        printf("Merge Sort\n");
        mergeSort(init, part, n);
        printf("%d", part[0]);
        for (int i = 1; i < n; i++) {
            printf(" %d", part[i]);
        }
    }
    delete[] part;
    delete[] init;
    return 0;
}

According to Wikipedia: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum. Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. 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.

Sample Input 1:

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

Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:

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

Sample Output 2:

Heap Sort
5 4 3 1 0 2 6 7 8 9

首先判断是否是插入排序的，插入排序的判断就是判断前面一部分是否是有序的，后面的一部分的两个序列是否是相等的，如果满足条件则是插入排序，否则就是堆排序，然后写一下插入排序和堆排序就行了

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>

using namespace std;

bool isInsert(int *init, int *part, int n) {
    int i = 1;
    while (i < n && part[i] >= part[i - 1]) i++;
    while (i < n && part[i] == init[i]) i++;
    if (i == n) return true;
    return false;
}

void insertSort(int *part, int n) {
    int i = 1;
    while (i < n && part[i] >= part[i - 1]) i++;
    sort(part, part + i + 1);
}

void adjust(int *part, int cur, int n) {
    int max = cur;
    if (2 * cur + 1 < n && part[2 * cur + 1] > part[max]) max = 2 * cur + 1;
    if (2 * cur + 2 < n && part[2 * cur + 2] > part[max]) max = 2 * cur + 2;
    if (max != cur) {
        swap(part[max], part[cur]);
        adjust(part, max, n);
    }
}

void heapSort(int *part, int end) {
    while (end >= 0 && part[end] > part[0]) end--;
    swap(part[0], part[end]);
    adjust(part, 0, end);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    int *init = new int[n], *part = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &init[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &part[i]);
    }
    bool insert = isInsert(init, part, n);
    if (insert) {
        printf("Insertion Sort\n");
        insertSort(part, n);
        printf("%d", part[0]);
        for (int i = 1; i < n; i++) {
            printf(" %d", part[i]);
        }
    } else {
        printf("Heap Sort\n");
        heapSort(part, n - 1);
        printf("%d", part[0]);
        for (int i = 1; i < n; i++) {
            printf(" %d", part[i]);
        }
    }
    delete[] part;
    delete[] init;
    return 0;
}