刷题平台：https://judge.u-aizu.ac.jp
Github项目：https://github.com/pengng/AIZU_ONLINE_JUDGE
4年前我还是用c语言刷题，现在已经开始用c++。原因是c++有STL，里面包含了一些常用的数据结构的实现，包括栈、队列、链表等。这样方便解一些复杂的题目时，不用再去自己实现基础的数据结构。
另外，开始使用Visual Studio开发工具代替以前的Sublime Text，创建项目、编译和断点调试会方便很多。
这个刷题平台不同于的LeetCode，它解题时需要自己处理标准输入/输出，而LeetCode只需要实现算法核心，输入则通过函数参数传入。
c的标准库到了c++下面的命名有了些变化，头文件名开头带了”c”，并且不需要结尾的”.h” 。例如：在c语言中<math.h>头文件在c++下变成<cmath>；<ctype.h>则变成<cctype>。
1.排序3个数字
输入3个整数，输出它们的升序排列，数字间用1个空格分隔，用换行符结尾。如下图所示：
#include <stdio.h>
void
priArr(int [], int);
void
sort(int [], int);
int
main(void)
{
int arr[3];
scanf("%d %d %d", arr, arr + 1, arr + 2);
sort(arr, 3);
priArr(arr, 3);
return 0;
}
void
priArr(int arr[], int len)
{
int i = 0;
printf("%d", arr[i++]);
for ( ; i < len; i++)
printf(" %d", arr[i]);
putchar('n');
}
void
sort(int arr[], int len)
{
int i, j, tmp;
for (i = 1; i < len; i++) {
tmp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = tmp;
}
}
后来觉得3个数字排序这种特例可以不用特地写一个排序函数，并且用数组来存储它们，所以用c++重新写。如下所示：
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
if (a > b)
{
swap(a, b);
}
if (a > c)
{
swap(a, c);
}
if (b > c)
{
swap(b, c);
}
cout << a << " " << b << " " << c << endl;
}
程序结尾输出了\(a,b,c \)三个数字，并且满足\(a \leq b \leq c \)。程序包含3个if结构：
- 第1个 if 执行之后，如果 \(a > b \) ，则交换 a 和 b 的值，此时满足 \(a \leq b \) ；
- 第2个 if 执行之后，如果 \(a > c \) ，则交换 a 和 c 的值，此时满足 \(a \leq b \) 且 \(a \leq c \) ；
- 第3个 if 执行之后，如果 \(b > c \) ，则交换 b 和 c 的值，此时满足 \(a \leq b \) 且 \(a \leq c \) 且 \(b \leq c \)，即 \(a \leq b \leq c \)。
对于”交换两个值“这样的常规操作，c++的标准库就包含了swap函数，这挺好的。
2.最小值，最大值和求和
输入n个整数，输出其中的最小值，最大值和这些值的总和。
最小值和最大值需要一个初始值，所以按照题目用#define宏定义了MIN和MAX。在c++版本的程序中，不再使用宏来定义，而是用<climits>中定义了的INT_MAX和INT_MIN。
#include <stdio.h>
#define MIN -1000000
#define MAX 1000000
int
main(void)
{
int min = MAX;
int max = MIN;
int num, c;
long long sum = 0;
scanf("%d", &c);
while (c--) {
scanf("%d", &num);
sum += num;
min = num < min ? num : min;
max = num > max ? num : max;
}
printf("%d %d %lldn", min, max, sum);
return 0;
}
#include<iostream>
#include<climits>
using namespace std;
int main() {
int minimum = INT_MAX;
int maximum = INT_MIN;
long long sum = 0LL;
int x, n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
sum += x;
if (x < minimum) minimum = x;
if (x > maximum) maximum = x;
}
cout << minimum << " " << maximum << " " << sum << endl;
}
3.倒序数字
将输入的n个整数倒序后输出。
原来c语言版本用的是动态数组，使用<stdlib.h>中的malloc函数来申请内存空间。后来觉得题目的n上限值较小(\(n \leq 100 \))，直接用这个上限当常数，做数组的固定大小即可。
用malloc并不能节约多少内存空间。同时数组中的各个数字范围较小，也可以用short int类型存储，但也因为n较小，而同样节约不了多少空间。
#include <stdio.h>
#include <stdlib.h>
int
main(void)
{
int n, num;
int i = 0;
int * arr;
scanf("%d", &n);
arr = (int *) malloc(n * sizeof(int));
while (i < n)
scanf("%d", arr + i++);
printf("%d", arr[--n]);
while (n--)
printf(" %d", arr[n]);
putchar('n');
free(arr);
return 0;
}
c++版本则是利用递归的性质，将数字序列倒序输出。
#include<iostream>
using namespace std;
void fn(int n) {
int x;
cin >> x;
if (--n > 0) fn(n);
if (n > 0) cout << " ";
cout << x;
}
int main() {
int n;
cin >> n;
fn(n);
cout << endl;
}
4.矩阵乘法
输入\(n, m, l \)和矩阵\(A_{nm} \)，以及矩阵\(B_{ml} \)。输出两个矩阵的乘积\(A_{nm}B_{ml} \)。
c语言用动态数组，而c++版本则用静态数组。因为题目中\(1 \leq n,m,l \leq 100 \)，也就是总的空间需要\(100 \times 100 \times 2 = 20,000 \)。
原来c版本用的是long long int类型，后来发现只需要单个数值是long long int即可，而数组项的类型可以用short int来节约空间。
#include <stdio.h>
#include <stdlib.h>
void
pri(long long **, long long **, int, int, int);
long long **
Malloc(int, int);
void
Scanf(long long * [], int, int);
int
main(void)
{
int n, m, l;
long long **matrixA, **matrixB;
scanf("%d %d %d", &n, &m, &l);
matrixA = Malloc(n, m);
matrixB = Malloc(m, l);
Scanf(matrixA, n, m);
Scanf(matrixB, m, l);
pri((long long **) matrixA, (long long **) matrixB, n, m, l);
return 0;
}
void
pri(long long **a, long long **b, int n, int m, int l)
{
int i, j, k;
long long sum;
for (i = 0; i < n; i++)
for (j = 0; j < l; j++) {
sum = 0;
for (k = 0; k < m; k++)
sum += a[i][k] * b[k][j];
printf("%lld", sum);
if (j == l - 1)
putchar('\n');
else
putchar(' ');
}
}
long long **
Malloc(int n, int m)
{
int i;
long long **arr = (long long **) malloc(sizeof(long long *) * n);
for (i = 0; i < n; i++)
arr[i] = (long long *) malloc(sizeof(long long) * m);
return arr;
}
void
Scanf(long long *arr[], int n, int m)
{
int i, j;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
scanf("%lld", *(arr + i) + j);
}
注意：计算矩阵的每一项时，需要用long long int类型。因为\(1 \leq a_{ij}, b_{ij} \leq 10,000 \)，所以\(1 \leq c_{ij} \leq 10,000,000,000 \)已经超过int类型的表示范围。
#include<iostream>
using namespace std;
int main() {
int n, m, l;
short A[100][100], B[100][100];
cin >> n >> m >> l;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> A[i][j];
}
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < l; j++)
{
cin >> B[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < l; j++)
{
long long sum = 0LL;
for (int k = 0; k < m; k++)
{
sum += A[i][k] * B[k][j];
}
if (j > 0) cout << " ";
cout << sum;
}
cout << endl;
}
}
5.切换大小写
输入一个字符串，输出一个字符串，其中大写字母转成小写字母，小写字母转成大写字母。
#include <stdio.h>
int
main(void)
{
char ch;
while ((ch = getchar()) != EOF)
if (ch >= 'A' && ch <= 'Z')
putchar(ch - 'A' + 'a');
else if (ch >= 'a' && ch <= 'z')
putchar(ch - 'a' + 'A');
else
putchar(ch);
return 0;
}
c语言是通过自己计算的，c++版本则使用标准库<cctype>中的islower、isupper、tolower、toupper函数。
#include<iostream>
#include<cctype>
using namespace std;
int main() {
char c;
while (cin.get(c))
{
if (isupper(c)) cout << (char)tolower(c);
else if (islower(c)) cout << (char)toupper(c);
else cout << c;
}
}