A - Pairing
Problem Statement
There are four balls, and the color of the i i i-th ball is A i A_i Ai.
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 A_1, A_2, A_3, A_4 A1,A2,A3,A4 is an integer between 1 1 1 and 4 4 4, inclusive.
Input
The input is given from Standard Input in the following format:
A 1 A_1 A1 A 2 A_2 A2 A 3 A_3 A3 A 4 A_4 A4
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 2 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 1 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 N N types of garbage are collected regularly. The i i i-th type of garbage ( i = 1 , 2 , … , N ) (i=1,2,\dots,N) (i=1,2,…,N) is collected on days when the date modulo q i q_i qi equals r i r_i ri.
Answer Q Q Q queries. In the j j j-th query ( j = 1 , 2 , … , Q ) (j=1,2,\dots,Q) (j=1,2,…,Q), given that the t j t_j tj-th type of garbage is put out on day d j d_j dj, answer the next day on which it will be collected.
Here, if the i i 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 ≤ N ≤ 100 1 \leq N \leq 100 1≤N≤100
KaTeX parse error: Expected 'EOF', got '&' at position 12: 0 \leq r_i &̲lt; q_i \leq 10…
1 ≤ Q ≤ 100 1 \leq Q \leq 100 1≤Q≤100
1 ≤ t j ≤ N 1 \leq t_j \leq N 1≤tj≤N
1 ≤ d j ≤ 1 0 9 1 \leq d_j \leq 10^9 1≤dj≤109
All input values are integers.
Input
The input is given from Standard Input in the following format:
N N N
q 1 q_1 q1 r 1 r_1 r1
q 2 q_2 q2 r 2 r_2 r2
⋮ \vdots ⋮
q N q_N qN r N r_N rN
Q Q Q
t 1 t_1 t1 d 1 d_1 d1
t 2 t_2 t2 d 2 d_2 d2
⋮ \vdots ⋮
t Q t_Q tQ d Q d_Q dQ
Output
Print Q Q Q lines. The j j j-th line ( 1 ≤ j ≤ Q ) (1\leq j \leq Q) (1≤j≤Q) should contain the answer to the j j 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 3 3 for the first time after day 1 1 1.
2nd query: The 1st type of garbage is collected on day 3 3 3 for the first time after day 3 3 3.
3rd query: The 1st type of garbage is collected on day 10 10 10 for the first time after day 4 4 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 N N positive numbers, A = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, \dots, A_N) A=(A1,A2,…,AN). Find the sequence B = ( B 1 , B 2 , … , B N ) B = (B_1, B_2, \dots, B_N) B=(B1,B2,…,BN) of length N N N defined as follows.
For i = 1 , 2 , … , N i = 1, 2, \dots, N i=1,2,…,N, define B i B_i Bi as follows:
Let B i B_i Bi be the most recent position before i i i where an element equal to A i A_i Ai appeared. If such a position does not exist, let B i = − 1 B_i = -1 Bi=−1.
More precisely, if there exists a positive integer j j j such that A i = A j A_i = A_j Ai=Aj and KaTeX parse error: Expected 'EOF', got '&' at position 3: j &̲lt; i, let B i B_i Bi be the largest such j j j. If no such j j j exists, let B i = − 1 B_i = -1 Bi=−1.
Constraints
1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1≤N≤2×105
1 ≤ A i ≤ 1 0 9 1 \leq A_i \leq 10^9 1≤Ai≤109
All input values are integers.
Input
The input is given from Standard Input in the following format:
N N N
A 1 A_1 A1 A 2 A_2 A2 … \dots … A N A_N AN
Output
Print the elements of B B 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 i = 1 i=1: There is no 1 1 1 before A 1 = 1 A_1 = 1 A1=1, so B 1 = − 1 B_1 = -1 B1=−1.
i = 2 i = 2 i=2: There is no 2 2 2 before A 2 = 2 A_2 = 2 A2=2, so B 2 = − 1 B_2 = -1 B2=−1.
i = 3 i = 3 i=3: The most recent occurrence of 1 1 1 before A 3 = 1 A_3 = 1 A3=1 is A 1 A_1 A1, so B 3 = 1 B_3 = 1 B3=1.
i = 4 i = 4 i=4: The most recent occurrence of 1 1 1 before A 4 = 1 A_4 = 1 A4=1 is A 3 A_3 A3, so B 4 = 3 B_4 = 3 B4=3.
i = 5 i = 5 i=5: There is no 3 3 3 before A 5 = 3 A_5 = 3 A5=3, so B 5 = − 1 B_5 = -1 B5=−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 × W H \times W H×W cells. Let ( i , j ) (i, j) (i,j) denote the cell at the i i i-th row from the top and the j j j-th column from the left.
Cell ( i , j ) (i, j) (i,j) is empty if S i , j S_{i,j} Si,j is .
, and blocked if it is #
.
Count the number of ways to start from an empty cell and make K K 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 K+1 K+1, ( ( i 0 , j 0 ) , ( i 1 , j 1 ) , … , ( i K , j K ) ) ((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K)) ((i0,j0),(i1,j1),…,(iK,jK)), satisfying the following.
1 ≤ i k ≤ H 1 \leq i_k \leq H 1≤ik≤H, 1 ≤ j k ≤ W 1 \leq j_k \leq W 1≤jk≤W, and S i k , j k S_{i_k, j_k} Sik,jk is .
, for each 0 ≤ k ≤ K 0 \leq k \leq K 0≤k≤K.
∣ i k + 1 − i k ∣ + ∣ j k + 1 − j k ∣ = 1 |i_{k+1} - i_k| + |j_{k+1} - j_k| = 1 ∣ik+1−ik∣+∣jk+1−jk∣=1 for each 0 ≤ k ≤ K − 1 0 \leq k \leq K-1 0≤k≤K−1.
( i k , j k ) ≠ ( i l , j l ) (i_k, j_k) \neq (i_l, j_l) (ik,jk)=(il,jl) for each KaTeX parse error: Expected 'EOF', got '&' at position 10: 0 \leq k &̲lt; l \leq K.
Constraints
1 ≤ H , W ≤ 10 1 \leq H, W \leq 10 1≤H,W≤10
1 ≤ K ≤ 11 1 \leq K \leq 11 1≤K≤11
H H H, W W W, and K K K are integers.
Each S i , j S_{i,j} Si,j is .
or #
.
There is at least one empty cell.
Input
The input is given from Standard Input in the following format:
H H H W W W K K K
S 1 , 1 S 1 , 2 … S 1 , W S_{1,1}S_{1,2}\dots S_{1,W} S1,1S1,2…S1,W
S 2 , 1 S 2 , 2 … S 2 , W S_{2,1}S_{2,2}\dots S_{2,W} S2,1S2,2…S2,W
⋮ \vdots ⋮
S H , 1 S H , 2 … S H , W S_{H,1}S_{H,2}\dots S_{H,W} SH,1SH,2…SH,W
Output
Print the answer.
Sample Input 1
2 2 2
.#
..
Sample Output 1
2
Here are the two possible paths:
( 1 , 1 ) → ( 2 , 1 ) → ( 2 , 2 ) (1,1) \rightarrow (2,1) \rightarrow (2,2) (1,1)→(2,1)→(2,2)
( 2 , 2 ) → ( 2 , 1 ) → ( 1 , 1 ) (2,2) \rightarrow (2,1) \rightarrow (1,1) (2,2)→(2,1)→(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 , … , A N ) A = (A_1, A_2, \dots, A_N) A=(A1,A2,…,AN) of N N N non-negative integers, and a positive integer M M 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 m o d M X \mathbin{\mathrm{mod}} M XmodM denotes the remainder when the non-negative integer X X X is divided by M M M.
Constraints
1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1≤N≤2×105
1 ≤ M ≤ 2 × 1 0 5 1 \leq M \leq 2 \times 10^5 1≤M≤2×105
0 ≤ A i ≤ 1 0 9 0 \leq A_i \leq 10^9 0≤Ai≤109
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 m o d M = 2 A_1 \mathbin{\mathrm{mod}} M = 2 A1modM=2
( A 1 + A 2 ) m o d M = 3 (A_1+A_2) \mathbin{\mathrm{mod}} M = 3 (A1+A2)modM=3
( A 1 + A 2 + A 3 ) m o d M = 3 (A_1+A_2+A_3) \mathbin{\mathrm{mod}} M = 3 (A1+A2+A3)modM=3
A 2 m o d M = 1 A_2 \mathbin{\mathrm{mod}} M = 1 A2modM=1
( A 2 + A 3 ) m o d M = 1 (A_2+A_3) \mathbin{\mathrm{mod}} M = 1 (A2+A3)modM=1
A 3 m o d M = 0 A_3 \mathbin{\mathrm{mod}} M = 0 A3modM=0
The answer is the sum of these values, 10 10 10. Note that the outer sum is not taken modulo M M 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 N N vertices. The i i i-th edge ( 1 ≤ i ≤ N − 1 ) (1 \leq i \leq N-1) (1≤i≤N−1) connects vertices u i u_i ui and v i v_i vi 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 3 3.
Constraints
3 ≤ N ≤ 2 × 1 0 5 3 \leq N \leq 2 \times 10^5 3≤N≤2×105
1 ≤ u i , v i ≤ N 1 \leq u_i, v_i \leq N 1≤ui,vi≤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 2 2 and 4 4 4 yields a simple graph where all vertices in the cycle have degree 3 3 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;
}
视频题解
AtCoder Beginner Contest 378(A ~ F 题讲解)
最后祝大家早日