紫书习题 第六章

发表于 | 分类于 |
字数统计: 2,938 字

我自己做的紫书第六章部分习题的整合。

例6-2 UVa514 Rails

题目链接

用栈模拟即可。
对于要求顺序的第$i$项，只有$2$种可能：

  1. 它不在栈里，那么把它前面的全部入栈。
  2. 它在栈里，那么除非它在栈顶，不然不可能满足此顺序。
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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, permu[1005], st[1005], top, in[1005];
void solve(){
    top = 0;
    memset(in, 0, sizeof(in));
    int cur = 1, ans = 1;
    for(int i = 1; i <= n; ++i){
        if(!in[permu[i]]){
            for(; cur < permu[i]; ++cur)
                st[top++] = cur,
                in[cur] = 1;
            cur++;
        }else{
            if(st[top - 1] == permu[i])
                top--, in[permu[i]] = 0;
            else{
                ans = 0;
                break;
            }
        }
    }
    printf("%s\n", ans ? "Yes" : "No");
}
void init(){
    for(; ; ){
        if(permu[1] = read()){
            for(int i = 2; i <= n; ++i)
                permu[i] = read();   
            solve();
        }else {
            printf("\n");
            break ;
        }
    }
}
int main(){
    for(; ; ){
        n = read();
        if(!n)break ;
        init();
    }
    return 0;
}

例6-4 UVa11988 Broken Keyboard (a.k.a. Beiju Text)

题目链接

直接用链表模拟即可。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
char s[5000005];
int cur, nxt[5000005], lst;
void solve(){
    cur = lst = 0;
    nxt[0] = -1;
    int len = strlen(s + 1);
    for(int i = 1; i <= len; ++i){
        if(s[i] == '['){
            cur = 0;
        }else if(s[i] == ']'){
            cur = lst;
        }else{
            nxt[i] = nxt[cur];
            nxt[cur] = i;
            cur = i;
            if(nxt[cur] == -1)
                lst = cur;
        }
    }
    for(int i = nxt[0]; i != -1; i = nxt[i])
        putchar(s[i]);
    putchar('\n');
}
int main(){
    while(scanf("%s", s + 1) == 1)
        solve();
    return 0;
}

例6-6 UVa679 Dropping Balls

题目链接

可以根据奇偶判断一个球在一个节点应该是向左还是向右走，同时算出有多少个球走到了下一个节点。
这样的话就可以递归计算。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int d, id, ans;
void init(){
    d = read(), id = read();
}
void get(int curd, int curi, int curp){
    if(curd == d){
        ans = curp;
        return ;
    }
    if(curi & 1)
        get(curd + 1, curi / 2 + 1, curp << 1);
    else
        get(curd + 1, curi / 2, curp << 1 | 1);
}
void solve(){
    get(1, id, 1);
    printf("%d\n", ans);
}
int main(){
    int T = read();
    while(T--){
        init();
        solve();
    }
    scanf("%d", &T);
    return 0;
}

例6-8 UVa548 Tree

题目链接

根据中序遍历和后序遍历构造树即可。
细节有一点多。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
char s[2000005];
int cur, p1[10005], p2[10005], n;
int lc[10005], rc[10005], key[10005], mini[10005], ans;
int read(){
    int x = 0;
    char c = s[cur];
    while(c < '0' || c > '9'){
        if(c == '\n' || c == EOF)
            return -1;
        c = s[++cur];
    }
    while(c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = s[++cur];
    return x; 
}
void init(){
    n = 0;
    for(cur = 0; ; ++n){
        p1[n] = read();
        if(p1[n] < 0) break;
    }
    fgets(s, 2000000, stdin);
    cur = 0;
    for(int i = 0; i < n; ++i)
        p2[i] = read();
}
int get(int il, int ir, int pl, int pr){
    if(ir - il < 0)
        return 0;
    int i, id = p2[pr];
    for(i = il; i <= ir; ++i)
        if(p1[i] == id) break;
    int len = i - il;
    lc[id] = get(il, i - 1, pl, pl + len - 1);
    rc[id] = get(i + 1, ir, pl + len, pr - 1);
    key[id] = id;
    if(lc[id] && rc[id]){
        if(key[lc[id]] > key[rc[id]])
            key[id] += key[rc[id]], mini[id] = mini[rc[id]];
        else if(key[lc[id]] < key[rc[id]])
            key[id] += key[lc[id]], mini[id] = mini[lc[id]];
        else
            key[id] += key[rc[id]], mini[id] = mini[rc[id]],
            mini[id] = min(mini[lc[id]], mini[rc[id]]);
    }else if(lc[id])
        key[id] += key[lc[id]], mini[id] = mini[lc[id]];
    else if(rc[id])
        key[id] += key[rc[id]], mini[id] = mini[rc[id]];
    else 
        mini[id] = id;
    return id;
}
void solve(){
    int root = get(0, n - 1, 0, n - 1);
    printf("%d\n", mini[root]);
}
int main(){
    while(fgets(s, 2000000, stdin) != NULL){
        init();
        solve();
    }
    return 0;
}

例6-9 UVa839 Not so Mobile

题目链接

按照递归顺序生成整个天平即可。
例题给出的代码中get函数的返回值是天平是否平衡，这里我稍微做了一些调整。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int ans = 1;
int get(){
    int wl = read(), dl = read(), wr = read(), dr = read();
    if(!wl) wl = get();
    if(!wr) wr = get();
    if(wl * dl != wr * dr)
        ans = 0;
    return wl + wr;
}
void solve(){
    ans = 1;
    get();
    printf("%s\n", ans ? "YES" : "NO");
}
int main(){
    int T = read();
    while(T--){
        solve();
        if(T > 0)
            printf("\n");
    }
    return 0;
}

例6-10 UVa699 The Falling Leaves

题目链接

也是利用递归构造出整个树的结构。

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 <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int root, lc[100005], rc[100005];
int cntl[100005], cntr[100005], maxl, maxr;
void build(int id, int pos){
    if(pos >= 0)
        cntr[pos] += id, maxr = max(maxr, pos);
    else
        cntl[-pos] += id, maxl = min(maxl, pos);
    lc[id] = read();
    if(lc[id] > 0)
        build(lc[id], pos - 1);
    rc[id] = read();
    if(rc[id] > 0)
        build(rc[id], pos + 1);
}
void solve(){
    memset(cntl, 0, sizeof(cntl));
    memset(cntr, 0, sizeof(cntr));
    maxl = maxr = 0;
    build(root, 0);
}
int main(){
    int T = 1;
    while((root = read()) != -1){
        solve();
        printf("Case %d:\n", T);
        for(int i = -maxl; i >= 1; --i)
            printf("%d ", cntl[i]);
        for(int i = 0; i < maxr; ++i)
            printf("%d ", cntr[i]);
        printf("%d\n\n", cntr[maxr]);
        T++;
    }
    return 0;
}

例6-13 UVa1103 Ancient Messages

题目链接

搜索联通块即可。
这里用了一点技巧：先把所有符号外围的白色填充掉，然后再对符号框架部分搜索。在搜索框架时发现了没有访问过的白色块就说明这个符号有洞，用这种方法统计出洞的个数即可。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}, lis[] = {'W', 'A', 'K', 'J', 'S', 'D'};
int dat[205][205], tot, cnt;
bool vis[205][205];
char ans[1005];
void init(){
    memset(dat, 0, sizeof(dat));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            int d;
            scanf("%1x", &d);
            if(d & 8)dat[i][j << 2] = 1;
            if(d & 4)dat[i][j << 2 | 1] = 1;
            if(d & 2)dat[i][j << 2 | 2] = 1;
            if(d & 1)dat[i][j << 2 | 3] = 1;
        }
    }
    m <<= 2;
}
void dfs(int cx, int cy, int o){//o代表当前填充的是框架还是白色块
    vis[cx][cy] = 1;
    
    for(int i = 0; i < 4; ++i){
        int ex = cx + dx[i], ey = cy + dy[i];
        if(ex >= 0 && ex < n && ey >= 0 && ey < m && !vis[ex][ey]){
            if(o){
                if(!dat[ex][ey])
                    dat[ex][ey] = ++tot,
                    dfs(ex, ey, 0);
                else if(dat[ex][ey] == 1)
                    dfs(ex, ey, 1);
            }else if(!dat[ex][ey])
                dat[ex][ey] = tot,
                dfs(ex, ey, 0);
        }
    }
}
void solve(){
    memset(vis, 0, sizeof(vis));
    tot = 2, cnt = 0;
    for(int i = 0; i < n; ++i){
        if(!vis[i][0] && !dat[i][0])
            dfs(i, 0, 0);
        if(!vis[i][m - 1] && !dat[i][m - 1])
            dfs(i, m - 1, 0);
    }
        
    for(int i = 0; i < m; ++i){
        if(!vis[0][i] && !dat[0][i])
            dfs(0, i, 0);
        if(!vis[n - 1][i] && !dat[n - 1][i])
            dfs(n - 1, i, 0);
    }
    
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(!vis[i][j] && dat[i][j] == 1){
                int his = tot;
                dfs(i, j, 1);
                ans[cnt++] = lis[tot - his];
            }
        }
    }
    sort(ans, ans + cnt);
    ans[cnt] = '\0';
    printf("%s\n", ans);
}
int main(){
    for(int T = 1; ; ++T){
        n = read(), m = read();
        if(!n && !m)
            break;
        printf("Case %d: ", T);
        init();
        solve();
    }
    return 0;
}

例6-15 UVa10305 Ordering Tasks

题目链接

直接拓扑排序即可。

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 <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, du[105];
int que[105], f, r, lis[105];
bool e[105][105];
void init(){
    memset(du, 0, sizeof(du));
    for(int i = 0; i < m; ++i){
        int u = read(), v = read();
        du[v]++;
        e[u][v] = 1;
    }
}
void solve(){
    f = r = 0;
    for(int i = 1; i <= n; ++i)
        if(!du[i])
            que[r++] = i;
    int cnt = 0;
    while(r - f){
        int cur = que[f++];
        lis[cnt++] = cur;
        for(int i = 1; i <= n; ++i)
            if(e[cur][i]){
                du[i]--;
                if(!du[i]) que[r++] = i;
            }
    }
    for(int i = 0; i < n - 1; ++i)
        printf("%d ", lis[i]);
    printf("%d\n", lis[n - 1]);
    memset(e, 0, sizeof(e));
}
int main(){
    for(; ; ) {
        n = read(), m = read();
        if (!n && !m) break;
        init();
        solve();
    }
    return 0;
}

6-1 UVa673 Parentheses Balance

题目链接

括号序列的匹配。。
用栈模拟即可。
我一开始没看清题，以为只要能配对即可，结果疯狂WA。。。

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 <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
char s[1005];
int st[10005], top;
void init(){
    fgets(s, 1000, stdin);
}
void solve(){
    int len = strlen(s), flag = 1;
    top = 0;
    for(int i = 0; i < len; ++i){
        if(s[i] == '(' || s[i] == '[')
            st[top++] = s[i];
        else if(s[i] == ')'){
            if(top && st[top - 1] == '(')
                top--;
            else{
                flag = 0;
                break;
            }
        }else if(s[i] == ']'){
            if(top && st[top - 1] == '[')
                top--;
            else{
                flag = 0;
                break;
            }
        }
    }
    if(top) flag = 0;
    printf("%s\n", flag ? "Yes" : "No");
}
int main(){
    fgets(s, 1000, stdin);
    int T;
    sscanf(s, "%d", &T);
    while(T--){
        init();
        solve();
    }
    return 0;
}

6-3 UVa536 Tree Recovery

题目链接

和根据后序和中序求先序一样。
只要知道先序的根在开头，后序的根在末尾即可。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
char s1[30], s2[30];
int root, lc[250], rc[250];
int get(int pl, int pr, int il, int ir){
    if(ir - il < 0)
        return 0;
    int id = s1[pl], i;
    for(i = il; i <= ir; ++i)
        if(s2[i] == id) break;
    int len = i - il;
    lc[id] = get(pl + 1, pl + len, il, i - 1);
    rc[id] = get(pl + len + 1, pr, i + 1, ir);
    return id;
}
void getP(int id){
    if(lc[id]) getP(lc[id]);
    if(rc[id]) getP(rc[id]);
    printf("%c", id);
}
void solve(){
    int len = strlen(s1);
    root = get(0, len - 1, 0, len - 1);
    getP(root);
    printf("\n");
}
int main(){
    while(scanf("%s%s", s1, s2) == 2)
        solve();
    return 0;
}