AtCoder Beginner Contest 344 （ABCDEF题）视频讲解

A - Spoiler

Problem Statement

You are given a string $S$ consisting of lowercase English letters and |. $S$ is guaranteed to contain exactly two |s.
Remove the characters between the two |s, including the |s themselves, and print the resulting string.

Constraints

$S$ is a string of length between $2$ and $100$, inclusive, consisting of lowercase English letters and |.
$S$ contains exactly two |s.

Input

The input is given from Standard Input in the following format:

$S$

Output

Print the answer.

Sample Input 1

atcoder|beginner|contest

Sample Output 1

atcodercontest

Remove all the characters between the two |s and print the result.

Sample Input 2

|spoiler|

Sample Output 2

It is possible that all characters are removed.

Sample Input 3

||xyz

Sample Output 3

xyz

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	string s;

	cin >> s;

	int cnt = 0;
	for (auto v : s)
		if (v == '|')
			cnt ++;
		else if (cnt != 1)
			cout << v;

	return 0;
}

B - Delimiter

Problem Statement

You are given $N$ integers $A_1,A_2,\dots ,A_N$, one per line, over $N$ lines. However, $N$ is not given in the input.

Furthermore, the following is guaranteed:
$A_i\ne 0$ ( $1\le i\le N-1$ )
$A_N=0$
Print $A_N,A_{N-1},\dots ,A_1$ in this order.

Constraints

All input values are integers.
$1\le N\le 100$
$1\le A_i\le 10^9$ ( $1\le i\le N-1$ )
$A_N=0$

Input

The input is given from Standard Input in the following format:

$A_1$
$A_2$
$⋮$
$A_N$

Output

Print $A_N,A_{N-1},\dots ,A_1$ in this order, as integers, separated by newlines.

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that $N$ is not given in the input.
Here, $N=4$ and $A=(3,2,1,0)$.

Sample Input 2

0

Sample Output 2

0

$A=(0)$.

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int x;
	std::vector<int> a;

	cin >> x;
	while (x != 0) {
		a.emplace_back(x);
		cin >> x;
	}
	a.emplace_back(x);

	reverse(a.begin(), a.end());

	for (auto v : a)
		cout << v << endl;

	return 0;
}

C - A+B+C

Problem Statement

You are given three sequences $A=(A_1,\dots ,A_N)$, $B=(B_1,\dots ,B_M)$, and $C=(C_1,\dots ,C_L)$.
Additionally, a sequence $X=(X_1,\dots ,X_Q)$ is given. For each $i=1,\dots ,Q$, solve the following problem:
Problem: Is it possible to select one element from each of $A$, $B$, and $C$ so that their sum is $X_i$?

Constraints

$1\le N,M,L\le 100$
$0\le A_i,B_i,C_i\le 10^8$
$1\le Q\le 2\times 10^5$
$0\le X_i\le 3\times 10^8$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $\dots$ $A_N$
$M$
$B_1$ $\dots$ $B_M$
$L$
$C_1$ $\dots$ $C_L$
$Q$
$X_1$ $\dots$ $X_Q$

Output

Print $Q$ lines.
The $i$-th line should contain Yes if it is possible to select one element from each of $A$, $B$, and $C$ so that their sum is $X_i$, and No otherwise.

Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No

It is impossible to select one element from each of $A$, $B$, and $C$ so that their sum is $1$.
Selecting $1$, $2$, and $2$ from $A$, $B$, and $C$, respectively, makes the sum $5$.
Selecting $2$, $4$, and $4$ from $A$, $B$, and $C$, respectively, makes the sum $10$.
It is impossible to select one element from each of $A$, $B$, and $C$ so that their sum is $50$.

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int n, m, l;

	cin >> n;
	std::vector<int> a(n + 1);
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	cin >> m;
	std::vector<int> b(m + 1);
	for (int i = 1; i <= m; i ++)
		cin >> b[i];
	cin >> l;
	std::vector<int> c(l + 1);
	for (int i = 1; i <= l; i ++)
		cin >> c[i];

	unordered_map<int, int> vis;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			for (int k = 1; k <= l; k ++)
				vis[a[i] + b[j] + c[k]] = 1;

	int q;
	cin >> q;

	while (q --)
	{
		int x;
		cin >> x;

		if (vis[x]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

D - String Bags

Problem Statement

You initially have an empty string $S$.

Additionally, there are bags $1,2,\dots ,N$, each containing some strings.

Bag $i$ contains $A_i$ strings $S_{i,1},S_{i,2},\dots ,S_{i,A_i}$.
You will repeat the following steps for $i=1,2,\dots ,N$:
Choose and perform one of the following two actions:
Pay $1$ yen, select exactly one string from bag $i$, and concatenate it to the end of $S$.
Do nothing.
Given a string $T$, find the minimum amount of money required to make the final $S$ equal $T$.

If there is no way to make the final $S$ equal $T$, print -1.

Constraints

$T$ is a string consisting of lowercase English letters with length between $1$ and $100$, inclusive.
$N$ is an integer between $1$ and $100$, inclusive.
$A_i$ is an integer between $1$ and $10$, inclusive.
$S_{i,j}$ is a string consisting of lowercase English letters with length between $1$ and $10$, inclusive.

Input

The input is given from Standard Input in the following format:

$T$
$N$
$A_1$ $S_{1,1}$ $S_{1,2}$ $\dots$ $S_{1,A_1}$
$A_2$ $S_{2,1}$ $S_{2,2}$ $\dots$ $S_{2,A_2}$
$⋮$
$A_N$ $S_{N,1}$ $S_{N,2}$ $\dots$ $S_{N,A_N}$

Output

Print the answer as an integer.

Sample Input 1

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

Sample Output 1

2

For example, doing the following makes the final $S$ equal $T$ with two yen, which can be shown to be the minimum amount required.
For $i=1$, select abc from bag $1$ and concatenate it to the end of $S$, making $S=$ abc.
For $i=2$, do nothing.
For $i=3$, select de from bag $3$ and concatenate it to the end of $S$, making $S=$ abcde.

Sample Input 2

abcde
3
2 ab abc
3 f c bcde
1 e

Sample Output 2

-1

There is no way to make the final $S$ equal $T$, so print -1.

Sample Input 3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

Sample Output 3

4

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 5e2 + 10;

string final;
int n;
int a[N], f[N][N];
string s[N][N];

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> final;
	cin >> n;

	int m = final.size();
	final = ' ' + final;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		for (int j = 1; j <= a[i]; j ++)
			cin >> s[i][j], s[i][j] = ' ' + s[i][j];
	}

	memset(f, 0x3f, sizeof f);
	for (int i = 0; i <= n; i ++) f[i][0] = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= a[i]; j ++) {
			for (int k = 1; k <= m - (int)s[i][j].size() + 2; k ++) {
				bool flg = 1;
				for (int l = 1; l < (int)s[i][j].size(); l ++)
					if (final[k + l - 1] != s[i][j][l]) {
						flg = 0;
						break;
					}
				if (flg) f[i][k + (int)s[i][j].size() - 2] = min(min(f[i - 1][k + (int)s[i][j].size() - 2], f[i - 1][k - 1] + 1), f[i][k + (int)s[i][j].size() - 2]);
			}
			for (int k = 1; k <= m; k ++)
				f[i][k] = min(f[i][k], f[i - 1][k]);
		}
	}

	if (f[n][m] >= 1e18) cout << -1 << endl;
	else cout << f[n][m] << endl;

	return 0;
}

---

E - Insert or Erase

Problem Statement

You are given a sequence $A=(A_1,\dots ,A_N)$ of length $N$. The elements of $A$ are distinct.
Process $Q$ queries in the order they are given. Each query is of one of the following two types:
1 x y : Insert $y$ immediately after the element $x$ in $A$. It is guaranteed that $x$ exists in $A$ when this query is given.
2 x : Remove the element $x$ from $A$. It is guaranteed that $x$ exists in $A$ when this query is given.
It is guaranteed that after processing each query, $A$ will not be empty, and its elements will be distinct.
Print $A$ after processing all the queries.

Constraints

$1\le N\le 2\times 10^5$
$1\le Q\le 2\times 10^5$
$1\le A_i\le 10^9$
$A_i\ne A_j$
For queries of the first type, $1\le x,y\le 10^9$.
When a query of the first type is given, $x$ exists in $A$.
For queries of the second type, $1\le x\le 10^9$.
When a query of the second type is given, $x$ exists in $A$.
After processing each query, $A$ is not empty, and its elements are distinct.
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $\dots$ $A_N$
$Q$
${\mathrm{Query}}_1$
$⋮$
${\mathrm{Query}}_Q$

Here, ${\mathrm{Query}}_i$ represents the $i$-th query and is given in one of the following formats:

$1$ $x$ $y$

$2$ $x$

Output

Let $A=(A_1,\dots ,A_K)$ be the sequence after processing all the queries. Print $A_1,\dots ,A_K$ in this order, separated by spaces.

Sample Input 1

4
2 1 4 3
4
2 1
1 4 5
2 2
1 5 1

Sample Output 1

4 5 1 3

The queries are processed as follows:
Initially, $A=(2,1,4,3)$.
The first query removes $1$, making $A=(2,4,3)$.
The second query inserts $5$ immediately after $4$, making $A=(2,4,5,3)$.
The third query removes $2$, making $A=(4,5,3)$.
The fourth query inserts $1$ immediately after $5$, making $A=(4,5,1,3)$.

Sample Input 2

6
3 1 4 5 9 2
7
2 5
1 3 5
1 9 7
2 9
2 3
1 2 3
2 4

Sample Output 2

5 1 7 2 3

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 2e5 + 10;

int n, q;
int a[N];
unordered_map<int, int> lst, nxt;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	nxt[0] = a[1];
	for (int i = 1; i <= n; i ++)
		lst[a[i]] = a[i - 1], nxt[a[i]] = a[i + 1];
	nxt[a[n]] = -1;

	cin >> q;

	while (q --) {
		int op, x, y;
		cin >> op >> x;

		if (op == 1) {
			cin >> y;
			lst[y] = x;
			nxt[y] = nxt[x];
			lst[nxt[x]] = y;
			nxt[x] = y;
		}
		else {
			int last = lst[x], next = nxt[x];
			nxt[last] = next, lst[next] = last;
		}
	}

	for (int i = nxt[0]; ~i; i = nxt[i])
		cout << i << " ";

	return 0;
}

F - Earn to Advance

Problem Statement

There is a grid with $N$ rows and $N$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.
Takahashi is initially at square $(1,1)$ with zero money.
When Takahashi is at square $(i,j)$, he can perform one of the following in one action:
Stay at the same square and increase his money by $P_{i,j}$.
Pay $R_{i,j}$ from his money and move to square $(i,j+1)$.
Pay $D_{i,j}$ from his money and move to square $(i+1,j)$.
He cannot make a move that would make his money negative or take him outside the grid.
If Takahashi acts optimally, how many actions does he need to reach square $(N,N)$?

Constraints

$2\le N\le 80$
$1\le P_{i,j}\le 10^9$
$1\le R_{i,j},D_{i,j}\le 10^9$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$P_{1,1}$ $\ldots$ $P_{1,N}$
$\vdots$
$P_{N,1}$ $\ldots$ $P_{N,N}$
$R_{1,1}$ $\ldots$ $R_{1,N-1}$
$\vdots$
$R_{N,1}$ $\ldots$ $R_{N,N-1}$
$D_{1,1}$ $\ldots$ $D_{1,N}$
$\vdots$
$D_{N-1,1}$ $\ldots$ $D_{N-1,N}$

Output

Print the answer.

Sample Input 1

3
1 2 3
3 1 2
2 1 1
1 2
4 3
4 2
1 5 7
5 3 3

Sample Output 1

8

It is possible to reach square $(3,3)$ in eight actions as follows: Stay at square $(1,1)$ and increase money by $1$. His money is now $1$. Pay $1$ money and move to square $(2,1)$. His money is now $0$. Stay at square $(2,1)$ and increase money by $3$. His money is now $3$. Stay at square $(2,1)$ and increase money by $3$. His money is now $6$. Stay at square $(2,1)$ and increase money by $3$. His money is now $9$. Pay $4$ money and move to square $(2,2)$. His money is now $5$. Pay $3$ money and move to square $(3,2)$. His money is now $2$. Pay $2$ money and move to square $(3,3)$. His money is now $0$. ## Sample Input 2 ``` 3 1 1 1 1 1 1 1 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ``` ## Sample Output 2 ``` 4000000004 ```

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 85;

int n;
int p[N][N], r[N][N], d[N][N];
int f[N][N][N * N], g[N][N][N * N];
std::vector<int> num;

int id(int x) { return lower_bound(num.begin(), num.end(), x) - num.begin(); }

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			cin >> p[i][j], num.emplace_back(p[i][j]);
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j < n; j ++)
			cin >> r[i][j];
	for (int i = 1; i < n; i ++)
		for (int j = 1; j <= n; j ++)
			cin >> d[i][j];

	sort(num.begin(), num.end());
	num.erase(unique(num.begin(), num.end()), num.end());

	memset(f, 0x3f, sizeof f);
	memset(g, -0x3f, sizeof g);
	f[1][1][id(p[1][1])] = 0, g[1][1][id(p[1][1])] = 0;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++) {
			for (int k = 0; k < num.size(); k ++) {
				if (f[i][j][k] >= 1e18) continue;
				int ir = max(k, id(p[i][j + 1])), tr = (r[i][j] - g[i][j][k] + num[k] - 1) / num[k], 
					jd = max(k, id(p[i + 1][j])), td = (d[i][j] - g[i][j][k] + num[k] - 1) / num[k];
				auto &right = f[i][j + 1][ir];
				auto &down = f[i + 1][j][jd];
				if (j < n) {
					if (r[i][j] < g[i][j][k]) {
						if (right > f[i][j][k] + 1) g[i][j + 1][ir] = g[i][j][k] - r[i][j], right = f[i][j][k] + 1;
						else if (right == f[i][j][k] + 1) g[i][j + 1][ir] = max(g[i][j][k] - r[i][j], g[i][j + 1][ir]);
					}
					if (right > f[i][j][k] + tr + 1) g[i][j + 1][ir] = tr * num[k] - (r[i][j] - g[i][j][k]), right = f[i][j][k] + tr + 1;
					if (right == f[i][j][k] + tr + 1 && tr * num[k] - (r[i][j] - g[i][j][k]) > g[i][j + 1][ir]) g[i][j + 1][ir] = tr * num[k] - (r[i][j] - g[i][j][k]);
				}

				if (i < n) {
					if (d[i][j] < g[i][j][k]){
						if (down > f[i][j][k] + 1) down = f[i][j][k] + 1, g[i + 1][j][jd] = g[i][j][k] - d[i][j];
						else if (down == f[i][j][k] + 1) g[i + 1][j][jd] = max(g[i + 1][j][jd], g[i][j][k] - d[i][j]);
					}
					if (down > f[i][j][k] + td + 1) g[i + 1][j][jd] = td * num[k] - (d[i][j] - g[i][j][k]), down = f[i][j][k] + td + 1;
					if (down == f[i][j][k] + td + 1 && td * num[k] - (d[i][j] - g[i][j][k]) > g[i][j + 1][jd]) g[i + 1][j][jd] = td * num[k] - (d[i][j] - g[i][j][k]);
				}
			}
		}

	int res = 1e18;
	for (int i = 0; i < num.size(); i ++)
		res = min(res, f[n][n][i]);

	cout << res << endl;

	return 0;
}

---

视频题解

欢迎大家关注我的B站空间：https://space.bilibili.com/630340560

---

最后祝大家早日