刷题日记——济南大学机试

折戟厦大，考虑调剂济南大学，但是更想去的是杭师大，还是刷题，济南大学比厦门大学题目简单很多，因此一篇文章不多分析，直接给出代码，全部采用纯C语言编写并且AC，不用C++的stl库。
争取今天一口气刷完济南大学的机试题目！

本次博客不分段，是一篇长博文，十分硬（jian）核（dan），建议配合目录查阅

济南大学机试题目链接，请点这里哟

字符串转化

代码

#include <stdio.h>

int main() {
	char num[1000];
	while (scanf("%s", num) != EOF) {
		int sum = 0;
		int i = 0;
		while (num[i] != '\0') {
			sum += num[i] - 'a' + 1;
			i++;
		}
		printf("%d\n", sum);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

整数去重

代码——列表避免暴力（空间换时间）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int num[20001];


int main() {
	int n;

	while (scanf("%d", &n) != EOF) {
		int real_n = 0;
		bool sheet[100] = {false};
		for (int i = 0; i < n; i++) {
			int temp;
			scanf("%d", &temp);
			if (sheet[temp] == false) {
				num[real_n++] = temp;
				sheet[temp] = true;
			}
		}
		for (int i = 0; i < real_n; i++) {
			printf("%d ", num[i]);
		}
		printf("\n");
	}
	return 0;
}

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

本题注意事项

• 本题有暴力方法，就是从头开始二重遍历，在后面遇到相同的元素就整体前移，这个方法十分耗时。
• C语言使用bool类型需要使用到stdbool.h头文件，不然会报错

更多关于C标准库的知识，可以参考以下的链接，建议考前还是突击一下，不然这个不知道真的很伤

• 常见15个C语言的标准库
• C 标准库 - 参考手册

求斐波那契数列的第n项

代码

肥波的题目真的做yue了，眼睛闭上代码都能写出来。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

unsigned long long f(int n) {
	if (n == 0 || n == 1 ) {
		return 1;
	}
	return f(n - 1) + f(n - 2);
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		printf("%lld\n", f(n));
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

进制转换问题

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main() {
	int n;
	scanf("%d", &n);
	int num[100];
	int i = 0;
	while (n != 0) {
		num[i] = n % 2;
		n /= 2;
		i++;
	}
	for (; i >= 1; i--) {
		printf("%d", num[i-1]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

奇数还是偶数

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

char *f(int n) {
	if (n % 2 == 0) {
		return "even number";
	}
	return "odd number";
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		printf("%s\n", f(n));
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

找出众数

代码——缝缝补补

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>



int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		int ptr[20000] = {0};
		int *counts = ptr + 10000;
		int index[501];
		int single_num = 0;
		for (int i = 0; i < n; i++) {
			int temp;
			scanf("%d", &temp);
			if (counts[temp] == 0) {//首次出现需要记录下标
				index[single_num++] = temp;//不记录重复出现的值
			}
			counts[temp]++;//计数
		}
		//找最大counts值的index值
		int max = 0;
		int tag;
		for (int i = 0; i < single_num; i++) {
			if (max < counts[index[i]]) {
				max = counts[index[i]];
				tag = index[i];
			}
		}
		printf("%d\n", tag);
	}
	return 0;
}

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

分析——缝缝补补法

这题比较有意思，我的题解代码经过三轮迭代：

• 第一轮：我一开始以为输入的所有数字都是1-1000，因此直接设置一个容量为1001的数组，序号是输入数字，数组值是出现次数，这样就像上面的整数去重一样，但是发现只能过三分之一的样例

• 第二轮：还好我有大会员，看了发现是输入数字竟然是四位的，于是数组容量设置成10000，结果还是只能过83.3%的样例，再看输入，发现居然有负数输入

• 第三轮：于是再改，直接把输入数组设置成容量为20000，同时为了最小变动，数组改名叫ptr，原来的数组名设置成为指针，指向ptr+10000的位置，这样你有负数我也不怕了

但是这样有个问题，就是，如果我提前不知道测试样例，我是不可能对第一轮的代码产生质疑的，肯定要想很久，到这里我就不得不喷N诺的开发者了，我们可以忍受你在网站上投放广告，或者要求我们帮你宣传，这些都可以，但是非要花30买小会员才能刷题（这人多也赚得够多了），非要花200才能告诉我们测试用例，复试机试就那么一两个月的事，你非要让我们200买一年真的太离谱了，一直这么玩，你不可能推广的开的

分析——全适应法（改进版：使用hash）

思路就是设置 数值-出现次数-序号 三个数据捆绑关系，这样有一个不方便的地方就是，每次判断数值是否出现时需要遍历
当然我有个粗略的改进方案，比如说把数组改成hash，模500放入，但是需要设置线性探测等避免冲突的方法。

括号匹配的问题

分析——数组模拟栈

使用C语言，没有栈的标准库，于是自己动手用数组模拟一个栈，需要实现pop和push，详细请看代码

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

char stack[1000];
int size = 0;

void pop() {
	stack[--size] = '\0';
}

void push(char n) {
	stack[size++] = n;
}


int main() {
	char str[1000];
	while (scanf("%s", str) != EOF) {
		//初始化
		size = 0;

		//获取长度
		int length = 0;
		while (str[length++] != '\0');
		//此外还可以用string.h中的int strlen(char str)获取str的长度
		//也可以用sizeof()
		int i;
		for (i = 0; i < length; i++) {
			if (str[i] == '[' || str[i] == '(') {
				push(str[i]);
			} else if (str[i] == ']') {
				if (stack[size - 1] == '[') {
					pop();
				} else {
					printf("NO");
					break;
				}
			} else if (str[i] == ')') {
				if (stack[size - 1] == '(') {//需要注意，栈顶元素的序号是size-1
					pop();
				} else {
					printf("NO");
					break;
				}
			}

		}
		if (i == length) {
			printf("YES");
		}
		printf("\n");
	}
	return 0;
}
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

单词翻转

代码

#include <stdio.h>
#include <string.h>

char str_seq[1001][16];
char temp[10000];

int main() {
	fgets(temp, 10000, stdin);
	int length = strlen(temp);
	int ptr = 0;
	int i = 0;
	while (ptr < length) {
		int j = 0;
		while (temp[ptr] != ' ' && temp[ptr] != '\n') {
			str_seq[i][j++] = temp[ptr++];
		}
		str_seq[i][j] = '\0';
		i++;
		ptr++;
	}
	for (int k = i - 1; k >= 0; k--) {
		printf("%s ", str_seq[k]);
	}
	printf("\n");

}
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

注意点

在翻阅别人的题解时注意到一个可以减少思考复杂度的点：

• 将输入字符串的最后一个’\n’字符pop出去
• 在原有’\n’字符替换成为空格’ ’

但注意，这是c++语法对string的操作

喝饮料问题

代码

一开始当成了0-1背包问题，写出的代码只能过40%样例

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

struct drink {
	int mi;
	int wi;
};

struct drink shop[1001];
double dp[1001][1001];

int max(int a, int b) {
	if (a > b) {
		return a;
	}
	return b;
}

int main() {
	int n, x;
	while (true) {
		scanf("%d %d", &x, &n);
		if (x == -1 && n == -1) {
			break;
		}
		//初始化dp
		for (int i = 0; i <= n; i++) {
			dp[i][0] = 0;
		}
		for (int i = 0; i <= x; i++) {
			dp[0][i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d %d", &shop[i].mi, &shop[i].wi);
		}

		//开始0-1背包
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= x; j++) {
				if (shop[i].wi > j) {
					//装不下
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - shop[i].wi] + shop[i].mi);
				}
			}
		}
		printf("%.3f\n", dp[n][x]);
	}
	return 0;
}
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

后来发现根本没有背包问题复杂，就是把最实惠的饮料全部喝了，把钱全部用完就好了

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

int value[1001];
int weigh[1001];
double worth[1001];

int find_max_index(int n) {
	double large = -1;
	int index;
	for (int i = 0; i < n; i++) {
		if (worth[i] > large) {
			index = i;
			large = worth[i];
		}
	}
	return index;
}

int main() {
	int n, x;
	while (true) {
		scanf("%d %d", &x, &n);
		if (x == -1 && n == -1) {
			break;
		}

		for (int i = 0; i < n; i++) {
			scanf("%d %d", &weigh[i], &value[i]);
			worth[i] = (double)weigh[i] / value[i];
		}
		double result = 0;
		int counts = 0;
		while (counts != n) {
			int index = find_max_index(n);
			if (x >= value[index]) {
				result += weigh[index];
				x -= value[index];
			} else {
				result += worth[index] * x;
				x -= x;
			}
			counts++;
			worth[index] = -1;
		}
		printf("%0.3f\n", result);
	}
	return 0;
}
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

简单的背包问题

代码——这是真的背包问题了

但是与01背包问题有区别，比01背包更简单，可以将01背包的weigh和value令为相同的值

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

int weigh[1000];
int value[1000];

int dp[1000][1000];

int max(int a, int b) {
	if (a > b) {
		return a;
	} else {
		return b;
	}
}

int main() {
	int s, n;
	while (scanf("%d %d", &s, &n) != EOF) {
		for (int i = 1; i <= n; i++) {
			scanf("%d", &weigh[i]);
			value[i] = weigh[i];
		}
		//初始化dp
		for (int i = 0; i <= n; i++) {
			dp[i][0] = 0;
		}
		for (int i = 0; i <= s; i++) {
			dp[0][i] = 0;
		}
		bool flag = false;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= s; j++) {
				if (weigh[i] > j) {
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weigh[i]] + value[i]);
				}
				if (dp[i][j] == s) {
					flag = true;
				}
			}
		}
		if (flag == true) {
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}
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

全部AC，合影留念

记录一下心情，下午收到杭师大老师的回复，算是我折戟厦大后一束希望之光，下面全力冲刺杭师大调剂！争取笔试满分！