众所周知,概率是一个看起来简单实际上很有意思的东西。
jzyz4467绑鞋带
发现难以下手。假如说已经系了\(i\)次,再随便挑一个准备让他与别人系,那么还剩下\(2(n-i)-1\)个头,但是因为他不能与自己所在段的另一端系上,所以剩下\(2(n-i)-2\)个头可供选择。
需要注意的是,当系了\(n-1\)次时,最后一次必须系在同一段上,所以只需要计算
一开始没有考虑清楚上面说的情况,一直乘到\(n-1\)导致过不去样例。这个故事告诉我们临界情况要考虑清楚。
jzyz5079汉堡
172的题面是有锅的。建议去更稳定的通道。
正难则反,考虑计算不会出现这种情况的概率。那么前\(n-2\)个小朋友必须两种各分了\((n-2)/2\)个。方案数是\(C_{n-2}^{(n-2)/2}\)。那么概率怎么算?每一种方案的概率是\((\cfrac{1}{2})^{n-2}\),所以最终答案为\(1-C_{n-2}^{(n-2)/2}(\cfrac{1}{2})^{n-2}\)。
可以开始写了!写写写,然后T了。看来需要\(O(1)\)查询。那我预处理一个阶乘!写写写,然后wa了。哦原来是太大了溢出了。那我直接预处理递推得到减号后面那一坨。写写写,这下终于过了。这个故事告诉我们写之前一定要想清楚,不然会浪费很多时间。
jzyz1900NOIP普及组模拟赛8-4.神盾局特工
\(n\leq20\),那不是状压吗。我设\(dp_{i,s}\)表示考虑了前\(i\)个人以后完成的任务状态为\(s\)的最大概率。转移是\(O(n^22^n)\)的,我再预处理一点东西,感觉复杂度大概率是到不了这个地步的。尝试写了一发,发现re了,然后注意到空间限制是32MB的。这下就很寄了。发现第一维是不需要的,把第一维扔了,仍然过不去。
后来我惊讶的注意到,我第一维枚举到那个人是非常蠢的。完全可以第一维枚举状态,从状态可以得知当前用了几个人,然后枚举状态中空缺的位置,让下一个人去更新填上当前空缺的状态,这样一来每个人都有机会尝试做每个任务,每个状态也会被充分的考虑到所有可能,是不重不漏的。
还是理解不够深刻。
jzyz4468超级购物
嗯,感觉这个比较直接。我先算一下每种购物情况出现的概率(一共有\(2^n\)种),然后在所有购物人数为\(r\)的情况中,看看都有谁购物了,给每个购物的人的答案加上这种情况出现的概率\(p\)。写一写,不过样例。哦,这是那个什么条件概率,我现在已经知道有\(r\)个人购物了,我需要在刚刚结果的基础上再除一个人数为\(r\)的情况出现的概率\(b\)。写一写,又不过样例。哦,我的\(b\)又算错了,在本题中每种情况出现的概率是不一样的,\(b\)应该累加每一种\(p\)才对。
看来我太不注意细节了。
jzyz4469(CF540D)Bad Luck Island
哈哈,这个不是\(O(n^3)\)DP直接做吗。于是有了这个:
点击查看代码
if(i && j){if(! k) dp[i][j - 1][k] += dp[i][j][k];else dp[i][j - 1][k] += dp[i][j][k] * 1.0 / 3.0;
}
if(j && k){if(! i) dp[i][j][k - 1] += dp[i][j][k];else dp[i][j][k - 1] += dp[i][j][k] * 1.0 / 3.0;
}
if(i && k){if(! j) dp[i - 1][j][k] += dp[i][j][k];else dp[i - 1][j][k] += dp[i][j][k] * 1.0 / 3.0;
}
点击查看代码
int tt = i + j + k;
if(i && j){if(! k) dp[i][j - 1][k] += dp[i][j][k];else dp[i][j - 1][k] += dp[i][j][k] * 1.0 * i * j / (1.0 * tt * tt);
}
if(j && k){if(! i) dp[i][j][k - 1] += dp[i][j][k];else dp[i][j][k - 1] += dp[i][j][k] * 1.0 * k * j / (1.0 * tt * tt);
}
if(i && k){if(! j) dp[i - 1][j][k] += dp[i][j][k];else dp[i - 1][j][k] += dp[i][j][k] * 1.0 * i * k / (1.0 * tt * tt);
}
点击查看代码
int tt = i * j + j * k + i * k;
if(i && j){if(! k) dp[i][j - 1][k] += dp[i][j][k];else dp[i][j - 1][k] += dp[i][j][k] * 1.0 * i * j / (1.0 * tt);
}
if(j && k){if(! i) dp[i][j][k - 1] += dp[i][j][k];else dp[i][j][k - 1] += dp[i][j][k] * 1.0 * k * j / (1.0 * tt);
}
if(i && k){if(! j) dp[i - 1][j][k] += dp[i][j][k];else dp[i - 1][j][k] += dp[i][j][k] * 1.0 * i * k / (1.0 * tt);
}
jzyz4472(CF148D)Bag of mice
又是DP。设\(dp_{i,j}\)表示有\(i\)个白球和\(j\)个黑球时先手赢的概率。然后我不会了。
事实上,有两个点:这样的题倒着推往往更好做;按一次操作来划分是困难的,应该按一轮操作来划分。
这是我之前不熟悉的。有了这个,我们得到以下:
这一轮先手抓到白球,直接赢了:\(dp_{i,j}\gets \cfrac{i}{i+j}\)。
这一轮先、后、逃分别为黑、黑、白:\(dp_{i,j}\gets \cfrac{j}{i+j}\times \cfrac{j-1}{i+j-1}\times \cfrac{i}{i+j-2}dp_{i-1,j-2}\)。
这一轮先、后、逃分别为黑、黑、黑,与上面类似就不写了。
其他状态先手就输了,故不讨论。
需要按照一些临界预处理一下\(dp_{i,0}\)和\(dp_{i,1}\)。我在写的时候wa了一发这样的:讨论抓到白球的时候我多乘了一个\(dp_{i-1,j}\)这是不对的,因为我们从头到尾都是按一整轮一整轮考虑的,先手抓到白球的话进行不了一争论就直接结束了。再回来考虑一下这样做的实质是什么。最后剩下的状态是好确定的,所以我们从少的往多的推。而一个状态,如果导向后面某个状态,这个状态的概率是计算好了的,我们直接拿他乘上导向该状态的概率并累加到当前状态就可以了。这也从另一个方面解释了我在上面提到的那个错误,直接抓到白球的话,就不会导向后面的状态了。
为什么想不出来,鉴定为练得少不熟悉套路导致的。
abc126cl Dice and Coin
很直接。注意一点小细节就可以了。
abc333fl Bomb Game 2
好题啊,根本没什么思路。后来看着qls画了一个状态图,也没完全搞懂。事实上可能是把他想的太过复杂了。总之我们设\(dp_{i,j}\)表示当前\(i\)个人的队列,最后第\(j\)个可以活下来的概率。如果\(j\)是第一个人,把他从第一个调到最后一个,他就变成了\(i\)个人中第\(i\)个,而调到最后一个的概率是一半,所以\(dp_{i,1}\gets \cfrac{1}{2}dp_{i,i}\)。如果\(j\)不是第一个人,那就z最前面那个人。要是那个人被踢了,他将变成\(i-1\)人中第\(j-1\)个;否则,他将变成\(i\)人中第\(j-1\)个。概率各占一半,所以\(dp_{i,j}\gets \cfrac{1}{2}(dp_{i-1,j-1}+dp_{i,j-1})\)。容易发现这个转移成了一个环。列个方程解一下然后重新表示一下就可以了。首先DP状态就没设计出来,然后也不知道怎么分类转移,太菜了。要多想。从简单的方面去想,别把问题复杂化。
发现没有点题。下次再点题。