ABC344 A-E题解

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

A

题目

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

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
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;
}

B

题目

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

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
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;
}

C

题目

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

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
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;
}

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 <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
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;
}

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 <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
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;
}