mengbierr

一个蒟蒻的博客

6月12

BZOJ3837: [Pa2013]Filary

当把距离取2时,一定能够选出n/2以上个数,所以随机一个位置有1/2概率在最优解里。
于是随机一个位置,计算取不同距离下的答案。
枚举每个位置,如果相同则一定有贡献,否则将这两个数做差,则距离取差的所有因数都会有贡献,将这些因数的答案+1即可。
多随机几次,每次有1/2概率得到正确答案,正确率1-(1/2)^k.

发表评论

电子邮件地址不会被公开。 必填项已用*标注