概率题一般正着推
期望题一般倒着推
图上的问题如果是 \(DAG\) 可以直接转移
否则可能要用到高斯消元
\(20\) 的数据范围大概率是装压
有些看似无限循环的式子其实可以倒着递推
1、骰子基础版 题目描述众所周知，骰子是一个六面分别刻有一到六点的立方体，每次投掷骰子，从理论上讲得到一点到六点的概率都是 \(1/6\)。今有骰子一颗，连续投掷 \(N\)次 ，问点数总和大于等于 \(X\) 的概率是多少？
输入仅有一行包含二个用空格隔开的整数，分别表示\(n\)和\(x\)，其中\(1<=N<=24,0<=x<150\)。
输出仅有一行包含一个有理数，要求以最简的形式精确地表达出连续投掷\(N\)次骰子，总点数大于等于\(X\)的概率。
样例输入3 9
样例输出20/27
分析设 \(f[i][j]\) 为第 \(i\) 次投掷骰子且总得分为 \(j\) 的方案数
则\(f[i][j]+=f[i-1][k],1 \leq j-k \leq 6\)
其实 \(24^6\) 的暴力也可以过
代码 #include<cstdio> const int maxn=30,maxm=200; typedef long long ll; ll f[maxn][maxm],tot,ans; int n,x; ll gcd(ll aa,ll bb){ if(bb==0) return aa; return gcd(bb,aa%bb); } int main(){ scanf("%d%d",&n,&x); f[0][0]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=6;j++){ for(int k=i;k<=i*6;k++){ if(k<j) continue; f[i][k]+=f[i-1][k-j]; } } } for(int i=1;i<=n*6;i++){ tot+=f[n][i]; } for(int i=x;i<=n*6;i++){ ans+=f[n][i]; } if(ans==0){ printf("0\n"); } else if(ans==tot){ printf("1\n"); } else{ ll gys=gcd(ans,tot); printf("%lld/%lld\n",ans/gys,tot/gys); } return 0; } 2、三角形的概率 题目描述这是一道数学题。
随机产生 \(3\) 个一定范围内的正整数，作为一个三角形的三条边，求他们能构成一个三角形的概率是多少？
你能证明吗？
你能用代码验证一下吗？
输入格式无
输出格式一个浮点数，表示答案，保留三位小数。
数据范围与提示
用作图法来证明即可，自己算算
分析其实是一道数学题
如果三条边 \(a,b,c\) 能构成三角形
必定有 \(a+b<c\)，\(c\) 为最长边
移项会得到 \(\frac{a}{c}+\frac{b}{c}<1\)
实际上求的就是两个小于 \(1\) 的正数相加大于 \(1\) 的概率
用几何概型解决
画一个边长为为 \(1\) 的正方形，则在对角线上面的部分即为符合条件的，所以概率为\(0.5\)
代码 #include<cstdio> int main(){ printf("0.500\n"); return 0; } 3、聪聪和可可 题目描述题目传送门
分析我们发现猫的走位比较神奇，因此可以提前预处理出猫在位置 \(i\) 且老鼠在位置 \(j\) 时，猫下一步走到的位置 \(nxt[i][j]\)
预处理可以用最短路来实现
如果 \(i\) 到 \(j\) 有一条边，并且 \(k\) 到 \(i\) 的最短路等于 \(k\) 到 \(j\) 的最短路加 \(1\)，则 \(nxt[i][k]=j\)
剩下的过程可以用记忆化搜索实现
代码 #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> inline int read(){ int x=0,fh=1; char ch=getchar(); while(ch<\'0\' || ch>\'9\'){ if(ch==\'-\') fh=-1; ch=getchar(); } while(ch>=\'0\' && ch<=\'9\'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*fh; } const int maxn=1e3+5; int head[maxn],tot=1; struct asd{ int to,next; }b[maxn<<1]; void ad(int aa,int bb){ b[tot].to=bb; b[tot].next=head[aa]; head[aa]=tot++; } int dis[maxn][maxn],nxt[maxn][maxn],n,m,s,t; bool vis[maxn]; std::queue<int> q; void spfa(int qd){ memset(vis,0,sizeof(vis)); dis[qd][qd]=0; q.push(qd); vis[qd]=1; while(!q.empty()){ int now=q.front(); q.pop(); vis[now]=0; for(int i=head[now];i!=-1;i=b[i].next){ int u=b[i].to; if(dis[qd][u]>dis[qd][now]+1){ dis[qd][u]=dis[qd][now]+1; if(!vis[u]){ q.push(u); vis[u]=1; } } } } } int du[maxn]; bool viss[maxn][maxn]; double f[maxn][maxn]; double dfs(int mao,int shu){ if(viss[mao][shu]) return f[mao][shu]; if(mao==shu) return 0; int aa=nxt[mao][shu]; int bb=nxt[aa][shu]; if(aa==shu || bb==shu) return 1; f[mao][shu]=1; for(int i=head[shu];i!=-1;i=b[i].next){ int u=b[i].to; f[mao][shu]+=dfs(bb,u)/(du[shu]+1); } f[mao][shu]+=dfs(bb,shu)/(du[shu]+1); viss[mao][shu]=1; return f[mao][shu]; } int main(){ memset(head,-1,sizeof(head)); memset(dis,0x3f,sizeof(dis)); memset(nxt,0x3f,sizeof(nxt)); n=read(),m=read(),s=read(),t=read(); for(int i=1;i<=m;i++){ int aa,bb; aa=read(),bb=read(); ad(aa,bb); ad(bb,aa); du[aa]++; du[bb]++; } for(int i=1;i<=n;i++) spfa(i); for(int i=1;i<=n;i++){ for(int j=head[i];j!=-1;j=b[j].next){ int u=b[j].to; for(int k=1;k<=n;k++){ if(dis[i][k]-1==dis[u][k]){ nxt[i][k]=std::min(nxt[i][k],u); } } } } printf("%.3f\n",dfs(s,t)); return 0; } 4、OSU! 题目描述题目传送门
分析\((x+1)^{3}=x^3+3x^2+3x+1\)
每次多增加的部分是 \(3x^2+3x+1\)
我们再开两个数组分别维护 \(x^2\) 的期望和 \(x\) 的期望
\(f1[i]=(f1[i-1]+1)\times p[i]\)
\(f2[i]=(f2[i-1]+2 \times f1[i-1] +1) \times p[i]\)
\(f3[i]=(f3[i-1]+3 \times f2[i-1] +3 \times f1[i-1] +1) \times p[i] +f3[i-1] \times (1-p[i])\)