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

A - Shout Everyday

Problem Statement

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at $A$ o’clock every day.
Takahashi, who lives in the Kingdom of AtCoder, goes to bed at $B$ o’clock and wakes up at $C$ o’clock every day (in the $24$-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has $24$ hours, and his sleeping time is less than $24$ hours.

Constraints

$0\le A,B,C<24$
$A$, $B$, and $C$ are pairwise different.
All input values are integers.

Input

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

$A$ $B$ $C$

Output

Print Yes if Takahashi can shout his love for takoyaki every day, and No otherwise.

Sample Input 1

21 8 14

Sample Output 1

Yes

Takahashi goes to bed at $8$ o’clock and wakes up at $14$ o’clock every day. He is awake at $21$ o’clock, so he can shout his love for takoyaki every day. Therefore, print Yes.

Sample Input 2

0 21 7

Sample Output 2

No

Takahashi goes to bed at $21$ o’clock and wakes up at $7$ o’clock every day. He is not awake at $0$ o’clock, so he cannot shout his love for takoyaki every day. Therefore, print No.

Sample Input 3

10 7 17

Sample Output 3

No

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing 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, b, c;cin >> a >> b >> c;if (b > c) {if (a >= b && a < 24 || a <= c) cout << "No" << endl;else cout << "Yes" << endl;} else {if (a >= b && a <= c) cout << "No" << endl;else cout << "Yes" << endl;}return 0;
}

B - Cut .0

Problem Statement

A real number $X$ is given to the third decimal place.
Print the real number $X$ under the following conditions.
The decimal part must not have trailing 0s.
There must not be an unnecessary trailing decimal point.

Constraints

KaTeX parse error: Expected 'EOF', got '&' at position 9: 0 \le X &̲lt; 100
$X$ is given to the third decimal place.

Input

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

$X$

Output

Output the answer.

Sample Input 1

1.012

Sample Output 1

1.012

1.012 can be printed as it is.

Sample Input 2

12.340

Sample Output 2

12.34

Printing 12.340 without the trailing 0 results in 12.34.

Sample Input 3

99.900

Sample Output 3

99.9

Printing 99.900 without the trailing 0s results in 99.9.

Sample Input 4

0.000

Sample Output 4

0

Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing 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;while (s.size() && s.back() == '0') s.pop_back();if (s.back() == '.') s.pop_back();cout << s << endl;return 0;
}

C - Enumerate Sequences

Problem Statement

Print all integer sequences of length $N$ that satisfy the following conditions, in ascending lexicographical order.
The $i$-th element is between $1$ and $R_i$, inclusive.
The sum of all elements is a multiple of $K$.

1. $|A|<|B|$ and $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$. There exists an integer $1\leq i\leq \min\{|A|,|B|\}$ such that both of the following are true: $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$ $A_i < B_i$

All input values are integers.
$1\le N\le 8$
$2\le K\le 10$
$1\le R_i\le 5$

Input

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

$N$ $K$
$R_1$ $R_2$ $\dots$ $R_N$

Output

Print the answer in the following format, where $X$ is the number of sequences to print, the $i$-th of which is $A_i=(A_{i,1},A_{i,2},\dots ,A_{i,N})$:

$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,N}$
$⋮$
$A_{X,1}$ $A_{X,2}$ $\dots$ $A_{X,N}$

Sample Input 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are $(1,1,2),(2,1,1),(2,1,3)$ in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

There may be no sequences to print.

In this case, the output can be empty.

Sample Input 3

5 5
2 3 2 3 2

Sample Output 3

1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;int n, k;
int r[10], a[10];void dfs(int u) {if (u > n) {int tot = 0;for (int i = 1; i <= n; i ++)tot += a[i];if (tot % k == 0) {for (int i = 1; i <= n; i ++) cout << a[i] << " ";cout << endl;}return;}for (int i = 1; i <= r[u]; i ++)a[u] = i, dfs(u + 1);
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> n >> k;for (int i = 1; i <= n; i ++)cin >> r[i];dfs(1);return 0;
}

D - Pedometer

Problem Statement

There are $N$ rest areas around a lake.

The rest areas are numbered $1$, $2$, …, $N$ in clockwise order.

It takes $A_i$ steps to walk clockwise from rest area $i$ to rest area $i+1$ (where rest area $N+1$ refers to rest area $1$).

The minimum number of steps required to walk clockwise from rest area $s$ to rest area $t$ ($s\ne t$) is a multiple of $M$.

Find the number of possible pairs $(s,t)$.

Constraints

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

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 as an integer.

Sample Input 1

4 3
2 1 4 3

Sample Output 1

4

The minimum number of steps to walk clockwise from rest area $1$ to rest area $2$ is $2$, which is not a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $1$ to rest area $3$ is $3$, which is a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $1$ to rest area $4$ is $7$, which is not a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $2$ to rest area $3$ is $1$, which is not a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $2$ to rest area $4$ is $5$, which is not a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $2$ to rest area $1$ is $8$, which is not a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $3$ to rest area $4$ is $4$, which is not a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $3$ to rest area $1$ is $7$, which is not a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $3$ to rest area $2$ is $9$, which is a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $4$ to rest area $1$ is $3$, which is a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $4$ to rest area $2$ is $5$, which is not a multiple of $3$.
The minimum number of steps to walk clockwise from rest area $4$ to rest area $3$ is $6$, which is a multiple of $3$.
Therefore, there are four possible pairs $(s,t)$.

Sample Input 2

2 1000000
1 1

Sample Output 2

0

Sample Input 3

9 5
9 9 8 2 4 4 3 5 3

Sample Output 3

11

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 2e5 + 10;int n, m;
int a[N * 2];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], a[i + n] = a[i];for (int i = 1; i <= 2 * n; i ++) (a[i] += a[i - 1]) %= m;unordered_map<int, int> cnt;int res = 0;for (int i = 2; i <= n; i ++) cnt[a[i]] ++;for (int i = n + 1; i <= 2 * n; i ++) {res += cnt[a[i]], cnt[a[i]] ++;if (i > n) cnt[a[i - n + 1]] --;}cout << res << endl;return 0;
}

E - Permute K times

Problem Statement

You are given a sequence $X$ of length $N$ where each element is between $1$ and $N$, inclusive, and a sequence $A$ of length $N$.

Print the result of performing the following operation $K$ times on $A$.
Replace $A$ with $B$ such that $B_i=A_{X_i}$.

Constraints

All input values are integers.
$1\le N\le 2\times 10^5$
$0\le K\le 10^{18}$
$1\le X_i\le N$
$1\le A_i\le 2\times 10^5$

Input

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

$N$ $K$
$X_1$ $X_2$ $\dots$ $X_N$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Let $A^{\prime }$ be the sequence $A$ after the operations. Print it in the following format:

$A_1^{\prime }$ $A_2^{\prime }$ $\dots$ $A_N^{\prime }$

Sample Input 1

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

Sample Output 1

7 2 3 5 1 9 3

In this input, $X=(5,2,6,3,1,4,6)$ and the initial sequence is $A=(1,2,3,5,7,9,11)$.
After one operation, the sequence is $(7,2,9,3,1,5,9)$.
After two operations, the sequence is $(1,2,5,9,7,3,5)$.
After three operations, the sequence is $(7,2,3,5,1,9,3)$.

Sample Input 2

4 0
3 4 1 2
4 3 2 1

Sample Output 2

4 3 2 1

There may be cases where no operations are performed.

Sample Input 3

9 1000000000000000000
3 7 8 5 9 3 7 4 2
9 9 8 2 4 4 3 5 3

Sample Output 3

3 3 3 3 3 3 3 3 3

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 2e5 + 10;int n, k;
int to[N][62], a[N];signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> n >> k;for (int i = 1; i <= n; i ++)cin >> to[i][0];for (int i = 1; i <= n; i ++)cin >> a[i];for (int j = 1; j < 62; j ++)for (int i = 1; i <= n; i ++)to[i][j] = to[to[i][j - 1]][j - 1];for (int i = 1; i <= n; i ++) {int p = i;for (int j = 61; j >= 0; j --)if (k >> j & 1) p = to[p][j];cout << a[p] << " ";}cout<< endl;return 0;
}

F - Rearrange Query

Problem Statement

You are given sequences of positive integers of length $N$: $A=(A_1,A_2,\dots ,A_N)$ and $B=(B_1,B_2,\dots ,B_N)$.
You are given $Q$ queries to process in order. The $i$-th query is explained below.
You are given positive integers $l_i,r_i,L_i,R_i$. Print Yes if it is possible to rearrange the subsequence $(A_{l_i},A_{l_i+1},\dots ,A_{r_i})$ to match the subsequence $(B_{L_i},B_{L_i+1},\dots ,B_{R_i})$, and No otherwise.

Constraints

$ 1\leq N,Q\leq 2\times 10^5$
$ 1\leq A_i,B_i\leq N$
$ 1\leq l_i \leq r_i\leq N$
$ 1\leq L_i \leq R_i\leq N$
All input values are integers.

Input

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

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$
$l_1$ $r_1$ $L_1$ $R_1$
$l_2$ $r_2$ $L_2$ $R_2$
$⋮$
$l_Q$ $r_Q$ $L_Q$ $R_Q$

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

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

Sample Output 1

Yes
No
No
Yes

For the 1st query, it is possible to rearrange $(1,2,3)$ to match $(2,3,1)$. Hence, we print Yes.
For the 2nd query, it is impossible to rearrange $(1,2)$ in any way to match $(1,4,2)$. Hence, we print No.
For the 3rd query, it is impossible to rearrange $(1,2,3,2)$ in any way to match $(3,1,4,2)$. Hence, we print No.
For the 4th query, it is possible to rearrange $(1,2,3,2,4)$ to match $(2,3,1,4,2)$. Hence, we print Yes.

Sample Input 2

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

Sample Output 2

Yes
Yes
No
No

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;
const int N = 2e5 + 10;int n, q, len;
int a[N], b[N], len1[N], len2[N];
pair<ull, ull> res1[N], res2[N];
ull hsh1, hsh2;
struct Query {int id, l, r;bool operator< (const Query &tmp)const {if (l / len == tmp.l / len) return r < tmp.r;return l / len < tmp.l / len;}
}qry1[N], qry2[N];ull h(ull x) {return (ull)x * x * x * 1237123 + 19260817;
}
ull f(int x) {ull cur = h(x & ((1ll << 31) - 1)) + h(x >> 31);return cur;
}
ull h2(ull x) {return (ull)x * x * 1145141 + 998244353;
}
ull f2(int x) {ull cur = h2(x & ((1ll << 27) - 1)) + h2(x >> 27);return cur;
}
void add1(int po) {int x = a[po];hsh1 += f(x), hsh2 += f2(x);
}
void del1(int po) {int x = a[po];hsh1 -= f(x), hsh2 -= f2(x);
}
void add2(int po) {int x = b[po];hsh1 += f(x), hsh2 += f2(x);
}
void del2(int po) {int x = b[po];hsh1 -= f(x), hsh2 -= f2(x);
}int main() {cin >> n >> q;for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)cin >> b[i];len = max(sqrt((double)n * n / q), 1.0);for (int i = 1; i <= q; i ++) {int l1, r1, l2, r2;cin >> l1 >> r1 >> l2 >> r2;qry1[i] = {i, l1, r1}, qry2[i] = {i, l2, r2};len1[i] = r1 - l1 + 1, len2[i] = r2 - l2 + 1;}sort(qry1 + 1, qry1 + 1 + q);sort(qry2 + 1, qry2 + 1 + q);for (int i = 1, l = 1, r = 0; i <= q; i ++) {int lo = qry1[i].l, ro = qry1[i].r, id = qry1[i].id;while (l > lo) add1( -- l);while (l < lo) del1(l ++);while (r > ro) del1(r --);while (r < ro) add1( ++ r);res1[id] = make_pair(hsh1, hsh2);}hsh1 = hsh2 = 0;for (int i = 1, l = 1, r = 0; i <= q; i ++) {int lo = qry2[i].l, ro = qry2[i].r, id = qry2[i].id;while (l > lo) add2( -- l);while (l < lo) del2(l ++);while (r > ro) del2(r --);while (r < ro) add2( ++ r);res2[id] = make_pair(hsh1, hsh2);}for (int i = 1; i <= q; i ++) {if (res1[i] == res2[i] && len1[i] == len2[i]) cout << "Yes" << endl;else cout << "No" << endl;}
}

视频题解

最后祝大家早日