概率与期望习题

习题"/>

概率与期望习题

概率与期望习题

• • 知识点
  • • 事件与样本空间
    • 概率满足的三个条件
    • 独立事件与条件概率
    • 全概率公式
    • 贝叶斯公式
    • 随机变量与期望
  • 例题
  • • （1）开门
    • （2）粉刷墙壁
  • 习题
  • • P6154 游走
    • P3232 [HNOI2013]游走
    • acwing217. 绿豆蛙的归宿
    • P3211 [HNOI2011]XOR和路径
    • acwing216. Rainbow的信号
    • acwing218. 扑克牌
    • acwing232. 守卫者的挑战
    • acwing233. 换教室
    • acwing307. 连通图
    • acwing337. 扑克牌
    • acwing 309. 装饰围栏

知识点

事件与样本空间

（1）样本点 ω \omega ω ：一种结果
（2）样本空间 Ω \Omega Ω：所有样本点的集合
（3）事件 E E E ：样本空间的子集，若干结果的集合

概率满足的三个条件

• 非负性：对于任意事件 A 都有 P ( A ) ≥ 0 P(A)\ge 0 P(A)≥0
• 正规性： P ( Ω ) = 1 P(\Omega) =1 P(Ω)=1
• 可加性：如果事件 A 1 , A 2 , … A_1,A_2,\dots A1​,A2​,… ，两两互斥，那么 P ( ⋃ A i ) = ∑ P ( A i ) P(\bigcup A_i)=\sum P(A_i) P(⋃Ai​)=∑P(Ai​)

独立事件与条件概率

（1）独立：对于事件A和B，如果 P ( A B ) = P ( A ) P ( B ) P(AB)=P(A)P(B) P(AB)=P(A)P(B) 那么称 A 和 B 是独立的。所谓独立，即两事件的结果不会哦相互影响。从样本点的角度来考虑，就是两者不包含相同的样本点
（2）条件概率：如果 P ( B ) > 0 P(B)>0 P(B)>0 ，那么 A 在 B 下发生的条件概率为

P ( A ∣ B ) = P ( A B ) P ( B ) P(A|B)=\frac {P(AB)}{P(B)} P(A∣B)=P(B)P(AB)​

即，已知 B 发生，在此前提下 A 发生的概率是多少。当 A 和 B独立时，那么 P ( A ∣ B ) = P ( A ) P(A|B)={P(A)} P(A∣B)=P(A)。

全概率公式

全概率公式：如果样本空间可以为划分为两两互斥的若干部分 A 1 , … , A k A_1,\dots,A_k A1​,…,Ak​ ，那么

P ( B ) = ∑ i = 1 k P ( B ∣ A i ) P ( A i ) P(B)=\sum_{i=1}^k P(B|A_i)P(A_i) P(B)=i=1∑k​P(B∣Ai​)P(Ai​)

全概率公式用于将不好算的事件拆分成若干小的事件，分别计算

贝叶斯公式

（1）贝叶斯公式：对于事件 A 和 B ，如果 P ( A ) > 0 P(A)>0 P(A)>0 且 P ( B ) > 0 P(B)>0 P(B)>0 ，那么

P ( A ∣ B ) = P ( B ∣ A ) P ( A ) P ( B ) P(A|B)=\frac {P(B|A)P(A)}{P(B)} P(A∣B)=P(B)P(B∣A)P(A)​

（2）通常我们会有样本空间的一个划分 A 1 , … , A k A_1,\dots,A_k A1​,…,Ak​ ，结合全概率公式，对于任意 1 ≤ i ≤ k 1\le i \le k 1≤i≤k 有

P ( A i ∣ B ) = P ( B ∣ A i ) P ( A i ) ∑ j P ( B ∣ A j ) P ( A j ) P(A_i|B)=\frac {P(B|A_i)P(A_i)}{\sum_j P(B|A_j)P(A_j)} P(Ai​∣B)=∑j​P(B∣Aj​)P(Aj​)P(B∣Ai​)P(Ai​)​

随机变量与期望

（1）随机变量：即将样本点映射到实数域的函数 X : Ω → R X: \Omega \rightarrow R X:Ω→R
（2）期望：即随机变量在概率意义下的平均值

E ( X ) = ∑ ω ∈ Ω X ( ω ) P ( ω ) E(X)=\sum_{\omega \in \Omega} X(\omega)P(\omega) E(X)=ω∈Ω∑​X(ω)P(ω)

（3）线性性：对于任意随机变量 X 和 Y ，满足：
E ( α X + β Y ) = α E ( X ) + β E ( Y ) E(\alpha X + \beta Y) = \alpha E(X)+\beta E(Y) E(αX+βY)=αE(X)+βE(Y)

期望线性性是始终成立的，无论两个随机变量是否独立

例题

（1）开门

题意：有 n 扇们，其中一扇门背后有奖金，其他门背后什么也没有。你选择了一扇门，此时主持人从剩下的 n-1 扇门中选择了一扇门打开，没有中奖 。问此时你选择不换门中奖的概率是多少，换门中奖的概率是多少？

思路：
不换： P = 1 n P=\frac 1n P=n1​
换门： P = n − 1 n × 1 n − 2 P=\frac {n-1}{n} \times \frac {1}{n-2} P=nn−1​×n−21​

（2）粉刷墙壁

题意：有一块 n × m n\times m n×m 的矩形网格要进行粉刷。每次粉刷匠都会等概率的选取两个格子，粉刷以这两个格子为顶点的矩形区域。求经过 k k k次粉刷之后，至少被刷了一次的格子数的期望。 1 ≤ n , m ≤ 1000 , 1 ≤ k ≤ 100 1\le n,m \le 1000,1\le k \le 100 1≤n,m≤1000,1≤k≤100

思路：

• 首先考虑一维：设点 X 被粉刷的概率为 P ( X ) P(X) P(X)， P ( X ) = x × ( n − x + 1 ) × 2 − 1 n 2 P(X)=\frac {x\times (n-x+1)\times 2 -1}{n^2} P(X)=n2x×(n−x+1)×2−1​，至少被刷一次的概率为： P ( A ) = 1 − ( 1 − P ( X ) ) k P(A)=1-(1-P(X))^k P(A)=1−(1−P(X))k
• 二维情况相当于两个独立的随机变量相乘即可： P ( X Y ) = P ( X ) P ( Y ) = x × ( n − x + 1 ) × 2 − 1 n 2 y × ( m − y + 1 ) × 2 − 1 m 2 P(XY)=P(X)P(Y)=\frac {x\times (n-x+1)\times 2 -1}{n^2}\frac {y\times (m-y+1)\times 2 -1}{m^2} P(XY)=P(X)P(Y)=n2x×(n−x+1)×2−1​m2y×(m−y+1)×2−1​
• 最后答案： ∑ i = 1 n ∑ j = 1 m 1 − ( 1 − P ( i j ) ) k \sum_{i=1}^n\sum_{j=1}^m 1-(1-P(ij))^k ∑i=1n​∑j=1m​1−(1−P(ij))k

习题

P6154 游走

链接：

题意：B 城可以看作一个有 n 个点 m 条边的有向无环图。可能存在重边。zbw 在 B 城随机游走，他会随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。定义一条路径的长度为经过的边数，你需要求出 zbw 走的路径长度的期望，答案对 998244353 取模

思路：计算出路径的总长度、总路径数，两者相除即可

• 设 g[i] 表示以 i 为终点的路径总数： g [ v ] = g [ v ] + g [ u ] g[v]=g[v]+g[u] g[v]=g[v]+g[u]
• 设 f[i] 表示以 i 为终点的路径总长度： f [ v ] = f [ u ] + w ( u , v ) × g [ u ] f[v]=f[u]+w(u,v)\times g[u] f[v]=f[u]+w(u,v)×g[u]
• 这里 g[i] 初始值为 1 ，因为题目表示起点和终点可以一致

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5,mod=998244353;int n,m;
ll in[maxn],f[maxn],g[maxn];
vector<int> e[maxn];int qpow(int b,int n,int mod)
{int res=1;while(n){if(n&1) res=1ll*res*b%mod;b=1ll*b*b%mod;n>>=1;}return res;
}void topo()
{queue<int> q;for(int i=1; i<=n; ++i)if(in[i]==0) q.push(i);while(!q.empty()){int u=q.front();q.pop();for(auto v: e[u]){g[v]=(g[v]+g[u])%mod;f[v]=(f[v]+f[u]+g[u])%mod;in[v]--;if(in[v]==0) q.push(v);}}ll a=0,b=0;for(int i=1; i<=n; ++i){a=(a+f[i])%mod;b=(b+g[i])%mod;}ll gcd=__gcd(a,b);a/=gcd,b/=gcd;ll ans=1ll*a*qpow(b,mod-2,mod)%mod;printf("%lld\n",ans);
}int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=m; ++i){int u,v;scanf("%d%d",&u,&v);e[u].push_back(v);in[v]++;}for(int i=1; i<=n; ++i) g[i]=1,f[i]=0;topo();return 0;
}

P3232 [HNOI2013]游走

链接：

题意：给定一个 n 个点 m 条边的无向连通图，顶点从 1 编号到 n，边从 1 编号到 m。小 Z 在该图上进行随机游走，初始时小 Z 在 1 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 n 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 m 条边进行编号，使得小 Z 获得的总分的期望值最小。

思路：假设经过每个点的期望次数是 x i x_i xi​ ，每个点的度数是 d i d_i di​ ，那么经过边 ( u , v ) (u,v) (u,v) 的期望次数就是： f i = x u d u + x v d v f_i=\frac {x_u}{d_u} + \frac {x_v}{d_v} fi​=du​xu​​+dv​xv​​

x u = ∑ v ∈ s o n [ u ] v ≠ n x v d v u ≠ 1 x_u=\sum_{v\in son[u] ~v\neq n} \frac {x_v}{d_v} ~u\neq 1 xu​=v∈son[u] v​=n∑​dv​xv​​ u​=1

x 1 = 1 + ∑ v ∈ s o n [ 1 ] v ≠ n x v d v x_1=1+\sum_{v\in son[1] ~v\neq n} \frac {x_v}{d_v} x1​=1+v∈son[1] v​=n∑​dv​xv​​

因此可以得到 n -1 个关于 x 的等式，高斯消元求解，计算 f i f_i fi​ 即可。

• 走到 n 就结束了，所以不用计算 n 的期望次数
• 一开始就在 1 的位置所以期望次数 + 1

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int maxn=500+5,maxm=2e5;int n,m;
vector<int> e[maxn];
pair<int,int> edges[maxm];
int d[maxn];
double x[maxn],f[maxm],a[maxn][maxn];int gauss(double a[][maxn],int n,int m)
{for(int row=1,col=1; row<=n&&col<=m; ++row,++col){int maxrow=row;for(int i=row+1; i<=n; ++i)if(fabs(a[i][col])>fabs(a[row][col])) maxrow=i;if(maxrow!=row){for(int i=col; i<=m+1; ++i)swap(a[row][i],a[maxrow][i]);}//if(a[row][col]==0) return -1;//存在自由变元for(int i=row+1; i<=n; ++i){double tmp=a[i][col]/a[row][col];for(int j=col; j<=m+1; ++j)a[i][j]-=a[row][j]*tmp;}}for(int i=m; i>=1; --i){double res=a[i][m+1];for(int j=i+1; j<=m; ++j)res-=a[i][j]*x[j];x[i]=res/a[i][i];}return 0;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=m; ++i){int u,v;scanf("%d%d",&u,&v);e[u].push_back(v);e[v].push_back(u);edges[i]= {u,v};d[u]++,d[v]++;}for(int u=1; u<n; ++u){a[u][u]=1.0;for(auto v: e[u])if(v!=n) a[u][v]=-1.0/d[v];}a[1][n]=1;gauss(a,n-1,n-1);for(int i=1; i<=m; ++i){int u=edges[i].fi,v=edges[i].se;if(u!=n) f[i]+=x[u]/d[u];if(v!=n) f[i]+=x[v]/d[v];}sort(f+1,f+1+m);reverse(f+1,f+1+m);double ans=0;for(int i=1; i<=m; ++i) ans+=f[i]*i;printf("%.3lf\n",ans);return 0;
}

acwing217. 绿豆蛙的归宿

链接：/

题意：给出一个有向无环的连通图，起点为1，终点为N，每条边都有一个长度。数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？

思路：这题跟上题类似，不过是上题的简化版本，不需要高斯消元。

• 先求出每个点的期望，然后求出边的期望即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;int n,m;
vector<pair<int,int> > e[maxn];
int out[maxn],in[maxn];
double x[maxn],f[maxn];struct Edge
{int u,v,w;
} edges[maxn<<1];void topo()
{x[1]=1;queue<int> q;for(int i=1; i<=n; ++i)if(in[i]==0) q.push(i);while(!q.empty()){int u=q.front();q.pop();if(u==n) continue;for(auto t: e[u]){int v=t.first;x[v]+=x[u]/out[u];in[v]--;if(in[v]==0) q.push(v);}}
}int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=m; ++i){int u,v,w;scanf("%d%d%d",&u,&v,&w);e[u].push_back({v,w});edges[i]= {u,v,w};out[u]++;in[v]++;}topo();double ans=0;for(int i=1; i<=m; ++i){int u=edges[i].u,w=edges[i].w;ans+=x[u]/out[u]*w;}printf("%.2lf\n",ans);return 0;
}

P3211 [HNOI2011]XOR和路径

链接：

题意：，从 1 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 N 号节点为止，便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值

思路：首先可以将每一位独立出来计算，这样就得到了一个只有 0、1 的图。假设 E i E_i Ei​ 表示从 i i i 到 n n n 路径异或和为 1 的概率

E u = { ∑ w ( u , v ) = 0 E v D v ∑ w ( u , v ) = 1 1 − E v D v E_u=\begin{cases} \sum_{w(u,v)=0} \frac{E_v}{D_v} \\ \sum_{w(u,v)=1} \frac {1-E_v}{D_v} \end{cases} Eu​={∑w(u,v)=0​Dv​Ev​​∑w(u,v)=1​Dv​1−Ev​​​

根据这两个式子，即可列出方程式，然后高斯消元即可

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int maxn=100+5;int n,m;
vector<pair<int,int> > e[maxn];
int in[maxn];
double a[maxn][maxn],x[maxn];int gauss(double a[][maxn],int n,int m)
{for(int row=1,col=1; row<=n&&col<=m; ++row,++col){int maxrow=row;for(int i=row+1; i<=n; ++i)if(fabs(a[i][col])>fabs(a[row][col])) maxrow=i;if(maxrow!=row){for(int i=col; i<=m+1; ++i)swap(a[row][i],a[maxrow][i]);}for(int i=row+1; i<=n; ++i){double tmp=a[i][col]/a[row][col];for(int j=col; j<=m+1; ++j)a[i][j]-=a[row][j]*tmp;}}for(int i=m; i>=1; --i){double res=a[i][m+1];for(int j=i+1; j<=m; ++j)res-=a[i][j]*x[j];if(a[i][i]!=0) x[i]=res/a[i][i];}return 0;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=m; ++i){int u,v,w;scanf("%d%d%d",&u,&v,&w);e[u].push_back({v,w});in[u]++;if(u!=v) in[v]++,e[v].push_back({u,w});}double ans=0;for(int i=30; i>=0; --i){memset(a,0,sizeof(a));memset(x,0,sizeof(x));for(int u=1; u<n; ++u){a[u][u]=in[u];for(auto x: e[u]){int v=x.fi,w=x.se>>i&1;if(w==0) a[u][v]--;else a[u][v]++,a[u][n+1]++;}}gauss(a,n,n);ans+=(1<<i)*x[1];}printf("%.3lf\n",ans);return 0;
}

acwing216. Rainbow的信号

链接：/

题意：给定 n 个数，等概率的选择两个数 l 和 r （如果 l > r ，自动交换），将区间 [ l , r ] [l,r] [l,r] 中的数取出，构成一个数列 P 。分别求数列 P xor 和、and 和、or 和的期望

思路：其实就是求所有区间形成的 xor 和、and 和 、or 和 ，最后平均到 n × n n\times n n×n 的区间上就好了

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;ll n;
ll a[maxn],b[maxn][31],s[maxn],cnt[2];
ll sum;double solve1()
{double ans=0;for(int j=0; j<=30; ++j){int cnt[2]= {1,0},now=0;for(int i=1; i<=n; ++i){now+=b[i][j];if(now&1) ans+=(1ll<<j)*cnt[0];else ans+=(1ll<<j)*cnt[1];cnt[now%2]++;}}ans-=sum;ans*=2;ans+=sum;return ans/(n*n);
}
double solve2()
{double ans=0;for(int j=0; j<=30; ++j){int last0=0;for(int i=1; i<=n; ++i){if(b[i][j]) ans+=(1ll<<j)*(i-last0);else last0=i;}}ans-=sum;ans*=2;ans+=sum;return ans/(n*n);
}
double solve3()
{double ans=0;for(int j=0; j<=30; ++j){int last1=0;for(int i=1; i<=n; ++i){if(b[i][j]) ans+=(1ll<<j)*i,last1=i;else ans+=(1ll<<j)*last1;}}ans-=sum;ans*=2;ans+=sum;return ans/(n*n);
}
int main()
{scanf("%lld",&n);for(int i=1; i<=n; ++i) scanf("%lld",&a[i]),sum+=a[i];for(int i=1; i<=n; ++i)for(int j=0; j<=30; ++j)if(a[i]>>j&1) b[i][j]=1;printf("%.3lf %.3lf %.3lf\n",solve1(),solve2(),solve3());return 0;
}

acwing218. 扑克牌

链接：/

题意：给定一副扑克牌 54 张牌，要求翻出 4 种花色的数量分别超过 A 、B、C、D 张，其中大小王可以充当任意花色，问期望最少需要翻开多少张牌

思路： 设 d p [ a ] [ b ] [ c ] [ d ] [ x ] [ y ] dp[a][b][c][d][x][y] dp[a][b][c][d][x][y] 分别表示 4 种花色的数量、以及大小王所表示的花色。每层的初始值都需要设为 1 ，因为需要花费 1

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int A,B,C,D;
double dp[15][15][15][15][5][5];
double dfs(int a,int b,int c,int d,int x,int y)
{if(dp[a][b][c][d][x][y]) return dp[a][b][c][d][x][y];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) return 0;double ans=1;int cnt=54-(a+b+c+d+(x>0)+(y>0));if(a<13) ans+=dfs(a+1,b,c,d,x,y)*(13-a)/cnt;if(b<13) ans+=dfs(a,b+1,c,d,x,y)*(13-b)/cnt;if(c<13) ans+=dfs(a,b,c+1,d,x,y)*(13-c)/cnt;if(d<13) ans+=dfs(a,b,c,d+1,x,y)*(13-d)/cnt;if(x==0){double res=1e18;for(int i=1;i<=4;++i) res=min(res,dfs(a,b,c,d,i,y)*1.0/cnt);ans+=res;}if(y==0){double res=1e18;for(int i=1;i<=4;++i) res=min(res,dfs(a,b,c,d,x,i)*1.0/cnt);ans+=res;}return dp[a][b][c][d][x][y]=ans;
}int main()
{scanf("%d%d%d%d",&A,&B,&C,&D);int cnt=max(0,A-13)+max(0,B-13)+max(0,C-13)+max(0,D-13);if(cnt>2) puts("-1.000");else printf("%.3lf\n",dfs(0,0,0,0,0,0));return 0;
}

acwing232. 守卫者的挑战

链接：/

题意：队员们被传送到了一个擂台上，最初身边有一个容量为 k 的包包。擂台赛一共有 n n n 项挑战，各项挑战依次进行。第 i i i 项挑战有一个属性 a i a_i ai​ ，如果 a i ≥ 0 a_i\ge 0 ai​≥0，表示这次挑战成功后可以再获得一个容量为 a i a_i ai​ 的包包；如果 a i = − 1 a_i=-1 ai​=−1 ，则表示这次挑战成功后可以得到一个大小为1的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把获得的所有的地图残片都带走（没有得到的不用考虑，只需要完成所有N项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功 L L L 次才能离开擂台。队员们一筹莫展之时，善良的守卫者Nizem 帮忙预估出了每项挑战成功的概率，其中第i项挑战成功的概率为 p i p_i pi​ 。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

0 ≤ K ≤ 2000 , 0 ≤ N ≤ 200 , − 1 ≤ a i ≤ 1000 , 0 ≤ L ≤ N , 0 ≤ p i ≤ 100 0≤K≤2000, 0≤N≤200, −1≤a_i≤1000, 0≤L≤N, 0≤p_i≤100 0≤K≤2000,0≤N≤200,−1≤ai​≤1000,0≤L≤N,0≤pi​≤100

思路：设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] 表示前 i 个物品成功 j 次，背包剩余 k 的概率。（可以避免 k 1200 的限制）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;int n,l,k;
int a[maxn];
double dp[210][210][410],p[210];double dfs(int i,int j,int k)
{if(i==n+1){if(j>=l&&k>=n) return 1;else return 0;}if(dp[i][j][k]!=-1) return dp[i][j][k];double ans=0;if(a[i]==-1) ans+=p[i]*dfs(i+1,j+1,k-1)+(1-p[i])*dfs(i+1,j,k);else ans+=p[i]*dfs(i+1,j+1,min(2*n,k+a[i]))+(1-p[i])*dfs(i+1,j,k);return dp[i][j][k]=ans;
}int main()
{scanf("%d%d%d",&n,&l,&k);for(int i=0; i<=n; ++i)for(int j=0; j<=n; ++j)for(int x=0; x<=2*n; ++x)dp[i][j][x]=-1;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]);printf("%.6lf\n",dfs(1,0,n+min(n,k)));return 0;
}

acwing233. 换教室

链接：/

题意：小明有 n 节课要上，每节课都有两个教室可以选择 c i c_i ci​ 和 d i d_i di​ 。在开学初，你可以向教务处申请选择是否更换教室，最多申请 m 次。默认在 c i c_i ci​ 上课，申请之后有 p i p_i pi​ 的概率更换到 d i d_i di​ 上课。现在小明想知道，申请哪几门课程可以使他因在教室间移动的路径的总和的期望值最小,请你帮他求出这个最小值。

思路：这里不能够实时决策，不能对通过概率得到的距离取最小值，只可以对申请的课程申请或者不申请取最小值。

• 设 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1] 表示前 i -1 节课申请了 j 次，第 i -1 节课申请（1）或不申请（0）之后需要走的最小路径期望
• 先用 floyd 跑出所有教室之间的最短距离，注意初始状态需要用到 0 到 其它教室的距离，需要初始化一下。转移时，需要考虑概率情况得到的距离，然后取最小的决策方案。

如果这里并不是开学初就申请完，那么就可以设 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1] 表示前 i -1 节课申请了 j 次，申请第 i -1 节课成功（1）或不成功（0）之后需要走的最小路径期望。这样就可以根据申请结果来取最小值。

d f s ( i , j , 0 ) dfs(i,j,0) dfs(i,j,0) 申请成功 d f s ( i + 1 , j + 1 , 1 ) + p [ i ] × d i s [ c [ i − 1 ] ] [ d [ i ] ] dfs(i+1,j+1,1) + p[i] \times dis[c[i-1]][d[i]] dfs(i+1,j+1,1)+p[i]×dis[c[i−1]][d[i]]
d f s ( i , j , 0 ) dfs(i,j,0) dfs(i,j,0) 申请失败 d f s ( i + 1 , j + 1 , 0 ) + ( 1 − p [ i ] ) × d i s [ c [ i − 1 ] ] [ d [ i ] ] dfs(i+1,j+1,0) + (1-p[i]) \times dis[c[i-1]][d[i]] dfs(i+1,j+1,0)+(1−p[i])×dis[c[i−1]][d[i]]
d f s ( i , j , 0 ) dfs(i,j,0) dfs(i,j,0) 不申请 d f s ( i + 1 , j , 0 ) + d i s [ c [ i − 1 ] ] [ c [ i ] ] dfs(i+1,j,0) + dis[c[i-1]][c[i]] dfs(i+1,j,0)+dis[c[i−1]][c[i]]
d f s ( i , j , 1 ) dfs(i,j,1) dfs(i,j,1) 申请成功 d f s ( i + 1 , j + 1 , 1 ) + p [ i ] × d i s [ d [ i − 1 ] ] [ d [ i ] ] dfs(i+1,j+1,1) + p[i] \times dis[d[i-1]][d[i]] dfs(i+1,j+1,1)+p[i]×dis[d[i−1]][d[i]]
d f s ( i , j , 1 ) dfs(i,j,1) dfs(i,j,1) 申请失败 d f s ( i + 1 , j + 1 , 0 ) + ( 1 − p [ i ] ) × d i s [ d [ i − 1 ] ] [ d [ i ] ] dfs(i+1,j+1,0) + (1-p[i]) \times dis[d[i-1]][d[i]] dfs(i+1,j+1,0)+(1−p[i])×dis[d[i−1]][d[i]]
d f s ( i , j , 1 ) dfs(i,j,1) dfs(i,j,1) 不申请 d f s ( i + 1 , j , 0 ) + d i s [ d [ i − 1 ] ] [ c [ i ] ] dfs(i+1,j,0) + dis[d[i-1]][c[i]] dfs(i+1,j,0)+dis[d[i−1]][c[i]]

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2000+5;int n,m,v,e;
int c[maxn],d[maxn];
double p[maxn];
int mp[310][310],dis[310][310];
double dp[2010][2010][2];void floyd(int n)
{for(int i=1; i<=n; ++i) mp[i][i]=0;memcpy(dis,mp,sizeof(mp));for(int k=1; k<=n; ++k)for(int i=1; i<=n; ++i)for(int j=1; j<=n; ++j)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);for(int i=0; i<=n; ++i) dis[0][i]=0;
}double dfs(int i,int j,int k)
{if(i>n) return 0;if(j>m) return 1e18;if(dp[i][j][k]) return dp[i][j][k];double ans1=0,ans2=0;if(k==0){ans1=p[i]*dis[c[i-1]][d[i]]+(1-p[i])*dis[c[i-1]][c[i]]+dfs(i+1,j+1,1);ans2=dis[c[i-1]][c[i]]+dfs(i+1,j,0);}else{ans1=p[i-1]*p[i]*dis[d[i-1]][d[i]]+(1-p[i-1])*p[i]*dis[c[i-1]][d[i]]+p[i-1]*(1-p[i])*dis[d[i-1]][c[i]]+(1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]]+dfs(i+1,j+1,1);ans2=p[i-1]*dis[d[i-1]][c[i]]+(1-p[i-1])*dis[c[i-1]][c[i]]+dfs(i+1,j,0);}return dp[i][j][k]=min(ans1,ans2);
}int main()
{scanf("%d%d%d%d",&n,&m,&v,&e);for(int i=1; i<=n; ++i) scanf("%d",&c[i]);for(int i=1; i<=n; ++i) scanf("%d",&d[i]);for(int i=1; i<=n; ++i) scanf("%lf",&p[i]);memset(mp,1,sizeof(mp));for(int i=1; i<=e; ++i){int u,v,w;scanf("%d%d%d",&u,&v,&w);mp[u][v]=mp[v][u]=min(w,mp[u][v]);}floyd(v);printf("%.2lf\n",dfs(1,0,0));return 0;
}

acwing307. 连通图

链接：/

题意：求 n 个点的无向联通图有多少个

思路：设 f[i] 表示 i 个点的无相连通图的数量。 f [ i ] = 2 C ( i , 2 ) − ∑ j = 1 i − 1 f [ j ] C i − 1 j − 1 2 C ( i − j , 2 ) f[i]=2^{C(i,2)}-\sum_{j=1}^{i-1}f[j]C_{i-1}^{j-1}2^{C(i-j,2)} f[i]=2C(i,2)−∑j=1i−1​f[j]Ci−1j−1​2C(i−j,2) 相当于：总的连通图的个数 减去 不连通的个数

C= [[0 for i in range(55)] for j in range(55)]
for i in range(0,51):C[i][0]=C[i][i]=1for j in range(1,i+1):C[i][j]=C[i-1][j-1]+C[i-1][j]f=[0]*51
f[1]=1
for i in range(2,51):f[i]= 2**C[i][2]for j in range(1,i):f[i]-=f[j]*2**C[i-j][2]*C[i-1][j-1]while(1):n=int(input())if n==0:breakprint(f[n])

acwing337. 扑克牌

链接：/

题意：给定 52 张牌中的 n 张牌，请计算将它们排成一列，相邻的牌面值不同的方案数。最多有 20000 组询问

思路：对于具体的面值是无所谓的，不同在于当前状态 只有 1 张面值相同的有多少， 2 张面值相同的有多少，3 张面值相同的有多少，4 张面值相同的有多少。同时记录下，上次所作出的选择

• 设 d p [ n 1 ] [ n 2 ] [ n 3 ] [ n 4 ] [ k ] dp[n1][n2][n3][n4][k] dp[n1][n2][n3][n4][k] ，假设当前填一张有两张面值相同的牌，可以得到转移 a n s + = 2 ∗ ( n 2 − ( k = = 3 ) ) d f s ( n 1 + 1 , n 2 − 1 , n 3 , n 4 , 2 ) ans+=2*(n_2-(k==3))dfs(n_1+1,n_2-1,n_3,n_4,2) ans+=2∗(n2​−(k==3))dfs(n1​+1,n2​−1,n3​,n4​,2)

#include <bits/stdc++.h>
#define se second
#define ull unsigned long long
using namespace std;
const int maxn=1e5+5;int t,n;
char s[4];
pair<int,int> p[55];
ull dp[15][15][15][15][5];
int calc(char c)
{if(c>='2'&&c<='9') return c-'0';if(c=='T') return 10;if(c=='J') return 11;if(c=='Q') return 12;if(c=='A') return 1;
}
ull dfs(int n1,int n2,int n3,int n4,int k)
{if(n1==0&&n2==0&&n3==0&&n4==0) return 1;if(dp[n1][n2][n3][n4][k]) return dp[n1][n2][n3][n4][k];ull ans=0;if(n1>=1) ans+=(ull)1*(n1-(k==2))*dfs(n1-1,n2,n3,n4,1);if(n2>=1) ans+=(ull)2*(n2-(k==3))*dfs(n1+1,n2-1,n3,n4,2);if(n3>=1) ans+=(ull)3*(n3-(k==4))*dfs(n1,n2+1,n3-1,n4,3);if(n4>=1) ans+=(ull)4*n4*dfs(n1,n2,n3+1,n4-1,4);return dp[n1][n2][n3][n4][k]=ans;
}int main()
{int Case=0;scanf("%d",&t);while(t--){scanf("%d",&n);vector<int> vec;for(int i=1; i<=n; ++i){scanf("%s",s);int val=calc(s[0]);vec.push_back(val);}sort(vec.begin(),vec.end());int m=vec.size();int k=0;p[++k]= {vec[0],1};for(int i=1; i<m; ++i)if(vec[i]==vec[i-1]) p[k].se++;else p[++k]= {vec[i],1};int cnt[5]= {0};for(int i=1; i<=k; ++i)cnt[p[i].se]++;printf("Case #%d: ",++Case);cout<<dfs(cnt[1],cnt[2],cnt[3],cnt[4],0)<<'\n';}return 0;
}

acwing 309. 装饰围栏

链接：/

题意：有 N 块长方形的木板，长度分别为1,2,…,N，宽度都是1。现在要用这 N 块木板组成一个宽度为 N 的围栏，满足在围栏中，每块木板两侧的木板要么都比它高，要么都比它低。也就是说，围栏中的木板是高低交错的。我们称“两侧比它低的木板”处于高位，“两侧比它高的木板”处于低位。显然，有很多种构建围栏的方案。每个方案可以写作一个长度为N的序列，序列中的各元素是木板的长度。把这些序列按照字典序排序。现在给定整数C，求排名为C的围栏中，各木板的长度从左到右依次是多少。

思路：设 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1] 表示长度为 i 最左边的数排名第 j 的方案数。（ 0 代表在低位， 1 代表在高位）

• 一步一步试出答案，dp[i][j][k]>=c 表示这个位置已经包含了，此时可以将排名第 j 的数字计入答案

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;int t,n,vis[25],a[25];
ll c,dp[25][25][2];void init()
{dp[1][1][0]=dp[1][1][1]=1;for(int i=2; i<=20; ++i)for(int j=1; j<=20; ++j){for(int k=j; k<=i-1; ++k)dp[i][j][0]+=dp[i-1][k][1];for(int k=1; k<=j-1; ++k)dp[i][j][1]+=dp[i-1][k][0];}
}int main()
{init();scanf("%d",&t);while(t--){scanf("%d %lld",&n,&c);memset(vis,0,sizeof(vis));int cur;for(int i=1; i<=n; ++i){if(dp[n][i][1]>=c){a[1]=i;cur=1;vis[i]=1;break;}else c-=dp[n][i][1];if(dp[n][i][0]>=c){a[1]=i;cur=0;vis[i]=1;break;}else c-=dp[n][i][0];}for(int i=2; i<=n; ++i){cur^=1;int j=1;for(int x=1; x<=n; ++x){if(vis[x]) continue;if(cur==0&&x<a[i-1]||cur==1&&x>a[i-1]){if(dp[n-i+1][j][cur]>=c){vis[x]=1;a[i]=x;break;}else c-=dp[n-i+1][j][cur];}++j;}}for(int i=1; i<=n; ++i)printf("%d%c",a[i],i==n?'\n':' ');}return 0;
}