期望与概率 dp
\(\text{By DaiRuiChen007}\)
I. [洛谷4316] - 绿豆蛙的归宿
\(\text{Link}\)
思路分析
DAG 上做期望 dp，可以爆搜，也可以拓扑排序的时候转移，不过还是爆搜比较简洁
记录一下走到当前节点的步数，到终点返回步数，每一步乘上走这种选择的概率求和即可
时间复杂度 \(\Theta(n)\)
总结：
对于一般的概率/期望 dp，比较常见的做法是记搜求解，或者确定终止条件倒推，有时候也可以使用刷表法正推做
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
int n,m;
struct node {
int des,val;
};
vector <node> edge[MAXN];
inline double dfs(int p,int d) {
if(p==n) return d;
double ret=0;
for(auto e:edge[p]) ret+=dfs(e.des,d+e.val)/((int)edge[p].size());
return ret;
}
signed main() {
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;++i) {
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
edge[u].push_back((node){v,w});
}
printf("%.2lf\n",dfs(1,0));
return 0;
}
II. [洛谷4550] - 收集邮票
\(\text{Link}\)
思路分析
假设 \(x\) 为集齐邮票的步数，那么本题所求答案等价于：
\[\begin{aligned}
\text{Answer}
&=E\left(\sum\limits_{i=1}^x i\right)\\
&=E\left(\dfrac{x(x+1)}2\right)\\
&=\dfrac 12(E(x)+E(x^2))
\end{aligned}
\]
注意答案为什么不是 \(\dfrac{E(x)E(x+1)}2\)，因为相关期望不具有可乘性
所以分别 dp 转移 \(E(x)\) 和 \(E(x^2)\)
设 \(F_i\) 为集齐已经拥有 \(i\) 张邮票，集齐 \(n\) 张邮票还需要的步数
设 \(dp_{i,0}\) 表示已经拥有 \(i\) 张邮票，直到买完 \(n\) 张邮票购买邮票张数的期望，即 \(E(F_i)\)，显然 \(dp_{n,0}=0\)，枚举这一次选择买到的是否是之前已经获得过的，有：
\[dp_{i,0}=\dfrac in\times E(F_i+1)+\dfrac{n-i}nE(F_{i+1}+1)
\]
由定义可知，\(E(F_i+1)=E(F_i)+1=dp_{i,0}+1\) 移项可得：
\[\begin{aligned}
dp_{i,0}&=\dfrac in\times (dp_{i,0}+1)+\dfrac{n-i}ndp_{i+1,0}\\
dp_{i,0}&=dp_{i+1,0}+\dfrac n{n-i}
\end{aligned}
\]
设 \(dp_{i,1}\) 表示已经拥有 \(i\) 张邮票，直到买完 \(n\) 张邮票的购买邮票张数的平方的期望，即 \(E(F_i^2)\)，显然 \(dp_{n,0}=0\)，枚举这一次选择买到的是否是之前已经获得过的，有：
\[dp_{i,0}=\dfrac in\times E\left((F_i+1)^2\right)+\dfrac{n-i}nE\left((F_{i+1}+1)^2\right)
\]
通过定义二项式定理和 \(dp\) 的定义爆拆 \(E\left((f_i+1)^2\right)\)
\[\begin{aligned}
E\left((F_i+1)^2\right)
&=E(F_i^2+2F_i+1)\\
&=E(F_i^2)+2E(F_i)+1\\
&=dp_{i,1}+2dp_{i,0}+1
\end{aligned}
\]
将 \(E\left((F_i+1^2\right)=dp_{i,1}+2dp_{i,0}+1\) 带入并且移项，有：
\[\begin{aligned}
dp_{i,1}&=\dfrac in(dp_{i,1}+2dp_{i,0}+1)+\dfrac{n-i}n(dp_{i+1,1}+2dp_{i+1,0}+1)\\
dp_{i,1}&=\dfrac {2i}{n-i}dp_{i,0}+2dp_{i+1,0}+dp_{i+1,1}+\dfrac n{n-i}
\end{aligned}
\]
答案为 \(\dfrac{dp_{1,0}+dp_{1,1}}2\)
暴力转移，时间复杂度 \(\Theta(n)\)
代码呈现
#include<bits/stdc++.h>
#define div division
using namespace std;
const int MAXN=1e4+1;
double dp[MAXN][2];
inline double div(int x,int y) {
return (double)x/(double)y;
}
signed main() {
int n;
scanf("%d",&n);
dp[n][0]=dp[n][1]=0;
for(int i=n-1;i>=0;--i) {
dp[i][0]=dp[i+1][0]+div(n,n-i);
dp[i][1]=2*div(i,n-i)*dp[i][0]+2*dp[i+1][0]+dp[i+1][1]+div(n,n-i);
}
printf("%.2lf\n",(dp[0][0]+dp[0][1])/2);
return 0;
}
另解思路
设 \(dp_{i,0}\) 表示已经拥有 \(i\) 张邮票，直到买完 \(n\) 张邮票的期望购买邮票张数，显然 \(dp_{n,0}=0\)，枚举这一次选择买到的是否是之前已经获得过的，有：
\[dp_{i,0}=1+\dfrac in\times dp_{i,0}+\dfrac{n-i}ndp_{i+1,0}
\]
移项可得：
\[dp_{i,0}=dp_{i+1,0}+\dfrac n{n-i}
\]
设 \(dp_{i,1}\) 表示已经拥有（白捡）\(i\) 张邮票，直到买完 \(n\) 张邮票的期望购买花费，显然 \(dp_{n,1}=0\)，考虑这一次选择的是否是之前已经有过的
从某个状态开始转移倒退，假设从这个状态开始直到完成的期望步数是 \(E(c)\)，那么在这个基础上，求出在这之前再做一次选择的价格 \(c'\) 的期望 \(E(c')\)，我们可以假设这一次选择是在期望 \(c\) 次选择之后做的，所以 \(E(c')\) 相当于 \(E(c+1)=E(c)+1\)，每一步对本次价格 \(c'\) 的贡献都是 \(1\)，整合起来恰好就是 \(E(c)\)，所以有：
\[dp_{i,1}=\dfrac in(dp_{i,1}+dp_{i,0}+1)+\dfrac{n-i}n(dp_{i+1,1}+dp_{i+1,0}+1)
\]
移项可得：
\[dp_{i,1}=\dfrac i{n-i}dp_{i,0}+dp_{i+1,1}+dp_{i+1,0}+\dfrac n{n-i}
\]
直接转移，时间复杂度 \(\Theta(n)\)
这种做法的递推式也可以用严谨的级数求和来证明，但我不会。。。
总结：
另解考虑用总步数的期望去计算单次代价的期望，高妙 trick。。。
注意，本题虽然可以设 \(x\) 为集齐邮票的期望步数，但是 \(E\left(\sum\limits_{i=1}^x i\right)\neq \dfrac12E(x+1)\times E(x)\)，因为相关期望不具有可乘性，所以这种想法不可行
当然，直接将 \(E\left(\sum\limits_{i=1}^x i\right)\) 拆成 \(\dfrac12(E(x^2)+E(x))\) 的想法似乎更平凡，更可做些
另解代码
#include<bits/stdc++.h>
#define div division
using namespace std;
const int MAXN=1e4+1;
double dp[MAXN][2];
inline double div(int x,int y) {
return (double)x/(double)y;
}
signed main() {
int n;
scanf("%d",&n);
dp[n][0]=dp[n][1]=0;
for(int i=n-1;i>=0;--i) {
dp[i][0]=dp[i+1][0]+div(n,n-i);
dp[i][1]=div(i,n-i)*dp[i][0]+dp[i+1][0]+dp[i+1][1]+div(n,n-i);
}
printf("%.2lf\n",dp[0][1]);
return 0;
}
III. [洛谷4819] - 杀人游戏
思路分析
将每个人向所有他知道身份的人连一条边
如果询问了某一个人，那么能够被他到达的点都可以确定身份
如果图中有环，只需要选择其中的一个点，这一步和直接将环缩成一个点没有区别
所以考虑用 tarjan 将原图缩成 DAG，然后在每个入度为 \(0\) 的强连通分量中选一个人问，假设这样的强连通分量共有 \(x\) 个，则答案为 \(1-\dfrac xn\)
不过，有时候可能会剩下最后一个人不知道身份，那么这个人一定是杀手，所以我们可以考虑这样一种情况：
某一个强联通分量的大小为 \(1\)
这个强联通分量删去后没有增加其他入度为 \(0\) 的强连通分量
那么这个强连通分量可以不选人询问，最后排除法一下就知道这个人的身份了
注意这样的人最多只有一个，此时答案为 \(1-\dfrac{x-1}n\)
注意建新图的时候不要连重边，可以拿个 map 记录一下
时间复杂度 \(\Theta(m\log m)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int low[MAXN],dfn[MAXN],dfncnt,sk[MAXN],top;
bool ins[MAXN];
int scc,bel[MAXN],deg[MAXN],siz[MAXN];
vector <int> edge[MAXN],g[MAXN];
map <pair<int,int>,bool> vis;
inline void tarjan(int p) {
low[p]=dfn[p]=++dfncnt;
sk[++top]=p;
ins[p]=true;
for(int v:edge[p]) {
if(!dfn[v]) {
tarjan(v);
low[p]=min(low[p],low[v]);
} else if(ins[v]) low[p]=min(low[p],low[v]);
}
if(low[p]==dfn[p]) {
++scc;
int k;
do {
k=sk[top--];
ins[k]=false;
bel[k]=scc;
++siz[scc];
} while(k!=p);
}
}
signed main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(int u=1;u<=n;++u) {
for(int v:edge[u]) {
if(bel[u]==bel[v]||vis[make_pair(bel[u],bel[v])]) continue;
g[bel[u]].push_back(bel[v]);
++deg[bel[v]];
vis[make_pair(bel[u],bel[v])]=true;
}
}
bool use=false;
int res=0;
for(int i=1;i<=scc;++i) {
if(deg[i]) continue;
++res;
if(siz[i]>1||use) continue;
bool ok=true;
for(int x:g[i]) {
if(deg[x]==1) {
ok=false;
break;
}
}
if(ok) --res,use=true;
}
printf("%.6lf\n",(double)(n-res)/(double)n);
return 0;
}
IV. [BZOJ3029] - 守卫者的挑战
\(\text{Link}\)
思路分析
大力概率 dp，设 \(dp_{i,j,k}\) 表示考虑前 \(i\) 场战斗，胜利 \(j\) 场，背包容量为 \(k\) 的概率
边界条件为：\(dp_{0,0,K}=1\)
注意到 \(k\ge n\) 就一定满足题意，所以计算背包容量的时候不需要考虑超过 \(n\) 的情况，把背包容量当成 \(n\) 就行
然后大力刷表即可转移：
\[\begin{aligned}
dp_{i+1,j+1,k+a_i}&\gets dp_{i,j,k}\times p_{i+1}\%\\
dp_{i+1,j,k}&\gets dp_{i,j,k}\times\left(1-p_{i+1}\%\right)
\end{aligned}
\]
统计答案为：
\[\text{Answer}=\sum_{j=l}^n\sum_{k=0}^n dp_{n,j,k}
\]
本题卡空间，滚动数组压掉第一维，空间复杂度 \(\Theta(n^2)\)
大力转移即可，时间复杂度 \(\Theta(n^3)\)
代码呈现
#include<bits/stdc++.h>
#define double long double
using namespace std;
const int MAXN=201;
double p[MAXN],dp[2][MAXN][MAXN<<1];
int a[MAXN],n,l,k;
inline int f(int x) {
return min(n,x)+n;
}
signed main() {
scanf("%d%d%d",&n,&l,&k);
for(int i=1;i<=n;++i) scanf("%Lf",&p[i]),p[i]/=100;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
dp[0][0][f(k)]=1;
for(int i=0;i<n;++i) {
int cur=i&1;
for(int j=0;j<=n;++j) {
for(int k=-n;k<=n;++k) {
if(!dp[cur][j][f(k)]) continue;
dp[cur^1][j+1][f(k+a[i+1])]+=p[i+1]*dp[cur][j][f(k)];
dp[cur^1][j][f(k)]+=(1-p[i+1])*dp[cur][j][f(k)];
}
}
memset(dp[cur],0,sizeof(dp[cur]));
}
double res=0;
for(int i=l;i<=n;++i) {
for(int j=0;j<=n;++j) {
res+=dp[n&1][i][f(j)];
}
}
printf("%.6Lf\n",res);
return 0;
}
V. [AcWing218] - 扑克牌
\(\text{Link}\)
思路分析
大力记搜，记录当前四种花色的牌出现的次数，以及大王小王用来当什么了（没用则是 \(0\)），每次考虑大王小王的花色时，在可能的四种情况中取个最小值即可
状态总数 \(S\) 大约是 \(13^4\times5^2\)
时间复杂度 \(\Theta(S)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
double dp[14][14][14][14][5][5];
bool vis[14][14][14][14][5][5];
int A,B,C,D;
inline double dfs(int a,int b,int c,int d,int x,int y) {
if(vis[a][b][c][d][x][y]) return dp[a][b][c][d][x][y];
int tot=a+b+c+d+(x?1:0)+(y?1:0);
if(a+(x==1)+(y==1)>=A&&b+(x==2)+(y==2)>=B&&c+(x==3)+(y==3)>=C&&d+(x==4)+(y==4)>=D) {
vis[a][b][c][d][x][y]=true;
return dp[a][b][c][d][x][y]=(double)tot;
}
double ans=0;
if(a!=13) ans+=dfs(a+1,b,c,d,x,y)*(13-a)/(54-tot);
if(b!=13) ans+=dfs(a,b+1,c,d,x,y)*(13-b)/(54-tot);
if(c!=13) ans+=dfs(a,b,c+1,d,x,y)*(13-c)/(54-tot);
if(d!=13) ans+=dfs(a,b,c,d+1,x,y)*(13-d)/(54-tot);
if(!x) {
double ret=INF;
for(int i:{1,2,3,4}) {
double s=dfs(a,b,c,d,i,y);
if(s) ret=min(ret,s);
}
ans+=ret/(54-tot);
}
if(!y) {
double ret=INF;
for(int i:{1,2,3,4}) {
double s=dfs(a,b,c,d,x,i);
if(s) ret=min(ret,s);
}
ans+=ret/(54-tot);
}
vis[a][b][c][d][x][y]=true;
return dp[a][b][c][d][x][y]=ans;
}
signed main() {
scanf("%d%d%d%d",&A,&B,&C,&D);
if(max(A-13,0)+max(B-13,0)+max(C-13,0)+max(D-13,0)>2) puts("-1.000");
else printf("%.3lf\n",dfs(0,0,0,0,0,0));
return 0;
}
VI. [BZOJ4374] - Little Elephant and Boxes
\(\text{Link}\)
思路分析
数据范围显然提示我们用折半搜索
我们可以固定钻石的条件，将对应状态下使用的金钱进行计算
更准确地讲，分为以下步骤：
- 01 背包预处理，用 \(dp_{i,j}\) 表示用 \(i\) 颗钻石购买 \(j\) 件物品所需要最少的金钱
折半搜索，分别记录下前一半和后一半中：在获得 \(i\) 个钻石的情况下，获得了多少金钱以及这种概况对应的概率
枚举购买的物品数量，以及花费了多少钻石去买这些物品，同时更新出购买这么多件物品至少至多要花费多少钱
枚举前一半和后一半分别贡献了多少钻石，以及前一半中贡献了多少金钱，以及其对应概率
根据刚才所计算出来的最多和最少花费，得到后一半最多最少分别要贡献多少金钱，计算出此时后一半有多少概率恰好获得的金钱在要求的范围（使得恰好买了那么多件物品）
将其前一半的概率和后一半的概率以及获得的物品总数相乘，统计贡献
注意到后一半的概率可以用前缀快速计算
时间复杂度 \(\Theta\left(mn\log (\frac n2!)\times2^\frac n2\right)\)
代码呈现
#include<bits/stdc++.h>
#define pid pair <int,double>
using namespace std;
const int MAXN=31,INF=INT_MAX;
int v[MAXN],p[MAXN],c[MAXN],d[MAXN],dp[MAXN][MAXN]; //use i diamond, buy j item, minimum cost
vector <pid> L[MAXN],R[MAXN]; //get i diamond, <j money, p probability>
int n,m;
inline void dfs(int item,int di,int co,double pr,bool op) {
if(!op&&item>n/2) {
L[di].push_back(make_pair(co,pr));
return ;
}
if(op&&item>n) {
R[di].push_back(make_pair(co,pr));
return ;
}
if(p[item]!=100) dfs(item+1,di+1,co,pr*(1-p[item]*0.01),op);
if(p[item]!=0) dfs(item+1,di,co+v[item],pr*p[item]*0.01,op);
}
inline void solve() {
scanf("%d%d",&n,&m);
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<=n;++i) L[i].clear(),R[i].clear();
for(int i=1;i<=n;++i) scanf("%d%d",&v[i],&p[i]);
dfs(1,0,0,1,false);
dfs(n/2+1,0,0,1,true);
for(int i=0;i<=n;++i) {
sort(L[i].begin(),L[i].end());
sort(R[i].begin(),R[i].end());
for(int j=1;j<(int)L[i].size();++j) L[i][j].second+=L[i][j-1].second;
for(int j=1;j<(int)R[i].size();++j) R[i][j].second+=R[i][j-1].second;
}
dp[0][0]=0;
for(int i=1;i<=m;++i) {
scanf("%d%d",&c[i],&d[i]);
for(int j=n;j>=d[i];--j) {
for(int k=i;k>=1;--k) {
dp[j][k]=min(dp[j][k],dp[j-d[i]][k-1]+c[i]);
}
}
}
double ans=0;
for(int item=1;item<=m;++item) {
int now=INF,nxt=INF;
for(int di=0;di<=n;++di) {
now=min(dp[di][item],now);
if(item<m) nxt=min(dp[di][item+1],nxt);
for(int xi=0;xi<=di;++xi) {
int yi=di-xi;
for(int i=0;i<(int)L[xi].size();++i) {
int co=L[xi][i].first;
double pl=L[xi][i].second,pr=0;
if(i) pl-=L[xi][i-1].second;
int indxl=(lower_bound(R[yi].begin(),R[yi].end(),make_pair(now-co,(double)0))-R[yi].begin())-1;
int indxr=(lower_bound(R[yi].begin(),R[yi].end(),make_pair(nxt-co,(double)0))-R[yi].begin())-1;
if(indxl>=0) pr-=R[yi][indxl].second;
if(indxr>=0) pr+=R[yi][indxr].second;
if(pr>0) ans+=item*pl*pr;
}
}
}
}
printf("%.4lf\n",ans);
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
VII. [洛谷6969] - Foreign Postcards
\(\text{Link}\)
思路分析
考虑简单 dp，首先做一个简单分析：\(f_i\) 表示第 \(i\) 个数作为某一选择中的第一张邮票被拿出来的概率
显然有 \(f_1=1\)，对于接下来的数考虑 \(i-1\) 所在的那一段是从哪个点考试被拿出来的，有：
\[f_m=\sum_{i=1}^{m-1}\dfrac {f_i}{n-i+1}
\]
通过观察可以发现 \(f_i=\dfrac 1{n-i+2}\)
然后考虑一个简单 dp，设 \(dp_i\) 表示 \(i\) 被翻转的概率，如果 \(S_i=\texttt C\)，则直接有 \(f_i\) 的概率成为段首，不被翻转，当然，\(i\) 有 \((1-f_i)\) 的概率被 \(dp_{i-1}\) 包含，所以有：
\[dp_i=(1-f_i)dp_{i-1}+[S_i=\texttt C]f_i
\]
然后统计答案的时候计算概率求和即可：
\[\text{Answer}=\sum_{i=1}^n [S_i=\texttt C]\times (1-dp_i)+[S_i=\texttt W]\times dp_i
\]
暴力，时间复杂度 \(\Theta(n)\)
代码呈现
#include<bits/stdc++.h>
#define double long double
using namespace std;
const int MAXN=1e6+1;
double dp[MAXN];
char str[MAXN];
signed main() {
scanf("%s",str+1);
int n=strlen(str+1);
for(int i=1;i<=n;++i) {
double f=1.0/(n-i+2);
if(i==1) f=1;
if(str[i]=='C') dp[i]+=f;
dp[i]+=dp[i-1]*(1-f);
}
double res=0;
for(int i=1;i<=n;++i) {
if(str[i]=='C') res+=1-dp[i];
else res+=dp[i];
}
printf("%.10Lf\n",res);
return 0;
}
VIII. [BZOJ2201] - 彩色圆环
\(\text{Link}\)
思路分析
考虑链的情况，然后再把 \(1\) 所在的那个环算进去组合成一个链
设 \(dp_{i,0/1}\) 表示考虑到第 \(i\) 颗珠子，当前珠子的颜色与第一颗珠子的颜色不相同/相同时的答案期望，边界条件 \(dp_{1,1}=1\)
枚举最后一个段的颜色和起终点有转移：
\[\begin{aligned}
dp_{j,0}&\gets dp_{i,0}\times(j-i)\times \left(\dfrac 1m\right)^{j-i}\times \dfrac{m-2}{m}\\
dp_{j,0}&\gets dp_{i,1}\times(j-i)\times \left(\dfrac 1m\right)^{j-i}\times \dfrac{m-1}{m}\\
dp_{j,1}&\gets dp_{i,0}\times(j-i)\times \left(\dfrac 1m\right)^{j-i}\times \dfrac{1}{m}\\
\end{aligned}
\]
统计答案的时候，我们可以考虑 \(1\) 所在区间的长度，然后将这个区间缩成一个点扔到剩下的区间里面
\[\text{Answer}=n\times\left(\dfrac 1m\right)^n+\sum_{i=1}^{n-1} i^2\times\left(\dfrac 1m\right)^i\times dp_{n-i+1,0}
\]
注意我们在转移 dp 的时候默认没有其他颜色与第一个相同，故有正确性
时间复杂度 \(\Theta(n^2)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=201;
double dp[MAXN][2],f[MAXN];
signed main() {
int n,m;
scanf("%d%d",&n,&m);
f[1]=1;
for(int i=2;i<=n;++i) f[i]=f[i-1]/m;
dp[1][1]=1;
for(int i=1;i<n;++i) {
for(int j=i+1;j<=n;++j) {
dp[j][0]+=dp[i][0]*f[j-i]*(j-i)*(m-2)/m;
dp[j][0]+=dp[i][1]*f[j-i]*(j-i)*(m-1)/m;
dp[j][1]+=dp[i][0]*f[j-i]*(j-i)/m;
}
}
double res=n*f[n];
for(int i=1;i<n;++i) res+=i*i*dp[n-i+1][0]*f[i];
printf("%.5lf\n",res);
return 0;
}
IX. [BZOJ2720] - 列队春游
\(\text{Link}\)
思路分析
注意到 \(a_j\ge a_i\) 的 \(j\) 对于每个 \(i\) 都仅有 \(1\) 个
所以只需要考虑对于某个 \(i\)，有多少个 \(j\) 满足 \(a_j< a_i\) 且 \(i\) 能看到 \(j\)
假设对于某个 \(i\)，所有满足 \(a_j< a_i\) 且 \(j\neq i\) 的 \(j\) 构成集合 \(\mathbf S_i\)
显然，\(\mathbf S_i\) 中的每个数对答案的贡献都是相等的，所以我们只需要考虑其中一个然后 \(\times|\mathbf S_i|\) 就行
假设我们考虑某个 \(x\in \mathbf S_i\) 被 \(i\) 看见的概率，显然 \(\mathbf S_i\) 中的其他数对 \(i\) 看见 \(x\) 并没有任何影响，所以只考虑 \(x\) 和所有 \(\ge a_i\) 的数
首先我们将所有 \(\ge a_i\) 的 \(n-|\mathbf S_i|\) 个数排列（包括 \(a_i\)），此时我们在 \(n-|\mathbf S_i|+1\) 个空中随便找一个空给 \(x\) ，剩下的 \(|\mathbf S_i|\) 个数随便插，注意到 \(x\) 能被 \(i\) 看见，当且仅当 \(x\) 在最开始 \(n-|\mathbf S_i|+1\) 个空中，选择了 \(i\) 前面的那一个， 因此 \(x\) 被 \(i\) 看见的概率是 \(\dfrac{1}{n-|\mathbf S_i|+1}\)
带入答案计算，有：
\[\begin{aligned}
\text{Answer}
&=n+\sum_{i=1}^n |\mathbf S_i|\times\dfrac 1{n-|\mathbf S_i|+1}\\
&=\sum_{i=1}^n \dfrac{|\mathbf S_i|}{n-|\mathbf S_i|+1}+1\\
&=\sum_{i=1}^n \dfrac{n+1}{n-|\mathbf S_i|+1}
\end{aligned}
\]
问题就转化成了如何求 \(|\mathbf S_i|\)，显然直接装桶算即可
时间复杂度 \(\Theta(w)\)，\(w\) 为 \(h_i\) 的值域
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1001;
int s[MAXN];
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
int h;
scanf("%d",&h);
++s[h];
}
double res=0,tot=0;
for(int i=1;i<MAXN;++i) {
res+=s[i]*(n+1)/(n-tot+1);
tot+=s[i];
}
printf("%.2lf\n",res);
return 0;
}
X. [洛谷4637] - 扫雷机器人
\(\text{Link}\)
思路分析
非常强的思维题，推理过程相当精彩
考虑求出期望的过程：
- 每种引爆地雷的顺序，共有 \(n!\) 种情况
对于每种顺序，计算出其中实际引爆的地雷个数，也就是所有没有在之前被引爆的地雷个数
将每种方案中实际引爆的地雷个数当成操作次数，乘上概率 \(\dfrac1{n!}\)，求和计算期望
由于期望具有线性性，所以我们可以考虑计算每个地雷对答案的贡献，也就是说，对于每个地雷，求出其会在多少种方案中被实际引爆
求出所有可以导致第 \(i\) 个地雷被引爆（直接或间接）的地雷集合，设为 \(\mathbf S_i\)，那么 \(i\) 第一个被引爆，当且仅当所有 \(\mathbf S_i\) 中的地雷都在 \(i\) 之后被引爆，
所以问题就转化成了：对于第 \(i\) 个元素，求出在所有排列中，满足 \(i\) 是 \(\mathbf S_i\) 中所有元素里的第一个的情况总数
由于其他的元素在哪里并不重要，所以我们只需要考虑 \(\mathbf S_i\) 中的元素之间的相对关系，不难得到满足 \(i\) 恰好是其中第一个数的方案数占所有方案数的比例为：\(\dfrac{(|\mathbf S_i|-1)!}{|\mathbf S_i|!}=\dfrac{1}{|\mathbf S_i|}\)，因此在所以排列中，第 \(i\) 颗地雷被实际引爆的次数应该是 \(\dfrac{n!}{|\mathbf S_i|}\) 次，这也是第 \(i\) 颗地雷对答案的贡献
套用期望的计算公式可以得到：
\[\begin{aligned}
\text{Answer}
&=\dfrac{1}{n!}\sum_{i=1}^n\dfrac{n!}{|\mathbf S_i|}\\
&=\sum_{i=1}^n\dfrac1{|\mathbf S_i|}
\end{aligned}
\]
所以问题就转化成求所有的 \(|\mathbf S_i|\)
可以将所有地雷向其能够直接引爆的点连一条边，我们需要求出对于每个点 \(i\)，有多少个点能够到达 \(i\)
考虑缩点，在 DAG 上做拓扑排序转移一个用 bitset 维护的 \(\mathbf S_i\) 即可
注意:如果我们直接在原图上做 \(n\) 次 BFS，复杂度在完全图上会退化到 \(\Theta(n^3)\)
时间复杂度 \(\Theta(n^2)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4001;
int p[MAXN],d[MAXN];
vector <int> edge[MAXN],g[MAXN];
bool vis[MAXN];
bitset <MAXN> f[MAXN];
int low[MAXN],dfn[MAXN],dfncnt,sk[MAXN],siz[MAXN],bel[MAXN],deg[MAXN],top,scc;
bool ins[MAXN],link[MAXN][MAXN];
inline void tarjan(int p) {
low[p]=dfn[p]=++dfncnt;
ins[p]=true; sk[++top]=p;
for(int v:edge[p]) {
if(!dfn[v]) {
tarjan(v);
low[p]=min(low[p],low[v]);
} else if(ins[v]) low[p]=min(low[p],low[v]);
}
if(low[p]==dfn[p]) {
++scc;
int k;
do {
k=sk[top--];
bel[k]=scc;
f[scc].set(k);
++siz[scc];
ins[k]=false;
} while(k!=p);
}
}
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&p[i],&d[i]);
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
if(abs(p[i]-p[j])<=d[i]) {
edge[i].push_back(j);
}
}
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;++i) {
for(int j:edge[i]) {
if(bel[i]==bel[j]||link[bel[i]][bel[j]]) continue;
g[bel[i]].push_back(bel[j]);
link[bel[i]][bel[j]]=true;
++deg[bel[j]];
}
}
queue <int> q;
for(int i=1;i<=scc;++i) {
if(!deg[i]) {
q.push(i);
}
}
while(!q.empty()) {
int p=q.front();
q.pop();
for(int v:g[p]) {
f[v]|=f[p];
--deg[v];
if(!deg[v]) q.push(v);
}
}
double res=0;
for(int i=1;i<=n;++i) res+=1.0/((int)f[bel[i]].count());
printf("%.4lf\n",res);
return 0;
}
XI. [洛谷4206] - 聪聪与可可
\(\text{Link}\)
思路分析
设 \(dp_{x,y}\) 表示聪聪在 \(x\)，可可在 \(y\) 时的答案，显然用记搜解决
首先计算出 \(x\) 的移动轨迹，然后对于 \(y\) 的每一种决策都枚举一下即可
以此我们需要预处理出 \(mov_{x,y}\) 表示聪聪在 \(x\)，可可在 \(y\) 时聪聪的下一步决策，做 \(n\) 次 BFS 预处理出距离然后直接计算即可
时间复杂度 \(\Theta(n(n+e))\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1001;
vector <int> edge[MAXN];
int dis[MAXN][MAXN],mov[MAXN][MAXN];
double dp[MAXN][MAXN];
bool vis[MAXN];
inline void BFS(int s) {
memset(vis,false,sizeof(vis));
dis[s][s]=0;
vis[s]=true;
queue <int> q;
q.push(s);
while(!q.empty()) {
int p=q.front();
q.pop();
for(int v:edge[p]) {
if(vis[v]) continue;
vis[v]=true;
dis[v][s]=dis[p][s]+1;
q.push(v);
}
}
}
inline double dfs(int c,int m) {
if(c==m) return 0;
int st1=mov[c][m],st2=mov[st1][m];
if(m==st1||m==st2) return 1;
if(dp[c][m]) return dp[c][m];
int siz=edge[m].size();
double ret=(dfs(st2,m)+1)/(1+siz);
for(int i:edge[m]) ret+=(dfs(st2,i)+1)/(1+siz);
return dp[c][m]=ret;
}
signed main() {
int n,m,s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
for(int i=1;i<=n;++i) BFS(i);
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
mov[i][j]=-1;
for(int k:edge[i]) {
if(mov[i][j]==-1||dis[k][j]<dis[mov[i][j]][j]||(dis[k][j]==dis[mov[i][j]][j]&&k<mov[i][j])) {
mov[i][j]=k;
}
}
}
}
printf("%.3lf\n",dfs(s,t));
return 0;
}
XII. [洛谷2221] - 高速公路
\(\text{Link}\)
思路分析
查询 \([l,r]\) 中的答案即所有区间中的路径长度和除以路径数量，考虑计算每条路径的计算次数，我们得到：
\[\text{Answer}[l,r]=\sum_{i=l}^{r-1} w(i,i+1)\times(i-l+1)\times(r-i)\div\dbinom {r-l+1}2
\]
将 \((i,i+1)\) 的边权转化为点权 \(a_i\) 以处理区间加，对答案稍作转化：
\[\begin{aligned}
\text{Answer}[l,r]
&=\sum_{i=l}^{r-1} a_i\times(i-l+1)\times(r-i)\div\dbinom {r-l+1}2\\[2ex]
&=\sum_{i=l}^{r-1} a_i\times[i\times(l+r-1)-(l-1)\times r-i^2]\div\dbinom{r-l+1}2\\[2ex]
&=\left[-(l-r)\times r\times \sum_{i=l}^{r-1} a_i+(r+l-1)\sum_{i=l}^{r-1} i\times a_i-\sum_{i=l}^{r-1}i^2\times a_i\right]\div\dbinom{r-l+1}2
\end{aligned}
\]
因此维护 \(\sum a_i,\sum i\times a_i,\sum i^2\times a_i\) 即可，注意到 \(\sum i,\sum i^2\) 可以用数学方法快速计算，因此可以用线段树维护
时间复杂度 \(\Theta(m\log n)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
int n,m;
struct node {
int sum0,sum1,sum2,tag;
node() { sum0=sum1=sum2=tag=0; }
inline friend node operator +(const node &x,const node &y) {
node z;
z.sum0=x.sum0+y.sum0;
z.sum1=x.sum1+y.sum1;
z.sum2=x.sum2+y.sum2;
return z;
}
};
class SegmentTree {
private:
node tree[MAXN<<2];
inline int left(int x) { return x<<1; }
inline int right(int x) { return x<<1|1; }
inline int prefix0(int x) { return x; }
inline int prefix1(int x) { return x*(x+1)/2; }
inline int prefix2(int x) { return x*(x+1)*(2*x+1)/6; }
inline int factor0(int l,int r) { return prefix0(r)-prefix0(l-1); }
inline int factor1(int l,int r) { return prefix1(r)-prefix1(l-1); }
inline int factor2(int l,int r) { return prefix2(r)-prefix2(l-1); }
inline void pushup(int pos) { tree[pos]=tree[left(pos)]+tree[right(pos)]; }
inline void addtag(int l,int r,int pos,int v) {
tree[pos].tag+=v;
tree[pos].sum0+=factor0(l,r)*v;
tree[pos].sum1+=factor1(l,r)*v;
tree[pos].sum2+=factor2(l,r)*v;
}
inline void pushdown(int l,int r,int pos) {
if(!tree[pos].tag) return ;
int mid=(l+r)>>1;
addtag(l,mid,left(pos),tree[pos].tag);
addtag(mid+1,r,right(pos),tree[pos].tag);
tree[pos].tag=0;
}
public:
inline void Modify(int ul,int ur,int k,int l=1,int r=n,int pos=1) {
if(ul<=l&&r<=ur) {
addtag(l,r,pos,k);
return ;
}
pushdown(l,r,pos);
int mid=(l+r)>>1;
if(ul<=mid) Modify(ul,ur,k,l,mid,left(pos));
if(mid<ur) Modify(ul,ur,k,mid+1,r,right(pos));
pushup(pos);
}
inline node Query(int ql,int qr,int l=1,int r=n,int pos=1) {
if(ql<=l&&r<=qr) return tree[pos];
pushdown(l,r,pos);
int mid=(l+r)>>1;
if(qr<=mid) return Query(ql,qr,l,mid,left(pos));
if(mid<ql) return Query(ql,qr,mid+1,r,right(pos));
return Query(ql,qr,l,mid,left(pos))+Query(ql,qr,mid+1,r,right(pos));
}
} S;
inline void reduct(int &x,int &y) {
int z=__gcd(x,y);
x/=z,y/=z;
}
signed main() {
cin>>n>>m;
while(m--) {
char op;
int l,r;
cin>>op>>l>>r;
if(op=='C') {
int v;
cin>>v;
S.Modify(l,r-1,v);
}
if(op=='Q') {
auto res=S.Query(l,r-1);
int x=(l+r-1)*res.sum1-res.sum2-r*(l-1)*res.sum0;
int y=(r-l+1)*(r-l)/2;
reduct(x,y);
printf("%lld/%lld\n",x,y);
}
}
return 0;
}
XIII. [洛谷7648] - MNOGOMENT
\(\text{Link}\)
思路分析
设 \(dp_{t,x,y,i}\) 表示当前时间 \(t\) 秒，比分 \(x:y\)，球在 \(i\) 手中，每次枚举可能性大力转移即可
时间复杂度 \(\Theta(TR^2n^2)\)，需要一定的卡常技巧才能通过本题
代码呈现
TLE on #12，用时 1.06s
#include<bits/stdc++.h>
using namespace std;
const int MAXN=201,MAXT=501;
int siz[MAXN];
vector <int> E[MAXN],F[MAXN];
float p[MAXN],dp[MAXT][MAXN][11][11];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,R,T;
cin>>n>>R>>T;
for(int i=1;i<=n;++i) {
int e,f;
cin>>p[i]>>e>>f;
siz[i]=e+f+1;
while(e--) {
int x;
cin>>x;
E[i].push_back(x);
}
while(f--) {
int x;
cin>>x;
F[i].push_back(x+n);
}
}
for(int i=n+1;i<=n+n;++i) {
int e,f;
cin>>p[i]>>e>>f;
siz[i]=e+f+1;
while(e--) {
int x;
cin>>x;
E[i].push_back(x+n);
}
while(f--) {
int x;
cin>>x;
F[i].push_back(x);
}
}
dp[0][1][0][0]=1;
for(int t=0;t<T;++t) {
for(int x=0;x<R;++x) {
for(int y=0;y<R;++y) {
for(int i=1;i<=n;++i) {
for(int j:E[i]) dp[t+1][j][x][y]+=dp[t][i][x][y]/siz[i];
for(int j:F[i]) dp[t+1][j][x][y]+=dp[t][i][x][y]/siz[i];
dp[t+1][n+1][x+1][y]+=dp[t][i][x][y]/siz[i]*p[i];
dp[t+1][n+1][x][y]+=dp[t][i][x][y]/siz[i]*(1-p[i]);
}
for(int i=n+1;i<=n+n;++i) {
for(int j:E[i]) dp[t+1][j][x][y]+=dp[t][i][x][y]/siz[i];
for(int j:F[i]) dp[t+1][j][x][y]+=dp[t][i][x][y]/siz[i];
dp[t+1][1][x][y+1]+=dp[t][i][x][y]/siz[i]*p[i];
dp[t+1][1][x][y]+=dp[t][i][x][y]/siz[i]*(1-p[i]);
}
}
}
}
for(int x=0;x<=R;++x) {
for(int y=0;y<=R;++y) {
if(x==R&&y==R) continue;
double ans=0;
if(x==R||y==R) {
for(int t=1;t<=T;++t) {
for(int i=1;i<=2*n;++i) {
ans+=dp[t][i][x][y];
}
}
} else for(int i=1;i<=2*n;++i) ans+=dp[T][i][x][y];
cout<<fixed<<setprecision(6)<<ans<<'\n';
}
}
return 0;
}
另解思路
考虑优化转移幅度，以进球为标志，每次转移多个事件
我们发现进球数量和时间不匹配，所以我们可以只考虑每次进球发生的时候
我们可以预处理出 \(i\) 队持球，\(t\) 秒之后 \(j\) 队进球的概率
设 \(dp_{t,x,y,i}\) 表示 \(t\) 秒之后，比分 \(x:y\) 且球在 \(i\) 队一号手上（对面刚刚进球）
枚举下一次进球的时间即可转移
注意，有可能从某个时刻开始没有进球，此时要直接把 \(dp_{t,x,y,i}\) 堆到 \(ans[x:y]\) 中
因此我们需要预处理 \(i\) 队持球时 \(t\) 秒没有进球的情况，直接用刚刚预处理出的概率累加然后做前缀和即可
时间复杂度 \(\Theta(Tn^2+T^2R^2)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=205,MAXT=505;
int siz[MAXN];
vector <int> E[MAXN],F[MAXN];
double p[MAXN];
double hold[MAXT][MAXN]; // t time i player hold the ball (without any score)
double score[2][2][MAXT]; // team i hold the ball, team j score at moment t
double s[2][MAXT]; // team i hold the ball, someone score before moment t
double dp[MAXT][11][11][2]; // time t, score x:y, ball give to team i
double ans[11][11];
signed main() {
int n,R,T;
scanf("%d%d%d",&n,&R,&T);
for(int i=1;i<=n;++i) {
int e,f;
scanf("%lf%d%d",&p[i],&e,&f);
siz[i]=e+f+1;
while(e--) {
int x;
scanf("%d",&x);
E[i].push_back(x);
}
while(f--) {
int x;
scanf("%d",&x);
F[i].push_back(x+n);
}
}
for(int i=n+1;i<=n+n;++i) {
int e,f;
scanf("%lf%d%d",&p[i],&e,&f);
siz[i]=e+f+1;
while(e--) {
int x;
scanf("%d",&x);
E[i].push_back(x+n);
}
while(f--) {
int x;
scanf("%d",&x);
F[i].push_back(x);
}
}
for(int team:{0,1}) {
memset(hold,0,sizeof(hold));
if(team) hold[0][n+1]=1;
else hold[0][1]=1;
for(int t=0;t<=T;++t) {
for(int i=1;i<=n;++i) {
for(int j:E[i]) hold[t+1][j]+=hold[t][i]/siz[i];
for(int j:F[i]) hold[t+1][j]+=hold[t][i]/siz[i];
hold[t+1][n+1]+=hold[t][i]*(1-p[i])/siz[i];
score[team][0][t+1]+=hold[t][i]*p[i]/siz[i];
}
for(int i=n+1;i<=n+n;++i) {
for(int j:E[i]) hold[t+1][j]+=hold[t][i]/siz[i];
for(int j:F[i]) hold[t+1][j]+=hold[t][i]/siz[i];
hold[t+1][1]+=hold[t][i]*(1-p[i])/siz[i];
score[team][1][t+1]+=hold[t][i]*p[i]/siz[i];
}
s[team][t]=score[team][0][t]+score[team][1][t];
if(t) s[team][t]+=s[team][t-1];
}
}
dp[0][0][0][0]=1;
for(int t=0;t<=T;++t) {
for(int x=0;x<=R;++x) {
for(int y=0;y<=R;++y) {
for(int team:{0,1}) {
if(x==R||y==R||t==T) {
ans[x][y]+=dp[t][x][y][team];
continue;
}
ans[x][y]+=dp[t][x][y][team]*(1-s[team][T-t]);
for(int k=1;k+t<=T;++k) {
dp[k+t][x][y+1][0]+=dp[t][x][y][team]*score[team][1][k];
dp[k+t][x+1][y][1]+=dp[t][x][y][team]*score[team][0][k];
}
}
}
}
}
for(int x=0;x<=R;++x) {
for(int y=0;y<=R;++y) {
if(x==R&&y==R) continue;
printf("%.10lf\n",ans[x][y]);
}
}
return 0;
}
