CF838D Airplane Arrangements
Codeforces Luogu 分析 我们考虑计算总方案数乘上合法的概率。然而这样子并不好计算，考虑一些转化。 我们加一个位置 $n+1$，然后把飞机看成一个环，问题变为每个人随机一个初始位置和方向，走到第一个空位停下，如果停在 $n+1$ 就不合法。 这样子最后的每种座位情况都是等概率的，那么 $n+1$ 上有人的概率为 $\frac{m}{n+1}$，即合法概率为 $\frac{n+1...
标签 概率期望 下的文章
- 首页
- 概率期望
AtCoder Grand Contest 006 简要题解
比赛地址 只会做 A，自闭了 Prefix and Suffix 枚举重叠部分的长度即可。 代码 Median Pyramid Easy 显然 $x=1$ 和 $x=2n-1$ 的情况无解。 我们在中间放上 $x$，在它左边放 $x-1$，右边放 $x+1$ 和 $x-2$，可以发现这样子中间就会出现两列 $x$ 一直通到最顶上。 然而 $n=2$ 时只有三个数，需要特判掉。 代码 Rabb...
洛谷6630 [ZJOI2020]传统艺能
Luogu LOJ 分析 因为期望具有线性性，所以可以对每个节点计算它在 $k$ 次操作后有标记的概率，全部加起来即为答案。 考虑 DP。设 $f_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后有标记的概率，$g_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后某个祖先有标记的概率，$h_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后自己和祖先都没有标记的概率。 转移需要再求...
CF1139D Steps to One
Codeforces Luogu 分析 直接算即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h>...
LOJ3080 「2019 集训队互测 Day 5」国际象棋
LOJ 分析 不难想到一个 $\mathcal{O}(n^3m^3)$ 的高斯消元做法，即将每个位置出发的期望步数作为变量，然后暴力高斯消元。 考虑将第一行、第二行、第一列的位置作为主元，并将其它元用主元线性表示。可以发现只有 $(x+2,y+1)$ 无法直接求出它的线性表示，但因为向八个方向走的概率之和为 $1$，所以可以用其它七个方向来求 $(x+2,y+1)$ 的线性表示。 当 $(x...
洛谷3750 [六省联考2017]分手是祝愿
Luogu LOJ 分析 首先可以发现，$i$ 只能被 $\geq i$ 的开关操作掉。从而我们只需要从大到小模拟一遍，如果 $i$ 亮着就操作 $i$ 开关，就可以算出最小需要操作的次数 $c$ 了。这样子就可以拿到 $50$ 分（实际上有 80 分）。 冷静分析一下可以发现，达到目标所需要按的开关组合是唯一确定的。我们把这些开关叫做正确的。 考虑一个 DP。设 $dp_i$ 表示从剩余 ...
LOJ6495 「雅礼集训 2018 Day1」树
LOJ 分析 设 $dp_{i,j}$ 表示 $1\sim i$ 构成的树高度为 $j$ 的方案数。 显然树上一定存在 $(1,2)$ 这条边，因此我们转移时讨论以 $2$ 为根的子树（记做 $A$）和整棵树其它部分（记做 $B$，显然它也是一棵树）的高度关系。 转移讨论一下整棵树最深的节点在哪里即可 边界为 $dp_{1,1}=dp_{1,2}=1$。 代码 偷懒把第一问打了个表 QAq...
CF1286D LCC
Codeforces Luogu 分析 容易发现最早碰撞的一定是相邻的两个球。 我们钦定某一对球是最先撞上的以及它们的运动方向，然后考虑 DP。设 $dp_{i,0/1}$ 表示前 $i$ 个球，当前的球往左/往右，且保证最早撞上的是钦定的那一对的概率。转移讨论一下几种情况即可。 这个转移显然可以写成若干个 $2\times 2$ 的矩阵相乘。如果我们把所有方案按时间从小到大排序再枚举，则每...
CF708E Student's Camp
Codeforces Luogu 分析 显然营地不连通只能是上下分开，即存在相邻两行剩下的砖块区间没有交。 考虑 DP。设 $f_{i,j,k}$ 表示前 $i$ 行，第 $i$ 行剩下 $[j,k]$，且前 $i$ 行连通的概率。容易得到转移 于是只要求出 $d_{l-1}$ 和 $d_{l-1}sr_{i-1,l-1}$ 的前缀和即可。第一个可以提前预处理出，第二个可以在 DP 时维护...
洛谷5405 [CTS2019]氪金手游
Luogu LOJ 分析 首先考虑原树为外向树的情况。此时 $u$ 子树中所有点选择时间都应比 $u$ 晚。 考虑这个概率。设 $u$ 子树 $w_i$ 的和为 $s$，整棵树 $w_i$ 的和为 $S$，则 $u$ 子树中所有点选择时间都比 $u$ 晚的概率为 这个概率只和子树有关，因此可以设 $dp_{i,j}$ 表示以 $i$ 为根的子树 $w_i$ 和为 $j$ 的概率，转移即为树...