【题解】 —算法竞赛入门经典第二版 【第四章例题】【6/6】

发表于 | 更新于 | 分类于

UVa 1339 Ancient Cipher【排序】

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 111;
const int M = 26;

int a[M], b[M];
char s1[N], s2[N];
int main()
{
    while(~scanf("%s%s", s1, s2))
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for(int i = 0; s1[i]; ++i)   ++a[s1[i] - 'A'];
        for(int i = 0; s2[i]; ++i)   ++b[s2[i] - 'A'];
        sort(a, a + M);
        sort(b, b + M);
        bool flag = true;
        for(int i = 0; i < M; ++i)
            if(a[i] != b[i])
                flag = false;
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

UVa 489 Hangman Judge【模拟】

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 <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 111;

bool win, lose;
char s1[N], s2[N];
int cas, chance, leftt, len1, len2;
void guess(char ch)
{
    bool flag = true;
    for(int i = 0; i < len1; ++i)
    {
        if(s1[i] == ch)
        {
            --leftt;
            s1[i] = ' ';
            flag = false;
        }
    }
    if(flag)    --chance;
    if(!chance) lose = 1;
    if(!leftt)   win = 1;
}
int main()
{
    while(scanf("%d%s%s", &cas, s1, s2) == 3 && cas != -1)
    {
        len1 = strlen(s1);
        len2 = strlen(s2);
        leftt = len1;
        chance = 7;
        win = lose = false;
        for(int i = 0; i < len2; ++i)
        {
            guess(s2[i]);
            if(win || lose) break;
        }

        printf("Round %d\n", cas);
        if(win)
            puts("You win.");
        else if(lose)
            puts("You lose.");
        else
            puts("You chickened out.");
    }
    return 0;
}

UVa 133 The Dole Queue【模拟】

(自己写的太丑了，不好意思贴出来)

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
// UVa133 The Dole Queue
// Rujia Liu
#include<stdio.h>
#define maxn 25
int n, k, m, a[maxn];

// 逆时针走t步，步长是d（-1表示顺时针走），返回新位置
int go(int p, int d, int t)
{
    while(t--)
    {
        do
        {
            p = (p+d+n-1) % n + 1;
        }
        while(a[p] == 0);   // 走到下一个非0数字
    }
    return p;
}

int main()
{
    while(scanf("%d%d%d", &n, &k, &m) == 3 && n)
    {
        for(int i = 1; i <= n; i++)
            a[i] = i;
        int left = n; // 还剩下的人数
        int p1 = n, p2 = 1;
        while(left)
        {
            p1 = go(p1, 1, k);
            p2 = go(p2, -1, m);
            printf("%3d", p1);
            left--;
            if(p2 != p1)
            {
                printf("%3d", p2);
                left--;
            }
            a[p1] = a[p2] = 0;
            if(left)
                printf(",");
        }
        printf("\n");
    }
    return 0;
}

UVa 213 Message Decoding【模拟】

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int readchar()
{
    while(1)
    {
        int ch = getchar();
        if(ch != '\n' && ch != '\r') return ch;
    }
}

int readint(int c)
{
    int v = 0;
    while(c--)
        v = v * 2 + readchar() - '0';
    return v;
}

int code[8][1<<8];
int readcodes()
{
    memset(code, 0, sizeof(code));
    code[1][0] = readchar();
    for(int len = 2; len <= 7; ++len)
    {
        for(int i = 0; i < (1 << len) - 1; ++i)
        {
            int ch = getchar();
            if(ch == EOF) return 0;
            if(ch == '\n' || ch == '\r') return 1;
            code[len][i] = ch;
        }
    }
    return 1;
}

void printcodes()
{
    for(int len = 1; len <= 7; ++len)
        for(int i = 0; i < (1 << len)-1; ++i)
        {
            if(code[len][i] == 0) return ;
            printf("code[%d][%d] = %c\n", len, i, code[len][i]);
        }
}

int main()
{
    while(readcodes())
    {
//        printcodes();
        while(1)
        {
            int len = readint(3);
            if(len == 0) break;
//            printf("len=%d\n", len);
            while(1)
            {
                int v = readint(len);
//                printf("v=%d\n", v);
                if(v == (1 << len) - 1) break;
                putchar(code[len][v]);
            }
        }
        puts("");
    }
    return 0;
}

UVa 512 Spreadsheet Tracking【模拟】

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
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

struct node
{
    char com[5];
    int x1, y1, x2, y2;
    int a, x[25];
} cmd[MAX];
int xx, yy;
int r, c, n;

int solve(int x, int y)
{
    xx = x, yy = y;
    for(int i = 0; i < n; ++i)
    {
        int dr = 0, dc = 0;
        if(cmd[i].com[0] == 'E')
        {
            if(cmd[i].x1 == xx && cmd[i].y1 == yy)
            {
                xx = cmd[i].x2;
                yy = cmd[i].y2;
            }
            else if(cmd[i].x2 == xx && cmd[i].y2 == yy)
            {
                xx = cmd[i].x1;
                yy = cmd[i].y1;
            }
        }
        else
        {
            for(int j = 0; j < cmd[i].a; ++j)
            {
                int x = cmd[i].x[j];
                if(cmd[i].com[0] == 'I')    //插入
                {
                    if(cmd[i].com[1] == 'R' && x <= xx) dr++;
                    if(cmd[i].com[1] == 'C' && x <= yy) dc++;
                }
                else                        //删除
                {
                    if(cmd[i].com[1] == 'R' && x == xx) return 0;
                    if(cmd[i].com[1] == 'C' && x == yy) return 0;
                    if(cmd[i].com[1] == 'R' && x < xx) dr--;
                    if(cmd[i].com[1] == 'C' && x < yy) dc--;
                }
            }
        }
        xx += dr;
        yy += dc;
    }
    return 1;
}

int main()
{
    int cas = 0;
    while(cin >> r >> c && r)
    {
        cin >> n;
        for(int i = 0; i < n; ++i)
        {
            cin >> cmd[i].com;
            if(cmd[i].com[0] == 'E')
                cin >> cmd[i].x1 >> cmd[i].y1 >> cmd[i].x2 >> cmd[i].y2;
            else
            {
                cin >> cmd[i].a;
                for(int j = 0; j < cmd[i].a; ++j)
                    cin >> cmd[i].x[j];
            }
        }

        if(cas)
            puts("");
        printf("Spreadsheet #%d\n", ++cas);

        int q, x, y;
        cin >> q;
        while(q--)
        {
            cin >> x >> y;
            printf("Cell data in (%d,%d) ", x, y);
            if(!solve(x, y))
                printf("GONE");
            else
                printf("moved to (%d,%d)", xx, yy);
            puts("");
        }
    }
    return 0;
}

UVa 12412 A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)【模拟】

题目大意：

编写一个成绩管理系统，对应的每次输入都作出相应的回复。

解题思路：

直接模拟即可，有很多细节要注意。

注意细节：

1.计算平均分的时候要注意一下精度问题。为防止精度丢失，我在每个计算出的精度后面都加上了eps(1e-5)。
2.计算rank时，不要忘记考虑并列的情况。（如果有两个学生成绩并列第一，那么除他们外最高分就是第三名）。
3.当从主菜单输入4时，只返回一句话，那句话中的 ‘ 应该是英文的，直接从描述中复制过来是中文的。
4.看到有些博客中写到要防止除0的情况发生。我的程序中除0就是在求单科ave时可能出现的，但是经过测试，数据中并没有这种情况，所以可以不必考虑。

【注】以上就是我出现的错误，其他的细节都是很好发现的了。如果没出现这些错误但是你还过不了的话，不要着急，再仔细想想哪些细节出了问题，或者是私信/留言给我，作为一个在这上面WA到怀疑XX之后还坚持不懈最终A了这道题的快乐的咸鱼，我会乐意帮助你的。

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
 
int op, tot;
struct node
{
    int chi, mat, eng, pro, sum, rk;  //四课分数
    string SID, CID, name;
    double ave;
    bool flag;
    int pas;
 
} a[MAX];
 
bool cmp(int A, int B)
{
    return A > B;
}
 
void hello()
{
    puts("Welcome to Student Performance Management System (SPMS).");
    puts("");
    puts("1 - Add");
    puts("2 - Remove");
    puts("3 - Query");
    puts("4 - Show ranking");
    puts("5 - Show Statistics");
    puts("0 - Exit");
    puts("");
}
 
void work1()
{
    string si, ci, na;
    int c, m, e, p;
    while(1)
    {
        puts("Please enter the SID, CID, name and four scores. Enter 0 to finish.");
        cin >> si;
        if(si == "0") return ;
 
        cin >> ci >> na >> c >> m >> e >> p;
        bool f = true;
        for(int i = 0; i < tot; ++i)
        {
            if(a[i].flag && a[i].SID == si)
            {
                puts("Duplicated SID.");
                f = false;
                break;
            }
        }
        if(f)
        {
            a[tot].SID = si;
            a[tot].CID = ci;
            a[tot].name = na;
            a[tot].chi = c;
            a[tot].eng = e;
            a[tot].mat = m;
            a[tot].pro = p;
            a[tot].sum = c + e + m + p;
            a[tot].ave = (c + e + m + p) / 4.0 + eps;
            a[tot].flag = true;
            ++tot;
        }
    }
}
 
void work2()
{
    string tt;
    while(1)
    {
        puts("Please enter SID or name. Enter 0 to finish.");
        cin >> tt;
        if(tt == "0") return ;
        int cnt = 0;
 
        for(int i = 0; i < tot; ++i)
        {
            if(a[i].flag)
            {
                if(a[i].name == tt || a[i].SID == tt)
                {
                    a[i].flag = false;
                    cnt++;
                }
            }
        }
        printf("%d student(s) removed.\n", cnt);
    }
}
 
void work3()
{
    //每次查询都计算一下rank
    int tem[MAX], rrk[MAX], srk = 1, now = 0;
    for(int i = 0; i < tot; ++i)
    {
        if(a[i].flag)
            tem[now++] = a[i].sum;
    }
    sort(tem, tem + now, cmp);
    rrk[0] = 1;
    srk++;
    for(int i = 1; i < now; ++i)
    {
        if(tem[i] != tem[i-1])
            rrk[i] = srk;
        else
            rrk[i] = rrk[i-1];
        ++srk;
    }
    for(int i = 0; i < tot; ++i)
    {
        if(a[i].flag)
        {
            for(int t = 0; t < now; ++t)
            {
                if(a[i].sum == tem[t])
                {
                    a[i].rk = rrk[t];
                    break;
                }
            }
        }
    }
 
    string tt;
    while(1)
    {
        puts("Please enter SID or name. Enter 0 to finish.");
        cin >> tt;
        if(tt == "0") return ;
 
        for(int i = 0; i < tot; ++i)
        {
            if(a[i].flag && (a[i].SID == tt || a[i].name == tt))
            {
                cout << a[i].rk << " " << a[i].SID << " " << a[i].CID << " " << a[i].name;
                printf(" %d %d %d %d %d %.2f\n", a[i].chi, a[i].mat, a[i].eng, a[i].pro, a[i].sum, a[i].ave);
            }
        }
    }
}
 
void work4()
{
    puts("Showing the ranklist hurts students' self-esteem. Don't do that.");
    return ;
}
 
void work5()
{
    puts("Please enter class ID, 0 for the whole statistics.");
    string tt;
    cin >> tt;
    int pas, fai, yy[5], qq;
    double suma, cnta, avea;
 
    puts("Chinese");
    suma = cnta = pas = fai = 0;
    for(int i = 0; i < tot; ++i)
    {
        if(a[i].flag && (a[i].CID == tt || tt == "0"))
        {
            ++cnta;
            suma += a[i].chi;
            if(a[i].chi >= 60)
                ++pas;
            else
                ++fai;
        }
    }
    if(cnta == 0)
        avea = 0;
    else
        avea = suma / cnta + eps;
    printf("Average Score: %.2f\n", avea);
    printf("Number of passed students: %d\n", pas);
    printf("Number of failed students: %d\n", fai);
    puts("");
 
    puts("Mathematics");
    suma = cnta = pas = fai = 0;
    for(int i = 0; i < tot; ++i)
    {
        if(a[i].flag && (a[i].CID == tt || tt == "0"))
        {
            ++cnta;
            suma += a[i].mat;
            if(a[i].mat >= 60)
                ++pas;
            else
                ++fai;
        }
    }
    if(cnta == 0)
        avea = 0;
    else
        avea = suma / cnta + eps;
    printf("Average Score: %.2f\n", avea);
    printf("Number of passed students: %d\n", pas);
    printf("Number of failed students: %d\n", fai);
    puts("");
 
    puts("English");
    suma = cnta = pas = fai = 0;
    for(int i = 0; i < tot; ++i)
    {
        if(a[i].flag && (a[i].CID == tt || tt == "0"))
        {
            ++cnta;
            suma += a[i].eng;
            if(a[i].eng >= 60)
                ++pas;
            else
                ++fai;
        }
    }
    if(cnta == 0)
        avea = 0;
    else
        avea = suma / cnta + eps;
    printf("Average Score: %.2f\n", avea);
    printf("Number of passed students: %d\n", pas);
    printf("Number of failed students: %d\n", fai);
    puts("");
 
    puts("Programming");
    suma = cnta = pas = fai = 0;
    for(int i = 0; i < tot; ++i)
    {
        if(a[i].flag && (a[i].CID == tt || tt == "0"))
        {
            ++cnta;
            suma += a[i].pro;
            if(a[i].pro >= 60)
                ++pas;
            else
                ++fai;
        }
    }
    if(cnta == 0)
        avea = 0;
    else
        avea = suma / cnta + eps;
    printf("Average Score: %.2f\n", avea);
    printf("Number of passed students: %d\n", pas);
    printf("Number of failed students: %d\n", fai);
    puts("");
 
    memset(yy, 0, sizeof(yy));
    puts("Overall:");
    for(int i = 0; i < tot; ++i)
    {
        if(a[i].flag && (a[i].CID == tt || tt == "0"))
        {
            qq = (a[i].chi >= 60) + (a[i].eng >= 60) + (a[i].pro >= 60) + (a[i].mat >= 60);
            yy[qq]++;
        }
    }
    printf("Number of students who passed all subjects: %d\n", yy[4]);
    printf("Number of students who passed 3 or more subjects: %d\n", yy[4] + yy[3]);
    printf("Number of students who passed 2 or more subjects: %d\n", yy[4] + yy[3] + yy[2]);
    printf("Number of students who passed 1 or more subjects: %d\n", yy[4] + yy[3] + yy[2] + yy[1]);
    printf("Number of students who failed all subjects: %d\n", yy[0]);
    puts("");
}
 
int main()
{ 
    hello();
    while(cin >> op && op)
    {
        if(op == 1)
            work1();
        else if(op == 2)
            work2();
        else if(op == 3)
            work3();
        else if(op == 4)
            work4();
        else if(op == 5)
            work5();
        hello();
    }
    return 0;
}
Donate comment here
0%