ABC344 A-E题解
文章目录
- A
- 题目
- AC Code：
- B
- 题目
- AC Code：
- C
- 题目
- AC Code：
- D
- 题目
- AC Code：
- E
- 题目
- AC Code：
不易不难，写到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 a_n an，然后让 n n n 加上 1 1 1，如果 a n a_n an 是 0 0 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 1，对于每一个询问，如果这个数的标记为 1 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 i j dp_{ij} dpij 来表示处理到第 i i i 排后使前 j j j 个字符相等的花费。一开始除了 d p 00 dp_{00} dp00 为 0 0 0 外，其他都为 ∞ \infin ∞。 很明显，如果当前字串 s s s 长 k k k，且 ∑ i = 1 k [ s i = t i + j − 1 ] = k \sum_{i=1}^k[s_i=t_{i+j-1}]=k ∑i=1k[si=ti+j−1]=k，即此字串从 j j j 到 j + k − 1 j+k-1 j+k−1 的位置都匹配，那么 d p 当前处理排数 j + k − 1 = min ( d p 当前处理排数 j + k − 1 , d p 上一排 j − 1 + 1 ) dp_{当前处理排数j+k-1}=\min(dp_{当前处理排数j+k-1}, dp_{上一排j-1}+1) dp当前处理排数j+k−1=min(dp当前处理排数j+k−1,dp上一排j−1+1)。迁移到下一排时，对于每一个 0 ≤ i ≤ ∣ t ∣ 0\le i\le|t| 0≤i≤∣t∣， d p 当前拍数 i = d p 上一排 i dp_{当前拍数i}=dp_{上一排i} dp当前拍数i=dp上一排i。注意 i i i 的范围，因为 d p x 0 dp_{x0} dpx0 也在讨论范围。我曾经在这里挂了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 A 里面的数，最后一个数也不能在 A A A 里面。这样做是为了方便删除。
如果你不会链表那么请看下面：
首先，用两个数组记录下每一个数值的上一个元素和下一个元素是什么。元素太大怎么办？键值对形式的数据结构是个好东西！（即 C++ 中的 map。）要创建一个链表，我们对于每一个 1 ≤ i ≤ N 1\le i\le N 1≤i≤N 的 A i A_i Ai，将其上一个设为 A i − 1 A_{i-1} Ai−1，将其后一个设为 A i + 1 A_{i+1} Ai+1，当然，将 A 0 A_0 A0 设为 0 0 0， A N + 1 A_{N+1} AN+1 设为 − 1 -1 −1 就方便操作了，当然不要忽略这两个节点的下一个和上一个！
要增加一个元素 y y y 在 x x x 后面，首先，备份一个 x x x 的下一个，将 x x x 的下一个设为 y y y， y y y 的下一个设为原来 x x x 的下一个，将 y y y 的上一个设为 x x x，将原来 x x x 的下一个的上一个设为 y y y。
要删除一个元素 p p p，我们将 p p p 的上一个的下一个设为 p p p 的下一个，将 p p p 的下一个的上一个设为 p p p 的上一个。
要输出这个链表，先从 0 0 0 的下一个开始，一直跳到下一个，如果下一个是 − 1 -1 −1 就跳出，否则，输出这个数。
建议用 C++ 编写代码，因为 A i A_i Ai 的范围较大，用较慢的 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;
}