2020 计蒜之道线上决赛 - C. 攀登山峰

本文使用了一种概率算法，不是正解，只求骗分。

题意

原题

给一个长度为n的数组A[1...n]。

现在有q个查询请求（q <= 1e5），每个请求给定一个长度为m的子数组A[i...j]和一个整数t。问在子数组中出现次数超过m/t的数字中（t <= 20），最大的数是多少。

题意中的坑

阈值m / t是一个实数。（题意不明先死个🐴好吗？）

解法

首先我们将每种数字出现的位置简历一个索引，此时对于任意一个数，我们可以用二分法在O(logn)的时间内求出其在某个区间内出现的次数。

因为t最大是20，也就意味着如果我们随机取数，那么取到一个符合出现次数限制的（超过m/t次）数字的概率是1/t。如果我们进行多次尝试，并使用上面的方法对其进行验证，几乎可以保证我们一定可以取到正确的那一个。

那么“多次尝试”是多少次呢？我们枚举所有的t，然后计算其在q=1e5的情况下的成功率。因为这是一个随机算法，我们先使用下面的代码分别计算一下成功率为10%和50%的期望尝试次数。

#coding=utf-8

for i in xrange(1, 21):
    fail = 1 - (1. / i)
    for j in xrange(1, 3000):
        ff = 1 - fail ** j
        if pow(ff, 100000) > 0.1:
            print i, j, pow(ff, 100000)
            break

由上表我们可以知道，对于不同的t，我们可以使用不同的尝试次数以达到预期的胜率。

总的时间复杂度为O(q * logn * attempt)，对于极限数据可能会有超时的风险，所以我们在随机尝试时可以加入些许的优化，例如加上输入输出外挂，以及不计算重复值与小于最大值的值等。剩下的工作就是孜孜不倦的提交，直到获得AC为止。（评测机你辛苦了）

以及，记得加上初始化随机数种子srand(time(NULL));，否则你的随机数每次都一样。。。

实际上总的胜率还是很高的，说明数据并没有达到极限，出题人手下留情做了个人（

代码请见这里

题意

题意中的坑

解法

Comments