杭电 OJ2020-2029

写在前面

本文记录了刷杭电 OJ2020-2029 的过程和一些想法，代码仅供参考！

2020 绝对值排序

Problem Description

输入 n (n<=100) 个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。

Input

输入数据有多组，每组占一行，每行的第一个数字为 n, 接着是 n 个整数，n=0 表示输入数据的结束，不做处理。

Output

对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。

Sample Input

3 3 -4 2
4 0 1 2 -3
0

Sample Output

-4 3 2
-3 2 1 0

解题思路

冒泡排序
也可以通过自己写一个 cmp 来调用 sort(),规则就是 fabs(a) > fabs(b)

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n, num[100];
    while (cin >> n && n) {  // n为0退出
        for (int i = 0; i < n; i++) cin >> num[i];
        for (int i = 0; i < n - 1; i++)  //冒泡排序
            for (int j = 0; j < n - i - 1; j++)
                if (fabs(num[j]) < fabs(num[j + 1])) {//比较交换
                    swap(num[j], num[j + 1]);
                }
        for (int i = 0; i < n; i++) {
            if (i == 0)
                cout << num[i];
            else
                cout << " " << num[i];
        }
        cout << endl;
    }
    return 0;
}

2021 发工资咯：）

Problem

作为杭电的老师，最盼望的日子就是每月的 8 号了，因为这一天是发工资的日子，养家糊口就靠它了，呵呵
但是对于学校财务处的工作人员来说，这一天则是很忙碌的一天，财务处的小胡老师最近就在考虑一个问题：如果每个老师的工资额都知道，最少需要准备多少张人民币，才能在给每位老师发工资的时候都不用老师找零呢？
这里假设老师的工资都是正整数，单位元，人民币一共有 100 元、50 元、10 元、5 元、2 元和 1 元六种。

Input

输入数据包含多个测试实例，每个测试实例的第一行是一个整数 n（n<100），表示老师的人数，然后是 n 个老师的工资。n=0 表示输入的结束，不做处理。

Output

对于每个测试实例输出一个整数 x, 表示至少需要准备的人民币张数。每个输出占一行。

Sample Input

3
1 2 3
0

Sample Output

4

解题思路

贪心思想，从面值大的开始，整除求余

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main() {
    int n, num;
    int count, type[6] = {100, 50, 10, 5, 2, 1};  //面值
    while (cin >> n && n) {                       // n为0退出
        count = 0;
        for (int i = 0; i < n; i++) {
            cin >> num;
            for (int j = 0; j < 6; j++) {
                count += num / type[j];  //最大可换取的张数
                num %= type[j];          //剩余工资
            }
        }
        cout << count << endl;
    }
    return 0;
}

2022 海选女主角

Problem Description

potato 老师虽然很喜欢教书，但是迫于生活压力，不得不想办法在业余时间挣点外快以养家糊口。
“做什么比较挣钱呢？筛沙子没力气，看大门又不够帅…”potato 老师很是无奈。
“张艺谋比你还难看，现在多有钱呀，听说还要导演奥运开幕式呢！你为什么不去娱乐圈发展呢？”lwg 在一旁出主意。
嗯，也是，为了生存，就委屈点到娱乐圈混混吧，马上就拍一部激光电影《杭电记忆 —— 回来我的爱》。
说干就干，马上海选女主角（和老谋子学的，此举可以吸引媒体的眼球，呵呵），并且特别规定，演员必须具有 ac 的基本功，否则直接 out!
由于策划师风之鱼（大师级水王）宣传到位，来应聘的 MM 很多，当然包括 nit 的蛋糕妹妹等呼声很高的美女，就连 zjut 的 jqw 都男扮女装来应聘（还好被安全顾问 hdu_Bin-Laden 认出，给轰走了），看来娱乐圈比 acm 还吸引人哪…
面试那天，刚好来了 m*n 个 MM，站成一个 m*n 的队列，副导演 Fe (OH) 2 为每个 MM 打了分数，分数都是 32 位有符号整数。
一开始我很纳闷：分数怎么还有负的？Fe (OH) 2 解释说，根据选拔规则，头发染成黄色、化妆太浓、穿的太少等等都要扣分数的，扣的多了就可能是负分了，当然，如果发现话语中夹有日语，就直接给 - 2147483648 分了。
分数送上来了，是我做决定的时候了，我的一个选拔原则是，要选一个面试分数绝对值（必须还是 32 位整数）最大的 MM。
特别说明：如果不幸选中一个负分的 MM, 也没关系，因为我觉得，如果不能吸引你，那要想法恶心你。

Input

输入数据有多组，每组的第一行是两个整数 m 和 n，表示应聘 MM 的总共的行列数，然后是 m 行整数，每行有 n 个，m 和 n 的定义见题目的描述。

Output

对于每组输入数据，输出三个整数 x,y 和 s，分别表示选中的 MM 的行号、列号和分数。
note: 行号和列号从一开始，如果有多个 MM 的分数绝对值一样，那么输出排在最前面的一个（即行号最小的那个，如果行号相同则取列号最小的那个）。

Sample Input

2 3
1 4 -3
-7 3 0

Sample Output

2 1 -7

解题思路

直接开二维数组，遍历一次找到绝对值最大数据位置
注意一个坑：这里如果直接用 int 或者 long，然后用 abs 来取绝对值，就可能造成数据溢出，解决方法是使用 double

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int m, n;
    double s, max;
    int posi, posj;
    while (cin >> m >> n) {
        max = posi = posj = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> s;
                if (fabs(s) > fabs(max)) {  //找绝对值最大值
                    max = s;
                    posi = i;
                    posj = j;
                }
            }
        }
        printf("%d %d %.0f\n", posi + 1, posj + 1, max);
    }
    return 0;
}

2023 求平均成绩

Problem Description

假设一个班有 n (n<=50) 个学生，每人考 m (m<=5) 门课，求每个学生的平均成绩和每门课的平均成绩，并输出各科成绩均大于等于平均成绩的学生数量。

Input

输入数据有多个测试实例，每个测试实例的第一行包括两个整数 n 和 m，分别表示学生数和课程数。然后是 n 行数据，每行包括 m 个整数（即：考试分数）。

Output

对于每个测试实例，输出 3 行数据，第一行包含 n 个数据，表示 n 个学生的平均成绩，结果保留两位小数；第二行包含 m 个数据，表示 m 门课的平均成绩，结果保留两位小数；第三行是一个整数，表示该班级中各科成绩均大于等于平均成绩的学生数量。每个测试实例后面跟一个空行。

Sample Input

2 2
5 10
10 20

Sample Output

7.50 15.00
7.50 15.00
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n, m;
    int s[50][5], stu_s[50], cou_s[5];
    while (cin >> n >> m) {
        memset(stu_s, 0, sizeof(stu_s));
        memset(cou_s, 0, sizeof(cou_s));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> s[i][j];
                stu_s[i] += s[i][j];  //每个学生的总成绩
                cou_s[j] += s[i][j];  //每门课的分数总和
            }
        }
        //第一行，输出学生平均成绩
        for (int i = 0; i < n; i++) {
            if (i == 0)
                printf("%.2f", 1.0 * stu_s[i] / m);
            else
                printf(" %.2f", 1.0 * stu_s[i] / m);
        }
        cout << endl;

        //第二行，输出课的平均成绩
        for (int i = 0; i < m; i++) {
            if (i == 0)
                printf("%.2f", 1.0 * cou_s[i] / n);
            else
                printf(" %.2f", 1.0 * cou_s[i] / n);
        }
        cout << endl;

        int count = 0;
        for (int i = 0; i < n; i++) {
            int flag = 1;
            for (int j = 0; j < m; j++) {
                if (s[i][j] < 1.0 * cou_s[j] / n) {  //单科
                    flag = 0;
                    break;
                }
            }
            if (flag) count++;  //各科成绩均大于等于平均成绩
        }
        cout << count << endl << endl;
    }
    return 0;
}

2024 C 语言合法标识符

Problem Description

输入一个字符串，判断其是否是 C 的合法标识符。

Input

输入数据包含多个测试实例，数据的第一行是一个整数 n, 表示测试实例的个数，然后是 n 行输入数据，每行是一个长度不超过 50 的字符串。

Output

对于每组输入数据，输出一行。如果输入数据是 C 的合法标识符，则输出 “yes”，否则，输出 “no”。

Sample Input

3
12ajf
fi8x_a
ff ai_2

Sample Output

no
yes
no

解题思路

遍历字符串，通过 isalpha(),isalnum()判断是否为字母，数字
C 合法标识符：由字母、数字、'_'组成，第一个字符必须是字母或者下划线

参考源码

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
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n, flag;
    string s;
    cin >> n;
    getchar();  //吃掉换行符
    while (n--) {
        flag = 1;
        getline(cin, s);                      //读取一行
        if (!isalpha(s[0]) && s[0] != '_') {  //若第一个字符不是字母或者下划线
            cout << "no" << endl;
            continue;
        }
        for (int i = 1; i < s.length(); i++) {
            if (!isalnum(s[i]) && s[i] != '_') {  //若字符不是字母、数字或者下划线
                flag = 0;
                break;
            }
        }
        if (flag)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
    return 0;
}

2025 查找最大元素

Problem Description

对于输入的每个字符串，查找其中的最大字母，在该字母后面插入字符串 “(max)”。

Input

输入数据包括多个测试实例，每个实例由一行长度不超过 100 的字符串组成，字符串仅由大小写字母构成。

Output

对于每个测试实例输出一行字符串，输出的结果是插入字符串 “(max)” 后的结果，如果存在多个最大的字母，就在每一个最大字母后面都插入 “(max)”。

Sample Input

abcdefgfedcba
xxxxx

Sample Output

abcdefg(max)fedcba
x(max)x(max)x(max)x(max)x(max)

解题思路

遍历字符串找最大值，之后遍历输出，若为最大值，则加(max)

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] > max) max = s[i];  //找最大值
        }
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == max)
                cout << s[i] << "(max)";  //若为最大值，则加(max)
            else
                cout << s[i];  //否则原样输出
        }
        cout << endl;
    }
    return 0;
}

2026 首字母变大写

Problem Description

输入一个英文句子，将每个单词的第一个字母改成大写字母。

Input

输入数据包含多个测试实例，每个测试实例是一个长度不超过 100 的英文句子，占一行。

Output

请输出按照要求改写后的英文句子。

Sample Input

i like acm
i want to get an accepted

Sample Output

I Like Acm
I Want To Get An Accepted

解题思路

读取字符串，首字母大写，若读到空格则下一个字母大写

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    char s[101];
    while (gets(s)) {
        s[0] = toupper(s[0]);         //首字母大写
        for (int i = 0; s[i]; i++) {  //若不为空
            if (s[i] == ' ' && isalpha(s[i + 1])) {
                s[i + 1] = toupper(s[i + 1]);  //若读到空格则下一个字母大写
            }
            cout << s[i];
        }
        cout << endl;
    }
    return 0;
}

2027 统计元音

Problem Description

统计每个元音字母在字符串中出现的次数。

Input

输入数据首先包括一个整数 n，表示测试实例的个数，然后是 n 行长度不超过 100 的字符串。

Output

对于每个测试实例输出 5 行，格式如下：
a:num1
e:num2
i:num3
o:num4
u:num5
多个测试实例之间由一个空行隔开。
请特别注意：最后一块输出后面没有空行：）

Sample Input

2
aeiou
my name is ignatius

Sample Output

a:1
e:1
i:1
o:1
u:1

a:2
e:1
i:3
o:0
u:1

解题思路

通过 if 或者 switch 选择计数，注意输出格式

参考源码

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 <cstring>
#include <iostream>
using namespace std;
int main() {
    int n, c1, c2, c3, c4, c5;
    string s;
    cin >> n;
    getchar();  //吃掉回车
    while (n--) {
        getline(cin, s);
        c1 = c2 = c3 = c4 = c5 = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == 'a') c1++;
            if (s[i] == 'e') c2++;
            if (s[i] == 'i') c3++;
            if (s[i] == 'o') c4++;
            if (s[i] == 'u') c5++;
        }
        cout << "a:" << c1 << endl;
        cout << "e:" << c2 << endl;
        cout << "i:" << c3 << endl;
        cout << "o:" << c4 << endl;
        cout << "u:" << c5 << endl;
        if (n) cout << endl;
    }
    return 0;
}

2028 Lowest Common Multiple Plus

Problem Description

求 n 个数的最小公倍数。

Input

输入包含多个测试实例，每个测试实例的开始是一个正整数 n，然后是 n 个正整数。

Output

为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。
你可以假设最后的输出是一个 32 位的整数。

Sample Input

2 4 6
3 2 5 7

Sample Output

12
70

解题思路

最小公倍数 lcm(x, y) = x * y / gcd(x, y) (其中 gcd()求最大公约数)
欧几里得算法求最大公约数：gcd(a, b) = gcd(b, a mod b)
知道公式之后就好做了

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int gcd(int a, int b) {
    if (b == 0)
        return a;  //若为0则最大公约数为a
    else
        return gcd(b, a % b);  //欧几里得算法
}
int main() {
    int n, num, ans;
    while (cin >> n) {
        ans = 1;
        while (n--) {
            cin >> num;
            ans = ans / gcd(ans, num) * num;  //先除再乘
        }
        cout << ans << endl;
    }
    return 0;
}

2029 Palindromes_easy version

Problem Description

“回文串” 是一个正读和反读都一样的字符串，比如 “level” 或者 “noon”等等就是回文串。请写一个程序判断读入的字符串是否是 “回文”。

Input

输入包含多个测试实例，输入数据的第一行是一个正整数 n,
表示测试实例的个数，后面紧跟着是 n 个字符串。

Output

如果一个字符串是回文串，则输出 “yes”, 否则输出 “no”.

Sample Input

4
level
abcde
noon
haha

Sample Output

yes
no
yes
no

解题思路

循环 i 从 0 到 len/2,比较 s[i] 和 s[len - i - 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
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        int flag = 1;
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {  //遍历一半
            if (s[i] != s[len - i - 1]) {    //比较 s[i] 和 s[len - i - 1]
                flag = 0;
                break;
            }
        }
        if (flag)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
    return 0;
}

相关内容