Atcoder Beginner Contest 304——A-D题讲解

这篇具有很好参考价值的文章主要介绍了Atcoder Beginner Contest 304——A-D题讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提!

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 2N100
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=jSi=Sj
0 ≤ A i ≤ 1 0 9 0 \leq A_i \leq 10^9 0Ai109
A i A_i Ai is an integer.
i ≠ j    ⟹    A i ≠ A j i \neq j \implies A_i \neq A_j i=jAi=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

题目翻译

本题的意思为从年龄最低的那个人开始按顺时针方向输出人名。


思路

  1. 找到年龄最低的人
  2. 顺时针输出人名

代码

#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 1031, 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 1041, 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 1051, 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 1061, 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 1071, 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 1081, 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 1091, 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 1091, 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 1081 (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 1031,则按原样打印 N N N

  • 如果 N N N 1 0 3 10^3 103 1 0 4 − 1 10^4-1 1041之间(包括 1 0 3 10^3 103 1 0 4 − 1 10^4-1 1041),则截断 N N N的个位并打印结果。

  • 如果 N N N 1 0 4 10^4 104 1 0 5 − 1 10^5-1 1051之间(包括10^4 和 1 0 5 − 1 和10^5-1 1051),则截断 N N N的十位及其以下的所有数字,并打印结果。

  • 如果 N N N 1 0 5 10^5 105 1 0 6 − 1 10^6-1 1061之间(包括 N N N),则截断 N N N的百位及其以下的所有位并打印结果。

  • 如果 N N N 1 0 6 10^6 106 1 0 7 − 1 10^7-1 1071之间(包括 1 0 7 − 1 10^7-1 1071),则截断 N N N的千位及其以下的所有数字并打印结果。

  • 如果 N N N 1 0 7 10^7 107 1 0 8 − 1 10^8-1 1081之间(包括 1 0 8 − 1 10^8-1 1081),则截断 N N N的万位及其以下的所有数字并打印结果。

  • 如果 N N N 1 0 8 10^8 108 1 0 9 − 1 10^9-1 1091之间(包括 1 0 9 − 1 10^9-1 1091),则截断 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} (a1b1)2+(a2b2)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 1N,D2000
− 1000 ≤ X i , Y i ≤ 1000 -1000 \leq X_i, Y_i \leq 1000 1000Xi,Yi1000
( 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):0xW,0yH}.
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 3W,H109
1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1N2×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 1A,B2×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.


思路

草莓会被分成如图的几块区域,如图:
Atcoder Beginner Contest 304——A-D题讲解
我们想要统计处最多的与最少的,可以对于每一个点,找与他相邻的边并把个数加1。

Atcoder Beginner Contest 304——A-D题讲解
之后我们枚举有点的边得组合,找最大值与最小值。其中最小值需特判,如果 有点的边得组合数 < ( 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

到了这里,关于Atcoder Beginner Contest 304——A-D题讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AtCoder Beginner Contest 297——A-E题讲解

    蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提! Hello, 大家好哇!本 初中生蒟蒻 讲解一下 AtCoder Beginner Contest 297 这场比赛的 A-E题 ! 今晚比前面几场要简单点,但我在B题翻了下车,第一次提交竟然WA了,做题要仔细啊。 开心的是,今晚终于进到绿名了! ===============

    2024年02月03日
    浏览(38)
  • AtCoder Beginner Contest 314(A~D题 + G题)讲解

    Problem Statement The number pi to the 100 100 100 -th decimal place is 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 . You are given an integer N N N between 1 1 1 and 100 100 100 , inclusive. Print the value of pi to the N N N -th decimal place. More precisely, truncate the value of pi to N N N decim

    2024年02月13日
    浏览(27)
  • AtCoder Beginner Contest 320

    给定 (a,b) ,输出 (a^b + b^a) 。 因为数不超过 (10) ,可以直接用 pow 计算然后转成 (int) 。不会有精度损失。 神奇的代码 给定一个字符串 (s) ,求长度最长的回文串。 因为长度只有 (100) ,可以直接枚举子串,然后暴力判断是不是回文串(翻转后是否和自身相同),复杂

    2024年02月08日
    浏览(34)
  • AtCoder Beginner Contest 327

    2023.11.08 update: 更新了G 给定一个字符串 (s) ,问是否包含 ab 或 ba 。 遍历判断即可。 神奇的代码 给定 (b) ,问是否存在 (a) 使得 (a^a = b) 。 由于指数爆炸的缘故, (a) 的范围不会很大,枚举 (a) ,看 (b % a) 是否为 (0) ,然后用 (b) 不断除以 (a) ,看最后除的次数是

    2024年02月06日
    浏览(44)
  • AtCoder Beginner Contest 314

    怎么好多陌生单词 审核怎么这么逆天,半小时还没审完 给定 (pi) 的值以及数 (n) ,要求保留 (n) 位小数输出,不四舍五入。 字符串形式储存然后截取末尾即可。 神奇的代码 (n) 个人玩轮盘赌游戏,简单说就是一个转盘有 (37) 个数字以及一个箭头,箭头会等概率停在某

    2024年02月13日
    浏览(36)
  • AtCoder Beginner Contest 326

    100楼层,一次可以上最多两层,或下最多三层。 给定两楼层,问能否一次到达。 比较大小,然后判断其差是是不是在 (2) 或 (3) 内即可。 神奇的代码 给定一个 (n) ,问不小于 (n) 的形如 (326) 的数字是多少。 形如 (326) 的数字,即数位有 (3) ,且百位 (times) 十位

    2024年02月08日
    浏览(33)
  • AtCoder Beginner Contest 302

    给定怪物的血量 (a) 和你每次攻击扣除的血量 (b) ,问打多少次怪物才会死。 答案即为 (lceil frac{a}{b} rceil = lfloor frac{a + b - 1}{b} rfloor) 神奇的代码 给定一个二维网格,格子上有字母,找到一连串位置,使得其字符串为 (snuke) ,要求这一连串位置俩俩相邻,即有共边或

    2024年02月05日
    浏览(69)
  • AtCoder Beginner Contest 305

    给定一个数字 (x) ,输出一个数字,它是最接近 (x) 的 (5) 的倍数。 令 (y = x % 5) ,如果 (y leq 2) ,那答案就是 (x - y) ,否则就是 (x + 5 - y) 。 神奇的代码 给定 (ABCDEFG) 的相邻距离,给定两个字母,问它们的距离。 累加距离即可。 神奇的代码 二维平面,有一个矩形

    2024年02月08日
    浏览(52)
  • AtCoder Beginner Contest 341

    给定 (n) ,输出 (n) 个 (0) 和 (n+1) 个 (1) 交替的字符串。 (101010...) 循环输出即可。 神奇的代码 货币兑换。 (A) 国货币每 (x_a) 钱可兑换 (B) 国货币 (y_a) 钱。 (B) 国货币每 (x_b) 钱可兑换 (C) 国货币 (y_b) 钱。 ... 给定你拥有的每国货币钱数和兑换规则,依次兑换

    2024年02月19日
    浏览(25)
  • AtCoder Beginner Contest 328

    给定 (n) 个数字和一个数 (x) 。 问不大于 (x) 的数的和。 按找要求累计符合条件的数的和即可。 神奇的代码 给定一年的月数和一个月的天数。 问有多少对 ((i,j)) ,表示第 (i) 个月的第 (j) 日, (i,j) 的数位上每个数字都是一样的。 范围只有 (O(100^2)) ,枚举所有的

    2024年02月05日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包