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

A - The bottom of the ninth

Problem Statement

Team Takahashi and Team Aoki are playing a baseball game, with Team Takahashi batting first.

Currently, the game has finished through the top of the ninth inning, and the bottom of the ninth is about to begin.
Team Takahashi scored $A_i$ runs in the top of the $i$-th inning $(1\le i\le 9)$, and Team Aoki scored $B_j$ runs in the bottom of the $j$-th inning $(1\le j\le 8)$.

At the end of the top of the ninth, Team Takahashi’s score is not less than Team Aoki’s score.

Determine the minimum number of runs Team Aoki needs to score in the bottom of the ninth to win the game.
Here, if the game is tied at the end of the bottom of the ninth, it results in a draw. Therefore, for Team Aoki to win, they must score strictly more runs than Team Takahashi by the end of the bottom of the ninth.

Team Takahashi’s score at any point is the total runs scored in the tops of the innings up to that point, and Team Aoki’s score is the total runs scored in the bottoms of the innings.

Constraints

$0\le A_i,B_j\le 99$
$A_1+A_2+A_3+A_4+A_5+A_6+A_7+A_8+A_9\ge B_1+B_2+B_3+B_4+B_5+B_6+B_7+B_8$
All input values are integers.

Input

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

$A_1$ $A_2$ $A_3$ $A_4$ $A_5$ $A_6$ $A_7$ $A_8$ $A_9$
$B_1$ $B_2$ $B_3$ $B_4$ $B_5$ $B_6$ $B_7$ $B_8$

Output

Print the minimum number of runs Team Aoki needs to score in the bottom of the ninth inning to win.

Sample Input 1

0 1 0 1 2 2 0 0 1
1 1 0 0 0 0 1 0

Sample Output 1

5

At the end of the top of the ninth inning, Team Takahashi has scored seven runs, and Team Aoki has scored three runs.

Therefore, if Team Aoki scores five runs in the bottom of the ninth, the scores will be $7-8$, allowing them to win.

Note that scoring four runs would result in a draw and not a victory.

Sample Input 2

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Sample Output 2

1

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#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 s1 = 0, s2 = 0, x;
	for (int i = 1; i <= 9; i ++)
		cin >> x, s1 += x;
	for (int i = 1; i <= 8; i ++)
		cin >> x, s2 += x;

	if (s1 < s2) {
		cout << 0 << endl;
	} else {
		cout << s1 - s2 + 1 << endl;
	}

	return 0;
}

B - Spot the Difference

Problem Statement

You are given two grids, each with $N$ rows and $N$ columns, referred to as grid $A$ and grid $B$.

Each cell in the grids contains a lowercase English letter.

The character at the $i$-th row and $j$-th column of grid $A$ is $A_{i,j}$.

The character at the $i$-th row and $j$-th column of grid $B$ is $B_{i,j}$.
The two grids differ in exactly one cell. That is, there exists exactly one pair $(i,j)$ of positive integers not greater than $N$ such that $A_{i,j}\ne B_{i,j}$. Find this $(i,j)$.

Constraints

$1\le N\le 100$
$A_{i,j}$ and $B_{i,j}$ are all lowercase English letters.
There exists exactly one pair $(i,j)$ such that $A_{i,j}\ne B_{i,j}$.

Input

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

$N$
$A_{1,1}{A}_{1,2}\dots A_{1,N}$
$A_{2,1}{A}_{2,2}\dots A_{2,N}$
$⋮$
$A_{N,1}{A}_{N,2}\dots A_{N,N}$
$B_{1,1}{B}_{1,2}\dots B_{1,N}$
$B_{2,1}{B}_{2,2}\dots B_{2,N}$
$⋮$
$B_{N,1}{B}_{N,2}\dots B_{N,N}$

Output

Let $(i,j)$ be the pair of positive integers not greater than $N$ such that $A_{i,j}\ne B_{i,j}$. Print $(i,j)$ in the following format:

$i$ $j$

Sample Input 1

3
abc
def
ghi
abc
bef
ghi

Sample Output 1

2 1

From $A_{2,1}=$ d and $B_{2,1}=$ b, we have $A_{2,1}\ne B_{2,1}$, so $(i,j)=(2,1)$ satisfies the condition in the problem statement.

Sample Input 2

1
f
q

Sample Output 2

1 1

Sample Input 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

Sample Output 3

5 9

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

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

const int N = 1e2 + 10;

int n;
char a[N][N], b[N][N];

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 >> a[i][j];
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			cin >> b[i][j];

	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			if (a[i][j] != b[i][j]) {
				cout << i << " " << j << endl;
				return 0;
			}

	return 0;
}

C - Merge the balls

Problem Statement

You have an empty sequence and $N$ balls. The size of the $i$-th ball $(1\le i\le N)$ is $2^{A_i}$.
You will perform $N$ operations.

In the $i$-th operation, you add the $i$-th ball to the right end of the sequence, and repeat the following steps:

1. If the sequence has one or fewer balls, end the operation. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the $N$ operations. #### Constraints

$1\le N\le 2\times 10^5$
$0\le A_i\le 10^9$
All input values are integers.

Input

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

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the number of balls in the sequence after the $N$ operations.

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:
After the first operation, the sequence has one ball, of size $2^2$.
After the second operation, the sequence has two balls, of sizes $2^2$ and $2^1$ in order.
After the third operation, the sequence has one ball, of size $2^3$. This is obtained as follows:
When the third ball is added during the third operation, the sequence has balls of sizes $2^2,2^1,2^1$ in order.
The first and second balls from the right have the same size, so these balls are removed, and a ball of size $2^1+2^1=2^2$ is added. Now, the sequence has balls of sizes $2^2,2^2$.
Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size $2^2+2^2=2^3$ is added, leaving the sequence with a ball of size $2^3$.
After the fourth operation, the sequence has one ball, of size $2^4$.
After the fifth operation, the sequence has two balls, of sizes $2^4$ and $2^5$ in order.
After the sixth operation, the sequence has three balls, of sizes $2^4$, $2^5$, $2^3$ in order.
After the seventh operation, the sequence has three balls, of sizes $2^4$, $2^5$, $2^4$ in order.
Therefore, you should print $3$, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:
After the first operation, the sequence has one ball, of size $2^0$.
After the second operation, the sequence has one ball, of size $2^1$.
After the third operation, the sequence has two balls, of sizes $2^1$ and $2^0$ in order.
After the fourth operation, the sequence has three balls, of sizes $2^1$, $2^0$, $2^1$ in order.
After the fifth operation, the sequence has four balls, of sizes $2^1$, $2^0$, $2^1$, $2^2$ in order.
Therefore, you should print $4$, the final number of balls in the sequence.

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#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;
	cin >> n;

	std::vector<int> b;
	int x;
	for (int i = 1; i <= n; i ++) {
		cin >> x;
		b.emplace_back(x);
		while (b.size() > 1 && b.back() == b[b.size() - 2]) {
			int tmp = b.back();
			b.pop_back(), b.pop_back();
			b.emplace_back(tmp + 1);
		}
	}

	cout << b.size() << endl;

	return 0;
}

D - Grid and Magnet

Problem Statement

There is a grid of $H$ rows and $W$ columns. Some cells (possibly zero) contain magnets.

The state of the grid is represented by $H$ strings $S_1,S_2,\dots ,S_H$ of length $W$. If the $j$-th character of $S_i$ is #, it indicates that there is a magnet in the cell at the $i$-th row from the top and $j$-th column from the left; if it is ., it indicates that the cell is empty.
Takahashi, wearing an iron armor, can move in the grid as follows:
If any of the cells vertically or horizontally adjacent to the current cell contains a magnet, he cannot move at all.
Otherwise, he can move to any one of the vertically or horizontally adjacent cells.

However, he cannot exit the grid.
For each cell without a magnet, define its degree of freedom as the number of cells he can reach by repeatedly moving from that cell. Find the maximum degree of freedom among all cells without magnets in the grid.
Here, in the definition of degree of freedom, “cells he can reach by repeatedly moving” mean cells that can be reached from the initial cell by some sequence of moves (possibly zero moves). It is not necessary that there is a sequence of moves that visits all such reachable cells starting from the initial cell. Specifically, each cell itself (without a magnet) is always included in the cells reachable from that cell.

Constraints

$1\le H,W\le 1000$
$H$ and $W$ are integers.
$S_i$ is a string of length $W$ consisting of . and #.
There is at least one cell without a magnet.

Input

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

$H$ $W$
$S_1$
$S_2$
$⋮$
$S_H$

Output

Print the maximum degree of freedom among all cells without magnets.

Sample Input 1

3 5
.#...
.....
.#..#

Sample Output 1

9

Let $(i,j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left. If Takahashi starts at $(2,3)$, possible movements include:
$(2,3)\to (2,4)\to (1,4)\to (1,5)\to (2,5)$
$(2,3)\to (2,4)\to (3,4)$
$(2,3)\to (2,2)$
$(2,3)\to (1,3)$
$(2,3)\to (3,3)$
Thus, including the cells he passes through, he can reach at least nine cells from $(2,3)$.

Actually, no other cells can be reached, so the degree of freedom for $(2,3)$ is $9$.
This is the maximum degree of freedom among all cells without magnets, so print $9$.

Sample Input 2

3 3
..#
#..
..#

Sample Output 2

1

For any cell without a magnet, there is a magnet in at least one of the adjacent cells.

Thus, he cannot move from any of these cells, so their degrees of freedom are $1$.

Therefore, print $1$.

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

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

const int N = 1e3 + 10;

int n, m;
char g[N][N];
int vis[N][N], dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}, st[N][N];
PII q[N * N];
int hh, tt;

int bfs(int sx, int sy) {
	hh = 0, tt = 0;
	int res = 1;
	queue<PII> qt;
	q[0] = {sx, sy}, st[sx][sy] = 1, vis[sx][sy] = 1;
	qt.emplace(sx, sy);

	while (hh <= tt) {
		auto tmp = q[hh ++];

		bool flg = 1;
		for (int i = 0; i < 4; i ++) {
			int xx = tmp.fi + dx[i], yy = tmp.se + dy[i];
			if (xx < 1 || yy < 1 || xx > n || yy > m) continue;
			if (g[xx][yy] == '#') {
				flg = 0;
				break;
			}
		}
		if (flg) {
			for (int i = 0; i < 4; i ++) {
				int xx = tmp.fi + dx[i], yy = tmp.se + dy[i];
				if (xx < 1 || yy < 1 || xx > n || yy > m) continue;
				if (!st[xx][yy]) res ++, st[xx][yy] = 1, qt.emplace(xx, yy);
				if (!vis[xx][yy]) q[ ++ tt] = {xx, yy}, vis[xx][yy] = 1;
			}	
		}
	}
	while (qt.size()) {
		auto v = qt.front();
		qt.pop();
		st[v.fi][v.se] = 0;
	}

	return res;
}

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

	cin >> n >> m;

	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			cin >> g[i][j];

	int res = 0;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (!vis[i][j] && g[i][j] == '.') {
				int val = bfs(i, j);
				res = max(res, val);
				// cout << i << " " << j << ":" << val << endl;
			}

	cout << res << endl;

	return 0;
}

---

E - Jump Distance Sum

Problem Statement

On a coordinate plane, there are $N$ points $P_1,P_2,\dots ,P_N$, where point $P_i$ has coordinates $(X_i,Y_i)$.

The distance $\text{dist}(A,B)$ between two points $A$ and $B$ is defined as follows:

A rabbit is initially at point $A$.
A rabbit at position $(x, y)$ can jump to $(x+1, y+1)$, $(x+1, y-1)$, $(x-1, y+1)$, or $(x-1, y-1)$ in one jump.
$\text{dist}(A, B)$ is defined as the minimum number of jumps required to get from point $A$ to point $B$.
If it is impossible to get from point $A$ to point $B$ after any number of jumps, let $\text{dist}(A, B) = 0$.

Calculate the sum $\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j)$. #### Constraints

$2\le N\le 2\times 10^5$
$0\le X_i,Y_i\le 10^8$
For $i\ne j$, $(X_i,Y_i)\ne (X_j,Y_j)$
All input values are integers.

Input

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

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$⋮$
$X_N$ $Y_N$

Output

Print the value of $\sum _{i=1}^{N-1}\sum _{j=i+1}^N\text{dist}(P_i,P_j)$ as an integer.

Sample Input 1

3
0 0
1 3
5 6

Sample Output 1

3

$P_1$, $P_2$, and $P_3$ have coordinates $(0,0)$, $(1,3)$, and $(5,6)$, respectively.

The rabbit can get from $P_1$ to $P_2$ in three jumps via $(0,0)\to (1,1)\to (0,2)\to (1,3)$, but not in two or fewer jumps,

so $\text{dist}(P_1,P_2)=3$.

The rabbit cannot get from $P_1$ to $P_3$ or from $P_2$ to $P_3$, so $\text{dist}(P_1,P_3)=\text{dist}(P_2,P_3)=0$.
Therefore, the answer is $\sum _{i=1}^2\sum _{j=i+1}^3\text{dist}(P_i,P_j)=\text{dist}(P_1,P_2)+\text{dist}(P_1,P_3)+\text{dist}(P_2,P_3)=3+0+0=3$.

Sample Input 2

5
0 5
1 7
2 9
3 8
4 6

Sample Output 2

11

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

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

const int N = 2e5 + 10;

int n;
PII p[N];

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

	cin >> n;

	for (int i = 1; i <= n; i ++) {
		int x, y;
		cin >> x >> y;
		p[i].fi = x + y, p[i].se = y - x;
	}

	sort(p + 1, p + 1 + n);

	int res = 0;
	int pcnt[2] = {0}, psum[2] = {0};
	for (int i = 1; i <= n; i ++) {
		int tmp = p[i].fi & 1;
		res += pcnt[tmp] * p[i].fi - psum[tmp];
		pcnt[tmp] ++, psum[tmp] += p[i].fi;
	}
	sort(p + 1, p + 1 + n, [&](PII a, PII b) {
		return a.se < b.se;
	});
	memset(pcnt, 0, sizeof pcnt);
	memset(psum, 0, sizeof psum);
	for (int i = 1; i <= n; i ++) {
		int tmp = p[i].fi & 1;
		res += pcnt[tmp] * p[i].se - psum[tmp];
		pcnt[tmp] ++, psum[tmp] += p[i].se;
	}

	cout << res / 2 << endl;

	return 0;
}

F - Double Sum

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\dots ,A_N)$.

Calculate the following expression:

$2\le N\le 4\times 10^5$
$0\le A_i\le 10^8$
All input values are integers.

Input

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

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the value of the expression.

Sample Input 1

3
2 5 3

Sample Output 1

4

For $(i,j)=(1,2)$, we have $\max (A_j-A_i,0)=\max (3,0)=3$.

For $(i,j)=(1,3)$, we have $\max (A_j-A_i,0)=\max (1,0)=1$.

For $(i,j)=(2,3)$, we have $\max (A_j-A_i,0)=\max (-2,0)=0$.

Adding these together gives $3+1+0=4$, which is the answer.

Sample Input 2

10
5 9 3 0 4 8 7 5 4 0

Sample Output 2

58

Solution

后期补一下这题目的视频

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

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

const int N = 4e5 + 10;

int n;
PII a[N];
struct fenwick
{
	int tr[N];
	void add(int x, int d) {
		for (int i = x; i < N; i += (i & -i)) tr[i] += d;
	}
	int sum(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & -i)) res += tr[i];
		return res;
	}
}sum, cnt;

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].fi, a[i].se = i;

	sort(a + 1, a + 1 + n);

	int res = 0;
	for (int i = 1; i <= n; i ++) {
		res += cnt.sum(a[i].se) * a[i].fi - sum.sum(a[i].se);
		cnt.add(a[i].se, 1), sum.add(a[i].se, a[i].fi);
	}

	cout << res << endl;

	return 0;
}

---

视频题解

---

最后祝大家早日