用户工具

站点工具


2020-2021:teams:hotpot:abc174

Atcoder Beginner Contest 174

A - Air Conditioner

题目大意

给出一个$X$,问$X$是否大于等于30

数据范围

$-40 \le X \le 40$

解题思路

直接一个if

B - Distance

题目大意

给出$N$个点的坐标和$D$,问有几个点和原点的距离小于等于$D$

数据范围

$1 \le N \le 2 \times 10^5$,$0 \le D \le 2 \times 10^5$

解题思路

直接$O(n)$模拟求解

C - Repsept

题目大意

给出$K$,问数列7、77、777…中第几是$K$的倍数,或者根本没有$K$的倍数

数据范围

$1 \le K \le 10^6$

解题思路

首先用欧拉定理可以证明如果$K$不是2和5的倍数就一定有解,然后直接枚举即可,解一定不会超过$K$很多

D - Alter Altar

题目大意

给出一串珠子,它们要么是白色要么是红色,现在可以把其中一个珠子换成另一种颜色或交换两个珠子,问最少需要多少步使这一串珠子不会出现一个红色珠子的左边是一个白色的珠子的情况

数据范围

$2 \le N \le 2 \times 10^5$

解题思路

贪心地想,每次把最左边的白色和最右边的红色交换即可

E - Logs

题目大意

给出$N$块圆木,每块有$A_i$的长度,最多切$K$刀,最小化剩下的圆木里的最大长度

数据范围

$1 \le N \le 2 \times 10^5$,$0 \le K \le 10^9$,$1 \le A_i \le 10^9$

解题思路

二分答案以后$O(n)$判断即可,时间复杂度$O(n \log n)$

F - Range Set Query

题目大意

给出$N$个数和$Q$个询问,每次询问区间$[l_i,r_i]$中有多少种不同的数

数据范围

$1 \le N,Q \le 5 \times 10^5$,所有数$\le 5 \times 10^5$

解题思路

经典莫队算法即可,也可以用树状数组维护每种数最后一个出现的位置然后求区间和

2020-2021/teams/hotpot/abc174.txt · 最后更改: 2020/08/07 15:54 由 misakatao