蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提!
Hello, 大家好哇!本初中生蒟蒻讲解一下AtCoder Beginner Contest 304这场比赛的A-D题!
===========================================================================================
A - First Player
题目描述
Problem Statement
There are
N
N
N people numbered
1
,
2
,
…
,
N
1, 2, \ldots, N
1,2,…,N, sitting in this clockwise order around a round table.
In particular, person
1
1
1 is sitting next to person
N
N
N in the clockwise direction.
For each
i
=
1
,
2
,
…
,
N
i = 1, 2, \ldots, N
i=1,2,…,N, person
i
i
i has a name
S
i
S_i
Si and an age
A
i
A_i
Ai.
Here, no two people have the same name or the same age.
Starting from the youngest person, print the names of all
N
N
N people in the order of their seating positions in clockwise order.
Constraints
2
≤
N
≤
100
2 \leq N \leq 100
2≤N≤100
N
N
N is an integer.
S
i
S_i
Si is a string of length between
1
1
1 and
10
10
10, consisting of lowercase English letters.
i
≠
j
⟹
S
i
≠
S
j
i \neq j \implies S_i \neq S_j
i=j⟹Si=Sj
0
≤
A
i
≤
1
0
9
0 \leq A_i \leq 10^9
0≤Ai≤109
A
i
A_i
Ai is an integer.
i
≠
j
⟹
A
i
≠
A
j
i \neq j \implies A_i \neq A_j
i=j⟹Ai=Aj
Input
The input is given from Standard Input in the following format:
N
N
N
S
1
S_1
S1
A
1
A_1
A1
S
2
S_2
S2
A
2
A_2
A2
⋮
\vdots
⋮
S
N
S_N
SN
A
N
A_N
AN
Output
Print
N
N
N lines.
For each
i
=
1
,
2
,
…
,
N
i = 1, 2, \ldots, N
i=1,2,…,N, the
i
i
i-th line should contain the name of the person sitting in the
i
i
i-th position clockwise from the youngest person.
Sample Input 1
5
alice 31
bob 41
carol 5
dave 92
ellen 65
Sample Output 1
carol
dave
ellen
alice
bob
The youngest person is person 3 3 3. Therefore, starting from person 3 3 3, print the names in the clockwise order of their seating positions: person 3 3 3, person 4 4 4, person 5 5 5, person 1 1 1, and person 2 2 2.
Sample Input 2
2
takahashi 1000000000
aoki 999999999
Sample Output 2
aoki
takahashi
题目翻译
本题的意思为从年龄最低的那个人开始按顺时针方向输出人名。
思路
- 找到年龄最低的人
- 顺时针输出人名
代码
#include <iostream>
using namespace std;
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
string s[101];
int a[101];
cin >> n;
int mn = 0x3f3f3f3f, pos;
for (int i =1 ;i <= n; i ++)
{
cin >> s[i] >> a[i];
if (a[i] < mn)
mn = a[i], pos = i;
}
for (int i = pos; i <= n; i ++) cout << s[i] << endl;
for (int i = 1; i < pos; i ++) cout << s[i] << endl;
return 0;
}
B - Subscribers
题目描述
Problem Statement
You are given an integer
N
N
N.
Print an approximation of
N
N
N according to the following instructions.
If
N
N
N is less than or equal to
1
0
3
−
1
10^3-1
103−1, print
N
N
N as it is.
If
N
N
N is between
1
0
3
10^3
103 and
1
0
4
−
1
10^4-1
104−1, inclusive, truncate the ones digit of
N
N
N and print the result.
If
N
N
N is between
1
0
4
10^4
104 and
1
0
5
−
1
10^5-1
105−1, inclusive, truncate the tens digit and all digits below it of
N
N
N and print the result.
If
N
N
N is between
1
0
5
10^5
105 and
1
0
6
−
1
10^6-1
106−1, inclusive, truncate the hundreds digit and all digits below it of
N
N
N and print the result.
If
N
N
N is between
1
0
6
10^6
106 and
1
0
7
−
1
10^7-1
107−1, inclusive, truncate the thousands digit and all digits below it of
N
N
N and print the result.
If
N
N
N is between
1
0
7
10^7
107 and
1
0
8
−
1
10^8-1
108−1, inclusive, truncate the ten-thousands digit and all digits below it of
N
N
N and print the result.
If
N
N
N is between
1
0
8
10^8
108 and
1
0
9
−
1
10^9-1
109−1, inclusive, truncate the hundred-thousands digit and all digits below it of
N
N
N and print the result.
Constraints
N N N is an integer between 0 0 0 and 1 0 9 − 1 10^9-1 109−1, inclusive.
Input
The input is given from Standard Input in the following format:
N N N
Output
Print the answer.
Sample Input 1
20230603
Sample Output 1
20200000
20230603
20230603
20230603 is between
1
0
7
10^7
107 and
1
0
8
−
1
10^8-1
108−1 (inclusive).
Therefore, truncate the ten-thousands digit and all digits below it, and print
20200000
20200000
20200000.
Sample Input 2
0
Sample Output 2
0
Sample Input 3
304
Sample Output 3
304
Sample Input 4
500600
Sample Output 4
500000
题目大意
-
如果 N N N小于或等于 1 0 3 − 1 10^3-1 103−1,则按原样打印 N N N。
-
如果 N N N在 1 0 3 10^3 103和 1 0 4 − 1 10^4-1 104−1之间(包括 1 0 3 10^3 103和 1 0 4 − 1 10^4-1 104−1),则截断 N N N的个位并打印结果。
-
如果 N N N在 1 0 4 10^4 104和 1 0 5 − 1 10^5-1 105−1之间(包括10^4 和 1 0 5 − 1 和10^5-1 和105−1),则截断 N N N的十位及其以下的所有数字,并打印结果。
-
如果 N N N在 1 0 5 10^5 105和 1 0 6 − 1 10^6-1 106−1之间(包括 N N N),则截断 N N N的百位及其以下的所有位并打印结果。
-
如果 N N N在 1 0 6 10^6 106和 1 0 7 − 1 10^7-1 107−1之间(包括 1 0 7 − 1 10^7-1 107−1),则截断 N N N的千位及其以下的所有数字并打印结果。
-
如果 N N N在 1 0 7 10^7 107和 1 0 8 − 1 10^8-1 108−1之间(包括 1 0 8 − 1 10^8-1 108−1),则截断 N N N的万位及其以下的所有数字并打印结果。
-
如果 N N N在 1 0 8 10^8 108和 1 0 9 − 1 10^9-1 109−1之间(包括 1 0 9 − 1 10^9-1 109−1),则截断 N N N的十万个数字及其以下的所有数字并打印结果。
思路
通过找规律发现,其实就是输出
N
N
N的前三位,剩余的位全部输出0。
为了方便起见,我们可以用字符串来存储
N
N
N
代码
#include <iostream>
using namespace std;
int main()
{
string s;
cin >> s;
for (int i = 0; i < min((int)s.size(), 3); i ++)
cout << s[i];
for (int i = 3; i < s.size(); i ++)
cout << 0;
}
C - Virus
题目描述
Problem Statement
There are
N
N
N people numbered
1
,
2
,
…
,
N
1, 2, \ldots, N
1,2,…,N on a two-dimensional plane, and person
i
i
i is at the point represented by the coordinates
(
X
i
,
Y
i
)
(X_i,Y_i)
(Xi,Yi).
Person
1
1
1 has been infected with a virus. The virus spreads to people within a distance of
D
D
D from an infected person.
Here, the distance is defined as the Euclidean distance, that is, for two points
(
a
1
,
a
2
)
(a_1, a_2)
(a1,a2) and
(
b
1
,
b
2
)
(b_1, b_2)
(b1,b2), the distance between these two points is
(
a
1
−
b
1
)
2
+
(
a
2
−
b
2
)
2
\sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}
(a1−b1)2+(a2−b2)2.
After a sufficient amount of time has passed, that is, when all people within a distance of
D
D
D from person
i
i
i are infected with the virus if person
i
i
i is infected, determine whether person
i
i
i is infected with the virus for each
i
i
i.
Constraints
1
≤
N
,
D
≤
2000
1 \leq N, D \leq 2000
1≤N,D≤2000
−
1000
≤
X
i
,
Y
i
≤
1000
-1000 \leq X_i, Y_i \leq 1000
−1000≤Xi,Yi≤1000
(
X
i
,
Y
i
)
≠
(
X
j
,
Y
j
)
(X_i, Y_i) \neq (X_j, Y_j)
(Xi,Yi)=(Xj,Yj) if
i
≠
j
i \neq j
i=j.
All input values are integers.
Input
The input is given from Standard Input in the following format:
N N N D D D
X 1 X_1 X1 Y 1 Y_1 Y1
X 2 X_2 X2 Y 2 Y_2 Y2
⋮ \vdots ⋮
X N X_N XN Y N Y_N YN
Output
Print
N
N
N lines. The
i
i
i-th line should contain Yes
if person
i
i
i is infected with the virus, and No
otherwise.
Sample Input 1
4 5
2 -1
3 1
8 8
0 5
Sample Output 1
Yes
Yes
No
Yes
The distance between person
1
1
1 and person
2
2
2 is
5
\sqrt 5
5, so person
2
2
2 gets infected with the virus.
Also, the distance between person
2
2
2 and person
4
4
4 is
5
5
5, so person
4
4
4 gets infected with the virus.
Person
3
3
3 has no one within a distance of
5
5
5, so they will not be infected with the virus.
Sample Input 2
3 1
0 0
-1000 -1000
1000 1000
Sample Output 2
Yes
No
No
Sample Input 3
9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6
Sample Output 3
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
题目翻译
本题的意思就是说第一个人被感染上了传染病(从传染病的角度看,这是传染源 ),后来只要与他相隔的距离小于等于
D
D
D的易感人群,都会被传染,此时这些人就会成为传播途径,再去传染其他人(帮大家复习一下生物,嘿嘿 )
思路
这道题我们可以用bfs,首先队列中有第一个人,之后进行枚举,与他距离小于等于 D D D的人放入队列,同时记录他已被传染。最后输出即可。
详情见代码~~~
代码
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
const int N = 2e3 + 10;
int x[N], y[N];
bool res[N], st[N];
int main()
{
int n, d;
cin >> n >> d;
for (int i = 1; i <= n; i ++)
cin >> x[i] >> y[i];
queue<int> patient;
patient.push(1), res[1] = 1;
while (patient.size())
{
auto t = patient.front();
patient.pop();
if (st[t]) continue;
st[t] = 1;
for (int i = 1; i <= n; i ++)
if (i != t && sqrt(abs(x[t] - x[i]) * abs(x[t] - x[i]) + abs(y[t] - y[i]) * abs(y[t] - y[i])) <= d)
res[i] = 1, patient.push(i);
}
for (int i = 1; i <= n; i ++)
cout << (res[i] ? "Yes" : "No") << endl;
}
D - A Piece of Cake
题目描述
Problem Statement
There is a rectangular cake with some strawberries on the
x
y
xy
xy-plane. The cake occupies the rectangular area
{
(
x
,
y
)
:
0
≤
x
≤
W
,
0
≤
y
≤
H
}
\lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace
{(x,y):0≤x≤W,0≤y≤H}.
There are
N
N
N strawberries on the cake, and the coordinates of the
i
i
i-th strawberry are
(
p
i
,
q
i
)
(p_i, q_i)
(pi,qi) for
i
=
1
,
2
,
…
,
N
i = 1, 2, \ldots, N
i=1,2,…,N. No two strawberries have the same coordinates.
Takahashi will cut the cake into several pieces with a knife, as follows.
First, cut the cake along
A
A
A different lines parallel to the
y
y
y-axis: lines
x
=
a
1
x = a_1
x=a1,
x
=
a
2
x = a_2
x=a2,
…
\ldots
…,
x
=
a
A
x = a_A
x=aA.
Next, cut the cake along
B
B
B different lines parallel to the
x
x
x-axis: lines
y
=
b
1
y = b_1
y=b1,
y
=
b
2
y = b_2
y=b2,
…
\ldots
…,
y
=
b
B
y = b_B
y=bB.
As a result, the cake will be divided into
(
A
+
1
)
(
B
+
1
)
(A+1)(B+1)
(A+1)(B+1) rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.
Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.
Constraints
3
≤
W
,
H
≤
1
0
9
3 \leq W, H \leq 10^9
3≤W,H≤109
1
≤
N
≤
2
×
1
0
5
1 \leq N \leq 2 \times 10^5
1≤N≤2×105
0
<
p
i
<
W
0 \lt p_i \lt W
0<pi<W
0
<
q
i
<
H
0 \lt q_i \lt H
0<qi<H
i
≠
j
⟹
(
p
i
,
q
i
)
≠
(
p
j
,
q
j
)
i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
i=j⟹(pi,qi)=(pj,qj)
1
≤
A
,
B
≤
2
×
1
0
5
1 \leq A, B \leq 2 \times 10^5
1≤A,B≤2×105
0
<
a
1
<
a
2
<
⋯
<
a
A
<
W
0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
0<a1<a2<⋯<aA<W
0
<
b
1
<
b
2
<
⋯
<
b
B
<
H
0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
0<b1<b2<⋯<bB<H
p
i
∉
{
a
1
,
a
2
,
…
,
a
A
}
p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
pi∈{a1,a2,…,aA}
q
i
∉
{
b
1
,
b
2
,
…
,
b
B
}
q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
qi∈{b1,b2,…,bB}
All input values are integers.
Input
The input is given from Standard Input in the following format:
$W$ $H$
$N$
$p_1$ $q_1$
$p_2$ $q_2$
$\vdots$
$p_N$ $q_N$
$A$
$a_1$ $a_2$ $\ldots$ $a_A$
$B$
$b_1$ $b_2$ $\ldots$ $b_B$
Output
Print the minimum possible number of strawberries m m m and the maximum possible number M M M on the chosen piece in the following format, separated by a space.
$m$ $M$
Sample Input 1
7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4
Sample Output 1
0 2
There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is 0 0 0, and the maximum possible number is 2 2 2.
Sample Input 2
4 4
4
1 1
3 1
3 3
1 3
1
2
1
2
Sample Output 2
1 1
Each piece has one strawberry on it.
思路
草莓会被分成如图的几块区域,如图:
我们想要统计处最多的与最少的,可以对于每一个点,找与他相邻的边并把个数加1。
之后我们枚举有点的边得组合,找最大值与最小值。其中最小值需特判,如果
有点的边得组合数
<
(
A
+
1
)
×
(
B
+
1
)
有点的边得组合数<(A+1)\times(B+1)
有点的边得组合数<(A+1)×(B+1)那么就是0。
详情见代码~~~
代码
#include <iostream>
#include <map>
#include <vector>
#define x first
#define y second
#define int long long
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int h, w, m;
int u, v;
int A, B;
int a[N], b[N];
vector<PII> pt;
map<PII, int> area;
signed main()
{
cin >> h >> w >> m;
while (m --)
{
cin >> u >> v;
pt.push_back({u, v});
}
cin >> A;
for (int i = 1; i <= A; i ++)
cin >> a[i];
cin >> B;
for (int j = 1; j <= B; j ++)
cin >> b[j];
for (auto c : pt)
{
int pa = lower_bound(a + 1, a + 1 + A, c.x) - a;
int pb = lower_bound(b + 1, b + 1 + B, c.y) - b;
area[{pa, pb}] ++;
}
int mx = 0, mn = 0x3f3f3f3f, num = 0;
for (auto c : area)
mn = min(mn, c.y), mx = max(mx, c.y), num ++;
if (num < (A + 1) * (B +1))
mn = 0;
cout << mn << " " << mx << endl;
}
大家有什么问题尽管提,我都会尽力回答的!文章来源:https://www.toymoban.com/news/detail-479261.html
吾欲您伸手,点的小赞赞。吾欲您喜欢,点得小关注!文章来源地址https://www.toymoban.com/news/detail-479261.html
到了这里,关于Atcoder Beginner Contest 304——A-D题讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!