MSC趣味C编程决赛总结

MSC趣味C编程决赛总结 我太弱了(46/151)

目录

1. Excel in Excel (100 分)
2. Fall in Hangzhou (100 分)

详细内容 1. Excel in Excel (100 分)

这是很有趣的一道题，

题目描述

在Microsoft Office Excel中，我们用十进制数字（0到9）来表示一行，用大写英文字母（A到Z）表示一列。一个字母和一个数字的组合（如C9）唯一表示一个单元格。

当然，如果行数超过十，我们会用更多位的十进制数去表示，例如列10, 列11, 列12, …；对于列，我们的也需要针对第26列之后的列的处理策略。

Excel中使用更多位大写英文字母来进行表示。列Z（第26列）后是列AA（第27列），然后是列AB, 列AC, 列AD…；列AZ的下一列是列BA，列BZ的下一列是列CA，以此类推。当两个字母也不够用了以后，就用三个字母。例如，列ZZ之后是列AAA, 列AAB, 列AAC, …, 列AAZ, 列ABA, 列ABB等等。我们把这些能唯一表示一列的英文字母组合（更严谨点，排列）称为列标识符。

输入格式：

每个测试文件包含一个测试样例。每个样例有若干行，其中最后一行是#。

样例中每一行是一个列序号（十进制数）或一个列标识符（大写英文字母字符串）。读到列序号时，你需要将其转换成列标识符；读到列标识符时，你需要将其转换成列序号。

输出格式：

对于输入样例中除了#的每一行，输出转化后的列标识符或列序号。

输入样例:

1
26
AA
100
ZZ
AAA
9285
313863917

输出样例:

A
Z
27
CV
702
703
MSC
ZJUMSC

算法分析

类似于进制转化，但是要做一些特殊处理。

方法一：直接转化为26进制数，然后对这个数的每一位遍历，如果某一位出现非正数，就向上一位借一个1下来。这一位加上26。
方法二：转化26进制数时，如果某一位出现了整除，就直接把这个数减一（上一位减一），然后输出时某一位为0就置为26再输出。

方法一

#include
#include
#define N 100
char s[N];
int ans[N], t;
int main(){
	while(gets(s)){
		if(s[0] == '#') break;
		else if(s[0] >= '0' && s[0] <= '9'){
			t = 0;
			int len = strlen(s);
			int sum = 0;
			for(int i = 0; i < len; ++ i){
				sum = sum * 10 + (s[i] - '0');
			}
			while(sum){
				ans[++ t] = sum % 26;
				sum = sum / 26;
			}
			for(int i = 1; i <= t; ++ i){
				if(ans[i] <= 0 && i != t){
					ans[i] += 26;
					ans[i + 1] --;
				}				
			}
			while(!ans[t]) t --;//删除前导0
			for(int i = t; i >= 1; -- i)
				printf("%c", 'A' + ans[i] - 1);	
			printf("n");
		}
		else{
			int len = strlen(s);
			int sum = 0, digit = 1;
			for(int i = len - 1; i >= 0; -- i){
				sum = sum + digit * (s[i] - 'A' + 1);
				digit *= 26;
			}
			printf("%dn", sum);
		}
	}
	return 0;
}

方法二

#include
#include
#define N 100
char s[N];
int ans[N], t;
int main(){
	while(gets(s)){
		if(s[0] == '#') break;
		else if(s[0] >= '0' && s[0] <= '9'){
			t = 0;
			int len = strlen(s);
			int sum = 0;
			for(int i = 0; i < len; ++ i){
				sum = sum * 10 + (s[i] - '0');
			}
			while(sum){
				ans[++ t] = sum % 26;
				if(sum % 26 == 0) sum -= 1;
				sum = sum / 26;
			}
			for(int i = t; i >= 1; -- i){
				if(!ans[i]) ans[i] = 26;
				printf("%c", 'A' + ans[i] - 1);	
			}
			printf("n");
		}
		else{
			int len = strlen(s);
			int sum = 0, digit = 1;
			for(int i = len - 1; i >= 0; -- i){
				sum = sum + digit * (s[i] - 'A' + 1);
				digit *= 26;
			}
			printf("%dn", sum);
		}
	}
	return 0;
}

2.Fall in Hangzhou (100 分)

类似的题目在洛谷P1318

题目描述

有一段石板路。每块石板可以认为是一个长方体（地面是边长为1的正方形）。石板路凹凸不平。如果有一块石板的前一块和后一块石板都比它高，那么这块石板上会积水。当然了，如果有几块连续的石板，它们前面和后面的两块石板比它们中的任意一块都高，那么它们之上也会积水。下面给出一组测试数据，请你算出最大的积水体积。

输入格式

每个测试文件的第一行是一个正整数n，代表有n组测试样例。

每个测试样例代表一条石板路，其第一行是一个正整数k，代表该石板路有k块石板；第二行是k个正整数，用空格分隔，依次代表每块石板的高度。测试样例不保证输入的行末没有多余空格。

提交的程序从标准输入(stdin)中读入数据即可。

输出格式

对于每个测试样例，在标准输出(stdout)中输出它的最大积水体积并换行。

输入样例

4
3
3 1 3
5
5 3 1 4 2
7
5 1 4 2 6 2 3
9
1 2 3 4 5 4 3 2 1

输出样例:

2
4
9
0

错误原因：对于多组数据处理时，忘记对数组进行初始化

(memset忘记用了，头文件是#include)

算法分析

从头到尾，从尾到头，算一下每个元素左边的最大高度和右边的最大高度。然后累计总和即为答案。

代码实现

#include
#include
#define N 1000005
int max(int a, int b){
	return a > b ? a : b;
}
int min(int a, int b){
	return a > b ? b : a;
}
int a[N], mxl[N], mxr[N];
int main(){
	int n, k;
	scanf("%d", &n);
	while(n --){
		memset(a, 0, sizeof(a));
		memset(mxl, 0, sizeof(mxl));
		memset(mxr, 0, sizeof(mxr));
		scanf("%d", &k);
		for(int i = 1; i <= k; ++ i){
			scanf("%d", &a[i]);
			mxl[i] = max(a[i - 1], mxl[i - 1]);
		}
		for(int i = k; i >= 1; -- i){
			mxr[i] = max(a[i + 1], mxr[i + 1]);
		}
		long long sum = 0;
		for(int i = 1; i <= k; ++ i)
			if(mxl[i] > a[i] && mxr[i] > a[i]) sum += (min(mxl[i], mxr[i]) - a[i]);
		printf("%lldn", sum);
	}
	return 0;
}