随机数

Fluorine Wang

2024-05-07

ACM

Algorithm

这里要开c++11.

随机数引擎

常见的有两个,一个是rand(),另一个是随机数引擎mt19937.

洗牌算法,和sort一样用,开头,结尾,随机数引擎.(随机打乱)

1 2	std::mt19937 rnd(seed); shuffle(dat,dat+1+n,rnd);

作为少见的闭区间作为参数的stl,直接传参就行,,
使用的时候要连着随机数引擎一起用.

1 2	uniform_int_distribution uni(114,514); int a=uni(rng);

实数域随机数等概率生成器,用法和上面一样.

正态分布”钟形曲线”,两个参数前面是 $\mu$ ,后面是 $\sigma$ ,生成的是 $N(\mu,\sigma^2)$ .

1	normal_distribution<double> N(10.0, 5.0);

交互题,有n个隐藏的不重合不共线的点,你每次可以询问三个点,返回三角形里面是否存在别的点(的下标,多个点返回一个),你要找一个里面不存在任何三角形的点,最多 $75$ 次询问.

出题人说,每次询问期望的点数是除3,所以随机地选取ijk坐标替代,期望会每次除3,也就是log次查询,带入本题1500个点期望7次内能得到答案,然而这个做法可以卡死,所以本题不接受hack,剩下的全是证明这个做法失败的概率有多高云云,反正就是随机.