AtCoder Beginner Contest 344
A - Spoiler (abc344 A)
题目大意
给定一个字符串，包含两个|，将|和两个|之间的字符消去。
解题思路
按照题意模拟即可。
Python比较简洁。
神奇的代码
s = input().split('|')
s = s[0] + s[2]
print(s)
B - Delimiter (abc344 B)
题目大意
给定\(n\)个数，倒序输出。
解题思路
储存这\(n\)个数，然后倒着输出即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
vector<int> a;
int x;
while (cin >> x) {
a.push_back(x);
}
reverse(a.begin(), a.end());
for (auto x : a) {
cout << x << '\n';
}
return 0;
}
C - A+B+C (abc344 C)
题目大意
给定三个数组\(a,b,c\)，回答 \(q\)次询问。
每次询问，给定 \(x\)，问能否从三个数组各选一个数，其和为 \(x\)。
解题思路
由于每个数组的个数不超过\(n=100\)，可以事先 \(O(n^3)\)预处理其所有可能的和，排个序。
然后对于每组询问，花\(O(\log n)\)二分找一下\(x\)是否存在即可。
代码是\(O(n^2)\)预处理+ \(O(n\log n)\)的查找。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, l;
cin >> n;
vector<int> a(n);
for (auto& x : a)
cin >> x;
cin >> m;
vector<int> b(m);
for (auto& x : b)
cin >> x;
cin >> l;
vector<int> c(l);
for (auto& x : c)
cin >> x;
vector<int> sum;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum.push_back(a[i] + b[j]);
}
}
sort(sum.begin(), sum.end());
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
bool ok = false;
for (int i = 0; i < l; i++) {
auto it = lower_bound(sum.begin(), sum.end(), x - c[i]);
if (it != sum.end() && *it == x - c[i]) {
ok = true;
break;
}
}
if (ok)
cout << "Yes" << endl;
else {
cout << "No" << endl;
}
}
return 0;
}
D - String Bags (abc344 D)
题目大意
\(n\)个袋子，每个袋子里有若干个字符串。
给定一个目标串 \(t\)，要求从每个袋子选出最多 \(1\)个字符串，按顺序拼接成 \(t\)。
问取出来的字符串个数的最小值。
解题思路
考虑朴素搜索的状态，即：
- 当前第几个袋子
- 当前匹配到了目标串\(t\)的前几位
通过以上两个状态，就可以从当前袋子选 \(1\)个字符串，然后看看能否匹配，并转移到下一个状态。
即设 \(dp[i][j]\)表示前 \(i\)个袋子拼接目标串 \(t\)的前 \(j\)位的最小字符串数。
状态数是 \(O(100 \times 100)\)，转移代价是 \(O(10 \times 10 \times 10)\)，总时间复杂度是 \(O(10^7)\)，可过。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
vector<int> dp(s.size() + 1, inf);
dp[0] = 0;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
vector<int> dp2 = dp;
int m;
cin >> m;
while (m--) {
string t;
cin >> t;
for (int j = 0; j < s.size(); j++) {
if (j + t.size() <= s.size() && s.substr(j, t.size()) == t) {
dp2[j + t.size()] = min(dp2[j + t.size()], dp[j] + 1);
}
}
}
dp.swap(dp2);
}
if (dp.back() == inf) {
dp.back() = -1;
}
cout << dp.back() << '\n';
return 0;
}
E - Insert or Erase (abc344 E)
题目大意
给定一个数组\(a\)，进行以下 \(q\)次操作，分两种。
1 x y，在\(x\)后面插入 \(y\)。2 x，将\(x\)删去。
保证每次操作后，各个数互不相同。
经过 \(q\)次操作后，输出最后的数组 \(a\)。
解题思路
由于会在\(x\)后面插入 \(y\)，也就是原来的元素之间，会突然插进新的数。数组的维护需要 \(O(n)\)。但用链表就可以 \(O(1)\)实现插入和删除。
但链表对于定位数所在位置需要 \(O(n)\)，这非常费时。因此我们需要用 map辅助定位，即\(map[x]\)就是指向 \(x\)的项的指针，从而可以快速定位，然后进行插入和删除即可。
可以学学std::list，写法更简洁，不用手动维护前驱后继，用map储存\(x\)对应的迭代器即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int dis = 2e5 + 8;
struct Node {
int val;
Node *l, *r;
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
map<int, Node*> pos;
Node* L = new Node();
Node* R = new Node();
L->r = R;
R->l = L;
int n;
cin >> n;
Node* la = L;
auto insert = [](Node* p, Node* x) {
x->l = p;
x->r = p->r;
p->r->l = x;
p->r = x;
};
auto remove = [](Node* x) {
x->l->r = x->r;
x->r->l = x->l;
};
for (int i = 0; i < n; i++) {
LL x;
cin >> x;
Node* X = new Node();
X->val = x;
insert(la, X);
la = X;
pos[x] = X;
}
int q;
cin >> q;
while (q--) {
int op;
cin >> op;
if (op == 1) {
LL x, y;
cin >> x >> y;
Node* Y = new Node();
Y->val = y;
insert(pos[x], Y);
pos[y] = Y;
} else if (op == 2) {
LL x;
cin >> x;
remove(pos[x]);
}
}
for (auto i = L->r; i != R; i = i->r) {
cout << i->val << ' ';
}
cout << '\n';
return 0;
}
F - Earn to Advance (abc344 F)
题目大意
二维网格，从左上走到右下，只能向右或向下走。
每一步，当在第\((i,j)\)时，往下走的代价（花费钱数）是 \(d_{i,j}\)，往右走的代价是 \(r_{i,j}\)。如果不走，则获得 \(p_{i,j}\)钱。
初始没钱。
沿途钱不能为负。问最小步数。
解题思路
这题有两个比较特别的性质：
- 充值点的\(p\)一定是递增的
- 到达一个充值点时，我们的最小步数（充值次数）一定是越小越好。
一个比较朴素的想法是\(dp[i][j][k]\)表示我们处在 \((i,j)\)，且钱数为 \(k\)，的最小步数。这样可以转移。
但钱数的复杂度高达 \(10^{10}\)，因此钱数不能在状态里，但我们转移又得知道钱数。怎么办呢？
考虑行走过程，我们会在某些位置停下来，充钱，而这些点的 \(p_{i,j}\)一定是递增的。
至于充钱点之间如何行走，无关紧要，取最小代价行走即可。
因此我们只考虑转移点之间的转移，即设\(dp[i][j]\)表示当前在点 \((i,j)\)时的最小步数,当前钱数。一个二元组。
转移时考虑下一个点 \((k,l)\)，其中满足 \(p_{k,l} \geq p_{i,j}\)，两点间的最小移动代价可以事先通过 \(O(80^4)\)预处理得到。 然后在\((i,j)\)充够钱后到达 \((k,l)\)。
因此，到达点 \((k,l)\)的方式有好多种，不同的方式有不同的 最小步数,当前钱数。要保留哪个呢？哪个是最优的呢？
可以观察到，我们保留步数最小的，如果步数相同，则保留钱数最多的，这样转移一定最优的。
因为，对于一种到达方式\((i_1,j_1) \to (k, l)\)，其最小步数和钱数为\((3,100)\) ，另一种到达方式\((i_2, j_2) \to (k,l)\)，为\((2,10)\)。我们可以证明后者是更优的。
从转移式子和转移时\(p_{i,j}\)递增的性质，可以得知\(100 \leq p_{i_1,j_1} \leq p_{k,l}, 10 \leq p_{i_2, j_2} \leq p_{k,l}\)，则 \(100 - 10 \leq p_{k,l}\)。即虽然后者步数少，钱少，但如果让步数相同，即在 \((k,l)\)充值到与前者相同的步数，此时我的钱数一定是更多的，也就是实际上更利于后面的移动。
转移的问题解决了，所以就一个\(dp\)就没了。
状态数是 \(O(n^2)\)，转移是 \(O(n^2)\)，总的时间复杂度是\(O(n^4)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<int>> p(n, vector<int>(n));
for (auto& i : p) {
for (auto& j : i) {
cin >> j;
}
}
vector<vector<int>> r(n, vector<int>(n - 1));
for (auto& i : r) {
for (auto& j : i) {
cin >> j;
}
}
vector<vector<int>> d(n - 1, vector<int>(n));
for (auto& i : d) {
for (auto& j : i) {
cin >> j;
}
}
vector<vector<array<LL, 2>>> dp(n, vector<array<LL, 2>>(n, {inf, 0}));
dp[0][0] = {0, 0};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
vector<vector<LL>> dis(n, vector<LL>(n, inf));
dis[i][j] = 0;
for (int k = i; k < n; k++) {
for (int l = j; l < n; l++) {
if (k > 0) {
dis[k][l] = min(dis[k][l], dis[k - 1][l] + d[k - 1][l]);
}
if (l > 0) {
dis[k][l] = min(dis[k][l], dis[k][l - 1] + r[k][l - 1]);
}
}
}
for (int k = i; k < n; k++)
for (int l = j; l < n; l++) {
if (k != n - 1 && l != n - 1) {
if (p[k][l] < p[i][j]) {
continue;
}
}
auto [ori_stay, ori_money] = dp[i][j];
LL cost = max(0ll, (dis[k][l] - ori_money + p[i][j] - 1) /
p[i][j]);
LL money = ori_money + cost * p[i][j] - dis[k][l];
LL stay = ori_stay + cost + k - i + l - j;
if (stay < dp[k][l][0] ||
(stay == dp[k][l][0] && money > dp[k][l][1]))
dp[k][l] = {stay, money};
}
}
}
cout << dp[n - 1][n - 1][0] << '\n';
return 0;
}
G - Points and Comparison (abc344 G)
题目大意
<++>
解题思路
<++>
神奇的代码