当前栏目
杭电OJ2020-2029
杭电 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)
参考源码
#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
解题思路
贪心思想，从面值大的开始，整除求余
参考源码
#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
参考源码
#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
解题思路
简单题，细心一点就好，求行列的平均值
参考源码
#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 合法标识符：由字母、数字、'_'组成，第一个字符必须是字母或者下划线
参考源码
#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)
参考源码
#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
解题思路
读取字符串，首字母大写，若读到空格则下一个字母大写
参考源码
#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 选择计数，注意输出格式
参考源码
#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) 知道公式之后就好做了
参考源码
#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] 是否相等 或者也可以采用双指针的形式，一个正向，一个反向，比较字符是否相等
参考源码
#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;
}