NJUCSE17

2017 问题求解一 期末考试

2018-01-05 by Fancy

关于字符串的读入：（以下c表示字符，s表示字符串）
1、读入一个字符：getchar(c); scanf("%c", &c);
2、读入一个字符（跳过空格和回车）：cin>>c;
（注：如果读入字符前后已知有空格，比如第一题里的操作符，那么可以scanf("%s", s); 然后用s[0]
3、读入一串字符（到空格和回车停止）：cin>>s; scanf("%s", s);
4、读入一行字符（到回车停止）：gets(s); cin.getline(s, 1005, '\n'); fgets(s, 1005, stdin);
（注：读入一行字符串时，需要先把上一行（如果有读入数字啥的）结尾的换行符吃掉。可以直接先读一行或者while(c!='\n') c=getchar();
（注：gets()由于缓冲区溢出漏洞，被c11废除
（注：fgets()会把回车也读进去
　
（注：Windows里的换行符是'\n'，OS X里的换行符是'\r'，Linux里是'\n'和'\r'
（当然你愿意特判的话也可以全部getchar()

1360 Problem A 项链

MJ很喜欢用彩色珠子做的项链。他制作项链包括以下两个基本操作：
A i C：在位置 i 插入颜色为 C ( 颜色用大写字母表示 ) 的珠子；
D i： 去掉在位置 i 的珠子；
S i j：交换位置 i,j 的珠子 ( i,j 可能相同，大小关系任意 ) ；
P：查看当前项链状态；
例如，下面操作序列将得到项链“BA”
A 0 A
A 0 B
再继续执行下列操作之后，将得到项链“CDA”
D 0
A 0 C
A 1 D
在执行下列操作，最终得到项链“ADC”
S 0 2

暴力，插入和删除就把后面的全都移一位
　
时间复杂度：
插入、删除、打印：O(n)
交换：O(1)
　
我考场上用的是vector，理论时间复杂度一样
　
log复杂度大概可以平衡树（手动滑稽

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
#include <iostream>
#include <cstdio>
int T, n, a[3005];
inline void Add() {
	int pos;
	char val[5];
	scanf("%d%s", &pos, val);
	for(int i = n++; i > pos; i--)
		a[i] = a[i - 1];
	a[pos] = val[0] - 'A';
}
inline void Delete() {
	int pos;
	scanf("%d", &pos);
	n--;
	for(int i = pos; i < n; i++)
		a[i] = a[i + 1];
}
inline void Swap() {
	int x, y;
	scanf("%d%d", &x, &y);
	std::swap(a[x], a[y]);
}
inline void Print() {
	for(int i = 0; i < n; i++)
		printf("%c", a[i] + 'A');
	printf("\n");
}
int main() {
	for(scanf("%d", &T); T; T--) {
		char opt[5];
		scanf("%s", opt);
		if (opt[0] == 'A') Add();
		else if (opt[0] == 'D') Delete();
		else if (opt[0] == 'S') Swap();
		else Print();
	}
}
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 <algorithm>
#include <cstdio>
#include <vector>
std::vector<int> a;
int main() {
	int T;
	for(scanf("%d", &T); T; T--) {
		int x, y;
		char opt[5], z[5];
		scanf("%s", opt);
		if (opt[0] == 'A') {
			scanf("%d%s", &x, z);
			a.insert(a.begin() + x, z[0] - 'A');
		} else if (opt[0] == 'D') {
			scanf("%d", &x);
			a.erase(a.begin() + x);
		} else if (opt[0] == 'S') {
			scanf("%d%d", &x, &y);
			std::swap(a[x], a[y]);
		} else {
			for(std::vector<int>::iterator iter = a.begin(); iter != a.end(); iter++)
				printf("%c", *iter + 'A');
			//for(int i = 0; i < a.size(); i++) printf("%c", a[i] + 'A'); //和上两行的作用一样
			printf("\n");
		}
	}
}

1361 Problem B 括号匹配

判断给定字符串中的括号是否匹配。匹配输出1，否则输出0。
每个字符串最多含有 ‘(‘, ‘[‘, ‘{‘, ‘)’, ‘]’, ‘}’ 六种不同字符。
规定空字符串是”括号匹配的”。

因为最后忘了判断栈是否为空WA了两发，身败名裂

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 <cstdio>
int T, n, top, stack[1005], a[200];
char s[1005];
inline bool DoIt() {
	gets(s);
	n = strlen(s);
	top = 0;
	for(int i = 0; i < n; i++) {
		int x = a[s[i]];
		if(!x) continue;
		if(x & 1) stack[++top] = x;
		else if(top && x - stack[top] == 1) top--;
		else return 0;
	}
	return !top;
}
int main() {
	a['('] = 1; a[')'] = 2;
	a['['] = 3; a[']'] = 4;
	a['{'] = 5; a['}'] = 6;
	for(scanf("%d", &T), gets(s); T; T--)  //这个gets为了把第一行的换行符吃掉
		printf("%d\n", DoIt());
}

1347 Problem C “相邻”积

现有一N行M列的正整数数阵A，找出A中相邻且按同一方向排列（在同一直线上）的4个数，使得它们的乘积K最大。“相邻”定义为：一个数在另一个数的上、下、左、右或对角线的最近位置。
比如A为：
90 24 26 33
12 37 38 1
57 28 91 42
23 11 15 25
主对角线上的4个数相乘可以得到最大积7575750。

暴力枚举每一个点的每一种方向
其中八个方向可以简化为四个，因为从左到右和从右到左是一样的
O(n^2*16)
　
当然常数可以变成4，就是按每个方向扫一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
int n, m, ans, a[1005][1005], X[]={0, 1, 1, 1, 0}, Y[]={0, 1, 0, -1, -1};
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%d", &a[i][j]);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			for(int t = 1; t <= 4; t++) {  //枚举方向
				int tot = 1, x = i, y = j;
				for(int k = 1; k <= 4; k++, x += X[t], y += Y[t]) {  //X和Y数组为方向向量
					if(x < 1 || x > n || y < 1 || y > m) break;
					tot *= a[x][y];
				}
				ans = std::max(ans, tot);
			}
	printf("%d\n", ans);
}

1362 Problem D 冒泡排序

请你实现冒泡算法，要求利用递归来替换该算法的外层循环
注意从后往前排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cstdio>
int n, a[1001];
void Dfs(int st) {
	if(st == n) return;
	for(int i = n; i > st; i--)
		if(a[i] > a[i - 1]) std::swap(a[i], a[i - 1]);
	for(int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	printf("\n");
	return Dfs(st + 1);
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	Dfs(1);
}
Tags: 编程
← “计科竞赛一览”主题团生 算法题常见错误汇总 →