hdvsyu's blog

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1. Then N lines follow, each describes a node in the format: Address Data Next where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

给定一个链表，每K个翻转一下，最后输出。 给定的地址都是5位数的，可以开一个10w的数组，通过数组索引可以很方便的找到结点的下一个结点，调用reserse方法可以将指定的地址进行逆序翻转，最后得到翻转后的链表，格式化输出。 代码如下：

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

using namespace std;

struct Node {
    int address, data, next;
};

int main() {
    int head = 0, n = 0, k = 0;
    scanf("%d %d %d", &head, &n, &k);
    vector<struct Node> v(100000);
    for (int i = 0; i < n; i++) {
        struct Node node;
        scanf("%d %d %d", &node.address, &node.data, &node.next);
        v[node.address] = node;
    }

    vector<struct Node> nodes;
    for (int i = 0; head != -1; i++) {
        nodes.push_back(v[head]);
        head = v[head].next;
    }

    k = k > nodes.size() ? k % nodes.size() : k;
    for (int i = 0; i <= nodes.size() - k; i += k) {
        reverse(nodes.begin() + i, nodes.begin() + i + k);
    }

    for (int i = 0; i < nodes.size(); i++) {
        if (i != nodes.size() - 1) {
            printf("%05d %d %05d\n", nodes[i].address, nodes[i].data, nodes[i + 1].address);
        } else {
            printf("%05d %d -1\n", nodes[i].address, nodes[i].data);
        }
    }
    return 0;
}

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive N (< 105) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by -1. Then N lines follow, each describes a node in the format: Address Key Next where Address is the address of the node in memory, Key is an integer in [-105, 105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.

Sample Input:

5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345

Sample Output:

5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1

给定一系列结点，要求将它排序。 题目给出的结点是以5位数的头地址和5位数的尾地址组成的，所以开一个10w的数组，根据数组的下标索引可以很方便的找到结点的下一个结点。 代码如下：

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

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

struct Node {
    int key, address, next;
};

int main() {
    int n = 0, head = 0, m = 0;
    scanf("%d %d", &n, &head);
    vector<struct Node> v(100000);
    for (int i = 0; i < n; i++) {
        struct Node t;
        scanf("%d %d %d", &t.address, &t.key, &t.next);
        v[t.address] = t;
    }
    struct Node *nodes = new struct Node[n];
    for (int i = 0; head != -1; i++) {
        nodes[m++] = v[head];
        head = v[head].next;
    }
    qsort(nodes, m, sizeof(nodes[0]), [](const void *a, const void *b) {
        const struct Node arg1 = *static_cast<const struct Node *>(a);
        const struct Node arg2 = *static_cast<const struct Node *>(b);

        if (arg1.key > arg2.key) return 1;
        return -1;
    });

    if (m != 0) {
        printf("%d %05d\n", m, nodes[0].address);
        for (int i = 0; i < m; i++) {
            if (i != m - 1)
                printf("%05d %d %05d\n", nodes[i].address, nodes[i].key, nodes[i + 1].address);
            else
                printf("%05d %d -1\n", nodes[i].address, nodes[i].key);
        }
    } else {
        cout << 0 << " -1";
    }
    delete[] nodes;
    return 0;
}

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18→7→-4→0→5→-6→10→11→-2 and K being 10, you must output -4→-6→-2→7→0→5→10→18→11.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=1000). The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1. Then N lines follow, each describes a node in the format: Address Data Next where Address is the position of the node, Data is an integer in [-105, 105], and Next is the position of the next node. It is guaranteed that the list is not empty.

Output Specification:

For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

Sample Output:

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

把链表分成三个部分，小于的一部分，大于0小于等于k的一部分，大于k的一部分。 和前面集体LinkList的处理方式相同，采用5位数的数组来定位数组的地址。

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

using namespace std;

struct node {
    int first, value, next;
};

vector<node> neg, lesser, greater;

void spit(node *nodes, int first, int k) {
    while (first != -1) {
        if (nodes[first].value < 0) {
            neg.push_back(nodes[first]);
        } else if (nodes[first].value <= k) {
            lesser.push_back(nodes[first]);
        } else {
            greater.push_back(nodes[first]);
        }
        first = nodes[first].next;
    }
}

vector<node> ans;

void merge() {
    ans = neg;
    for (int i = 0; i < lesser.size(); i++) {
        ans.push_back(lesser[i]);
    }
    for (int i = 0; i < greater.size(); i++) {
        ans.push_back(greater[i]);
    }
}

void printAns() {
    int i = 0;
    for (; i < ans.size() - 1; i++) {
        printf("%05d %d %05d\n", ans[i].first, ans[i].value, ans[i + 1].first);
    }
    printf("%05d %d -1\n", ans[i].first, ans[i].value);
}

int main() {
    int first = 0, n = 0, k = 0, temp = 0;
    scanf("%d %d %d", &first, &n, &k);
    node nodes[100000];
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        scanf("%d %d", &nodes[temp].value, &nodes[temp].next);
        nodes[temp].first = temp;
    }
    spit(nodes, first, k);
    merge();
    printAns();

    return 0;

}

Cutting an integer means to cut a K digits long integer Z into two integers of (K/2) digits long integers A and B. For example, after cutting Z = 167334, we have A = 167 and B = 334. It is interesting to see that Z can be devided by the product of A and B, as 167334 / (167 x 334) = 3. Given an integer Z, you are supposed to test if it is such an integer.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 20). Then N lines follow, each gives an integer Z (10<=Z<=231). It is guaranteed that the number of digits of Z is an even number.

Output Specification:

For each case, print a single line “Yes” if it is such a number, or “No” if not.

Sample Input:

3
167334
2333
12345678

Sample Output:

Yes
No
No

给定一个数字，将这个数字分成两端，判断两端的乘积能够被给定的数字整除 代码如下：

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

#include <cstdio>
#include <cstring>

int toInt(char *z, int s, int e) {
    int num = 0;
    for (int i = s; i <= e; i++) {
        num = num * 10 + z[i] - '0';
    }
    return num;
}

int main() {
    int n = 0;
    scanf("%d", &n);
    char z[30];
    for (int i = 0; i < n; i++) {
        scanf("%s", z);
        int znum = toInt(z, 0, strlen(z) - 1);
        int a = toInt(z, 0, strlen(z) / 2 - 1);
        int b = toInt(z, strlen(z) / 2, strlen(z) - 1);
        if ((a * b != 0) && znum % (a * b) == 0) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (<=230).

Output Specification:

For each test case, print the number of 1’s in one line.

Sample Input:

12

Sample Output:

5

对于一个n为的数字，每次只考虑其中的一位，对于这一位可以产生多少一个1进行讨论。 假设给定一个数字为21087 考虑数字7，对于7这个位置要产生1，只有(0000-2108) 1 ，产生2109个1 考虑数字8，对于7这个位置要产生8，只有(000-210) 1 (0-9)，有2110个1 考虑数字0，对于0这个位置要产生1，那么只有(00-20) 1 (00-99) ，所以一共有21 * 100 = 2100个1 考虑数字1，对于1这个位置，有(0-1) 1 (000-999)和21(000-087)，共有2 * 1000 + 88 = 2088个1 考虑数字2，对于2这个位置要产生1，有1 (0000-9999) 共有10000个1 对于数字3，则一共产生18407个1 更一般地： 假设now是一个n位数的第now位，对now位置上面的数字进行讨论，cur是now在n位数的数位，left表示now左边的数字，right表示右边的数字，可得： 如何now位置的数字是0，那么可以产生left * cur个1 如何now位置的数字是1，那么可以产生left * cur + right + 1个1 否则，可以产生(left + 1) * cur个1 根据上面的算法描述，可以得到代码如下：

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

#include <cstdio>

int main() {
    int n = 0, cur = 1, left = 0, right = 0, now = 0, ans = 0;
    scanf("%d", &n);
    while (n / cur != 0) {
        left = n / (cur * 10);
        right = n % cur;
        now = n % (cur * 10) / cur;
        if (now == 0) {
            ans += left * cur;
        } else if (now == 1) {
            ans += left * cur + right + 1;
        } else {
            ans += (left + 1) * cur;
        }
        cur *= 10;
    }
    printf("%d\n", ans);
}

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample Output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

The maximum travel distance = 1200.00

用贪心算法求解
假设增加一个目的地处的加油站，距离为目的地的距离，价格为0，考虑从0距离开始能否到达最后一个加油站的问题
因为先开始没有油，所以如果所有的加油站距离都没有等于0的，那么说明车哪也去不了，直接输出并return
将加油站按照距离dis从小到大排序3.先去第一个加油站，设置变量nowdis表示当前所在的距离，maxdis是能够到达的最大距离，nowprice是当前的站点的价格，totalPrice是总的价格。

reference: https://www.liuchuo.net/archives/2461

case 2 是起点就是终点，这个时候应该是花费为0.00而不是最远距离为0.00
case 4 是终点有加油站，并且这个加油站的价格比较高，这样会导致你加满油达到终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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

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

using namespace std;

struct sta {
    double dis, price;

    sta(int d, double p) {
        dis = d;
        price = p;
    }
};

vector<struct sta> gas;

bool cmp(sta a, sta b) {
    return a.dis < b.dis;
}

int findLower(int cur, int cmax, int davg) {
    for (int i = cur + 1; i < gas.size() && gas[i].dis - gas[cur].dis <= cmax * davg; i++) {
        if (gas[cur].price >= gas[i].price) {
            return i;
        }
    }
    return -1;
}

int findMin(int cur, int cmax, int davg) {
    int inf = 999999, min = 0;
    for (int i = cur + 1; i < gas.size() && gas[i].dis - gas[cur].dis <= cmax * davg; i++) {
        if (gas[i].price < inf) {
            min = i;
            inf = gas[i].price;
        }
    }
    if (inf == 999999) return -1;
    else return min;
}

int main() {
    int n = 0, cur = 0;
    double cmax = 0, d = 0, davg = 0, p = 0, temp = 0, tank = 0, total = 0;
    scanf("%lf %lf %lf %d", &cmax, &d, &davg, &n);

    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &p, &temp);
        if (temp == d) gas.push_back(sta(temp, 0));
        else gas.push_back(sta(temp, p));
    }

    sort(gas.begin(), gas.end(), cmp);

    if (gas[0].dis != 0) {
        printf("The maximum travel distance = 0.00");
        return 0;
    }

    while (true) {
        int low = findLower(cur, cmax, davg);
        if (low == -1) {
            low = findMin(cur, cmax, davg);
            if (low == -1) {
                break;
            } else {
                total += (cmax - tank) * gas[cur].price;
                tank = cmax - (gas[low].dis - gas[cur].dis) * 1.0 / davg;
            }
        } else {
            if ((gas[low].dis - gas[cur].dis) * 1.0 / davg >= tank) {
                total += gas[cur].price * ((gas[low].dis - gas[cur].dis) * 1.0 / davg - tank);
                tank = 0;
            } else {
                tank -= (gas[low].dis - gas[cur].dis) * 1.0 / davg;
            }
        }
        cur = low;
    }

    if (gas[cur].dis + cmax * davg < d) {
        printf("The maximum travel distance = %.2f", gas[cur].dis + cmax * davg);
    } else {
        printf("%.2f", total + gas[cur].price * ((d - gas[cur].dis) * 1.0 / davg) - tank);
    }
    return 0;
}

批改多选题是比较麻烦的事情，本题就请你写个程序帮助老师批改多选题，并且指出哪道题错的人最多。

输入格式：

输入在第一行给出两个正整数N（<=1000）和M（<=100），分别是学生人数和多选题的个数。随后M行，每行顺次给出一道题的满分值（不超过5的正整数）、选项个数（不少于2且不超过5的正整数）、正确选项个数（不超过选项个数的正整数）、所有正确选项。注意每题的选项从小写英文字母a开始顺次排列。各项间以1个空格分隔。最后N行，每行给出一个学生的答题情况，其每题答案格式为“(选中的选项个数 选项1 ……)”，按题目顺序给出。注意：题目保证学生的答题情况是合法的，即不存在选中的选项数超过实际选项数的情况。

输出格式：

按照输入的顺序给出每个学生的得分，每个分数占一行。注意判题时只有选择全部正确才能得到该题的分数。最后一行输出错得最多的题目的错误次数和编号（题目按照输入的顺序从1开始编号）。如果有并列，则按编号递增顺序输出。数字间用空格分隔，行首尾不得有多余空格。如果所有题目都没有人错，则在最后一行输出“Too simple”。

输入样例：

3 4
3 4 2 a c
2 5 1 b
5 3 2 b c
1 5 4 a b d e
(2 a c) (2 b d) (2 a c) (3 a b e)
(2 a c) (1 b) (2 a b) (4 a b d e)
(2 b d) (1 e) (2 b c) (4 a b c d)

输出样例：

3
6
5
2 2 3 4

用个结构体存储每个题目的信息，然后提取出每个学生的选项，判定学生的选项是否和答案是相等的，否则就做相应的处理

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

#include <cstdio>

struct Item {
    int score, unit, t;
    char *choose = new char[6];
};

bool equal(const struct Item &a, const struct Item &b) {
    if (a.t != b.t) return false;
    for (int i = 0; i < a.t; i++) {
        if (a.choose[i] != b.choose[i]) return false;
    }
    return true;
}

int main() {
    int n = 0, m = 0;
    scanf("%d %d", &n, &m);
    struct Item *items = new struct Item[m];
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &items[i].score, &items[i].unit, &items[i].t);
        for (int j = 0; j < items[i].t; j++) {
            scanf(" %c", &items[i].choose[j]);
        }
    }

    int *error = new int[m];
    int maxValue = -1;
    for (int i = 0; i < n; i++) {
        int score = 0;
        for (int j = 0; j < m; j++) {
            struct Item s;
            char c = getchar();
            c = getchar();
            scanf("%d", &s.t);
            for (int k = 0; k < s.t; k++) {
                c = getchar();
                scanf("%c", &s.choose[k]);
            }
            c = getchar();
            if (equal(items[j], s)) score += items[j].score;
            else {
                error[j]++;
                if (error[j] > maxValue) maxValue = error[j];
            }
        }
        printf("%d\n", score);
    }

    if (maxValue == -1) {
        printf("Too simple");
    } else {
        printf("%d", maxValue);
        for (int i = 0; i < m; i++) {
            if (error[i] == maxValue) {
                printf(" %d", i + 1);
            }
        }
    }
    delete[] items;
    delete[] error;
    return 0;
}

给定一串长度不超过105的字符串，本题要求你将其中所有英文字母的序号（字母a-z对应序号1-26，不分大小写）相加，得到整数N，然后再分析一下N的二进制表示中有多少0、多少1。例如给定字符串“PAT (Basic)”，其字母序号之和为：16+1+20+2+1+19+9+3=71，而71的二进制是1000111，即有3个0、4个1。

输入格式：

输入在一行中给出长度不超过105、以回车结束的字符串。

输出格式：

在一行中先后输出0的个数和1的个数，其间以空格分隔。

输入样例：

PAT (Basic)

输出样例：

3 4

先把所有的字母的序号加起来，然后求二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <cstdio>
#include <cctype>
#include <cstring>

int main() {
    char s[100010];
    gets(s);
    int sum = 0;
    for (int i = 0; i < strlen(s); i++) {
        if (isupper(s[i])) {
            sum += s[i] - 'A' + 1;
        } else if (islower(s[i])) {
            sum += s[i] - 'a' + 1;
        }
    }
    int one = 0, zero = 0;
    while (sum != 0) {
        one += sum % 2;
        zero += sum % 2 == 0;
        sum /= 2;
    };
    printf("%d %d", zero, one);
    return 0;
}

给定N个非0的个位数字，用其中任意2个数字都可以组合成1个2位的数字。要求所有可能组合出来的2位数字的和。例如给定2、5、8，则可以组合出：25、28、52、58、82、85，它们的和为330。

输入格式：

输入在一行中先给出N（1<N<10），随后是N个不同的非0个位数字。数字间以空格分隔。

输出格式：

输出所有可能组合出来的2位数字的和。

输入样例：

3 2 8 5

输出样例：

330

可以发现，每个数字必然出现在十位n-1次，出现在个位n-1次，由此就可以得到sum += (num * 10 + num) * (n - 1)了

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

#include <cstdio>

int main() {
    int n = 0, sum = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int t = 0;
        scanf("%d", &t);
        sum += (t * 10 + t) * (n - 1);
    }
    printf("%d", sum);
    return 0;
}

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the corresponding tree may no longer be unique. Now given a pair of postorder and preorder traversal sequences, you are supposed to output the corresponding inorder traversal sequence of the tree. If the tree is not unique, simply output any one of them.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first printf in a line “Yes” if the tree is unique, or “No” if not. Then print in the next line the inorder traversal sequence of the corresponding binary tree. If the solution is not unique, any answer would do. It is guaranteed that at least one solution exists. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input 1:

7
1 2 3 4 6 7 5
2 6 7 4 5 3 1

Sample Output 1:

Yes
2 1 6 4 7 3 5

Sample Input 2:

4
1 2 3 4
2 4 3 1

Sample Output 2:

No
2 1 3 4

用unique标记是否唯一，如果为1就表示中序是唯一的。 已知二叉树的前序和后序是无法唯一确定一颗二叉树的，因为可能会存在多种情况，这种情况就是一个结点可能是根的左孩子也有可能是根的右孩子，如果发现了一个无法确定的状态，置unique = 0，又因为题目只需要输出一个方案，可以假定这个不可确定的孩子的状态是右孩子，接下来的问题是如何求根结点和左右孩子划分的问题了，首先我们需要知道树的表示范围，需要四个变量，分别是前序的开始的地方prel，前序结束的地方prer，后序开始的地方postl，后序结束的地方postr，前序的开始的第一个应该是后序的最后一个是相等的，这个结点就是根结点，以后序的根结点的前面一个结点作为参考，寻找这个结点在前序的位置，就可以根据这个位置来划分左右孩子，递归处理。

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

#include <cstdio>
#include <vector>

using namespace std;
vector<int> ans;
int *pre, *post, unique = 1;

int findFromPre(int x, int l, int r) {
    for (int i = l; i <= r; i++) {
        if (x == pre[i]) {
            return i;
        }
    }
    return -1;
}

void setIn(int prel, int prer, int postl, int postr) {
    if (prel == prer) {
        ans.push_back(pre[prel]);
        return;
    }
    if (pre[prel] == post[postr]) {
        int x = findFromPre(post[postr - 1], prel + 1, prer);
        if (x - prel > 1) {
            setIn(prel + 1, x - 1, postl, postl + x - prel - 2);
            ans.push_back(post[postr]);
            setIn(x, prer, postl + x - prel - 2 + 1, postr - 1);
        } else {
            unique = 0;
            ans.push_back(post[postr]);
            setIn(x, prer, postl + x - prel - 2 + 1, postr - 1);
        }
    }
}

int main() {
    int n = 0;
    scanf("%d", &n);
    pre = new int[n];
    post = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &post[i]);
    }
    setIn(0, n - 1, 0, n - 1);
    printf("%s\n", unique ? "Yes" : "No");
    printf("%d", ans[0]);
    for (int i = 1; i < ans.size(); i++) {
        printf(" %d", ans[i]);
    }
    printf("\n");
    return 0;
}