A – Spoiler (abc344 A)
题目大意
给定一个字符串,包含两个|
,将|
和两个|
之间的字符消去。
解题思路
按照题意模拟即可。
Python
比较简洁。
神奇的代码
s = input().split('|')
s = s[0] + s[2]
print(s)
B – Delimiter (abc344 B)
题目大意
给定(n)个数,倒序输出。
解题思路
储存这(n)个数,然后倒着输出即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
vector a;
int x;
while (cin >> x) {
a.push_back(x);
}
reverse(a.begin(), a.end());
for (auto x : a) {
cout
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(nlog n))的查找。
神奇的代码
#include
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 a(n);
for (auto& x : a)
cin >> x;
cin >> m;
vector b(m);
for (auto& x : b)
cin >> x;
cin >> l;
vector c(l);
for (auto& x : c)
cin >> x;
vector sum;
for (int i = 0; i > q;
while (q--) {
int x;
cin >> x;
bool ok = false;
for (int i = 0; i
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
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 dp(s.size() + 1, inf);
dp[0] = 0;
int n;
cin >> n;
for (int i = 0; i dp2 = dp;
int m;
cin >> m;
while (m--) {
string t;
cin >> t;
for (int j = 0; j
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
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 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 > 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 val
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
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> p(n, vector(n));
for (auto& i : p) {
for (auto& j : i) {
cin >> j;
}
}
vector> r(n, vector(n - 1));
for (auto& i : r) {
for (auto& j : i) {
cin >> j;
}
}
vector> d(n - 1, vector(n));
for (auto& i : d) {
for (auto& j : i) {
cin >> j;
}
}
vector>> dp(n, vector>(n, {inf, 0}));
dp[0][0] = {0, 0};
for (int i = 0; i > dis(n, vector(n, inf));
dis[i][j] = 0;
for (int k = i; 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 dp[k][l][1]))
dp[k][l] = {stay, money};
}
}
}
cout
G – Points and Comparison (abc344 G)
题目大意
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net