Messy

Cyan题解

发表于 |

A. A+B练习

简单输入输出练习。
输出答案用空行分开，但是最后一行的换行符不能省略，否则会出现迷之PE。

AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int n, a;
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        int sum = 0;
        while (n--) {
            cin >> a;
            sum += a;
        }
        cout << sum << endl;
        if (T > 0) cout << endl;
    }
}


B. 出现次数最多的数

题意简述：

给定n个正整数(si)，找出它们中出现次数最多的数。如果这样的数有多个，请输出其中最小的一个。
本题数据范围较小，1 ≤ n ≤ 1000 ，1 ≤ si ≤ 10000。
解法也有很多，以下给出一个较简单的办法：
用一个10000大小的数组表示各个数的出现次数，对于每次输入，将对应的数的出现次数+1，同时记录出现过的数，用以之后的比较。

AC代码：
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 <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int hs[10010]; //例如hs[30] == 4, 表示值为30的数有4个
int num[1010]; //记录输入的数
int main(){
    int n, t, maxcount, cnt, ans;
    while (cin >> n) {
        maxcount = -1; //最多的出现次数
        ans = 0x7f7f7f7f; //出现次数最多的数
        memset(hs, 0, sizeof(hs));
        for (int i = 0; i < n; ++i) {
            cin >> t;
            num[i] = t;
            hs[t]++;
        }
        for (int i = 0; i < n; ++i) {
            cnt = hs[num[i]];
            if (cnt > maxcount || (cnt == maxcount && ans > num[i])) {
                maxcount = cnt;
                ans = num[i];
            }
        }
        cout << ans << endl;
    }
    return 0;
}


C. ISBN号码

题意简述：

有ISBN号码如0-670-82162-4，最后一位为验证码，由前几位计算得到，写程序判断ISBN号码是否正确，若不正确则输出正确的号码，否则输出Right.

AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int order[] = {0, 2, 3, 4, 6, 7, 8, 9, 10};
int main(){
    string s1,s2;
    while (cin >> s1) {
        s2 = s1;
        int sum = 0;
        for (int i = 0; i < 9; ++i) {
            sum += (i + 1) * (s2[order[i]] - '0');
        }
        sum %= 11;
        s2[12] = (sum == 10) ? 'X' : (sum + '0');
        cout << ((s1 == s2) ? "Right" : s2) << endl;
    }
}


D. 排序

题意简述：

输入一串数字字符，将其中的5当做分隔符，剩下的数排序输出。
注意以下几组数据：

505123123205077555
0 77 12312320
00005051231232050775
0 0 77 12312320
50512312320555507750005
0 0 77 12312320
505123123205077
0 77 12312320
051231232055077
0 77 12312320
5550
0
1155663535006555
3 6 11 663
10000000055051120
0 1120 100000000
00060054
4 600


都是细节！

AC代码：
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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    char a[2020];
    int n[1010];
    int cnt = 0;
    int st = 0;
    while (scanf("%s",a) != EOF){
        cnt = st = 0;
        if (a[strlen(a)-1] != '5') a[strlen(a)] = '5';
        char tmp[20];
        for (int i = 0; i < strlen(a); ++i) {
            if (a[i] == '5' && i - st > 0) {
                memset(tmp, 0, sizeof(tmp));
                strncpy(tmp, a+st, i-st); //拷贝一段字符
                st = i + 1;
                n[cnt++] = atoi(tmp); //字符转数字
            }
            else if (i - st == 0 && a[st] == '5') st++;
        }
        sort(n, n+cnt);
        for (int i = 0; i < cnt; ++i) {
            cout << n[i];
            if (i < cnt - 1) cout << " ";
            else cout << endl;
        }
        memset(a, 0, sizeof(a));
        memset(n, 0, sizeof(n));
    }
}


E. 数值统计

大水题，略。

F. Z字形扫描

这题没有人通过，比较遗憾。
题意补充：多组测试数据，以EOF结尾。输出结果不用去掉行尾的空格。
这题一开始写的代码相当矬，下面给出的相对比较优雅的代码来自网络，有少量修改。
其实就是一道强行模拟可过的题，仔细一点还是都能过的。

AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int main(){
    int n;
    int a[500][500];
    while (cin >> n) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> a[i][j];
        
        for(int k = 1; k <= n; k++)
            for(int i = k-1, j = 0; i >= 0; i--, j++)
                if (k & 1) cout << a[i][j] << " ";
                else cout << a[j][i] << " ";
        
        for(int k = n - 1; k > 0; k--)
            for(int i = n - 1, j = n - k; j < n; i--, j++)
                if (k & 1) cout << a[i][j] << " ";
                else cout << a[j][i] << " ";
        
        cout << endl;
    }
}


G. 数字三角形

动态规划入门题。
这题还可以用如下的方法考虑：
从底端往上端推，把左下和右下两个数中比较大的那个加给上面的数。层层推进，最后得到的最上端的数就是所求的最大值。

AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int a[110][110];
    int n;
    cin >> n;
    memset(a, 0, sizeof(a));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = n-2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            a[i][j] += max(a[i+1][j], a[i+1][j+1]);
        }
    }
    cout << a[0][0] << endl;
    return 0;
}


H. 马遍历棋盘

题意简述：

给出一个n*m的国际象棋棋盘，问能否用马遍历这个棋盘，并且每个位置只能经过一次。如果能，输出字典序最小的结果；如果不能，输出impossible。
简单DFS，对于马的八个方向，如果能走则标记，回溯的时候取消标记，直到找到结果。
马八个方向的顺序是要根据自己建立的坐标设计好的，否则不能按照题意中“字典序最小”的要求输出。

AC代码：
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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
bool checked[30][30];
char outputs[300];
int xmax,ymax;
int total;
int dx[] = {-1,1,-2,2,-2,2,-1,1};
int dy[] = {-2,-2,-1,-1,1,1,2,2};
bool isPossible(int x, int y){
    if (x < xmax && y < ymax && x >= 0 && y >= 0 && checked[x][y] == 0) {
        return true;
    }
    return false;
}
int dfs(int x, int y, int step){
    if (step == total) return 1;
    int nx, ny;
    for (int k = 0; k < 8; ++k) {
        nx = x + dx[k];
        ny = y + dy[k];
        if (isPossible(nx, ny)) {
            checked[nx][ny] = 1;
            if (dfs(nx, ny, step + 1)) {
                outputs[step * 2] = ny + 'A';
                outputs[step * 2 + 1] = nx + '1';
                return 1;
            }
            checked[nx][ny] = 0;
        }
    }
    return 0;
}
int main(){
    int T;
    cin >> T;
    for (int c = 1; c <= T; ++c) {
        cin >> xmax >> ymax;
        total = xmax * ymax;
        memset(checked, 0, sizeof(checked));
        memset(outputs, 0, sizeof(outputs));
        outputs[0] = 'A';
        outputs[1] = '1';
        checked[0][0] = 1;
        cout << "Scenario #" << c << ":" << endl;
        if (dfs(0, 0, 1)) {
            cout << outputs << endl;
        }
        else cout << "impossible" << endl;
        cout << endl;
    }
    return 0;
}

建议多去找点搜索的题目做。以后的比赛还会有DFS和BFS的题出现。


I. 3n+1问题

其实一般最后一题是水题。

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
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n, m;
    while (cin >> n >> m) {
        bool flag = 0;
        if (n > m) {
            swap(n, m);
            flag = 1;
        }
        int t, cnt = 1, ans = 0;
        for (int i = n; i <= m; i++) {
            t = i;
            while (t != 1) {
                if (t & 1) t = 3 * t + 1;
                else t = t / 2;
                cnt++;
            }
            if (cnt > ans) ans = cnt;
            cnt = 1;
        }
        if (flag) swap(n, m);
        cout << n << " " << m << " " << ans << endl;
    }
    return 0;
}

小结

第一次班赛整体较简单，主要为C++上机考试做准备。
本次比赛共14人参加，10人交题。
AC总计20次。

各题通过情况：

A B C D E F G H I
AC 7 1 1 1 8 0 1 0 1
Submit   20   23   18   11   13   0   1   0   2 

主要问题：

  • 代码风格问题
    • 没有正确的缩进格式
    • 没有适当加空格
  • 输入输出问题
    • 对于多组输入输出的数据，没有加换行符
  • 逻辑不清晰
  • 审题不仔细

以上所有问题，都是练习不够造成的。