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

A - Pairing

Problem Statement

There are four balls, and the color of the $i$-th ball is $A_i$.
Find the maximum number of times you can perform this operation: choose two balls of the same color and discard both.

Constraints

Each of $A_1,A_2,A_3,A_4$ is an integer between $1$ and $4$, inclusive.

Input

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

$A_1$ $A_2$ $A_3$ $A_4$

Output

Print the maximum number of times the operation can be performed as an integer.

Sample Input 1

2 1 2 1

Sample Output 1

2

The first and third balls both have color $2$, so you can perform the operation to discard the first and third balls together.
Next, the second and fourth balls both have color $1$, so you can perform the operation to discard the second and fourth balls together.
Hence, you can perform a total of two operations.

Sample Input 2

4 4 4 1

Sample Output 2

1

Sample Input 3

1 2 3 4

Sample Output 3

0

There are cases where you cannot perform the operation even once.

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 a[4];
	for (int i = 0; i < 4; i ++) cin >> a[i];

	sort(a, a + 4);

	int res = 0;
	for (int i = 1; i < 4; i ++)
		if (a[i] == a[i - 1]) {
			res ++;
			i ++;
		}

	cout << res << endl;

	return 0;
}

B - Garbage Collection

Problem Statement

In AtCoder City, $N$ types of garbage are collected regularly. The $i$-th type of garbage $(i=1,2,\dots ,N)$ is collected on days when the date modulo $q_i$ equals $r_i$.
Answer $Q$ queries. In the $j$-th query $(j=1,2,\dots ,Q)$, given that the $t_j$-th type of garbage is put out on day $d_j$, answer the next day on which it will be collected.
Here, if the $i$-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

Constraints

$1\le N\le 100$
KaTeX parse error: Expected 'EOF', got '&' at position 12: 0 \leq r_i &̲lt; q_i \leq 10…
$1\le Q\le 100$
$1\le t_j\le N$
$1\le d_j\le 10^9$
All input values are integers.

Input

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

$N$
$q_1$ $r_1$
$q_2$ $r_2$
$⋮$
$q_N$ $r_N$
$Q$
$t_1$ $d_1$
$t_2$ $d_2$
$⋮$
$t_Q$ $d_Q$

Output

Print $Q$ lines. The $j$-th line $(1\le j\le Q)$ should contain the answer to the $j$-th query.

Sample Input 1

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

Sample Output 1

3
3
10
17
10

1st query: The 1st type of garbage is collected on day $3$ for the first time after day $1$.
2nd query: The 1st type of garbage is collected on day $3$ for the first time after day $3$.
3rd query: The 1st type of garbage is collected on day $10$ for the first time after day $4$.

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> q(n), r(n);
	for (int i = 0; i < n; i ++)
		cin >> q[i] >> r[i];

	int Q;
	cin >> Q;

	while (Q -- ) {
		int t, d;
		cin >> t >> d, t --;

		int rr = d % q[t];
		if (rr > r[t]) cout << r[t] + q[t] - rr + d << endl;
		else cout << r[t] - rr + d << endl;
	}

	return 0;
}

C - Repeating

Problem Statement

You are given a sequence of $N$ positive numbers, $A=(A_1,A_2,\dots ,A_N)$. Find the sequence $B=(B_1,B_2,\dots ,B_N)$ of length $N$ defined as follows.
For $i=1,2,\dots ,N$, define $B_i$ as follows:
Let $B_i$ be the most recent position before $i$ where an element equal to $A_i$ appeared. If such a position does not exist, let $B_i=-1$.

More precisely, if there exists a positive integer $j$ such that $A_i=A_j$ and KaTeX parse error: Expected 'EOF', got '&' at position 3: j &̲lt; i, let $B_i$ be the largest such $j$. If no such $j$ exists, let $B_i=-1$.

Constraints

$1\le N\le 2\times 10^5$
$1\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 elements of $B$ in one line, separated by spaces.

Sample Input 1

5
1 2 1 1 3

Sample Output 1

-1 -1 1 3 -1

$i=1$: There is no $1$ before $A_1=1$, so $B_1=-1$.
$i=2$: There is no $2$ before $A_2=2$, so $B_2=-1$.
$i=3$: The most recent occurrence of $1$ before $A_3=1$ is $A_1$, so $B_3=1$.
$i=4$: The most recent occurrence of $1$ before $A_4=1$ is $A_3$, so $B_4=3$.
$i=5$: There is no $3$ before $A_5=3$, so $B_5=-1$.

Sample Input 2

4
1 1000000000 1000000000 1

Sample Output 2

-1 -1 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 n;
	cin >> n;

	unordered_map<int, int> pos;
	for (int i = 1; i <= n; i ++) {
		int x;
		cin >> x;
		if (pos.count(x)) cout << pos[x] << " ";
		else cout << -1 << " ";
		pos[x] = i;
	}
	cout << endl;

	return 0;
}

D - Count Simple Paths

Problem Statement

There is a grid of $H\times W$ cells. Let $(i,j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left.
Cell $(i,j)$ is empty if $S_{i,j}$ is ., and blocked if it is #.
Count the number of ways to start from an empty cell and make $K$ moves to adjacent cells (up, down, left, or right), without passing through blocked squares and not visiting the same cell more than once.
Specifically, count the number of sequences of length $K+1$, $((i_0,j_0),(i_1,j_1),\dots ,(i_K,j_K))$, satisfying the following.
$1\le i_k\le H$, $1\le j_k\le W$, and $S_{i_k,j_k}$ is ., for each $0\le k\le K$.
$|i_{k+1}-i_k|+|j_{k+1}-j_k|=1$ for each $0\le k\le K-1$.
$(i_k,j_k)\ne (i_l,j_l)$ for each KaTeX parse error: Expected 'EOF', got '&' at position 10: 0 \leq k &̲lt; l \leq K.

Constraints

$1\le H,W\le 10$
$1\le K\le 11$
$H$, $W$, and $K$ are integers.
Each $S_{i,j}$ is . or #.
There is at least one empty cell.

Input

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

$H$ $W$ $K$
$S_{1,1}{S}_{1,2}\dots S_{1,W}$
$S_{2,1}{S}_{2,2}\dots S_{2,W}$
$⋮$
$S_{H,1}{S}_{H,2}\dots S_{H,W}$

Output

Print the answer.

Sample Input 1

2 2 2
.#
..

Sample Output 1

2

Here are the two possible paths:
$(1,1)\to (2,1)\to (2,2)$
$(2,2)\to (2,1)\to (1,1)$

Sample Input 2

2 3 1
.#.
#.#

Sample Output 2

0

Sample Input 3

10 10 11
....#..#..
.#.....##.
..#...##..
...#......
......##..
..#......#
#........#
..##......
.###....#.
...#.....#

Sample Output 3

218070

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;

int H, W, K;
char g[15][15];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int res = 0;

void DFS(int x, int y, int k) {
	if (!k) {
		res ++;
		return;
	}
	g[x][y] = '#';
	for (int i = 0; i < 4; i ++) {
		int xx = x + dx[i], yy = y + dy[i];
		if (xx < 1 || yy < 1 || xx > H || yy > W || g[xx][yy] == '#') continue;
		DFS(xx, yy, k - 1);
	}
	g[x][y] = '.';
}

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

	cin >> H >> W >> K;
	for (int i = 1; i <= H; i ++)
		for (int j = 1; j <= W; j ++)
			cin >> g[i][j];

	for (int i = 1; i <= H; i ++)
		for (int j = 1; j <= W; j ++) {
			if (g[i][j] == '#') continue;
			DFS(i, j, K);
		}

	cout << res << endl;

	return 0;
}

E - Mod Sigma Problem

Problem Statement

You are given a sequence $A=(A_1,A_2,\dots ,A_N)$ of $N$ non-negative integers, and a positive integer $M$.
Find the following value:
[
\sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right).
]
Here, $X\mathrm{mod}M$ denotes the remainder when the non-negative integer $X$ is divided by $M$.

Constraints

$1\le N\le 2\times 10^5$
$1\le M\le 2\times 10^5$
$0\le A_i\le 10^9$

Input

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

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

Output

Print the answer.

Sample Input 1

3 4
2 5 0

Sample Output 1

10

$A_1\mathrm{mod}M=2$
$(A_1+A_2)\mathrm{mod}M=3$
$(A_1+A_2+A_3)\mathrm{mod}M=3$
$A_2\mathrm{mod}M=1$
$(A_2+A_3)\mathrm{mod}M=1$
$A_3\mathrm{mod}M=0$
The answer is the sum of these values, $10$. Note that the outer sum is not taken modulo $M$.

Sample Input 2

10 100
320 578 244 604 145 839 156 857 556 400

Sample Output 2

2736

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;

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) {
		if (!x) return 0;
		int res = 0;
		for (int i = x; i; i -= (i & -i)) res += tr[i];
		return res;
	}
}A, B;
int n, m;
int a[N], b[N];

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

	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], b[i] = (b[i - 1] + a[i]) % m;

	int res = 0;
	A.add(1, m), B.add(1, 1);
	for (int i = 1; i <= n; i ++) {
		res += A.sum(b[i] + 1) - B.sum(b[i] + 1) * (m - b[i]);
		res += A.sum(m) - A.sum(b[i] + 1) + b[i] * (B.sum(m) - B.sum(b[i] + 1));
		A.add(b[i] + 1, m - b[i]), B.add(b[i] + 1, 1);
	}

	cout << res << endl;

	return 0;
}

F - Add One Edge 2

Problem Statement

You are given a tree with $N$ vertices. The $i$-th edge $(1\le i\le N-1)$ connects vertices $u_i$ and $v_i$ bidirectionally.
Adding one undirected edge to the given tree always yields a graph with exactly one cycle.
Among such graphs, how many satisfy all of the following conditions?
The graph is simple.
All vertices in the cycle have degree $3$.

Constraints

$3\le N\le 2\times 10^5$
$1\le u_i,v_i\le N$
The given graph is a tree.
All input values are integers.

Input

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

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

Output

Print the answer.

Sample Input 1

6
1 2
2 3
3 4
4 5
3 6

Sample Output 1

1

Adding an edge connecting vertices $2$ and $4$ yields a simple graph where all vertices in the cycle have degree $3$, so it satisfies the conditions.

Sample Input 2

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

Sample Output 2

0

There are cases where no graphs satisfy the conditions.

Sample Input 3

15
1 15
11 14
2 10
1 7
9 8
6 9
4 12
14 5
4 9
8 11
7 4
1 13
3 6
11 10

Sample Output 3

6

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;
std::vector<int> g[N];
int d[N], lg[N], fa[N];
int res = 0, cnt[N];

void dfs(int u) {
	if (d[u] == 3) {
		for (auto v : g[u]) {
			if (v == fa[u]) continue;
			fa[v] = u;
			dfs(v);
			lg[u] += lg[v];
			res -= lg[v] * (lg[v] - 1) / 2;
		}
		res += lg[u] * (lg[u] - 1) / 2;
	} else if (d[u] == 2) {
		for (auto v : g[u]) {
			if (v == fa[u]) continue;
			fa[v] = u;
			dfs(v);
			if (d[v] == 2) continue;
			res += lg[v];
		}
		lg[u] = 1;
	} else {
		for (auto v : g[u]) {
			if (v == fa[u]) continue;
			fa[v] = u;
			dfs(v);
		}
	}
}

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

	cin >> n;
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v), g[v].push_back(u);
		d[u] ++, d[v] ++;
	}

	dfs(1);

	cout << res << endl;

	return 0;
}

视频题解

最后祝大家早日