Maples' Space

树和二叉树刷题

Posted on In 4.3k 4 mins.
树和二叉树刷题记录。题单：https://vjudge.net/contest/246458#overview

A. Dropping Balls

uva-122

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
// uva-679
// 树 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int l; scanf("%d", &l);
    for (int i = 1; i <= l; i++) {
        int D, I;
        scanf("%d%d", &D, &I);
        int k = 1;
        for (int i = 1; i <= D-1; i++) {
            if (I % 2 == 1) {
                I = (I + 1) / 2;
                k = k << 1;
            }
            else {
                I = I / 2;
                k = k << 1 | 1;
            }
        }
        printf("%d\n", k);
    }
    int end; scanf("%d", &end);
    
    return 0;
}

C. Tree

uva-548

数组构建二叉树，dfs遍历二叉树。涉及StringStream的使用。

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
// uva-548
// tree, dfs, stringstream
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e4 + 5;
int inorder[maxn];
int postorder[maxn];
int ltree[maxn];
int rtree[maxn];
int n;
int best, best_sum;

bool readline(int *a)
{
    string line;
    if (!getline(cin, line)) return false;
    stringstream ss(line);
    n = 0;
    int x;
    while (ss >> x) a[n++] = x;
    return n > 0;
}

// inorder[l1...r1] and postorder[l2, r2]
int build(int l1, int r1, int l2, int r2)
{
    if (l1 > r1) return 0;
    int root = postorder[r2];
    int p = l1;
    while (inorder[p] != root) p++;
    int cnt = p - l1;
    ltree[root] = build(l1, p - 1, l2, l2 + cnt - 1);
    rtree[root] = build(p + 1, r1, l2 + cnt, r2 - 1);
    return root;
}

void dfs(int now, int sum)
{
    sum += now;
    if (!ltree[now] && !rtree[now]) {
        if (sum < best_sum || (sum == best_sum && now < best)) {
            best = now;
            best_sum = sum;
        }
    }
    if (ltree[now]) {
        dfs(ltree[now], sum);
    }
    if (rtree[now]) {
        dfs(rtree[now], sum);
    }
}

int main()
{
    while (readline(inorder)) {
        readline(postorder);
        memset(ltree, 0, sizeof(ltree));
        memset(rtree, 0, sizeof(rtree));
        build(0, n - 1, 0, n - 1);
        best_sum = 0x3f3f3f;
        dfs(postorder[n - 1], 0);
        cout << best << endl;
    }
    
    return 0;
}

D. Not so Mobile

uva-839

也不算树？递归，函数传引用。

（话说文件输入真好用，我怎么之前没用呢……

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
#include <bits/stdc++.h>
using namespace std;

bool solve(int &w)
{
    int wl, dl, wr, dr;
    scanf("%d%d%d%d", &wl, &dl, &wr, &dr);
    bool b1 = true;
    bool b2 = true;
    if (!wl) b1 = solve(wl);
    if (!wr) b2 = solve(wr);
    w = wl + wr;
    return b1 && b2 && (wl * dl == wr * dr);
}

int main()
{
//    freopen("./data/d/1.in", "r", stdin);
    
    int t; scanf("%d", &t);
    int w;
    while (t--) {
        bool res = solve(w);
        if (res) printf("YES\n");
        else printf("NO\n");
        if (t) printf("\n");
    }
    
    return 0;
}

E. The Falling Leaves

uva-699

使用数组构建二叉树。输入树的先序遍历建树（递归建树）。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100;
int sum[maxn];

void build(int p)
{
    int now;
    scanf("%d", &now);
    if (now == -1) return;
    sum[p] += now;
    build(p - 1);
    build(p + 1);
}

bool init()
{
    int root;
    scanf("%d", &root);
    if (root == -1) return false;
    memset(sum, 0, sizeof(sum));
    int position = maxn / 2;
    sum[position] = root;
    build(position - 1);
    build(position + 1);
    return true;
}

int main()
{
//    freopen("./data/e/1.in", "r", stdin);
    
    int cnt = 1;
    while (init()) {
        int i = 0;
        while (!sum[i]) i++;
        printf("Case %d:\n%d", cnt, sum[i]);
        for (i = i + 1 ; ; i++) {
            if (!sum[i]) break;
            printf(" %d", sum[i]);
        }
        printf("\n\n");
        cnt++;
    }
    
    return 0;
}

F. Quadtrees

uva-297

非二叉树，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
#include <bits/stdc++.h>
using namespace std;

const int len = 32;
const int maxn = 1024 + 5;
int image[len][len];
int cnt;

// w边长, (row, col)左上角坐标, index字符 
void draw(string s, int w, int row, int col, int& index)
{
    char ch = s[index];
    index++;
    if (ch == 'p') {
        draw(s, w / 2, row, col + w / 2, index);
        draw(s, w / 2, row, col, index);
        draw(s, w / 2, row + w / 2, col, index);
        draw(s, w / 2, row + w / 2, col + w / 2, index);
    }
    else if (ch == 'f') {
        for (int i = row; i < row + w; i++) {
            for (int j = col; j < col + w; j++) {
                image[i][j] = 1;
            }
        }
    }
}

int main()
{
//    freopen("./data/f/1.in", "r", stdin);
    
    int t; scanf("%d", &t);
    while (t--) {
        string s1, s2;
        cin >> s1 >> s2;
        memset(image, 0, sizeof(image));
        int index1 = 0;
        int index2 = 0;
        draw(s1, 32, 0, 0, index1);
        draw(s2, 32, 0, 0, index2);
        cnt = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (image[i][j]) cnt++;
            }
        }
        printf("There are %d black pixels.\n", cnt);
    }
    
    return 0;
}