概述
- 随机选择通过随机地取总数据的某一部分,来尝试着获取总体数据或总体数据的代表性部分的信息,恰如抽样调查。
例题
CodeChef MSTONE
-
题意:给出落在 \(7\) 条直线上的 \(n\) 个点(有些点可能是交点),求点数最多的那条直线上的点数。
-
数据范围:
-
\(T\leqslant 30\)。
-
\(n\leqslant 10^4\)。
-
\(|x|,|y|\leqslant 1.5\times 10^4\)。
-
\(858ms\) 时限。
-
-
每次随机选两个不同的点(把 \(n=1\) 特判掉),暴力 check 其他点和它们是否共线。注意竖线的 check 方式要特判。
-
单轮正确率 \(\geqslant \dfrac{1}{7^2}\),因为点最多的直线上点较多,被选中的概率较大。
-
那个奇怪的时限算下来是 \(times=286\),恰好是整数。总正确率(考虑了多组数据影响) \(92.07\%\),嗯,大概就是多交几次就够了。
-
官方题解更妙:
-
每次在点池(一开始是所有点)中随一个点,把其他点按照和它连线的斜率排序。
-
从而我们能找到一条过该点的点数最多的直线,在点池中将这条直线上的点全部删去,反复该过程直到点池空了。
-
分类讨论一下。
-
\(n\leqslant 42\):最终答案可能不是某条原始直线。此时直接用我们的随机化,显然正确率不再是问题。
-
\(n>42\):最终答案一定是某条原始直线,该原始直线一定被我们找到,把点池删空的时间复杂度不超过 \(O(n\log n)\)。
-
-
证明一下下面这个结论:
-
如果每次都删一条原始直线,结论显然正确。
-
下面证明删非原始直线对结论没有本质影响。
-
删非原始直线,说明取出的点所在直线点数 \(<7\)。
-
故这样的操作至多进行不到 \(7\times 7=49\) 次。事实上这是个 \(O\),\(\Theta\) 大概就在 \(7\) 左右,复杂度是对的。
-
-
-
-
upd:既然可以排序斜率,自然可以桶排(hash 一下)...至少 \(\dfrac{1}{7}\) 的概率随到的点在答案直线上...于是正确率超高。
CF1114E Arithmetic Progression
-
题意:
-
给定一个打乱的等差数列 \(a_{1\dots n}\)(\(n\) 是给出的),请在不超过 \(60\) 次操作内求出首项和公差(认为公差 \(\geqslant 0\))。
-
操作分为两种:询问 \(a_i\) 和询问是否存在 \(>x\) 的数。
-
-
数据范围:\(2\leqslant n\leqslant 10^6,0\leqslant a_i\leqslant 10^9\)。
-
首先二分把末项求出来,\(30\) 次。
-
然后!随机问 \(30\) 个点,排序,相邻做差,对差求 \(\gcd\)!
-
有极大的概率 \(\gcd\) 就是公差,\(\gcd\) 不是公差的前提是所选各项的项数差的 \(\gcd>1\),我不会算但反正就是很小的一个概率啦。
CF1729E Guess the Cycle Size
-
题意:
-
给定一个大小为 \(n\) 的(简单)环,环上点的编号构成一个 \(1\sim n\) 的排列,请在不超过 \(60\) 次操作内求出环的大小。
-
操作只有一种:询问 \(u,v\) 的距离。
-
如果 \(\max(u,v)>n\),返回 \(-1\)。
-
否则等概率随机返回两条路径中某一条的长度。这里的“任意一条”指的是,对于询问 \((u,v)\),总是取同一条,但可能 \((v,u)\) 对应的是另一条。
-
-
-
数据范围:\(n\leqslant 10^{18}\)。
-
先花点时间算一个 \(n\) 的下界(可能不必要?)。
-
在下界内每次随两个点 \(u,v\),同时询问 \((u,v)\) 和 \((v,u)\)。
-
两者返回同一条路径(这里就认为是路径长度相同,忽略掉对称点的微小影响)的概率是 \(\dfrac{1}{2}\times \dfrac{1}{2}\times 2=\dfrac{1}{2}\)。
-
则一直错的概率很小,肯定小于 \(0.1\%\),足够通过本题。
CF1305F Kuroni and the Punishment
-
题意:给定一个数列 \(a_{1\dots n}\),单次操作可以将 \(a_i+1\) 或 \(-1\),求最小的操作次数,使得 \((\gcd_{i=1}^n a_i)>1\)(必须总有 \(a_i>0\))。
-
数据范围:\(n\leqslant 2\times 10^5,1\leqslant a\leqslant 10^{12},2.5s\) 时限。
-
首先我们发现,\(ans\leqslant n\)。因为把它们都改成偶数一定可行。
-
在此基础上考虑更优的解,更优的解中被改动 \(>1\) 次的 \(a_i\) 一定不超过 \(\dfrac{n}{2}\) 个。
-
于是每次随一个 \(i\),把 \(a_i-1,a_i,a_i+1\) 的每个质因数都暴力试一下看看对应的 \(ans\) 是多少。单轮正确率 \(\geqslant \dfrac{1}{2}\)。
-
考虑 \(times\),因为 \(a_i\leqslant 10^{12}\),所以 \(\max\{\omega(a_i)\}\leqslant 11\)。大约能做 \(250\) 次,正确率显然奇高无比。
CF364D
-
题意:给定一个数列 \(a_{1\dots n}\)。定义其 \(\operatorname{Ghd}\) 为所有大小至少为 \(n\) 的一半的集合(可重)的 \(\gcd\) 的最大值,求其 \(\operatorname{Ghd}\)。
-
数据范围:\(n\leqslant 10^6,a_i\leqslant 10^{12},4s\) 时限。
-
考虑模仿上一题的思路,每次随一个点,它有 \(\dfrac{1}{2}\) 的概率在答案集合中。问题是,怎么求 \(\gcd\)?
-
首先我们知道,钦定选这个数 \(a_i\) 之后,每个数字 \(g\) 出现的次数即可整除的集合大小就是 \(\sum\limits_{j=1}^n[j\ne i\And g\mid\gcd(a_j,a_i)]\)。
-
所以不妨先构造 \(b_j=\gcd(a_i,a_j)\),后面都对 \(b\) 进行操作。
-
考虑 \(a_i\) 的所有约数,显然它们每一个都可能是 \(t\geqslant \dfrac{n}{2}\) 的可行解之一。可是暴力显然不行,\(d(10^{12})\to 6720\),暴力扫一遍就 T 了。
-
稍等!如果那样的话,我们还取 \(b_j\) 干嘛?现在本质不同的 \(b_j\) 恰只有 \(d(a_i)\) 种!
-
综上,总复杂度为 \(times\times (n\log n+d(a_i)^2)\),可以期望将 \(times\) 取 \(10\),于是我们有 \(\dfrac{1023}{1024}\) 的正确率,足够通过本题。