#创作计划# 猎奇

复仇者_帅童

2025-09-07 14:43:51

发布于：广东

71阅读

0回复

0点赞

在“忠诚”这题中，我使用了乱搞解法，因为数据水通过了。

做法如下：

将 $A$ 数组从大到小排序，并且记录每个数原来的下标。
查询时，将 $A$ 数组从头到尾遍历一遍，找到第一个原来的下标在询问区间内的数，并输出它。

这么猎奇的做法为什么能过呢？原来它在随机数据（ $A_i$ ，查询区间的左、右端点均随机生成）下，时间复杂度期望 $O(q\log n)$ ！接下来，我要证明这个结论：

由于随机生成，所以排序后原来的下标也是随机的。这就相当于在数组中随机撒点，看看哪个点最先落在区间上。显然，如果长度为 $l$ ，每次撒点撒中的概率为 $\frac{l}{n}$ ，而有点撒中的期望撒点次数为 $\frac{n}{l}$ 。

那 $l$ 为多少呢？显然它由区间的左右端点决定。注意到区间左右端点是随机的，所以 $l=1$ 的概率约为 $\frac{n}{n^2}$ ， $l=2$ 的概率为 $2\times \frac{n-1}{n^2}$ ， $l=3$ 的概率为 $2\times \frac{n-3}{n^2}$ ，......， $l=n$ 的概率为 $2\times \frac{1}{n^2}$ 。

所以，整体的期望如下：

$\frac{n}{n^2}\times \frac{n}{1}+ 2(\frac{n-1}{n^2}\times \frac{n}{2}+\frac{n-2}{n^2}\times \frac{n}{3}+...+\frac{1}{n^2}\times \frac{n}{n})\\\space\\ \lt2(\frac{n}{n}+\frac{n-1}{2n}+\frac{n-2}{3n}+...+\frac{1}{n^2})\\\space\\ \lt 2(\frac{n}{n}+\frac{n}{2n}+\frac{n}{3n}+...+\frac{n}{n^2})\\\space\\ =2(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})\\\space\\ \lt 2(\frac{1}{1}+\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+...+\frac{1}{2^{\lfloor\log_2 n\rfloor}}+\frac{1}{2^{\lfloor\log_2 n\rfloor}}+...+\frac{1}{2^{\lfloor\log_2 n\rfloor}})\\\space\\ =2(\lfloor \log_2 n\rfloor+1)\\\space\\ =O(\log n)$

所以时间复杂度为 $O(q\log n)$ 。

hack 这个算法的做法也挺简单的，一种做法如下：

将第 $i$ 次询问的区间设置成 $[i,i]$ 即可。

显然无论 $A$ 数组长什么样，这些查询会让该算法分别撒点 $1$ 次， $2$ 次， $3$ 次，......， $n$ 次，时间复杂度退化为 $O(qn)$ 。

有帮助，赞一个

去预览

0/2000

全部评论 9

沈思邈
当然，你这里计算时间复杂度时， $\displaystyle\sum_{i=1}^{n}\dfrac{1}{i}$ 可以近似的看成是 $\ln{n}$ ，再近似成 $\log{n}$

4天前来自上海
0
- 复仇者_帅童
  回复沈思邈
  是的，但是我感觉 $\ln n$ 是约等于不严谨，就写了个一定比他大的式子
  
  4天前来自广东
  0
- 复仇者_帅童
  回复复仇者_帅童
  我这种方法就是拿调和级数是发散的的那个证明改了一下，确定了它的上界
  
  4天前来自广东
  0
XRaiB
真棒

1周前来自广东
0
复仇者_帅童
d

1周前来自广东
0
星梦
n
2

n−1

×
2
n

+
n
2

n−2

×
3
n

+...+
n
2

1

×
n
n

)

1周前来自陕西
0
aaaaaa
zc

2025-09-02 来自广东
0
aaaaaa
d

2025-09-02 来自广东
0
aaaaaa
d

2025-09-02 来自广东
0
复仇者_帅童
此时在由乃救爷爷中亦有记载

2025-09-02 来自广东
0
复仇者_帅童
d

2025-09-02 来自广东
0

全部评论 9

热门讨论