我们日常生活中，随机化主要有三种。
1. 这种随机化有一定概率是错的，但是时间一定在范围之内：
如：MillerRabin素数测试，模拟退火，比赛时输出rand（也不能说这个没有正确的概率）
如果你发现题目中有如下性质，那么你可以用随机化试一试：
要你从a1a2a3....an选择一些数，构造一个序列b1b2b3....bm，使序列合法且m尽可能大。
1
2
3
4
5
6
7
8
9
10
11
12
| for (register int k=1;k<=10000;++k){
random_shuffle(a+1,a+1+n);
for (register int i=1;i<=n;++i){
if (!Check()){
ans=max(ans,....);
break;
}
}
}
printf("%d\n",ans);
|
例题：
P4212 外太空旅行
2.这种随机化一定是对的，但是时间可能超时（看你脸白不白）：
如果你发现题目中有如下性质，那么你可以用随机化试一试：
要你从a1a2a3....an选择一些数，构造一个合法序列b1b2b3....bm，这种构造方法有很多，因此是SPJ，模板如下：
（b为下标序列）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| for (register int t=1;t<=100000;++t){
random_shuffle(b+1,b+1+n);
for (register int i=1;i<=n;++i){
if (Check()){
for (register int j=1;j<=i;++j){
printf("%d ",a[b[j]]);
}
printf("\n");
return 0;
}
}
}
|
例题：
LOJ #6220.sum
CF405D Toy Sum
3.随机化用来均摊时间复杂度，如快排，Treap。
这类题目比较玄学，大部分是找最小的最大值或最大的最小值（前提二分不可做）
例题：
CF981F Round Marriage
最后一点非常重要：
srand(19260817)
