Atcoder Beginner Contest 335 (A - F 题)
A - 2023
Problem Statement
You are given a string
S
S
S consisting of lowercase English letters and digits.
S
S
S is guaranteed to end with 2023
.
Change the last character of
S
S
S to 4
and print the modified string.
Constraints
- S S S is a string of length between 4 4 4 and 100 100 100, inclusive, consisting of lowercase English letters and digits.
-
S
S
S ends with
2023
.
Input
The input is given from Standard Input in the following format:
S S S
Output
Print the answer.
Sample Input 1
hello2023
Sample Output 1
hello2024
Changing the last character of hello2023
to 4
yields hello2024
.
Sample Input 2
worldtourfinals2023
Sample Output 2
worldtourfinals2024
Sample Input 3
2023
Sample Output 3
2024
S
S
S is guaranteed to end with 2023
, possibly being 2023
itself.
Sample Input 4
20232023
Sample Output 4
20232024
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
string S;
cin >> S;
int N = S.size();
S = ' ' + S;
S[N] = '4';
S.erase(0, 1);
cout << S << endl;
return 0;
}
B - Tetrahedral Number
Problem Statement
You are given an integer N N N.
Print all triples of non-negative integers ( x , y , z ) (x,y,z) (x,y,z) such that x + y + z ≤ N x+y+z\leq N x+y+z≤N in ascending lexicographical order.
What is lexicographical order for non-negative integer triples?
A triple of non-negative integers ( x , y , z ) (x,y,z) (x,y,z) is said to be lexicographically smaller than ( x ′ , y ′ , z ′ ) (x',y',z') (x′,y′,z′) if and only if one of the following holds:
- x < x ′ x < x' x<x′;
- x = x ′ x=x' x=x′ and y < y ′ y< y' y<y′;
- x = x ′ x=x' x=x′ and y = y ′ y=y' y=y′ and z < z ′ z< z' z<z′.
Constraints
- 0 ≤ N ≤ 21 0 \leq N \leq 21 0≤N≤21
- N N N is an integer.
Input
The input is given from Standard Input in the following format:
N N N
Output
Print all triples of non-negative integers ( x , y , z ) (x,y,z) (x,y,z) such that x + y + z ≤ N x+y+z\leq N x+y+z≤N in ascending lexicographical order, with x , y , z x,y,z x,y,z separated by spaces, one triple per line.
Sample Input 1
3
Sample Output 1
0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 3 0
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 2 0
2 0 0
2 0 1
2 1 0
3 0 0
Sample Input 2
4
Sample Output 2
0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 1 0
0 1 1
0 1 2
0 1 3
0 2 0
0 2 1
0 2 2
0 3 0
0 3 1
0 4 0
1 0 0
1 0 1
1 0 2
1 0 3
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 3 0
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 2 0
3 0 0
3 0 1
3 1 0
4 0 0
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int N;
cin >> N;
for (int X = 0; X <= N; X ++)
for (int Y = 0; Y <= N; Y ++)
for (int Z = 0; Z <= N; Z ++)
if (X + Y + Z <= N)
cout << X << " " << Y << " " << Z << endl;
return 0;
}
C - Loong Tracking
Problem Statement
Takahashi has created a game where the player controls a dragon on a coordinate plane.
The dragon consists of N N N parts numbered 1 1 1 to N N N, with part 1 1 1 being called the head.
Initially, part i i i is located at the coordinates ( i , 0 ) (i,0) (i,0). Process Q Q Q queries as follows.
1 C
: Move the head by 1 1 1 in direction C C C. Here, C C C is one ofR
,L
,U
, andD
, which represent the positive x x x-direction, negative x x x-direction, positive y y y-direction, and negative y y y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i i i ( 2 ≤ i ≤ N ) (2\leq i \leq N) (2≤i≤N) moves to the coordinates where part i ? 1 i-1 i?1 was before the move.2 p
: Find the coordinates of part p p p.
Constraints
- 2 ≤ N ≤ 1 0 6 2 \leq N \leq 10^6 2≤N≤106
- 1 ≤ Q ≤ 2 × 1 0 5 1 \leq Q \leq 2\times 10^5 1≤Q≤2×105
- For the first type of query,
C
C
C is one of
R
,L
,U
, andD
. - For the second type of query, 1 ≤ p ≤ N 1\leq p \leq N 1≤p≤N.
- All numerical input values are integers.
Input
The input is given from Standard Input in the following format:
N
N
N
Q
Q
Q
q
u
e
r
y
1
\mathrm{query}_1
query1?
?
\vdots
?
q
u
e
r
y
Q
\mathrm{query}_Q
queryQ?
Each query is in one of the following two formats:
1 1 1 C C C
2 2 2 p p p
Output
Print
q
q
q lines, where
q
q
q is the number of queries of the second type.
The
i
i
i-th line should contain
x
x
x and
y
y
y separated by a space, where
(
x
,
y
)
(x,y)
(x,y) are the answer to the
i
i
i-th such query.
Sample Input 1
5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5
Sample Output 1
113
The integers that can be expressed as the sum of exactly three repunits are
3
,
13
,
23
,
33
,
113
,
…
3, 13, 23, 33, 113, \ldots
3,13,23,33,113,… in ascending order. For example,
113
113
113 can be expressed as
113
=
1
+
1
+
111
113 = 1 + 1 + 111
113=1+1+111.
Note that the three repunits do not have to be distinct.
Sample Input 2
3 0
2 0
1 1
1 0
1 0
At each time when processing the second type of query, the parts are at the following positions:
Note that multiple parts may exist at the same coordinates.
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int SIZE = 2e5 + 10;
int N, Q;
int X[SIZE], Y[SIZE];
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> N >> Q;
int i = 0;
X[0] = 1, Y[0] = 0;
while (Q --)
{
int op, P;
char T;
cin >> op;
if (op == 1)
{
cin >> T;
i ++;
if (T == 'R') X[i] = X[i - 1] + 1, Y[i] = Y[i - 1];
else if (T == 'U') Y[i] = Y[i - 1] + 1, X[i] = X[i - 1];
else if (T == 'L') X[i] = X[i - 1] - 1, Y[i] = Y[i - 1];
else Y[i] = Y[i - 1] - 1, X[i] = X[i - 1];
}
else
{
cin >> P;
if (i < P) cout << P - i << " " << 0 << endl;
else cout << X[i - P + 1] << " " << Y[i - P + 1] << endl;
}
}
return 0;
}
D - Loong and Takahashi
Problem Statement
There is a grid with N N N rows and N N N columns, where N N N is an odd number at most 45 45 45.
Let ( i , j ) (i,j) (i,j) denote the cell at the i i i-th row from the top and j j j-th column from the left.
In this grid, you will place Takahashi and a dragon consisting of N 2 ? 1 N^2-1 N2?1 parts numbered 1 1 1 to N 2 ? 1 N^2-1 N2?1 in such a way that satisfies the following conditions:
- Takahashi must be placed at the center of the grid, that is, in cell ( N + 1 2 , N + 1 2 ) (\frac{N+1}{2},\frac{N+1}{2}) (2N+1?,2N+1?).
- Except for the cell where Takahashi is, exactly one dragon part must be placed in each cell.
- For every integer
x
x
x satisfying
2
≤
x
≤
N
2
?
1
2 \leq x \leq N^2-1
2≤x≤N2?1, the dragon part
x
x
x must be placed in a cell adjacent by an edge to the cell containing part
x
?
1
x-1
x?1.
- Cells ( i , j ) (i,j) (i,j) and ( k , l ) (k,l) (k,l) are said to be adjacent by an edge if and only if ∣ i ? k ∣ + ∣ j ? l ∣ = 1 |i-k|+|j-l|=1 ∣i?k∣+∣j?l∣=1.
Print one way to arrange the parts to satisfy the conditions. It is guaranteed that there is at least one arrangement that satisfies the conditions.
Constraints
- 3 ≤ N ≤ 45 3 \leq N \leq 45 3≤N≤45
- N N N is odd.
Input
The input is given from Standard Input in the following format:
N N N
Output
Print
N
N
N lines.
The
i
i
i-th line should contain
X
i
,
1
,
…
,
X
i
,
N
X_{i,1},\ldots,X_{i,N}
Xi,1?,…,Xi,N? separated by spaces, where
X
i
,
j
X_{i,j}
Xi,j? is T
when placing Takahashi in cell
(
i
,
j
)
(i,j)
(i,j) and
x
x
x when placing part
x
x
x there.
Sample Input 1
5
Sample Output 1
1 2 3 4 5
16 17 18 19 6
15 24 T 20 7
14 23 22 21 8
13 12 11 10 9
The following output also satisfies all the conditions and is correct.
9 10 11 14 15
8 7 12 13 16
5 6 T 18 17
4 3 24 19 20
1 2 23 22 21
On the other hand, the following outputs are incorrect for the reasons given.
Takahashi is not at the center.
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 T
The cells containing parts 23 23 23 and 24 24 24 are not adjacent by an edge.
1 2 3 4 5
10 9 8 7 6
11 12 24 22 23
14 13 T 21 20
15 16 17 18 19
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int SIZE = 50;
int N;
int Result[SIZE][SIZE];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> N;
int X = 1, Y = 1, Sd = 0;
for (int i = 1; i <= N; i ++)
Result[0][i] = 1e18, Result[N + 1][i] = 1e18, Result[i][0] = 1e18, Result[i][N + 1] = 1e18;
for (int i = 1; i <= N * N - 1; i ++)
{
Result[X][Y] = i;
if (Result[X + dx[Sd]][Y + dy[Sd]]) Sd = (Sd + 1) % 4;
X += dx[Sd], Y += dy[Sd];
}
for (int i = 1; i <= N; i ++)
{
for (int j = 1; j <= N; j ++)
if ((1 + N >> 1) == i && i == j)
cout << "T ";
else
cout << Result[i][j] << " ";
cout << endl;
}
return 0;
}
E - Non-Decreasing Colorful Path
Problem Statement
There is a connected undirected graph with
N
N
N vertices and
M
M
M edges, where the
i
i
i-th edge connects vertex
U
i
U_i
Ui? and vertex
V
i
V_i
Vi? bidirectionally.
Each vertex has an integer written on it, with integer
A
v
A_v
Av? written on vertex
v
v
v.
For a simple path from vertex 1 1 1 to vertex N N N (a path that does not pass through the same vertex multiple times), the score is determined as follows:
- Let S S S be the sequence of integers written on the vertices along the path, listed in the order they are visited.
- If S S S is not non-decreasing, the score of that path is 0 0 0.
- Otherwise, the score is the number of distinct integers in S S S.
Find the path from vertex 1 1 1 to vertex N N N with the highest score among all simple paths and print that score.
What does it mean for S S S to be non-decreasing? A sequence S = ( S 1 , S 2 , … , S l ) S=(S_1,S_2,\dots,S_l) S=(S1?,S2?,…,Sl?) of length l l l is said to be non-decreasing if and only if S i ≤ S i + 1 S_i \le S_{i+1} Si?≤Si+1? for all integers 1 ≤ i < l 1 \le i < l 1≤i<l.
Constraints
- All input values are integers.
- 2 ≤ N ≤ 2 × 1 0 5 2 \le N \le 2 \times 10^5 2≤N≤2×105
- N ? 1 ≤ M ≤ 2 × 1 0 5 N-1 \le M \le 2 \times 10^5 N?1≤M≤2×105
- 1 ≤ A i ≤ 2 × 1 0 5 1 \le A_i \le 2 \times 10^5 1≤Ai?≤2×105
- The graph is connected.
- 1 ≤ U i < V i ≤ N 1 \le U_i < V_i \le N 1≤Ui?<Vi?≤N
- ( U i , V i ) ≠ ( U j , V j ) (U_i,V_i) \neq (U_j,V_j) (Ui?,Vi?)=(Uj?,Vj?) if i ≠ j i \neq j i=j.
Input
The input is given from Standard Input in the following format:
N
N
N
M
M
M
A
1
A_1
A1?
A
2
A_2
A2?
…
\dots
…
A
N
A_N
AN?
U
1
U_1
U1?
V
1
V_1
V1?
U
2
U_2
U2?
V
2
V_2
V2?
?
\vdots
?
U
M
U_M
UM?
V
M
V_M
VM?
Output
Print the answer as an integer.
Sample Input 1
5 6
10 20 30 40 50
1 2
1 3
2 5
3 4
3 5
4 5
Sample Output 1
4
The path 1 → 3 → 4 → 5 1 \rightarrow 3 \rightarrow 4 \rightarrow 5 1→3→4→5 has S = ( 10 , 30 , 40 , 50 ) S=(10,30,40,50) S=(10,30,40,50) for a score of 4 4 4, which is the maximum.
Sample Input 2
4 5
1 10 11 4
1 2
1 3
2 3
2 4
3 4
Sample Output 2
0
There is no simple path from vertex 1 1 1 to vertex N N N such that S S S is non-decreasing. In this case, the maximum score is 0 0 0.
Sample Input 3
10 12
1 2 3 3 4 4 4 6 5 7
1 3
2 9
3 4
5 6
1 2
8 9
4 5
8 10
7 10
4 6
2 8
6 7
Sample Output 3
5
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int SIZE = 2e5 + 10;
int N, M, A[SIZE], P[SIZE], F[SIZE];
std::vector<PIII> Edge;
std::vector<int> G[SIZE];
int Vis[SIZE];
vector<int> Point;
int Find(int x)
{
if (P[x] != x) P[x] = Find(P[x]);
return P[x];
}
void BFS()
{
queue<int> Q;
Q.push(Find(1));
while (Q.size())
{
int u = Q.front();
Q.pop();
if (Vis[u]) continue;
Vis[u] = 1;
Point.push_back(u);
for (auto c : G[u])
Q.push(c);
}
}
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], P[i] = i;
int u, v;
for (int i = 1; i <= M; i ++)
{
cin >> u >> v;
if (A[u] > A[v]) swap(u, v);
if (A[u] == A[v]) P[Find(v)] = Find(u);
else Edge.push_back({A[u], {u, v}});
}
// for (auto c : Edge)
// G[Find(c.first)].push_back(Find(c.second));
// BFS();
sort(Edge.begin(), Edge.end());
memset(F, -0x3f, sizeof F);
F[Find(1)] = 1;
for (auto c : Edge)
{
int u = Find(c.second.first), v = Find(c.second.second);
F[v] = max(F[v], F[u] + 1);
}
cout << max(0ll, F[Find(N)]) << endl;
return 0;
}
F - Hop Sugoroku
Problem Statement
There is a row of
N
N
N squares labeled
1
,
2
,
…
,
N
1,2,\dots,N
1,2,…,N and a sequence
A
=
(
A
1
,
A
2
,
…
,
A
N
)
A=(A_1,A_2,\dots,A_N)
A=(A1?,A2?,…,AN?) of length
N
N
N.
Initially, square
1
1
1 is painted black, the other
N
?
1
N-1
N?1 squares are painted white, and a piece is placed on square
1
1
1.
You may repeat the following operation any number of times, possibly zero:
- When the piece is on square
i
i
i, choose a positive integer
x
x
x and move the piece to square
i
+
A
i
×
x
i + A_i \times x
i+Ai?×x.
- Here, you cannot make a move with i + A i × x > N i + A_i \times x > N i+Ai?×x>N.
- Then, paint the square i + A i × x i + A_i \times x i+Ai?×x black.
Find the number of possible sets of squares that can be painted black at the end of the operations, modulo 998244353 998244353 998244353.
Constraints
- All input values are integers.
- 1 ≤ N ≤ 2 × 1 0 5 1 \le N \le 2 \times 10^5 1≤N≤2×105
- 1 ≤ A i ≤ 2 × 1 0 5 1 \le A_i \le 2 \times 10^5 1≤Ai?≤2×105
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 answer as an integer.
Sample Input 1
5
1 2 3 1 1
Sample Output 1
8
There are eight possible sets of squares painted black:
- Square 1 1 1
- Squares 1 , 2 1,2 1,2
- Squares 1 , 2 , 4 1,2,4 1,2,4
- Squares 1 , 2 , 4 , 5 1,2,4,5 1,2,4,5
- Squares 1 , 3 1,3 1,3
- Squares 1 , 4 1,4 1,4
- Squares 1 , 4 , 5 1,4,5 1,4,5
- Squares 1 , 5 1,5 1,5
Sample Input 2
1
200000
Sample Output 2
1
Sample Input 3
40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output 3
721419738
Be sure to find the number modulo 998244353 998244353 998244353.
Solution
具体见文后视频。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int SIZE = 2e5 + 10, SIZE2 = 450, MOD = 998244353;
int N;
int A[SIZE];
int F[SIZE], G[SIZE2][SIZE2];
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];
F[1] = 1;
int B = sqrt(N) + 1;
for (int i = 1; i <= N; i ++)
{
for (int j = 1; j <= B; j ++)
F[i] = (F[i] + G[j][i % j]) % MOD;
if (A[i] > B)
for (int j = i + A[i]; j <= N; j += A[i])
F[j] = (F[j] + F[i]) % MOD;
else
G[A[i]][i % A[i]] = (G[A[i]][i % A[i]] + F[i]) % MOD;
}
int Result = 0;
for (int i = 1; i <= N; i ++)
Result = (Result + F[i]) % MOD;
cout << Result << endl;
return 0;
}
视频题解
Atcoder Beginner Contest 335 讲解(A - F题)
最后祝大家早日
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!