ABC344 A-E题解

不易不难，写到5题很简单，但是要有足够的思维能力。

A

题目

我们用一个 flag 变量记录我们是不是在两个竖杠之间，如果是，就不能输出这个字符，否则如果这个字符不是竖杠，就输出这个字符。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
string s;
bool flag = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> s;
	for (int i = 0; i < (int)s.size(); i++) {
		if (s[i] == '|') flag = !flag;
		if (!flag && s[i] != '|') cout << s[i];
	}
	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

B

题目

一直输入 $a_n$，然后让 $n$ 加上 $1$，如果 $a_n$ 是 $0$ 就跳出输入循环。最后倒着输出数组内容即可。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int a[2001];
int n = 1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> a[n];
	while (a[n]) {
		n++;
		cin >> a[n];
	}
	for (int i = n; i >= 1; i--) cout << a[i] << '\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

C

题目

与其输入一个数后寻找合适的三个数，不如与处理处可行的数。对于可行的三个数，我们将这三个数的和标记为 $1$，对于每一个询问，如果这个数的标记为 $1$ 就说明有三个数的和是询问的的数。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n, m, l;
int a[110], b[110], c[110];
int q;
map<int, bool> mp;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++) cin >> b[i];
	cin >> l;
	for (int i = 1; i <= l; i++) cin >> c[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int k = 1; k <= l; k++) {
				mp[a[i] + b[j] + c[k]] = 1;
			}
		}
	}
	cin >> q;
	while (q--) {
		int x;
		cin >> x;
		if (mp[x]) cout << "Yes\n";
		else cout << "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

D

题目

又是一个炸裂的 D。

此题可以用动态规划来解决。我们用 $d{p}_{ij}$ 来表示处理到第 $i$ 排后使前 $j$ 个字符相等的花费。一开始除了 $d{p}_{00}$ 为 $0$ 外，其他都为 $\infty$。 很明显，如果当前字串 $s$ 长 $k$，且 ${\sum }_{i=1}^k[s_i=t_{i+j-1}]=k$，即此字串从 $j$ 到 $j+k-1$ 的位置都匹配，那么 $d{p}_{当前处理排数j+k-1}=\min (d{p}_{当前处理排数j+k-1},d{p}_{上一排j-1}+1)$。迁移到下一排时，对于每一个 $0\le i\le |t|$，$d{p}_{当前拍数i}=d{p}_{上一排i}$。注意 $i$ 的范围，因为 $d{p}_{x0}$ 也在讨论范围。我曾经在这里挂了10次。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
char t[200];
int n;
int a[200];
char s[200][20][20];
int dp[200][200];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> (t + 1) >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		for (int j = 1; j <= a[i]; j++) cin >> (s[i][j] + 1);
	}
	int lent = strlen(t + 1);
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= lent; j++) {
			dp[i][j] = min(dp[i][j], dp[i - 1][j]);
		}
		for (int j = 1; j <= a[i]; j++) {
			int len = strlen(s[i][j] + 1);
			for (int k = lent - len + 1; k >= 1; k--) {
				if (dp[i - 1][k - 1] != 0x3f3f3f3f) {
					bool flag = 0;
					for (int l = k; l < len + k; l++) {
						if (s[i][j][l - k + 1] != t[l]) {
							flag = 1;
							break;
						}
					}
					if (!flag) {
						dp[i][k + len - 1] = min(dp[i][k + len - 1], dp[i - 1][k - 1] + 1);
					}
				}
			}
		}
	}
	if (dp[n][lent] != 0x3f3f3f3f) cout << dp[n][lent];
	else cout << -1;
	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

E

题目

题目中说到：

Its elements will be distinct.
每一个元素都不一样。

说明我么可以记录某个数值的后面一个元素是什么，前一个元素是什么……

然后我们可以惊奇的发现这东西就是一个链表。

实现一个双链表，第一个数必须是一个不在 $A$ 里面的数，最后一个数也不能在 $A$ 里面。这样做是为了方便删除。

如果你不会链表那么请看下面：

首先，用两个数组记录下每一个数值的上一个元素和下一个元素是什么。元素太大怎么办？键值对形式的数据结构是个好东西！（即 C++ 中的 map。）要创建一个链表，我们对于每一个 $1\le i\le N$ 的 $A_i$，将其上一个设为 $A_{i-1}$，将其后一个设为 $A_{i+1}$，当然，将 $A_0$ 设为 $0$，$A_{N+1}$ 设为 $-1$ 就方便操作了，当然不要忽略这两个节点的下一个和上一个！

要增加一个元素 $y$ 在 $x$ 后面，首先，备份一个 $x$ 的下一个，将 $x$ 的下一个设为 $y$，$y$ 的下一个设为原来 $x$ 的下一个，将 $y$ 的上一个设为 $x$，将原来 $x$ 的下一个的上一个设为 $y$。

要删除一个元素 $p$，我们将 $p$ 的上一个的下一个设为 $p$ 的下一个，将 $p$ 的下一个的上一个设为 $p$ 的上一个。

要输出这个链表，先从 $0$ 的下一个开始，一直跳到下一个，如果下一个是 $-1$ 就跳出，否则，输出这个数。

建议用 C++ 编写代码，因为 $A_i$ 的范围较大，用较慢的 python 可能会超出时间限制。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n, a[200100], q;
map<int, int> lst, nxt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	a[n + 1] = -1;
	for (int i = 1; i <= n; i++) {
		lst[a[i]] = a[i - 1];
		nxt[a[i]] = a[i + 1];
	}
	nxt[0] = a[1];
	lst[-1] = a[n];
	cin >> q;
	while (q--) {
		int op;
		cin >> op;
		if (op == 2) {
			int x;
			cin >> x;
			nxt[lst[x]] = nxt[x];
			lst[nxt[x]] = lst[x];
		}
		else {
			int x, y;
			cin >> x >> y;
			int p = nxt[x];
			nxt[x] = y;
			lst[y] = x;
			nxt[y] = p;
			lst[p] = y;
		}
	}
	int now = nxt[0];
	while (now != -1) {
		cout << now << ' ';
		now = nxt[now];
	}
	cout << '\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