1 条题解
-
0
题目分析
由于 ,因此 的范围就是 ,即 。直接枚举 的话,时间复杂度是 。
20pts
对于的数据,我们可以直接枚举 ,时间复杂度是 。
100pts
注意到当 时,,因此我们先枚举 ,把 , 的 全部找出来。这里的时间复杂度为 ,我们可以将所有的 存储在一个 vector 中,然后对该 vector 进行排序并去重,得到这部分 的数量。
接下来考虑剩下的 且 的 的数量。
一个比较直观的想法是认为这部分的数量为 。但容易发现会有重复计算的情况:如果 ,其中 ,那么 ,这个数实际上已经在上面计算的 的部分中出现过。
因此,我们需要去掉重复的部分。考虑怎样的 是重复的,即存在 ,且 (其中 ),容易发现这些重复的 都在我们之前枚举计算的范围内,即这些数已经出现在 vector 中。
因此,我们可以计算 ,再减去在 vector 中出现过的 的数。通过二分查找找到对应的下标相减即可得到重复的数量。
- 1
信息
- ID
- 119
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者