蒟蒻来讲题，还望大家喜。若哪有问题，大家尽可提！
Hello, 大家好哇！本初中生蒟蒻讲解一下AtCoder Beginner Contest 297这场比赛的A-E题！
今晚比前面几场要简单点，但我在B题翻了下车，第一次提交竟然WA了，做题要仔细啊。
开心的是，今晚终于进到绿名了！
===========================================================================================
A - Double Click
原题
Problem Statement
Takahashi turned on a computer at time
0
0
0 and clicked the mouse
N
N
N times. The
i
i
i-th
(
1
≤
i
≤
N
)
(1 \le i \le N)
(1≤i≤N) click was at time
T
i
T_i
Ti.
If he consecutively clicked the mouse at time
x
1
x_1
x1 and time
x
2
x_2
x2 (where KaTeX parse error: Expected 'EOF', got '&' at position 5: x_1 &̲lt; x_2), a double click is said to be fired at time
x
2
x_2
x2 if and only if
x
2
−
x
1
≤
D
x_2 - x_1 \le D
x2−x1≤D.
What time was a double click fired for the first time? If no double click was fired, print -1 instead.
Constraints
1
≤
N
≤
100
1 \le N \le 100
1≤N≤100
1
≤
D
≤
1
0
9
1 \le D \le 10^9
1≤D≤109
1
≤
T
i
≤
1
0
9
(
1
≤
i
≤
N
)
1 \le T_i \le 10^9(1 \le i \le N)
1≤Ti≤109(1≤i≤N)
KaTeX parse error: Expected 'EOF', got '&' at position 5: T_i &̲lt; T_{i+1}(1 \…
All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
N
N
D
D
D
T
1
T_1
T1
T
2
T_2
T2
…
\dots
…
T
N
T_N
TN
Output
If at least one double click was fired, print the time of the first such event; otherwise, print -1.
Sample Input 1
4 500
300 900 1300 1700
Sample Output 1
1300
Takahashi clicked the mouse at time
900
900
900 and
1300
1300
1300. Since
1300
−
900
≤
500
1300 - 900 \le 500
1300−900≤500, a double click was fired at time
1300
1300
1300.
A double click had not been fired before time
1300
1300
1300, so
1300
1300
1300 should be printed.
Sample Input 2
5 99
100 200 300 400 500
Sample Output 2
-1
No double click was fired, so print -1.
Sample Input 3
4 500
100 600 1100 1600
Sample Output 3
600
If multiple double clicks were fired, be sure to print only the first such event.
思路
题目简单，不写了
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define endl '\n'
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)
using namespace std;
typedef pair<int, int> PII;
const int N = 1e2 + 10;
int n, d;
int a[N];
inline int read()
{
int w = 1, s = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return w * s;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> d;
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int i = 2; i <= n; i ++)
if (a[i] - a[i - 1] <= d)
{
cout << a[i];
return 0;
}
cout << -1 << endl;
return 0;
}
B - chess960
原题
Problem Statement
Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.You are given a string $S$ of length eight. $S$ has exactly one
K and
Q, and exactly two
R's,
B's , and
N's. Determine if $S$ satisfies all of the following conditions. Suppose that the $x$-th and $y$-th $(x < y)$ characters from the left of $S$ are
B; then, $x$ and $y$ have different parities.
K is between two
R's. More formally, suppose that the $x$-th and $y$-th $(x < y)$ characters from the left of $S$ are
R and the $z$-th is
K; then $x< z < y$. #### Constraints
S
S
S is a string of length
8
8
8 that contains exactly one K and Q, and exactly two R's, B's , and N's.
Input
The input is given from Standard Input in the following format:
S
S
S
Output
Print Yes if
S
S
S satisfies the conditions; print No otherwise.
Sample Input 1
RNBQKBNR
Sample Output 1
Yes
The
3
3
3-rd and
6
6
6-th characters are B, and
3
3
3 and
6
6
6 have different parities.
Also, K is between the two R's. Thus, the conditions are fulfilled.
Sample Input 2
KRRBBNNQ
Sample Output 2
NoK is not between the two R's.
Sample Input 3
BRKRBQNN
Sample Output 3
No
思路
题目简单，但要注意不要理解错题意，下标奇偶性不同是字母B，K是在两个R之间
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define endl '\n'
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)
using namespace std;
typedef pair<int, int> PII;
string s;
vector<int> pl;
inline int read()
{
int w = 1, s = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return w * s;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> s;
int has= 0, k = 0;
for (int i = 0; i < s.size(); i ++)
{
if (s[i] == 'B')
pl.psb(i + 1);
if (s[i] == 'K' && has != 1)
{
cout << "No" << endl;
return 0;
}
if (s[i] == 'R')
has ++;
}
if (pl[0] % 2 != pl[1] % 2)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
C - PC on the Table
原题
Problem Statement
Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.You are given $H$ strings $S_1,S_2,\ldots,S_H$, each of length $W$, consisting of
. and
T. Takahashi may perform the following operation any number of times (possibly zero): Choose integers satisfying $1\leq i \leq H$ and $1 \leq j \leq W-1$ such that the $j$-th and $(j+1)$-th characters of $S_i$ are both
T. Replace the $j$-th character of $S_i$ with
P, and $(j+1)$-th with
C. He tries to maximize the number of times he performs the operation. Find possible resulting $S_1,S_2,\ldots,S_H$. #### Constraints
1
≤
H
≤
100
1\leq H \leq 100
1≤H≤100
2
≤
W
≤
100
2\leq W \leq 100
2≤W≤100
H
H
H and
W
W
W are integers.
S
i
S_i
Si is a string of length
W
W
W consisting of . and T.
Input
The input is given from Standard Input in the following format:
H
H
H
W
W
W
S
1
S_1
S1
S
2
S_2
S2
⋮
\vdots
⋮
S
H
S_H
SH
Output
Print a sequence of strings,
S
1
,
S
2
,
…
,
S
H
S_1,S_2,\ldots,S_H
S1,S2,…,SH, separated by newlines, possibly resulting from maximizing the number of times he performs the operation.
If multiple solutions exist, print any of them.
Sample Input 1
2 3
TTT
T.T
Sample Output 1
PCT
T.T
He can perform the operation at most once.
For example, an operation with
(
i
,
j
)
=
(
1
,
1
)
(i,j)=(1,1)
(i,j)=(1,1) makes
S
1
S_1
S1 PCT.
Sample Input 2
3 5
TTT…
.TTT.
TTTTT
Sample Output 2
PCT…
.PCT.
PCTPC
思路
找相邻的T更改为PC即可！
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define endl '\n'
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)
using namespace std;
typedef pair<int, int> PII;
const int N = 1e2 + 10;
int r, c;
char a[N][N];
inline int read()
{
int w = 1, s = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return w * s;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> r >> c;
for (int i = 1; i <= r; i ++)
for (int j = 1; j <= c; j ++)
cin >> a[i][j];
for (int i = 1; i <= r; i ++)
for (int j = 1; j < c; j ++)
if (a[i][j] == 'T' && a[i][j] == a[i][j + 1])
{
a[i][j] = 'P';
a[i][j + 1] = 'C';
j ++;
}
for (int i = 1; i <= r; i ++)
{
for (int j = 1; j <= c; j ++)
cout << a[i][j];
cout << endl;
}
return 0;
}
D - Count Subtractions
原题
Problem Statement
You are given positive integers
A
A
A and
B
B
B.
You will repeat the following operation until
A
=
B
A=B
A=B:
compare
A
A
A and
B
B
B to perform one of the following two:
if KaTeX parse error: Expected 'EOF', got '&' at position 3: A &̲gt; B, replace
A
A
A with
A
−
B
A-B
A−B;
if KaTeX parse error: Expected 'EOF', got '&' at position 3: A &̲lt; B, replace
B
B
B with
B
−
A
B-A
B−A.
How many times will you repeat it until
A
=
B
A=B
A=B? It is guaranteed that a finite repetition makes
A
=
B
A=B
A=B.
Constraints
1
≤
A
,
B
≤
1
0
18
1 \le A,B \le 10^{18}
1≤A,B≤1018
All values in the input are integers.
Input
The input is given from Standard Input in the following format:
A
A
A
B
B
B
Output
Print the answer.
Sample Input 1
3 8
Sample Output 1
4
Initially,
A
=
3
A=3
A=3 and
B
=
8
B=8
B=8. You repeat the operation as follows:
KaTeX parse error: Expected 'EOF', got '&' at position 2: A&̲lt;B, so replace
B
B
B with
B
−
A
=
5
B-A=5
B−A=5, making
A
=
3
A=3
A=3 and
B
=
5
B=5
B=5.
KaTeX parse error: Expected 'EOF', got '&' at position 2: A&̲lt;B, so replace
B
B
B with
B
−
A
=
2
B-A=2
B−A=2, making
A
=
3
A=3
A=3 and
B
=
2
B=2
B=2.
KaTeX parse error: Expected 'EOF', got '&' at position 2: A&̲gt;B, so replace
A
A
A with
A
−
B
=
1
A-B=1
A−B=1, making
A
=
1
A=1
A=1 and
B
=
2
B=2
B=2.
KaTeX parse error: Expected 'EOF', got '&' at position 2: A&̲lt;B, so replace
B
B
B with
B
−
A
=
1
B-A=1
B−A=1, making
A
=
1
A=1
A=1 and
B
=
1
B=1
B=1.
Thus, you repeat it four times.
Sample Input 2
1234567890 1234567890
Sample Output 2
0
Note that the input may not fit into a 32-bit integer type.
Sample Input 3
1597 987
Sample Output 3
15
题意
A和B两个数，每次操作将大数变成大数减小数的差值，直到A和B相等时停止，问一共需要操作多少次？
思路
对于A和B，因为最终A==B，所以操作过程中，谁是A，谁是B并不重要。我们不妨设A始终大于B，即把大数给A，那么会出现以下情况：
设cnt=0，用来记录操作数。
情况1：如果A=B，直接输出cnt；
情况2：如果A能整除B，那么cnt+=A/B，输出cnt；
情况3：如果A不能整除B，那么cnt+=A/B，A=A%B；
此时重新回到开始，比较新的A和B，让A是大数，B是小数，再判断以上三种情况。
本题比较简单，如果有兴趣，可以做一下AtCoder Regular Contest 159的B题，难度比这个题目高不少，但作法类似。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
#define endl '\n'
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)
using namespace std;
typedef pair<int, int> PII;
int a, b;
inline int read()
{
int w = 1, s = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return w * s;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> a >> b;
int cnt = 0;
while (1)
if (a == b)
{
cout << cnt << endl;
return 0;
}
else if (a < b)
swap(a, b);
else
{
if (a % b == 0)
{
cnt += a / b - 1;
cout << cnt << endl;
return 0;
}
else
{
cnt += a / b;
a = a % b;
}
}
return 0;
}
E - Kth Takoyaki Set
原题
Problem Statement
In AtCoder Kingdom,
N
N
N kinds of takoyakis (ball-shaped Japanese food) are sold. A takoyaki of the
i
i
i-th kind is sold for
A
i
A_i
Ai yen.
Takahashi will buy at least one takoyaki in total. He is allowed to buy multiple takoyakis of the same kind.
Find the
K
K
K-th lowest price that Takahashi may pay. Here, if there are multiple sets of takoyakis that cost the same price, the price is counted only once.
Constraints
1
≤
N
≤
10
1 \le N \le 10
1≤N≤10
1
≤
K
≤
2
×
1
0
5
1 \le K \le 2 \times 10^5
1≤K≤2×105
1
≤
A
i
≤
1
0
9
1 \le A_i \le 10^9
1≤Ai≤109
All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
N
N
K
K
K
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
4 6
20 25 30 100
Sample Output 1
50
The four kinds of takoyakis sold in AtCoder Kingdom cost
20
20
20 yen,
25
25
25 yen,
30
30
30 yen, and
100
100
100 yen.
The six lowest prices that Takahashi may pay are
20
20
20 yen,
25
25
25 yen,
30
30
30 yen,
40
40
40 yen,
45
45
45 yen, and
50
50
50 yen. Thus, the answer is
50
50
50.
Note that at least one takoyaki must be bought.
Sample Input 2
2 10
2 1
Sample Output 2
10
Note that a price is not counted more than once even if there are multiple sets of takoyakis costing that price.
Sample Input 3
10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872
Sample Output 3
5705443819
题意
给定一个N个元素的整数序列a，序列中元素任意组合（同一元素可以多次）的和，判断第K小的和是多少。
如样例1：
a={20,25,30,100}
那么最小的数是20，其次依次是25、30、40（20+20）、45（20+25）、50（20+30 或者 25+25）、55（25+20）、60（30+30）……
所以K=6时，第6小的是50。
思路
这个题目可以这样理解，以样例1为例，最小的数是直接可以知道的，即20，那么从20往后，每次都是用当前数加一遍序列里的所有数，然后把当前数抛掉，再找下一个最小数，这个最小数再把序列里的所有数加一遍，再重复，直到第K个数，用个数轴来表示更清晰一点：
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#define endl '\n'
#define int long long
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)
using namespace std;
typedef pair<int, int> PII;
const int N = 15;
int n, k;
int a[N];
set<int> s;
inline int read()
{
int w = 1, s = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return w * s;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> a[i];
s.insert(0);
int cnt = 0;
while (cnt < k)
{
for (int i = 1; i <= n; i ++)
s.insert(*s.cbegin() + a[i]);
s.erase(*s.cbegin());
cnt ++;
}
cout << *s.cbegin() << endl;
return 0;
}
今天就到这里了！
大家有什么问题尽管提，我都会尽力回答的！文章来源：https://www.toymoban.com/news/detail-438231.html
吾欲您伸手，点的小赞赞。吾欲您喜欢，点得小关注！文章来源地址https://www.toymoban.com/news/detail-438231.html
到了这里，关于AtCoder Beginner Contest 297——A-E题讲解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
