Steven_MengのBlog

我们日常生活中,随机化主要有三种。

$1.$ 这种随机化有一定概率是错的,但是时间一定在范围之内:

如:$Miller Rabin$素数测试,模拟退火,比赛时输出rand(也不能说这个没有正确的概率)

如果你发现题目中有如下性质,那么你可以用随机化试一试:

要你从$a_1 a_2 a_3 …. a_n$选择一些数,构造一个序列$b_1b_2b_3….b_m$,使序列合法且$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.$这种随机化一定是对的,但是时间可能超时(看你脸白不白):

如果你发现题目中有如下性质,那么你可以用随机化试一试:

要你从$a_1 a_2 a_3 …. a_n$选择一些数,构造一个合法序列$b_1b_2b_3….b_m$,这种构造方法有很多,因此是$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)

 评论