P1215题解

· · 题解

看到楼下还缺少一种算法，果断来补。
今天我们要讲的是：（敲黑板！划重点！）随机化。

首先，随机化可以用在什么样的题里面呢？

  1. 没有明显的算法的题目。例如，班主任找到你，让你给这个级部写一个分班程序，你也没有什么好的算法，于是随机生成班级，不断更新最优解，一个小时之后验收就行了。（反正又不是OI，没有什么时限）
  2. 计算某某事件的概率，然后你发现这个事件很好模拟，于是模拟它10000000次，利用蒙特卡洛方法及概率的大数原理，以频率代替概率。
    （注1：概率大数原理为：做N次试验，事件A发生了M次，当N\rightarrow+ \infty时，\frac {M} {N} \rightarrow P(A)）
    （注2：据经验，当做10000000次试验时，所求概率“不确定性”一般会在(10^{-4},10^{-3})以内。）
  3. 求所有可能情况，然后这个事件很好模拟，于是你模拟了10000000次，并且有理由相信所有的情况都发生过了（运气再不好也有90~95分吧）。例如：本题。
  4. 骗分

回到本题。 我们将倒奶的操作重复25000000遍（这是不放心的举措，实际上，以运行时间600~700ms为宜）。剩下的，就是pj-的情况判断。 我们对照代码分析一下：

#include <bits/stdc++.h>

using namespace std;

//桶被编号为0,1,2
int f[6]={0,0,1,1,2,2};//意为from，从哪个桶倒出奶
int t[6]={1,2,0,2,0,1};//意为to，向哪个桶倒奶
int p[21];//C桶剩余奶量的判断

int main(){
    int a[3];
    scanf("%d %d %d",a,a+1,a+2);//输入ABC桶的容积
    int x[3]={0,0,a[2]};//x数组表示现有牛奶的体积
    srand(123456789+2*a[0]*a[1]*a[2]);//写一个很乱的种子
    for (int i=0;i<25000000;i++){
        int caozuo=rand()%6;//一共有6种倒牛奶的操作
        int dv=a[t[caozuo]]-x[t[caozuo]];//意为△V，转移牛奶的体积
        if (dv>x[f[caozuo]]){//如果一下子倒不满就全倒进去
            x[t[caozuo]]+=x[f[caozuo]];
            x[f[caozuo]]=0;
        }
        else{//否则就倒满
            x[t[caozuo]]+=dv;
            x[f[caozuo]]-=dv;
        }
        if (!x[0]){//如果A是空的
            p[x[2]]=1;//统计C桶现有牛奶体积
        }
    }
    for (int i=0;i<=a[2];i++){
        if (p[i]) printf("%d ",i);
    }
    return 0;
}

当采用随机化以后，算法难度瞬间降到普及-，代码量也小（33行），各位OIer不妨一试。以上就是我对随机化的一家之言。