30 | 5月 | 2018 | 超客的水墨烟雨

uva297

maksyuki 发表于 oj 分类，标签: 数据结构-二叉树

30 5月 2018

A quadtree is a representation format used to encode images. The fundamental idea behind the quadtree is that any image can be split into four quadrants. Each quadrant may again be split in four sub quadrants, etc. In the quadtree, the image is represented by a parent node, while the four quadrants are represented by four child nodes, in a predetermined order.

Of course, if the whole image is a single color, it can be represented by a quadtree consisting of a single node. In general, a quadrant needs only to be subdivided if it consists of pixels of different colors. As a result, the quadtree need not be of uniform depth.

A modern computer artist works with black-and-white images of 32 × 32 units, for a total of 1024 pixels per image. One of the operations he performs is adding two images together, to form a new image. In the resulting image a pixel is black if it was black in at least one of the component images, otherwise it is white.

This particular artist believes in what he calls the preferred fullness: for an image to be interesting (i.e. to sell for big bucks) the most important property is the number of filled (black) pixels in the image. So, before adding two images together, he would like to know how many pixels will be black in the resulting image. Your job is to write a program that, given the quadtree representation of two images, calculates the number of pixels that are black in the image, which is the result of adding the two images together.

In the figure, the first example is shown (from top to bottom) as image, quadtree, pre-order string (defined below) and number of pixels. The quadrant numbering is shown at the top of the figure.

Input

The first line of input specifies the number of test cases (N) your program has to process.

The input for each test case is two strings, each string on its own line. The string is the pre-order representation of a quadtree, in which the letter ‘p’ indicates a parent node, the letter ‘f’ (full) a black quadrant and the letter ‘e’ (empty) a white quadrant. It is guaranteed that each string represents a valid quadtree, while the depth of the tree is not more than 5 (because each pixel has only one color).

Output

For each test case, print on one line the text ‘There are X black pixels.’, where X is the number of black pixels in the resulting image.

Sample Input

3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe

Sample Output

There are 640 black pixels.

There are 512 black pixels.

There are 384 black pixels.

题目类型：二叉树递归遍历

算法分析：按照先序遍历的顺序构建，当遇到叶子节点'f'时，直接将其所包含的像素中仍没有计算过的累加起来

/**************************************************
filename       :d.cpp
author         :maksyuki
created time   :2018/5/30 16:27:56
last modified  :2018/5/30 16:59:27
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 32 + 6;

bool color[maxn][maxn];
int ans;
string s;

void draw(int &pos, int x, int y, int h) {
    if(!s[pos]) return;
    char ch = s[pos++];
    if(ch == 'p') {
        draw(pos, x, y + h / 2, h / 2);
        draw(pos, x, y, h / 2);
        draw(pos, x + h / 2, y, h / 2);
        draw(pos, x + h / 2, y + h / 2, h / 2);
    }
    else if(ch == 'f') {
        for(int i = x; i < x + h; i++)
            for(int j = y; j < y + h; j++)
                if(!color[i][j]) {
                    color[i][j] = true;
                    ans++;
                }
    }
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t;
    cin >> t;
    while(t--) {
        memset(color, false, sizeof(color));
        ans = 0;
        for(int i = 1; i <= 2; i++) {
            cin >> s;
            int len = 32, p = 0;
            draw(p, 0, 0, len);
        }
        
        cout << "There are " << ans << " black pixels." << endl;
    }
    return 0;
}

100

101

102

103

104

105

/**************************************************

filename :d.cpp

author :maksyuki

created time :2018/5/30 16:27:56

last modified :2018/5/30 16:59:27

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 32 + 6;

bool color[maxn][maxn];

int ans;

string s;

void draw(int &pos, int x, int y, int h) {

if(!s[pos]) return;

char ch = s[pos++];

if(ch == 'p') {

draw(pos, x, y + h / 2, h / 2);

draw(pos, x, y, h / 2);

draw(pos, x + h / 2, y, h / 2);

draw(pos, x + h / 2, y + h / 2, h / 2);

}

else if(ch == 'f') {

for(int i = x; i < x + h; i++)

for(int j = y; j < y + h; j++)

if(!color[i][j]) {

color[i][j] = true;

ans++;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t;

cin >> t;

while(t--) {

memset(color, false, sizeof(color));

ans = 0;

for(int i = 1; i <= 2; i++) {

cin >> s;

int len = 32, p = 0;

draw(p, 0, 0, len);

}

cout << "There are " << ans << " black pixels." << endl;

}

return 0;

}

uva699

maksyuki 发表于 oj 分类，标签: 数据结构-二叉树

30 5月 2018

Each year, fall in the North Central region is accompanied by the brilliant colors of the leaves on the trees, followed quickly by the falling leaves accumulating under the trees. If the same thing happened to binary trees, how large would the piles of leaves become?

We assume each node in a binary tree ”drops” a number of leaves equal to the integer value stored in that node. We also assume that these leaves drop vertically to the ground (thankfully, there’s no wind to blow them around). Finally, we assume that the nodes are positioned horizontally in such a manner that the left and right children of a node are exactly one unit to the left and one unit to the right, respectively, of their parent. Consider the following tree on the right:

The nodes containing 5 and 6 have the same horizontal position (with different vertical positions, of course). The node containing 7 is one unit to the left of those containing 5 and 6, and the node containing 3 is one unit to their right. When the ”leaves” drop from these nodes, three piles are created: the leftmost one contains 7 leaves (from the leftmost node), the next contains 11 (from the nodes containing 5 and 6), and the rightmost pile contains 3. (While it is true that only leaf nodes in a tree would logically have leaves, we ignore that in this problem.)

Input

The input contains multiple test cases, each describing a single tree. A tree is specified by giving the value in the root node, followed by the description of the left subtree, and then the description of the right subtree. If a subtree is empty, the value ‘-1’ is supplied. Thus the tree shown above is specified as ‘5 7 -1 6 -1 -1 3 -1 -1’. Each actual tree node contains a positive, non-zero value. The last test case is followed by a single ‘-1’ (which would otherwise represent an empty tree).

Output

For each test case, display the case number (they are numbered sequentially, starting with 1) on a line by itself. On the next line display the number of “leaves” in each pile, from left to right, with a single space separating each value. This display must start in column 1, and will not exceed the width of an 80-character line. Follow the output for each case by a blank line. This format is illustrated in the examples below.

Sample Input

5 7 -1 6 -1 -1 3 -1 -1
8 2 9 -1 -1 6 5 -1 -1 12 -1
-1 3 7 -1 -1 -1
-1

Sample Output

Case 1:

7 11 3

Case 2:

9 7 21 15

题目类型：二叉树递归遍历

算法分析：按照先序遍历建树并更新结果，注意这里对输入的处理

/**************************************************
filename       :c.cpp
author         :maksyuki
created time   :2018/5/30 16:07:54
last modified  :2018/5/30 16:20:33
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 166;

int sum[maxn], id = 1;

void build(int rt, int pos) {
    sum[pos] += rt;    
    int va, vb;
    cin >> va;
    if(va != -1) build(va, pos - 1);
    cin >> vb;
    if(vb != -1) build(vb, pos + 1);
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int rt;
    while(cin >> rt) {
        if(rt == -1) break;
        
        memset(sum, 0, sizeof(sum));
        build(rt, maxn / 2);

        cout << "Case " << id++ << ":" << endl;

        bool is_first = true;
        for(int i = 0; i < maxn; i++)
            if(sum[i]) {
                if(is_first) {
                    is_first = false;
                    cout << sum[i];
                }
                else cout << " " << sum[i];
            }
        cout << endl << endl;
    }
    return 0;
}

100

/**************************************************

filename :c.cpp

author :maksyuki

created time :2018/5/30 16:07:54

last modified :2018/5/30 16:20:33

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 166;

int sum[maxn], id = 1;

void build(int rt, int pos) {

sum[pos] += rt;

int va, vb;

cin >> va;

if(va != -1) build(va, pos - 1);

cin >> vb;

if(vb != -1) build(vb, pos + 1);

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int rt;

while(cin >> rt) {

if(rt == -1) break;

memset(sum, 0, sizeof(sum));

build(rt, maxn / 2);

cout << "Case " << id++ << ":" << endl;

bool is_first = true;

for(int i = 0; i < maxn; i++)

if(sum[i]) {

if(is_first) {

is_first = false;

cout << sum[i];

}

else cout << " " << sum[i];

}

cout << endl << endl;

}

return 0;

}

uva839

maksyuki 发表于 oj 分类，标签: 数据结构-二叉树

30 5月 2018

Before being an ubiquous communications gadget, a mobile was just a structure made of strings and wires suspending colourfull things. This kind of mobile is usually found hanging over cradles of small babies.

The figure illustrates a simple mobile. It is just a wire, suspended by a string, with an object on each side. It can also be seen as a kind of lever with the fulcrum on the point where the string ties the wire. From the lever principle we know that to balance a simple mobile the product of the weight of the objects by their distance to the fulcrum must be equal. That is Wl × Dl = Wr × Dr where Dl is the left distance, Dr is the right distance, Wl is the left weight and Wr is the right weight.

In a more complex mobile the object may be replaced by a sub-mobile, as shown in the next figure. In this case it is not so straightforward to check if the mobile is balanced so we need you to write a program that, given a description of a mobile as input, checks whether the mobile is in equilibrium or not.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input is composed of several lines, each containing 4 integers separated by a single space. The 4 integers represent the distances of each object to the fulcrum and their weights, in the format: Wl Dl Wr Dr

If Wl or Wr is zero then there is a sub-mobile hanging from that end and the following lines define the the sub-mobile. In this case we compute the weight of the sub-mobile as the sum of weights of all its objects, disregarding the weight of the wires and strings. If both Wl and Wr are zero then the following lines define two sub-mobiles: first the left then the right one.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. Write ‘YES’ if the mobile is in equilibrium, write ‘NO’ otherwise.

Sample Input

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

Sample Output

YES

题目类型：二叉树递归遍历

算法分析：按照后序遍历判断是否满足条件，注意这里对输入的处理

/**************************************************
filename       :b.cpp
author         :maksyuki
created time   :2018/5/30 15:26:50
last modified  :2018/5/30 15:52:28
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

bool solve(int &w) {
    int d1, w1, d2, w2;
    bool ls = true, rs = true;
    cin >> w1 >> d1 >> w2 >> d2;
    if(!w1) ls = solve(w1);
    if(!w2) rs = solve(w2);
    
    w = w1 + w2;

    return ls && rs && (w1 * d1 == w2 * d2);
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
   
    int t;
    cin >> t;
    while(t--) {
        int w;
        if(solve(w)) cout << "YES" << endl;
        else cout << "NO" << endl;

        if(t) cout << endl;
    }
    return 0;
}

/**************************************************

filename :b.cpp

author :maksyuki

created time :2018/5/30 15:26:50

last modified :2018/5/30 15:52:28

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

bool solve(int &w) {

int d1, w1, d2, w2;

bool ls = true, rs = true;

cin >> w1 >> d1 >> w2 >> d2;

if(!w1) ls = solve(w1);

if(!w2) rs = solve(w2);

w = w1 + w2;

return ls && rs && (w1 * d1 == w2 * d2);

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t;

cin >> t;

while(t--) {

int w;

if(solve(w)) cout << "YES" << endl;

else cout << "NO" << endl;

if(t) cout << endl;

}

return 0;

}

uva548

maksyuki 发表于 oj 分类，标签: 数据结构-二叉树

30 5月 2018

You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.

Input

The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.

Output

For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.

Sample Input

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

Sample Output

255

题目类型：二叉树递归遍历

算法分析：按照题目要求使用二叉树的中序遍历和后序遍历来建树，然后使用DFS计算出题目中的最小叶子。注意递归建树时的边界条件和每次DFS递归中的实参的值

/**************************************************
filename       :a.cpp
author         :maksyuki
created time   :2018/5/30 14:48:06
last modified  :2018/5/30 15:15:42
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int lch[maxn], rch[maxn], in[maxn], post[maxn];
int cnt, minval, pos;

int build(int l1, int r1, int l2, int r2) {
    if(l1 > r1) return 0;
    int rt = post[r2];
    int p = l1;
    while(in[p] != rt) p++;

    int pp = p - l1;
    lch[rt] = build(l1, p - 1, l2, l2 + pp - 1);
    rch[rt] = build(p + 1, r1, l2 + pp, r2 - 1);
    return rt;
}

void dfs(int rt, int sum) {
    sum += rt;
    if(!lch[rt] && !rch[rt]) {
        if(sum < minval || (sum == minval && rt < pos)) {
            minval = sum;
            pos = rt;
        }
    }
    if(lch[rt]) dfs(lch[rt], sum);
    if(rch[rt]) dfs(rch[rt], sum);
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    string sa, sb;
    while(getline(cin, sa)) {
        getline(cin, sb);
        memset(lch, -1, sizeof(lch));
        memset(rch, -1, sizeof(rch));

        stringstream ssa(sa);
        int tmp;
        cnt = 0;
        while(ssa >> tmp) {
            in[cnt++] = tmp;
        }
        
       stringstream ssb(sb);
        int i = 0;
        while(ssb >> tmp) {
            post[i++] = tmp;
        }

        build(0, cnt - 1, 0, cnt - 1);
        
        minval = INF, pos = -1;
        dfs(post[cnt-1], 0);
        
        cout << pos << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

/**************************************************

filename :a.cpp

author :maksyuki

created time :2018/5/30 14:48:06

last modified :2018/5/30 15:15:42

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int lch[maxn], rch[maxn], in[maxn], post[maxn];

int cnt, minval, pos;

int build(int l1, int r1, int l2, int r2) {

if(l1 > r1) return 0;

int rt = post[r2];

int p = l1;

while(in[p] != rt) p++;

int pp = p - l1;

lch[rt] = build(l1, p - 1, l2, l2 + pp - 1);

rch[rt] = build(p + 1, r1, l2 + pp, r2 - 1);

return rt;

}

void dfs(int rt, int sum) {

sum += rt;

if(!lch[rt] && !rch[rt]) {

if(sum < minval || (sum == minval && rt < pos)) {

minval = sum;

pos = rt;

}

if(lch[rt]) dfs(lch[rt], sum);

if(rch[rt]) dfs(rch[rt], sum);

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

string sa, sb;

while(getline(cin, sa)) {

getline(cin, sb);

memset(lch, -1, sizeof(lch));

memset(rch, -1, sizeof(rch));

stringstream ssa(sa);

int tmp;

cnt = 0;

while(ssa >> tmp) {

in[cnt++] = tmp;

}

stringstream ssb(sb);

int i = 0;

while(ssb >> tmp) {

post[i++] = tmp;

}

build(0, cnt - 1, 0, cnt - 1);

minval = INF, pos = -1;

dfs(post[cnt-1], 0);

cout << pos << endl;

}

return 0;

}

超客的水墨烟雨

uva297

uva699

uva839

uva548

分类目录

标签云

书签

近期评论

2018年5月
一	二	三	四	五	六	日
« 1月				6月 »
	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