首页 > itarticle > 紫书习题 第五章

紫书习题 第五章

admin 1月 18, 2021 0

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

例5-1 UVa10474 Where is the Marble?

题目链接

排序后二分查找即可。

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 <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int (){
    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, q, st[10005];
void init(){
    for(int i = 0; i < n; ++i)
        st[i] = read();
    sort(st, st + n);
}
void solve(){
    int x;
    for(int i = 0; i < q; ++i){
        x = read();
        int index = lower_bound(st, st + n, x) - st;
        if(st[index] == x)
            printf("%d found at %dn", x, index + 1);
        else
            printf("%d not foundn", x);
    }
}
int main(){
    for(int T = 1; ; ++T){
        n = read(), q = read();
        if(!n && !q)break ;
        printf("CASE# %d:n", T);
        init();
        solve();
    }
    return 0;
}

例5-5 UVa12096 The SetStack Computer

题目链接

将集合映射成数，然后进行操作。
非常好的练习STL的题。

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
 

#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <set>
#include <map>
#define INF 2000000000
using namespace std;
typedef long long ll;
int (){
    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; 
}
typedef set<int> Set;
map<Set, int> mp;
int n, stack[10005], top, tot;
Set st[2005];
int getID(Set *s){
    if(!mp.count(*s)){
        mp[*s] = tot, tot++;
        return tot - 1;
    }
    return mp[*s];
}
void push(){
    stack[top++] = 0;
}
void dup(){
    stack[top] = stack[top - 1];
    top++;
}
void _union(){
    int xa, xb, id; 
    xa = stack[--top], xb = stack[--top];
    Set ss; 
    set_union(st[xa].begin(), st[xa].end(), st[xb].begin(), st[xb].end(), inserter(ss, ss.begin()));
    id = getID(&ss);
    st[id] = ss;
    stack[top++] = id;
}
void _inter(){
    int xa, xb, id; 
    xa = stack[--top], xb = stack[--top];
    Set ss; 
    set_intersection(st[xa].begin(), st[xa].end(), st[xb].begin(), st[xb].end(), inserter(ss, ss.begin()));
    id = getID(&ss);
    st[id] = ss;
    stack[top++] = id;
}
void add(){
    int xa, xb, id; 
    xa = stack[--top], xb = stack[--top];
    Set ss = st[xb]; 
    ss.insert(xa);
    id = getID(&ss);
    st[id] = ss;
    stack[top++] = id;
}
void init(){
    n = read();
    top = tot = 1;
    mp.clear();
    Set s;
    mp[s] = 0, st[0] = s;
}
void solve(){
    char opr[12];
    for(int i = 0; i < n; ++i){
        scanf("%s", opr);
        if(opr[0] == 'P')push();
        if(opr[0] == 'D')dup();
        if(opr[0] == 'U')_union();
        if(opr[0] == 'I')_inter();
        if(opr[0] == 'A')add();
        printf("%dn", st[stack[top - 1]].size());
        
    }
    printf("***n");
}
int main(){
    int T = read();
    while(T--){
        init();
        solve();
    }
    return 0;
}

例5-7 UVa136 Ugly Numbers

题目链接

用一个堆，每次取出最小的丑数，然后生成新的丑数。
本题在其他地方有多个变种，故不在此贴出代码。
答案：859963392

例5-8 UVa1592 Database

题目链接

先对每一个字符串进行处理，将字符串映射为数后枚举，然后从上到下扫描每一行，对同一行的两个格子打包成一个pair，然后再对pair进行映射，映射为当前的行号。之后即可判断是否有符合条件的。
和集合栈计算机那道题有异曲同工之妙。

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 <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <map>
#include <string>
#define INF 2000000000
using namespace std;
typedef long long ll;
int (){
    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, tab[10005][11];
char s[110];
map<string, int> mp1;
map<pair<int, int>, int> mp2;
void init(){
    mp1.clear();
    int tots = 0;
    for(int i = 0; i < n; ++i){
        fgets(s, 99, stdin);
        int len = strlen(s);
        for(; isspace(s[len - 1]); --len)
            s[len - 1] = '
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能