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 311 C - E题讲解

    Problem Statement There is a directed graph with N N N vertices and N N N edges. The i i i -th edge goes from vertex i i i to vertex A i A_i A i ​ . (The constraints guarantee that i ≠ A i i neq A_i i  = A i ​ .) Find a directed cycle without the same vertex appearing multiple times. It can be shown that a solution exists under the constraints of t

    2024年02月15日
    浏览(30)
  • 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日
    浏览(30)
  • AtCoder Beginner Contest 310

    感觉F又双叒叕写复杂了 点杯咖啡,要 (p) 元,但可以用一个优惠券,使得咖啡只要 (q) 元,但你需要额外购买 (n) 个商品中(价格为 (a_i) )的一个。 问点杯咖啡的最小价格。 考虑直接买还是使用优惠券,使用优惠券的话就选 (n) 个商品中价格最小的。 两种情况取最小

    2024年02月16日
    浏览(28)
  • AtCoder Beginner Contest 320

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

    2024年02月08日
    浏览(38)
  • AtCoder Beginner Contest 348

    给定 (n) ,输出 (ooxooxoox...) ,长度为 (n) 。 按题意模拟即可。 神奇的代码 给定 (n) 个点,对每个点,求出与其距离最远的点的下标。 (n) 只有 (100) ,对于每个点,花 (O(n)) 遍历每个点最大化距离,时间复杂度为 (O(n^2)) 。 神奇的代码 (n) 个豌豆,每个豌豆有美味值

    2024年04月08日
    浏览(42)
  • AtCoder Beginner Contest 314

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

    2024年02月13日
    浏览(40)
  • AtCoder Beginner Contest 335

    给定一个字符串,将最后一位改成 4 。 模拟即可。 神奇的代码 给定 (n) ,按字典序输出非负整数 (i,j,k) ,使得 (i+j+kleq n) (n) 只有 (21) ,直接 (O(n^3)) 枚举判断即可。 神奇的代码 二维网格,贪吃蛇,移动,进行 (q) 次操作,分两种 指定贪吃蛇下一步移动的方向 指定

    2024年01月19日
    浏览(32)
  • AtCoder Beginner Contest 322

    给定一个字符串,找到最先出现 ABC 的位置。 直接查找判断即可。 神奇的代码 给定字符串 s 和 t ,问 s 是不是 t 的前缀和后缀。 根据前后缀定义判断即可。这里试了下 python 神奇的代码 (n) 天,有 (m) 天会放烟花。 问每一天,距离未来最近的放烟花的天数。 两个双指针一

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

    给定 (n) 个学生的分数,以及及格分 (x) ,问多少人及格了。 依次判断即可。 神奇的代码 回答 (n) 个问题,每个问题给定 (a,l,r) ,问函数 (f(x) = |x - a|) 在 ([l,r]) 的最小值。 全定义域下,最小值显然在 (x=a) 取得。绝对值函数图像是 (V) 型。 现在限定在 ([l,r]) ,则

    2024年02月05日
    浏览(116)
  • AtCoder Beginner Contest 318

    咕咕咕,总力战还没打,凹不过卷狗,躺了.jpg 给定 (n, m, p) ,问有多少个 (i) 满足 (0 m+pi leq n) 减去初始的 (m) ,剩下的就是看 (p) 的倍数个数。 神奇的代码 一个二维空间,有 (n) 个矩形覆盖。 问有多大的空间被覆盖了。重复覆盖算一次。 空间大小只有 (100) ,矩形

    2024年02月10日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包