RUSH_D_CAT

题解

/ 注册

全部文章 / 题解（共2篇）

题解 | 2024牛客OI赛前集训营-提高组（第五场）

T1 20 pts: 对每组询问，暴力枚举所有区间，计算区间 gcd 的值即可。复杂度 50 pts: 对每组查询，用 ST 表求区间 gcd，枚举左端点，二分右端点即可。复杂度 80 pts: 考虑到数据随机的性质，根据质数的密度，gcd = 1 的区间长度上界是级别的。那我们可以对每个...

2024-10-15

5 98

题解 | 第十二届国防科技大学程序设计竞赛

A. Lines Hint: 按斜率的取值分组，我们只关心每组有多少条直线。 Solution: 用 cnt(k)cnt(k)cnt(k) 表示斜率为 kkk 的直线条数，我们按斜率对直线进行分组。可以发现，考虑 Bob 的最后一步操作：如果存在某个斜率 k′k'k′，有 cnt(k′)cnt(k...

2022-06-04

16 607